Originally posted by: AndyHam

I have a question about accessing a "type" of interval on a sequence.

Suppose there are two sequences:

1. seqBot: keeps track of robot location.
2. seqRet: keeps track of floating auxiliary resource

Now, a robot needs to pick up the auxiliary resource and drop it off to a machine. The total traveling distance can be calculated as follows:

= t[robot location][auxiliary resource location] + t[auxiliary resource location] [machine location]

I have a following code which works well, but I realized that it is not efficient. It does not converge to optimal even with a very small problem (  nj=7; //number of jobs  nm=2; //number of machines  nr=2; //number of reticles  nLotBot=1; //number of vehicles for lot delivery  nRetBot=1; // number of vehicles for reticle delivery)

Is there any better way to model this problem?

forall(mr in MR){

    forall (b in Bots) {

       presenceOf(retTransBot[mr][b]) => sizeOf(retTransBot[mr][b])==

          t[typeOfPrev(seqBot[b],   retTransBot[mr][b],StkIdx,StkIdx)]

           [typeOfPrev(seqRet[mr.ret],itvMR[mr],StkIdx,StkIdx)]  +      

          t[typeOfPrev(seqRet[mr.ret],itvMR[mr],StkIdx,StkIdx)][mr.mch];   

       }    

 }

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: GGR

Hi Andy

 

Sorry for the late answer

 

If I understand well, you try to schedule the route of the transportation system (the robot) from location to location to move a machine facility (let's call it a tool)

then the tools is an unary  machine whose interval are the task to execute at a certain location.

 

Let's call operation[task][location] a task at a location.  Let's suppose the location is a unary resource.and D_l the transition time matrix between locations. 

Beware it is not perfect OPL

I suppose you have defines the tuple sets: Tasks<machine, whatever>, Locations<>, Operations<task, location>

forall(l in Locations)
  noOverlap(all (o in Operations, o.location = l) operations[o.task][l])
  
forall(t in Tasks)
  alternative(tasks[t], all (o in Operations; t.task = t) operations[t][o.location])

var sequence machines[m in Machines] all (o in Operations; o.machine = m) operations[o.task][o.location], all (o in Operations; o.machine = m) o.location
 
forall(m in Machines)
  noOverlap(machines[m], D_l)

You have to assign the robots has to transport the machines of from operation  location to a another operation location. The robot move start at a location corresponding to the exit of the previous operations (you know the location). a robot ends at a location corresponding to entering of the next operation (you know the location).

I suppose you have define the tuple sets Robots<> and  Moves<operation, robot> :

dvar interval starts[o in Operations] optional size 0
dvar interval ends[o in Operations] optional size 0


dvar robotStarts[m in Moves][r in Robots] optional size 0
dvar robotEnds[m in Moves][r in Robots] optional size 0

dvar sequence robots[r in Robots] all(m in Moves, m.robot = r) robotStarts[m] + all(m in Moves, m.robot = r) robotEnds[m]
               , all(m in Moves, m.robot = r) m.operation.location + all(m in Moves, m.robot = r) m.operation.location
               
forall(o in Operations)
    alternative[starts[o], all (m in Moves, r in Robots; m.operation = o) robotStarts[m][r])
    alternative[starts[o], all (m in Moves, r in Robots; m.operation = o) robotEndss[m][r])
    presenceOf(starts[o]) = presenceOf(ends[o])
    startAtEnd(starts[o], operations[o])
    endAtStart(ends[o], operations[o])
    
forall(r in Robots)  
  noOverlap(robots[r], D_l)

• You need now to take some precaution to define the task, depending on how works the factory. For example, if the task occupy the location waiting for the robots, you have to make slack in the task definition. That is the tasks has a variable size whose minimum is the processing time of the task.
• You have to add a search phase to declare you schedule only the operations (starts and ends will be automatically fix)

The model is cubic  (number of possible  moves). The size  may be huge if there is a non small number of robots. Ibig size generally prevent having an efficient optimisation procedure. There is a classical workaround :

 

usually, the robots pool is not a critical resource or robots transportation time is small with respect to task processing time. Then you can have a two phase model.

 

First you solve the model ignoring the robot management (model 1)

The model 1 incumbent is an assignment of a task at a location and the sequence on machine and location.. 

Be the tuple sets Operations<task, location, machine, nextOperationAtLocation, nextOperationOnMachine>

 Model 2 declares operations (non optional)  and tell the precedence (startsBeforeEnd) between an operation and its nextOperationAtLocation and its nextOperationOnMachine (with a delay the transportation time between their locations) : you have fixed the sequence in location for a machine

Then model 2 tells the robots allocation model form these operations 

 

If  there is still time for trying to improve the model 2 incumbent, you can use some tricks slightly relaxing the model and using model 2 incumbent as starting point.

• Relax locations and machines sequence  (keeping anyway location and machine assignment)
• Relax location operation location assignment using an alternative of few small time travel neighbour locations that are closed to the starting point ones (few locations to avoid a cubic effect)

 

 

Hope that helps

 

 

 

 

 

 

 

 

is  an operation is a is an alternative of

 

from what I understand Robots is an sequence whose transition distance it the time travel between two locations.

I figure out you model the (tool, robot)  thanks to an alternative of robots.

 

My question is why 

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: AndyHam

Thanks for the insight. In particular, creating intervals with size 0 to mark the transfer tasks was very helpful. However, it took many days for me to digest ^^.
Now, I managed to have two different CP models for "Integrated scheduling of jobs, reticles, machines, AMHS and ARHS in a semiconductor manufacturing".
This paper studies a simultaneous scheduling of production and material transfer that arises at the semiconductor photolithography area. In particular, jobs are transferred by a material handling system that employees a fleet of vehicles. Reticles serving as an auxiliary resource are also transferred from one place to another by a different set of vehicles. 

Unfortunately, both models failed to find an feasible solution for large-sized problems so a constructive heuristic was built to generate an initial feasible solution for a warm-start. The CP models fed by this constructive heuristic successfully generate solutions for large-sized problems. Now, I am working on MIP model, but it is not fun. I am spoiled ^^. I am too much used to flexible modeling with CP so I don't want to touch the stubborn MIP modeling ^^

 

dvar interval itvLotBotInit[LotBots] in -1..0 size 1;
dvar interval itvRetBotInit[RetBots] in -1..0 size 1;
dvar interval itvRetInit[Reticles] in -1..0 size 1;

dvar interval itvJob[j in par_Jobs]  size j.pt; 
dvar interval itvMach[j2m in par_J2M2Rs] optional;

dvar interval lot2Bot4Load[par_J2M2Rs][LotBots] optional size 0;;
dvar interval lot2Bot4Unload[par_J2M2Rs][LotBots] optional size 0;;

dvar interval itvMR[MR] optional;
dvar interval retLoad[MR] optional size 0;
dvar interval retLoadBot[MR][RetBots] optional size 0;
dvar interval retUnload[MR] optional size 0;
dvar interval retUnloadBot[MR][RetBots] optional size 0;

#DecisionOptimization
#OPLusingCPOptimizer