Originally posted by: AndyHam

Dear IBM,

After spending two weeks without any success, I am writing this SOS message.

Consider unrelated parallel machine scheduling problem wherein processing time of each job varies at each machine.  In addition to set of machines and set of jobs, let's suppose there are set of vehicles, which transfer jobs across machines and stocker (see attached figure 1). Namely, a vehicle moves to stocker to pickup a job and transfers to destination for processing. Then, a vehicle moves to a machine to pickup the job and transfer to stocker for storage. The goal is to have an integrated scheduling of production and material handling.

The transfer-task of vehicle seems to be able to expressed when the destination location is determined within its sequence (see attached figure 2). However, in this unrelated parallel machine scheduling problem, the destination locations are determined by Machine sequence. Therefore, it seems to be difficult to utilize noOverlap keyword of Vehicle sequence. The transition distance is determined by the last location of vehicle and the next machine. In this case, how to consider a transition matrix related to two different sequences? 

Also, should we need to create three different intervals for pkup, processing, and drop for each job? Then assign pkup and drop intervals to vehicle and processing interval to machine? Finally connect them with precedence-relation? 

How to model an empty vehicle which moves to stocker or machine for pickup? Note the job must be available for a processing during this vehicle's empty move. However, during a job is loaded on a vehicle, the job must not be available for a processing.

Any tip/advice will be appreciated.
Andy

Hi,

about

how to consider a transition matrix related to two different sequences? 

have you tried sameSequence ?

A binary constraint on a pair of sequence variables. The constraint states that the relative position of related interval variables is the same in both sequences, seq1 and seq2.

regards

Originally posted by: AndyHam

Thanks for the tip.

I don't think we can apply sameSequence to this problem. In the fig. 2, the sizes of seqVeh and seqMach are different. For instance, the sequence of m2 is j1->j3 and the sequence of v1 is j1->j1->j2->j1->j1->j3….. Namely, the sizes of the two sequences are different and the order does not necessarily same.

I am still dead in the water :)

Originally posted by: Petr Vilím

Hello,

If I understand your problem right then I think that the trick could be to use zero-duration interval variables for the
vehicle. I.e. model each job by the following interval variables:
- job: present (master of the alternative)
- jobOnMachine[m]: array of optional intervals, duration depends on the machine m
- stockerPickup[v]: optional, zero duration, models the time when job is taken from stocker by vehicle v
- jobOnMachineDrop[m][v]: optional, zero duration, models the time when job is dropped on machine m by vehicle v
- jobOnMachinePickup[m][v]: optional, zero duration, models the time when job is taken from machine m by vehicle v
- stockerDrop[v]: optional, zero duration, models the time when the finished job is returned to the stocker by vehicle v
And the following constraints:
- For each machine m: noOverlap of all jobOnMachine[m]
- For each vehicle v: noOverlap of all stockerPickup[v], stockerDrop[v], jobOnMachineDrop[m][v], jobOnMachinePickup[m][v] with appropriate setup times
- Alternative constraints (job must be executed by some machine, picked up by some vehicle from stocker and returned by
  some (possibly different) vehicule from the stocker).
- Synchronization constraints:
    startAtStart(jobOnMachineDrop[m][v], jobOnMachine[m])
    endAtEnd(jobOnMachinePickup[m][v], jobOnMachine[m])
- For a vehicle, do not schedule anything between pickup and delivery of a job:
    previous(seqVehicle[v], stockerPickup[v], jobOnMachineDrop[m][v])
    previous(seqVehicle[v], jobOnMachinePickup[m][v], stockerDrop[v])
- Possibly add redundant constraints for durations of vehicle moves (probably not necessary):
    startAtStart(stockerPickup[v], jobOnMachineDrop[m][v], transitionTime)
    startAtStart(jobOnMachinePickup[m][v], stockerDrop[v], transitionTime)

The number of interval variables could be high when there are a lot of machines and a lot of vehicles. I don't see a better exact solution.

Best regards, Petr

Originally posted by: AndyHam

Dear Petr,

Thanks for the detailed advice.
I think I understand the approach. 
Let me update here with some results after few days.

In addition to "zero-duration interval variables", there are two more key learning for me as follows:
#1 One set of intervals can be mapped to different sets of intervals
    alternative(job[j],jobOnMachine[j,m])
    alternative(job[j],stockerPickup[j,v])
    alternative(job[j],jobOnMachineDrop[j,m])
    alternative(job[j],jobOnMachinePickup[j,m])
    alternative(job[j],stockerDrop[j,v])

#2 Owing to #1, the transfer-task of vehicle can be traced via 
    noOverlap (seqVehicle[v], T)

This is a great lesson for me. Thanks again!
It is really fun for me to model the problem which was once not even describable by traditional methods.
It is time for Operations Research textbook to include CP besides LP, BIP, NLP, Heuristics, etc.

Andy

Hi,

about "It is time for Operations Research textbook to include CP besides LP, BIP, NLP, Heuristics, etc. "

do not hesitate to share

https://www.linkedin.com/feed/update/urn:li:activity:6285348551291604992https://www.linkedin.com/feed/update/urn:li:activity:6285348551291604992https://www.linkedin.com/feed/update/urn:li:activity:6285348551291604992https://www.linkedin.com/feed/update/urn:li:activity:6285348551291604992https://www.linkedin.com/feed/update/urn:li:activity:6285348551291604992

https://www.slideshare.net/PhilippeLaborie/introduction-to-cp-optimizer-for-scheduling?trk=v-feed

regards

Originally posted by: Petr Vilím

I'm glad you like it!

I agree with #2. Alternatives in #1 are probably not right though. It is right that one "master" interval can be used in multiple alternatives. However I don't think you can use job[j] e.g. in alternative over stockerPickup because job[j] is not zero duration while stockerPickup isn't. Furthermore stockerPickup must happen some time before job[j].

So I think that you need to introduce more interval variables as master for alternatives. E.g. something like this for stockerPickup:

- interval variable masterStockerPickup[j] present

- alternative(masterStockerPickup, all (v in Vehicules) stockerPickup[v])

And it is necessary to link the alternatives. E.g. when job is dropped on machine m by vehicle v then it must be also picked up by the same vehicle from the stocker:

- presenceOf(stockerPickup[v]) >= presenceOf(jobOnMachineDrop[m,v])

Note that there is >= and not == in the constraint: the constraint must hold even if a different machine m is chosen.

Best regards, Petr

Originally posted by: AndyHam

I initially thought I understood the approach, but I was not. After so many trial-errors, I think I am getting close, although my approach has went to different direction from Petr's suggestion. I have one quick question about OPL syntax.

I would like to forbid conducting same type of tasks consecutively: Drop==>Drop and Pkup==>Pkup. The transition matrix does not work in my case so I would like to try out CumulFunction. For each machine, add 1 if a vehicle drops a job to machine and subtract 1 if a vehicle picks up a job from machine.

Can I declare the cumulFunction something like below?

Subject to

forall (m in Machines) cfJobOnHand[m] >= 0;
forall (m in Machines) cfJobOnHand[m] <= 1;

Thanks for your help!

Hi,

as far as syntax is concerned, I would write something like

cumulFunction cpuUsage =
   -sum(t in TaskNames:ord(TaskNames,t) mod 50 ==0) stepAtStart(itvs[t],1)
     +sum(t in TaskNames:ord(TaskNames,t) mod 50 >=1) stepAtStart(itvs[t],1);

and then you may use alwaysIn

alwaysIn(cpuUsage,15,20,1,200*nbCPU);

regards

Originally posted by: PhilippeLaborie

Hi Andy,
I'm not sure why the transition matrix does not work for modelling this. You could say the transition distance between two consecutive Drop (two consecutive Pkup) is IntervalMax (or any large number). If your transition distance if posted to hold on direct successors only (noOverlap(seq, tdist, onDirect=1), then it will rule out the forbidden transitions.

But I'm not sure why you need this. I would suggest a model as follow (quite similar to the one proposed by Petr). For each job i:

job[i]: the job (present)
moveTo[i]: the moving activity (present) from the stocker to the machine of job i by a vehicle
moveFrom[i]: the moving activity (present) from the machine of job i to the stocker by a vehicle

jobOnMachine[i][m]: optional interval for job i on machine m
moveToMachine[i][m]: optional interval representing the moving activity from the stocker to the machine m of job i by a vehicle, size is given by the transition time from stocker to m
moveFromMachine[i][m]: optional interval representing the moving activity from the machine m of job i to the stocker by a vehicle, size is given by the transition time from m to the stocker
 

moveToMachineByVehicle[i][m][v]: optional interval representing the moving activity from the stocker to the machine m of job i by vehicle v
moveFromMachineByVehicle[i][m][v]: optional interval representing the moving activity from the machine m of job i to the stocker by vehicle v

then you have alternative constraints
alternative(job[i], [ all(m) jobOnMachine[i][m] ])
alternative(moveTo[i], [ all(m) moveToMachine[i][m] ])
alternative(moveToMachine[i][m], [ all(v) moveToMachineByVehicle[i][m][v] ])
alternative(moveFrom[i], [ all(m) moveFromMachine[i][m] ])
alternative(moveFromMachine[i][m], [ all(v) moveFromMachineByVehicle[i][m][v] ])

and precedence constraints:
endBeforeStart(moveTo[i], job[i])
endBeforeStart(job[i], moveFrom[i])

and logical constraints:
presenceOf(jobOnMachine[i][m]) == presenceOf(moveToMachine[i][m])
presenceOf(jobOnMachine[i][m]) == presenceOf(moveFromMachine[i][m])

and noOverlap:
forall(m) noOverlap( [ all(i) jobOnMachine[i][m] ])
forall(v) noOverlap( [ all(i,m) moveToMachineByVehicle[i][m][v], all(i,m) moveFromMachineByVehicle[i][m][v] ], TransitionDistance)

The idea of the model is to only model as interval variables the movements of the vehicles when they carry something, the movements when they are empty are just handled by transition times (no interval variable) in the transition distance. If you have M machine and thus, M+1 locations by including the stocker, you can pre-compute the transition distance for the noOverlap on vehicles using 2M types (as you have 2 kinds of intervals: the Stocker to Machine m ones and the machine m to Stocker ones).

Originally posted by: AndyHam

Dear Philippe,

Thanks for the detailed advice.

I think I understand the main idea, but I believe I am still not well understanding the syntax of noOverlap:

The following code has two intervals with transition distance, unlike the common usage of noOverlap (Sequence, transition distance).

forall(v in Vehicles)  noOverlap(all(j in Jobs, m in Machines) moveToMachineByVehicle[j][m][v], all(j in Jobs, m in Machines) moveFromMachineByVehicle[j][m][v], m2m_dist);

The code generates an error so I replaced it with the following codes. There is no error anymore, but the transition time is not correctly imposed.

dvar sequence seqVeh[v in Vehicles]

  in       append(all(m in Machines, j in Jobs) moveToMachineByVehicle[j][m][v],

                       all(m in Machines, j in Jobs) moveFromMachineByVehicle[j][m][v])

  types append(all(m in Machines, j in Jobs) m, all(m in Machines, j in Jobs) (nbMchs+1) );

forall(v in Vehicles) noOverlap(all(j in Jobs, m in Machines) moveToMachineByVehicle[j][m][v]);

forall(v in Vehicles) noOverlap(all(j in Jobs, m in Machines) moveFromMachineByVehicle[j][m][v]);

forall (v in Vehicles) noOverlap(seqVeh[v],m2m_dist);

Any help will be nice.

Thanks,

Andy

Originally posted by: PhilippeLaborie

The right syntax is the one with append. Your model seems correct (except that you probably still did not define the size of some interval variables :

dvar interval moveToMachine[Jobs][m in Machines] optional size Dist[nbMchs+1][m];
dvar interval moveFromMachine[Jobs][m in Machines] optional size Dist[m][nbMchs+1];

But indeed, the sequences seqVeh are very strange, here it should have 20 interval variables but in the display it only shows 10 interval variables. 

We will investigate .and let you know what happens ... 

An alternative way is to define single arrays instead of the two arrays for the arrays  (FromMachine/ToMachine) and differentiate between the two with an additional dimension in the array indexed by a 0..1 range: 0 means FromMachine, 1 means ToMachine).

This would avoid the append as you would have all the necessary interval variables for the sequence in a single array.

Originally posted by: PhilippeLaborie

In fact I think that the problem comes from the transition time matrix m2m_dist that your are using here which is wrong. You cannot use the original matrix between machine positions here because the interval variables on the sequence represent moving activities with different origin and destination positions. You have 2*nbMchs types of intervals in the sequence seqVeh[v].

You should for instance index the intervals moveFromMachineByVehicle[j][m][v] by an index m (in 1..nbMchs) and the intervals moveToMachineByVehicle[j][m][v] by an index m+nbMchs (in nbMchs+1..2*nbMchs).

An interval of index i <= nbMchs is an interval moveFromMachineByVehicle that starts at location i (machine) and finished at the stocker.

An interval of index i > nbMchs is an interval moveToMachineByVehicle that starts from the stocker and finishes at location i-nbMchs (machine)

Thus the transition distance matrix used in the sequence (let's call it TD) should be indexed on 1..2*nbMchs and such that:

if i <= nbMchs and j <= nbMchs: TD[i,j] = Dist[Stocker][j]

if i <= nbMchs and j > nbMchs: TD[i][j] = Dist[i][j]

if i > nbMchs and j <= nbMchs: TD[i][j] = Dist[i-nbMchs][j]

if i > nbMchs and j > nbMchs: TD[i][j] = Dist[i-nbMchs][Stocker]

Originally posted by: AndyHam

It took several days for me to grasp the logic ^^.  
Finally, the model starts work!

One additional question regarding an OPL syntax: how to append three different arrays.
I am trying to initialize the location of vehicle by using append keyword.

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

dvar sequence seqVeh[v in Vehicles]

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

However, I have an error, "The function append(dvar interval[ ],dvar interval[ ],dvar interval) does not exist."
How to append three different arrays?
Thanks,
Andy

Hi,

in the example sched_sequence,

if I change

dvar sequence workers[w in WorkerNames] in
    all(h in Houses, t in TaskNames: Worker[t]==w) itvs[h][t] types
    all(h in Houses, t in TaskNames: Worker[t]==w) h;

into

dvar sequence workers[w in WorkerNames] in
    append(all(h in Houses, t in TaskNames: (Worker[t]==w )&& (h!=1) && (h!=2)) itvs[h][t] ,
    all(h in Houses, t in TaskNames: Worker[t]==w && h==1) itvs[h][t],
    all(h in Houses, t in TaskNames: Worker[t]==w && h==2) itvs[h][t]
    )
    
    types
    append(all(h in Houses, t in TaskNames: Worker[t]==w && h!=1 && h!=2) h,
    all(h in Houses, t in TaskNames: Worker[t]==w && h==1) 1,
    all(h in Houses, t in TaskNames: Worker[t]==w && h==2) 2
    );

it works fine!

In your example I would rewrite

vehicleInitLoc[v]

and

Loc_of_vehicle[v]);

into

all(dummy in 1..1) vehicleInitLoc[v]

and

all(dummy in 1..1) Loc_of_vehicle[v]);

regards

Originally posted by: AndyHam

all(dummy in 1..1) ...

It works well! Thanks!

I will validate the model with several test instances and come back to this forum.

Originally posted by: AndyHam

My guess is the two-stage model will improve the performance a bit, but not much. Please give me any other idea, which I can try on.

Originally posted by: PhilippeLaborie

Hi Andy,

I don't think the decomposition in 2 steps you mention will work because providing a starting point solution could help in speeding up the convergence for finding a good quality solution but it will not help for proving optimality and here, the problem is with optimality proofs.

In fact I think that on this type of problem, because of the sequence dependent setup times, CPO can be very good at finding good quality or optimal solution for even much larger problem sizes but it won't be very good at *proving* optimality. Looking at your model I can propose a few changes that can help proving optimality for small size instances, they are implemented in the attached model that proves the solution at makespan 73 is optimal, but I'm don't expect these optimality proofs to scale well.

Summary of main changes in the model:

1- use of redundant cumulative functions for the machines and the vehicles

2- increase of the inference level for noOverlap and cumul functions

3- use of a search phase on sequence variable to first fix the ordering on the vehicles

4- use of a single objective (here cmax). If you want to get faster optimality proofs in case of bi-criterion, I suggest to treat the two criterions in 2 different models: first minimize cmax, then add a constraint not to degradate cmax, pass the previous solution as starting point and minimize lastDelivery in a second solve.

Note that these changes (especially 2 and 3) will help for proving optimality but may on the contrary result in worse performance for finding good quality solutions to larger instances.

Philippe

Originally posted by: AndyHam

Thanks for the insight. Those changes make a big difference (hours==>0.6 s)
I will run an experimental study and come back to this forum.

2 and 3 are very interesting tuning.
1 seems to be equivalent with valid inequalities in MIP.
Thanks for the big help.