Originally posted by: Aboudou

Hi All,
I'm trying to model a scheduling problem with two dedicated parallel machine with due date, sequence dependent family setup and buffer at the end of the machine. I have 3 kind of objects these machine can manufacture A, B and C. Machine 1 can do jobs A and B and Machine 2 can do jobs A and C. Machine can have only 46 job. A job remain on the machine buffer from the start of the scheduling until his due date. I've done a first model which contains 3 types on interval array jobs, modes(optional) and stock. I use jobs and modes for the alternative constraint for type A job. And the stock interval help me keep track how long job remain on the machine and do the pulse on this interval for the stock constraint. I'm not happy with this model because it has a lot of trouble for finding a solution. I think i need to get rid of the stock array but i don't find an other way to tell to the cumul function to start with the start of an interval until his due date how can I do this ? And is there an option with CPO like CPLEX for emphases feasibility over optimality in order to find a quick first solution ? my model is below.

 using CP; // on utilise CP Optimizer 
/********************
 * Type declaration *
 ********************/
 tuple triplet {
   int id1;
   int id2;
   int value;
 };
 tuple Mode {
  int jobId; // Job id
  int type;      // type des portes 1:B98, 2:K98, 3:X38
  int diversite; //diversité des portes 1: sans trou\L38 2:avec trou\B32
  int duedate;   // due date des taches
  int mch;   // Machine
 };
/********************
 * Data declaration *
 ********************/
 int       nbMachines = ...;    // m le nombre de machine differents
 int       nbJobs = ...;        // nombre de jobs a traité 
 range     M = 1 .. nbMachines; // ensmeble des machines
 range     J = 1 .. nbJobs;
 int       offset=...;
 int       duree[M] = ...;         //temps de fabrication d'une porte
 {Mode}    Modes = ...;
 {triplet} setuptime = ...;     // matrice des temps de setup
/**********************
 * Decision variables *
 **********************/ 
 dvar interval modes[md in Modes] optional in 0..md.duedate+offset size duree[md.mch];
 dvar interval jobs[J];
 dvar interval stock[md in Modes] optional in 0..md.duedate+offset;
 dvar interval cmax;
 dvar sequence rims[m in M] in all(md in Modes: md.mch == m) modes[md] types
                               all(md in Modes: md.mch == m) md.type;
                               
 // Declaration des stocks                             
 cumulfunction dynamique = sum(md in Modes: md.mch == 1) pulse(stock[md],1);
 cumulfunction dynamique2 = sum(md in Modes: md.mch == 2) pulse(stock[md],1);
/****************
 * Search phase *
 ****************/
 execute{
        cp.param.TimeLimit=1800;        
        }
/**********************
 * Objective function *
 **********************/
minimize lengthOf(cmax);
/***************
 * Constraints *
 ***************/
 subject to{
     alwaysIn(dynamique, cmax, 0, 46); // Contrainte de stock
     alwaysIn(dynamique2, cmax, 0, 46);
     longeur : span(cmax,all(m in Modes)modes[m]);
     forall(md in Modes){
         stock1 : startOf(stock[md]) == startOf(modes[md]);
         stock2 : endOf(stock[md],md.duedate + offset) == md.duedate + offset;
         presenceOf(stock[md]) == presenceOf(modes[md]);
        }
 forall(j in J)
   alter : alternative(jobs[j], all(md in Modes: md.jobId==j) modes[md]);
 forall(m in M)
   ordo : noOverlap(rims[m], setuptime);
 } 

Originally posted by: isczg

Hello,

You can use integer decision variables to store daily stock quantity  instead of using stock interval array and cumulFunction. But I'm not sure this way of modeling will perform better than yours.

The rough code sample is :

int max_days = max (md in modes) md.duedate + offset;

dvar int+ daily_stock1[0..max_days]; // daily stock quantity on machine 1

s.t. { 

   //////////////////

   forall (t in 0..max_days]

           daily_stock1[t] == sum (md in Modes: md.mch == 1) ( startOf(modes[md]) <= t ) - sum (md in Modes: md.mch == 1) (md.duedate + offset <= t);

            // stock quantity at t equals (number of jobs starting before t) - (number of jobs leaving before t)

   max (t in 0..max_days) daily_stock1[t] <= 46; // stock limit constraint

   /////////////////////////

}

Originally posted by: Aboudou

hello
I've try your implementation but my value of max_days is too big(4640) so when I try to solve it my pc crashes because it doesn't have enough memory. Maybe with a smaller value it

would work.

regards

Originally posted by: PhilippeLaborie

Hello,

Could you attach a .dat file for your model that illustrate the problem?

Originally posted by: Aboudou

Hi,
Tthere is the .dat et the 2 versions of the .mod

Regards

Originally posted by: PhilippeLaborie

I think some constraints can be made tighter in order to propagate better. I tried this set of constraints:
 

/***************
 * Constraints *
 ***************/
subject to {
  k98trou       <= 4;
  k98strou      <= 14;
  b98trourims1  <= 12;
  b98strourims1 <= 16;
  dynamique     <= 46;
  dynamique2    <= 46;
  span(cmax, all(j in J) jobs[j]);
  forall(md in Modes){
        startAtStart(stock[md], modes[md]);
        endOf(stock[md], md.duedate + offset) == md.duedate + offset;
        presenceOf(stock[md]) == presenceOf(modes[md]);
  }
  forall(j in J)
    alternative(jobs[j], all(md in Modes: md.jobId==j) modes[md]);
  forall(m in M)
    noOverlap(rims[m], setuptime);
}

Main differences:
- the alwaysIn on the cumul functions hold over the complete horizon instead of just the spanning interval (which is not fixed)

- the span constraint is expressed on the job intervals (present) rather than on the models (optional ones)

- the constraint that the stock and models intervals start at the same time is expressed with a startAtStart constraint rather than an equality of startOf, this way the engine can exploit ti better

With this model V12.6.3 finds an initial solution very fast:

 ! ----------------------------------------------------------------------------
 ! Minimization problem - 1,535 variables, 2,115 constraints
 ! Presolve      : 1,142 extractables eliminated
 ! Workers              = 1
 ! TimeLimit            = 600
 ! Initial process time : 0.03s (0.03s extraction + 0.00s propagation)
 !  . Log search space  : 10,318.1 (before), 10,318.1 (after)
 !  . Memory usage      : 8.0 MB (before), 8.8 MB (after)
 ! Using sequential search.
 ! ----------------------------------------------------------------------------
 !          Best Branches  Non-fixed            Branch decision
                    1,000      1,026            on stock#63
                    2,000        619            on modes#366
 *         4,400    2,420 0.61s                      -

Philippe

Originally posted by: Aboudou

Thanks it is working a lot better. I just have a little question. I'm using V12.6.0.0 and in my .ops i use the defaut option serach type is in auto and processus number is equal to -1 and  in my tab "Journal du moteur" i have :
 

 ! ----------------------------------------------------------------------------
 ! Minimization problem - 1 535 variables, 3 254 constraints
 ! Presolve      : 1 142 extractables eliminated
 ! TimeLimit            = 1 800
 ! Initial process time : 0,01s (0,00s extraction + 0,01s propagation)
 !  . Log search space  : 12 665,9 (before), 12 665,9 (after)
 !  . Memory usage      : 9,8 MB (before), 10,6 MB (after)
 ! Using parallel search with 4 workers.
 ! ----------------------------------------------------------------------------

Does it work better for this type of problem to use a sequential search over the parallel serach? And is it normal that I have 3254 constraints and you have 2115 while using same constraints and data?

Regards.

Originally posted by: PhilippeLaborie

The number of workers being equal to -1 in the settings means that it is the default mode and in this case the engine uses the maximal number of threads (so 4 I guess) on your machine. 

In general, it pays off to use more workers than using sequential search. But with sequential search, it is easier to interpret the search log, that's why I still had Workers=1 in my model. But for performance, Workers=4 should be better.

Concerning the number of constraints, I think something changed in CP Optimizer on the way to count constraints, especially when they are simplified in the presolve so that probably explain the difference.

This being said V12.6 is from 2013, if you can use the latest version (V12.6.3) you will get some bug fixes and possibly some performance improvements.