Originally posted by: Ayan00

Hi,

In my job shop problem, there are multiple worker types for specific function and there are several workers for one type.

In one mode, there is one worker type but all workers belonging to the type are capable.

 

I would like to schedule there is only one worker working on one mode.  In my .mod shown below, it is not enough to limit the 1 to 1 relationship

between worker and mode. 

using CP;

// data structure
int nJobs = ...;
int nMchs = ...;
int nMoldIds = ...;
int nWorkerT = ...;
range Jobs = 0..nJobs;
range Mchs = 1..nMchs;  // There are nMchs machines, and they are accordance with id of machines
range MoldIds = 1..nMoldIds; // There are nMoldIds molds. 


tuple Operation {
  int id;               // Operation id
  int jobId;    // Job id
  int pos;              // Position in job
  int moldId;   // Mode id
};

tuple Mode {
  int id; 
  int opId;             // Operation id
  int mId;              // Machine with id equal to mId
  int pt;               // Processing time on the machine 
  int workerTid;        // Worker type
  int jId;
};
tuple Worker {
  int id;
  int workerT;
  int releaseT;
};

{Operation} Ops      = ...;
{Mode}             Modes    = ...;
{Worker}    Workers  = ...;
int             DueTime[Jobs]     = ...;
int     ReleaseTime[Mchs] = ...;
int     setup[MoldIds][MoldIds] = ...;  // Setup time of transitting from one MoldId to another MoldId

tuple triplet { int t1; int t2; int v; }
{triplet} tt[m in Mchs] = 
  { <t1,t2,setup[t1][t2]> | t1,t2 in MoldIds : 0<=setup[t1][t2]} union
  { <t1,t2,(maxint div 2)-1> | t1,t2 in MoldIds : setup[t1][t2]<0 }; // Forbidden transitions

// Position of last operation of job j
int jlast[j in Jobs] = max(o in Ops: o.jobId==j) o.pos;

int eReleaseTimeW[md in Modes] = min(wT in Workers:   md.workerTid==wT.workerT) wT.releaseT;

dvar interval ops  [Ops];
dvar interval modes[md in Modes] optional in  maxl(ReleaseTime[md.mId], eReleaseTimeW[md])..DueTime[md.jId] size md.pt;
dvar sequence mchs [m in Mchs]
in all (md in Modes: md.mId == m) modes[md]
types all(md in Modes, op in Ops: md.mId == m && md.opId == op.id) op.moldId;
dvar sequence wks [w in Workers]
in all(md in Modes: md.workerTid==w.workerT) modes[md];
/*cumulFunction modeUsage[md in Modes] = 
        sum(w in Workers) stepAtStart(modes[md], 1);
dexpr int wAssign[op in Ops] = sum (md in Modes: op.id==md.opId) 1 * presenceOf(modes[md]);
dexpr int modeUsage[w in Workers] = 
  sum (op in Ops, md in Modes: w.workerT==md.workerTid && op.id==md.opId) 1 * presenceOf(modes[md]);*/
// How to enable the mode will be assigned to only one worker belongs to the type????? 

minimize max(j in Jobs, o in Ops: o.pos==jlast[j]) endOf(ops[o]);
subject to {
        // Check how to get the 1st operation sequenced, to get the mode, which enable to add setup time
        forall (op1 in Ops, op2 in Ops, md1 in Modes, md2 in Modes: 
                md1.opId==op1.id && md2.opId==op2.id && op1.jobId==0 && op2.jobId!=0 && md1.mId!=md2.mId)
                endBeforeStart(modes[md1], modes[md2]);
        forall (j in Jobs, o1 in Ops, o2 in Ops: j!=0 && o1.jobId==j && o2.jobId==j&&o2.pos==1+o1.pos)
          endBeforeStart(ops[o1], ops[o2]);
        forall (o in Ops) {
          alternative(ops[o], all(md in Modes: md.opId==o.id) modes[md]);
         // wAssign[o] <= 1; // replicate with alternative
        }    
        // Operations on a given machine cannot overlap
        forall (m in Mchs)
          noOverlap(mchs[m],tt[m],1);   
        forall (w in Workers) {
          noOverlap(wks[w]); 
         // modeUsage[w] <=1;
  }    
} 

execute {
  for (var m in Modes) {
    if (modes[m].present)
      writeln("Operation " + m.opId + " on machine " + m.mId +  " with mode "+
      Ops[m.opId].moldId+ " starting at " + modes[m].start+" for "+m.pt);
  }
}

Then all workers satisfy the type for the mode will be assigned:

I tried to use cumul function to limit the mode only be used once, but i have difficulty in correctly modeling it.

 

Another way to get around I can think of is to avoid worker type and use worker directly inside mode, but is it kind of 

redundant or will it influence calculation performance?

 

Any suggestion is appreciated. Thanks!

 

 

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: GGR

Hi

 

You describe an multi mode open-shop problem. You have an example in the distribution of CPO. In any case your model seems right to me.

 

If I understand you correctly, You want to add a condition about available workers of operation usage. That is, in your notation, the set of  worker of mode in Modes cannot process more than C[nWorkerT]  operation simultaneously.

The only difficulty is to take in account the usage condition of the worker: in your case different release dates. The most general way is to have an alternative of modes on workers as you did. But you have noticed that the difference in the usage of workers is the number of workers of a mode available at a given time. As it corresponds to a start availability date, you can simply model it as a fixed pulse of capacity one ending at the release date of the worker. So the model come without alternative and sequence of workers.

 

forall (t in 1..nWorkerT)
  sum (md in Modes: md.workerTid == t) pulse(modes[md], 1) + sum(w in Workers: w.workerT == t) pulse(0, w.releaseT, 1) <= C[t];

 

Hope that helps

 

 

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: Ayan00

Hi GGR,

Thanks for your help. You help me better understand OPL cumul function:)

For "an example in the distribution of CPO", do you mean this one: https://www.ibm.com/developerworks/community/blogs/jfp/entry/solving_flexible_job_shop_scheduling_problems?lang=en  

 

It relates to start availability date. I tried your method, but i found the result doesn't change. Here is the example of workers with type==1:

tuple Worker {
  int id;
  int workerT;
  int releaseT;
};

tuple Mode {
  int id; 
  int opId;             // Operation id
  int mId;              // Machine with id equal to mId
  int pt;               // Processing time on the machine 
  int workerTid;        // Worker type
  int jId;
};

We can see both workers id 2 and 3 are scheduled with same mode id 3 at time 20, even

worker id 2 is only released at time 35. 

 

I have 3 constraints for workers and operation:

1. workers are scheduled only after being released

2. one worker can only do one operation at a time

3. one operation only needs one worker

 

According to the gantt, both 1 and 3 are unsatisfied now.

As you suggested below:

forall (t in 1..nWorkerT)
  sum (md in Modes: md.workerTid == t) pulse(modes[md], 1) + sum(w in Workers: w.workerT == t) pulse(0, w.releaseT, 1) <= C[t];

I think it is a clever approach but it doesn't really satisfy constraints 1 and 3.

 

There are two workers of type 1, 1st one is released at time 5, 2nd one at 35.

For this one:

cumulFunction wUsage1[t in 0..nWorkerT] = sum (md in Modes: md.workerTid == t) pulse(modes[md], 1); 

I select the mode intervals needs worker type 1, the 1st one starts from time 20.

Then for workers with type 1:

cumulFunction wUsage2[t in 0..nWorkerT] = sum(w in Workers: w.workerT == t) pulse(0, w.releaseT, 1);

After time 35, all workers are released.

 

#DecisionOptimization

Originally posted by: GGR

Hi

For "an example in the distribution of CPO", do you mean this one

Essentially yes, plus a secondary resource that are the workers (just like the open shop has two set of resources)

 

I have 3 constraints for workers and operation:

1. workers are scheduled only after being released

2. one worker can only do one operation at a time

3. one operation only needs one worker

 

Let's have a look to the global cumulative constraint for a set of workers of same capabilities (type):

sum (md in Modes: md.workerTid == t) pulse(modes[md], 1) + sum(w in Workers: w.workerT == t) pulse(0, w.releaseT, 1) <= C[t];

 

1: is told by adding the pulse(0, w.releaseT, 1): before its release date a worker is use for whatever else that executing an operation (that takes one unit of the numbers of workers)

3) is told by adding the pulse(modes[md], 1): processing an operation requires one unit of the number of workers

2)  the cumulative model is based upon the following symmetry rule: when both available, two workers is anytime  equivalent in the future: that is if I suppose I assign a worker to start the processing of an operation, I can choose  to use this same worker until the end of the processing.

As a consequence, it is useless to know which worker is assigned to an operation to solve the problem. Then a post processing greedy algorithm compute a possible allocation of one worker for each operation..

input : set of operations with their start date has given by CP Optimizer solution
input : set of workers
output : assignment of a worker to each operation

for all workers tell not idle the worker until its release date
while there is a not assigned operation sorted by smallest start time with smallest duration tie break

    select a worker idle at the start date of the operation
    assign the operation to the worker
    set not idle the worker until the end date of the operation

There is few examples of not strictly  similar disjunctive resources for which the cumulative relaxation symmetry is exact.Anyway , the global cumulative is in general a very efficient redundant constraint.

 

Hope that helps

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: Ayan00

Hi Rogerie,

I understand the idea now. The objective is to minimize the total makespan, CP Optimizer has calculated the possible makespan

by satisfying all the constraints, then I just need to follow your idea to write post processing greedy algorithm for worker

allocation. 

 

Thanks a lot:):)

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: GGR

Hi

 

You are right. But remember that if there is other conditions on workers (like rest and work shift, at work due date, transition time) the cumulative of operation is not enough and you need the alternative of sequence model of workers.

 

Hope that helps

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: Ayan00

Hi Rogerie,

 

Thanks for your reminding and I was thinking about it.

 

(1) For the work shift, in my case there are 3 shifts during a day: 6:00-14:00, 14:00-22:00, 22:00-6:00.

There are same skilled and numbers of workers in each shift so I think it can be just regarded as one worker since no any interruption.

I had a look at the example you answered previously:

https://www.ibm.com/developerworks/community/forums/html/topic?id=74edca48-608a-4e83-b582-3accdc3033f1

I think it is for non deterministic worker number and shift hours.

 

(2) For rest, in my case, workers doing same functions won't have a rest together, and then I assume they can help each other have a look.

For interest, I checked the example sched_calendar then simulated as following:

I assume for each worker type, the break is same, then it works correctly; However, when I tried with alternative of sequence model

of workers ( for each worker with different break time) by adding main code below:

dvar interval workers[w in Workers] optional in w.releaseT..(maxint div 2)-1 
intensity Calendar[w.id];

for (md in Modes)
  alternative(modes[md], all (w in Workers: md.workerTid == w.workerT) workers[w]);               

forall(w in Workers) {
      forbidStart(workers[w], Calendar[w.id]);
      forbidEnd  (workers[w], Calendar[w.id]);
        }

And I deleted previous cumul functions about worker usages <= C[t]. The result shows:

 

! Conflict refining terminated

! ----------------------------------------------------------------------------

! Conflict status           : Terminated normally, conflict found

! Conflict size             : 3 constraints

! Number of iterations      : 27

! Total memory usage        : 785.5 kB

! Conflict computation time : 0.07s

! ----------------------------------------------------------------------------

There is no warning indicating where is the problem. Do i miss something?

(There is full version of code in the attachment)

 

(3) Additionally, in my case, there is only one worker able to do setup operation during each shift. So setup worker is 

a critical resource.  To add constraint that the setup worker cannot work on 2 setup operations at a time. I define setup 

interval like following (there is operation without machine needed, so I define mid equal to 0):

tuple Setup { 
        int tOps;   // change to Ops
        int pt;         // setup time needed to change from another mode into the mold op "id" is using.
 }
 
 {Setup}       Setups = ...;

 dvar interval setups [st in Setups] optional size st.pt;
 dvar int typeOfPrevResult[md in Modes];
 dvar sequence mchs[m in 1..nMchs] in all (md in Modes:md.mId==m) modes[md] 
    types all(md in Modes, op in Ops: md.mId==m && md.opId==op.id) op.moldId;
     
 cumulFunction wSetup = sum (st in Setups: st.pt>0) pulse(setups[st], 1); 
 
 // constraint: limit setup worker resource to one
        forall ( md in Modes, m in Mchs, o in Ops: 
           o.jobId!=0 && md.mId!=0 && md.mId == m && o.id==md.opId) {
           typeOfPrevResult[md] == typeOfPrev(mchs[m], modes[md], -1, 0);
           forall(st in Setups: st.tOps==o.moldId) {
                        (typeOfPrevResult[md]!=o.moldId) =>
                        presenceOf(setups[st])==1;
                        startAtEnd(ops[o], setups[st]);
                }                               
        } 
        
        forall (m in Mchs: m!=0) {
          noOverlap(mchs[m]);
          wSetup <= 1;
        }

I wrote by my own and it seems working through result. I am not very confident in it because i didn't find

other similar solutions online. Could you give me some opinions?

 

Thanks a lot!

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: Petr Vilím

Hello,

your model doesn't have a solution because of the following constraints:

alternative("ops({2,1,1,2})", ["modes({2,2,1,30,1,1})", "modes({3,2,2,25,1,1})"]);
alternative("modes({2,2,1,30,1,1})", ["workers({2,1,35})", "workers({3,1,5})"]);
alternative("modes({3,2,2,25,1,1})", ["workers({2,1,35})", "workers({3,1,5})"]);

To simplify my description I'm going to change the names:

alternative(ops, [mode1, mode2]);
alternative(mode1, [worker1, worker2]);
alternative(mode2, [worker1, worker2]);

Interval variable ops is present, the remaining variables are optional. Lets say we choose mode1 in the first alternative (cHoosing mode2 instead leads to exactly the same problem):

alternative(ops, [mode1, mode2]);

Therefore mode1 will be present, mode2 will be absent. Now there's third constraint:

alternative(mode2, [worker1, worker2]);

Because mode2 is absent the alternative above forces both worker1 and worker2 to be absent. However now back to second constraint:

alternative(mode1, [worker1, worker2]);

Because mode1 is present exactly one of worker1 and worker2 must be present. But there are both absent. So there is no solution.

It seems to me that you probably didn't want to reuse the same interval variables [worker1, worker2] in both alternative constraints.

 

I hope it helps, Petr

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: Ayan00

Thanks Petr, I totally understand now. 

 

I just got to learn CPLEX for one month, from you I know how to do next time when there

are conflicts, i will check each constraint inside "subject to", combining with data file.

 

Best regards

 

 

#DecisionOptimization
#OPLusingCPOptimizer