Decision Optimization

 View Only
Expand all | Collapse all

CP Tardiness in permutation flowshop scheduling

  • 1.  CP Tardiness in permutation flowshop scheduling

    Posted Mon May 17, 2021 04:14 PM
    Hello, 
    I am new in Constraint Programming. I need to run a model to determine the tardiness of a set of 20 jobs in 5 machines. My model takes a long time running and cannot get an exact solution. Could someone give me some hint?

    The model and data are below. Thank you all

    Hermilio Vilarinho

    ================================================================================================================

    using CP;

    //Parameters
    int nJobs=...;
    range Jobs=1..nJobs;
    int nMachines=...;
    range Machines=1..nMachines;
    int Duration[Machines][Jobs]=...;
    int Due_Date[Jobs]=...;


    //Decision variables
    dvar interval Process[j in Jobs][m in Machines] size Duration[m][j];
    dvar sequence Seqm[m in Machines] in all(j in Jobs) Process[j][m];

    execute {
    cp.param.TimeLimit = 3600;
    }

    //Objective Function
    dexpr int Tardiness[j in Jobs] = maxl(0, endOf(Process[j][nMachines])-Due_Date[j]);
    minimize sum (j in Jobs) Tardiness[j];

    //Constraints
    subject to {
    forall (m in Machines)
    noOverlap(Seqm[m]);
    forall (j in Jobs, o in 1..nMachines-1)
    endBeforeStart(Process[j][o], Process[j][o+1]);
    };

    ================================================================================================
    Data:

    nJobs=20;
    nMachines=5;

    Duration=[[54 83 15 71 77 36 53 38 27 87 76 91 14 29 12 77 32 87 68 94],
    [79 3 11 99 56 70 99 60 5 56 3 61 73 75 47 14 21 86 5 77],
    [16 89 49 15 89 45 60 23 57 64 7 1 63 41 63 47 26 75 77 40],
    [66 58 31 68 78 91 13 59 49 85 85 9 39 41 56 40 54 77 51 31],
    [58 56 20 85 53 35 53 41 69 13 86 72 8 49 47 87 58 18 68 28]];


    Due_Date=[300 300 300 300 300 500 500 500 500 500 1000 1000 1000 1000 1000 1200 1200 1200 1200 1200];




    ------------------------------
    Hermilio Carneiro Vilarinho Fernandes
    ------------------------------

    #DecisionOptimization


  • 2.  RE: CP Tardiness in permutation flowshop scheduling

    Posted Tue May 18, 2021 02:29 AM
    Edited by System Fri January 20, 2023 04:46 PM
    Hello,

    First, if your problem is a "permutation" flow-shop" as the title suggests, then you are missing some constraints enforcing that the order of the operations is the same on each machines. This is a "sameSequence" constraint. The modified model is the one below.

    int nJobs=...;
    int nMachines=...;
    range Jobs=1..nJobs;
    range Machines=1..nMachines;
    int Duration[Machines][Jobs]=...;
    int Due_Date[Jobs]=...;
    
    //Decision variables
    dvar interval Process[j in Jobs][m in Machines] size Duration[m][j];
    dvar sequence Seqm[m in Machines] in all(j in Jobs) Process[j][m] types all(j in Jobs) j;
    
    //Objective Function
    dexpr int Tardiness[j in Jobs] = maxl(0, endOf(Process[j][nMachines])-Due_Date[j]);
    minimize sum (j in Jobs) Tardiness[j];
    
    //Constraints
    subject to {
      forall (m in Machines) {
        noOverlap(Seqm[m]);
        if (1<m) {
          sameSequence(Seqm[1], Seqm[m]);
        }
      }
      forall (j in Jobs, o in 1..nMachines-1)
      endBeforeStart(Process[j][o], Process[j][o+1]);
    };​


    For this type of objective function (total tardiness), the lower bounds computed by CP Optimizer are indeed not very good and that is why it has difficulties for proving optimality. Because the main target of CP Optimizer is industrial scheduling problems which are usually much larger than this flow shop instance, the focus of the search is more on producing good quality solutions fast rather than focusing on lower bounds and proofs. 

    On your instance, a solution with total tardiness cost of 1687 is quickly produced (in about 1s on my laptop). I'm pretty sure this solution is of very good quality. Indeed ... the gap is large (lower bound is 369) but my guess is that it is because the lower bound is bad. There is not much you can do about it here. Given that the problem is not very large and that (if it is a permutation flowshop) the only decisions is the sequencing on one machine, maybe you could try a MIP model with a disjunctive formulation, it may give you a better lower bound ...



    ------------------------------
    Philippe Laborie
    ------------------------------