Originally posted by: AndyHam

Dear IBM,
I am doing a POC about Factory Production Planning‎ problem for a manufacturing business.

The company is currently using a MIP model.

But, the computational time is too long due to the sequence-dependent setup.

I am trying to see if we can formulate this problem into CP.

A main concern I have is "the quantity of each product is not a predetermined, but a decision."

Of course, there is a daily demand so the goal is to decide

- when and how much of each product should be started.

- detailed sequencing of each machine.

 

There are many other constraints, but here is a sketch of the problem.
If you can give me some direction, it will be appreciated.

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

INPUT

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

(Daily Demand)

Product Day              Demand

A     2019/08/01        1075

B    2019/08/01        1225

C    2019/08/01        1050

........................

A   2019/08/31        1500

B   2019/08/31        975

C   2019/08/31        1120

 

(Product Route)

All products follow a same route

Step      Machines            PT

1           m1                       10         

2           m2, m3, m4        190

 

(Product Change-over Penalty)

Machine From   To          Penalty

m3          A          B               50

m3          B         C               120

.....................

m5         B          C               240

 

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

Here are decisions to make.

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

(Daily input qty for each product)

Day              Product      Demand

2019/07/25        A            1200

2019/07/25        B             900

2019/07/25        C           1105

........................

2019/08/31        C           700
 

(Daily work schedule for each machine)

Day                   Mch       Product        Qty

2019/07/25        m1       A                 1000

2019/07/25        m2       C                  800

2019/07/25        m3       B                   780

..................................

2019/08/31        m3       C                1250

Note each machine works on a single type of product at each day.

Namely, each machine would not change to other product during a day.

 

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: AndyHam

I tried to make a model during the weekend. Here is my trial. 

The model works, but it is very slow. If I change the nDays into 10, it generates a schedule, but my goal is to have a quarterly plan.

Right now, the model tries to maximize the sum of minutes assigned to each machine.

Namely, the model should assign 1440 minutes (after subtracting the setup penalty) to each machine at every day.

But, the model could not even assign 1440 minutes at day 5, but assigned only 60.
If you can give me an advice, it will be appreciated.

name    position    declaredPosition    type    start    end    size

      itvModes[<3,"m2">][0]    0    22    3    0        1440    1440
    itvModes[<3,"m2">][1]    1    23    3    1440    2880    1440
    itvModes[<3,"m2">][2]    2    24    3    2880    4320    1440
    itvModes[<3,"m2">][3]    3    25    3    4320    5760    1440
    itvModes[<3,"m2">][4]    4    26    3    5760    7200    1440
    itvModes[<3,"m2">][5]    5    27    3    7200    7260    60
    itvModes[<3,"m2">][6]    6    28    3    7260    8700    1440
    itvModes[<3,"m2">][7]    7    29    3    8700    10140    1440
    itvModes[<3,"m2">][8]    8    30    3    10140    11580    1440
    itvModes[<3,"m2">][9]    9    31    3    11580    12960    1380
 

using CP;
int nDays = ...;
range Trains = 0..nDays;

tuple Mode {
  int p;   // product
  string mch;  // Machine
};
{Mode} Modes = ...;
{string} Mchs = {m.mch |m in Modes};

tuple t_setup {
    key    int p1; //product 1
    key    int p2; //product 2
    int     t;
};
{t_setup} Setup=...;

tuple t_Products {
    key string name;
    int p;
};
{t_Products} Products=...;

tuple t_Plan {
    key int day;
    key    int p; //product
    int qty;    
};
{t_Plan} Plan=...;

dvar interval itvProd  [Products][Trains] optional in 0..24*60*nDays size 60..24*60; 
dvar interval itvModes[md in Modes][Trains] optional ; 
dvar sequence mchs[m in Mchs] 
    in       all(md in Modes, t in Trains: md.mch == m) itvModes[md][t]
    types all(md in Modes, t in Trains: md.mch == m) md.p;

dexpr int sumMove = sum(t in Trains,p in Products) sizeOf(itvProd[p][t]); 
dvar int Delta[Plan];                 
execute {
  cp.param.TimeLimit = 20;
  cp.param.Workers = 3;
  cp.param.LogVerbosity=21;  
  cp.param.NoOverlapInferenceLevel = "Extended"  
  var f = cp.factory;
  cp.setSearchPhases(f.searchPhase(mchs)); 
}

//minimize sum(p in Plan) abs(Delta[p]) - sumMove;
minimize - sumMove;
subject to {
  forall (p in Products, t in Trains)
    alternative(itvProd[p][t], all(md in Modes: md.p==p.p) itvModes[md][t]);
  forall (m in Mchs)
    noOverlap(mchs[m], Setup);
  forall(m in Mchs, md1, md2 in Modes, b in Trains: m==md1.mch && m==md2.mch && b < nDays)
    prev(mchs[m],itvModes[md1][b],itvModes[md2][b+1]); 
  forall(m in Mchs, b in Trains)
    sum(md in Modes: m==md.mch) presenceOf(itvModes[md][b]) ==1;
  
/*  //minimize delta againt cum. scheduled amount - cum. plan amount
  forall(p in Plan)  
    sum(cp in Plan,pr in Products: p.day >= cp.day && pr.p==cp.p && pr.p==p.p) 
        (sizeOf(itvProd[pr][cp.day]) - cp.qty) ==Delta[p];         
*/ 
}

execute {
writeln("day"+"\t" + "oper" +"\t" + "mch" + "\t"+ "qty" );

for (var md in Modes)
for (var p in Products) 
for (var t in Trains) 
    if(md.p==p.p && itvModes[md][t].present && itvModes[md][t].size > 0) 
          writeln(p.name +"\t"+ md.mch + "\t" + itvModes[md][t].start +"\t"+ itvModes[md][t].end +"\t"+ itvModes[md][t].size) ;          
} 

 

 

nDays = 10;  //90

Products={
<"I1" 1>
<"I2" 2>
<"I3" 3>
<"I4" 4>
};

Modes = {//    Product Mch
<1     "m1">
<1     "m2">
<2    "m1">
<2    "m2">
<3    "m1">
<3    "m2">
<4    "m1">
<4    "m2">
};

Setup={
//p1 p2 t
<    2    1    60    >
<    1    2    120    >
<    3    4    240    >
<    4    3    180    >
<    2    4    240    >
<    2    3    180    >
<    1    4    240    >
<    1    3    180    >
<    4    2    120    >
<    4    1    60    >
<    3    2    120    >
<    3    1    60    >
};

Plan = {//    Day product Qty    
<    59    1    501    > 
<    60    1    848    >
<    61    1    753    >
<    62    1    767    >
<    63    1    564    >
<    64    1    638    >
<    65    1    542    >
<    66    1    606    >
<    67    1    768    >
<    68    1    777    >
<    69    1    741    >
<    70    1    618    >
<    71    1    827    >
<    72    1    865    >
<    73    1    812    >
<    74    1    537    >
<    75    1    533    >
<    76    1    542    >
<    77    1    825    >
<    78    1    543    >
<    79    1    675    >
<    80    1    526    >
<    81    1    860    >
<    82    1    608    >
<    83    1    856    >
<    84    1    602    >
<    85    1    850    >
<    86    1    889    >
<    87    1    780    >
<    88    1    818    >
<    89    1    502    >
<    90    1    603    >
<    14    2    579    >
<    15    2    755    >
<    16    2    512    >
<    17    2    887    >
<    18    2    766    >
<    19    2    815    >
<    20    2    523    >
<    21    2    799    >
<    22    2    798    >
<    23    2    839    >
<    35    2    666    >
<    36    2    522    >
<    37    2    527    >
<    38    2    810    >
<    39    2    568    >
<    40    2    856    >
<    55    3    611    >
<    56    3    621    >
<    57    3    749    >
<    58    3    619    >
<    59    3    794    >
<    60    3    704    >
<    61    3    840    >
<    62    3    783    >
<    63    3    503    >
<    64    3    858    >
<    65    3    580    >
<    66    3    507    >
<    67    3    827    >
<    68    3    675    >
<    69    3    776    >
<    70    3    857    >
<    71    3    665    >
<    72    3    539    >
<    73    3    803    >
<    74    3    504    >
<    75    3    598    >
<    76    3    769    >
<    77    3    622    >
<    78    3    754    >
<    79    3    755    >
<    80    3    701    >
<    81    3    553    >
<    82    3    508    >
<    83    3    748    >
<    84    3    831    >
<    85    3    662    >
<    86    3    590    >
<    87    3    610    >
<    88    3    574    >
<    89    3    774    >
<    90    3    734    >
<    61    4    609    >
<    63    4    561    >
<    64    4    537    >
<    65    4    578    >
<    66    4    724    >
<    67    4    739    >
<    68    4    662    >
<    70    4    803    >
<    71    4    817    >
<    72    4    620    >
<    73    4    506    >
<    74    4    566    >
<    75    4    641    >
<    77    4    599    >
<    78    4    725    >
<    79    4    522    >
<    80    4    803    >
<    81    4    783    >
<    82    4    840    >
<    84    4    617    >
<    85    4    626    >
<    86    4    769    >
<    87    4    856    >
<    88    4    599    >
<    89    4    782    >

};

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: GGR

Hy Andy

 

First of all, sorry for the late answered

--------------------------------------------------------------

About your problem. (Tell me if I understand correctly)

 

You have a set of task to sequence with a setup time on various identical machine, with same machine and precedence between tasks.

Your goal is to calculate a temporal planning curve subject to a minimum workload per period and a scheduling that assure you a feasible solution.

The typical time for scheduling is small or very small with respect of the planning period.

 

First question : Is the planning workload is individual per machine or global to all tasks? I suppose it is per machine.

 

The MIP does not work well because of the scheduling problem (machine assignment, setup, precedence) : That is a well known problem in MIP

The scheduling algorithm does not work well  because of the minimum workload requirement : That is a well known problem in Scheduling.

Last but not least, The two problems have a very different time scale

 

Here is what I am suggesting.

Long Time scale -> Planning Problem with relaxed scheduling : Relax the task and setup duration in  workload in a period assuming they belongs to one period at most. using a sensible lower bound. Temporal  Precedence are relaxed in precedence between assigned time period.

Create and solve the MIP problem.

 

These will give you

• a per period lower bound of the maximum workload,
• a time window and a assigned machine per tasks.

 

Short time unit -> Scheduling problem,

alternative of tasks in machine operations. For each machine : noOverlap on sequence with setup time of the operations

Adding minimum and maximum world per machine and period:

• have a look to the overlapLength expression : Be t_1 and t_2 the end-points of a period, be it the interval for on operation on a machine, overlapLenght(t_1, t_2, it) gives the part of the length of the interval in the period for the machine.
• Then per period and machine tells MinWorkLoad <= sum (operations o on machine) overlapLenght(t_1, t_2, o) <= maxWorkLoad
• maxWorkLoad is given by slightly relaxing the maximum workload found by the planning.

 

Then Use the solution of the planning (time period and resource assignment) as startingPoint.

if you do not want to change too much the time assignment of the task, you can add constraint that bound the start of the task to be in a neighbour time window.

-----------------------------------------------------------------

About Debugging a model.

 

I suggest you relax the constraints one at at a time to see which of one provokes the slow-down. When you find it either add constrained that over constrain in a sensible manner the model, either relax the guilty constraint and assume it, either try to found a good starting point.

In scheduling when you have several very different time scale, think decomposition by approximation for each time scale (the longest first). Use the previous solution as starting point.

 

 Hope that helps.

 

 

 

 

 

 

 

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: AndyHam

Sorry! I was in travel for a family vacation.

Thanks for the great insight. I like the following at most "In scheduling when you have several very different time scale, think decomposition by approximation for each time scale (the longest first). Use the previous solution as starting point." 

Regarding the question, this workload is per machine. Now, I am attempting to predetermine the amount of daily start plan by converting the daily shipping plan into the daily start plan after subtracting the average cycle time. Then, use CP only for job-to-machine allocation and sequencing with setup. Now, the model runs well.

#DecisionOptimization
#OPLusingCPOptimizer