Originally posted by: AndyHam

Dear IBM,
I am working on flexible job shop with job-transfer with mobile robot. There is a great FJSP cp example in Cplex studio, but I am attempting to write a new code to better trace mobile robots. Now, I need some help on OPL script.
 

Suppose there are two jobs (1 and 2). Job 1 has two steps and each step has two machines. For instance, Job 1 can be processed on either machine 3 or 2 at step 1.

(input)

alt ={

//job      step       mch       pt

<1          1             3             10>

<1          1             2             20>

<1          2             7             36>

<1          2             8             26>

<2          1             3             20>

<2          1             4             15>

<2          2             7             24>

<2          2             8             36>

<2          3             2             14>

<2          3             3             10>

};

 

Now, I would like to precalculate all possible combinations of job to machine assignment and term each combination "route".

For instance, Job 1 has possible routes of mch 3è7, mch 3è8, mch 2è7, and mch 2è8.

Can you please help me to write OPL script to generate the combination as shown below?

route     job         step       mch       pt    (Desired Output)

1             1             1             3             10

1             1             2             7             36

2             1             1             3             10

2             1             2             8             26

3             1             1             2             20

3             1             2             7             36

4             1             1             2             20

4             1             2             8             26

1             2             1             3             20

1             2             2             7             24

1             2             3             2             14

2             2   .......... .......... .......... ..........

Thanks,
Andy

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: PhilippeLaborie

Hi Andy,

Why do you want to do this computation in the script? The number of possible routes for a job grows exponentially with the number of operations, is it not an issue?

In general, I would try to handle the job transfer by the robot on each precedence between consecutive operations of a job. Do you see some problem with that?

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: AndyHam

Hi Philippe,
You are right. I successfully developed the transbot scheduling models for both JSP and FJSP owing to the help from this forum. 
A CP model for JSP with transbot outperformed all other benchmark approaches in the literature. The enclosed paper will appear on International Journal of Production Research. In particular, I merged pickup and dropoff tasks into one for a better performance.
However, the result of FJSP with transbot model was not much impressive so I am thinking about the alternative model. Unlike the subsequent machine ID of each job, upon completing an operation, is known a priori in a JSP problem, a machine ID must be determined in a FJSP since a job is processed on a machine out of a set of alternatives, which makes the transbot-scheduling much more complex. If I can use the above route concept, I will be able to trace the robot location more effectively. Namely, the FJSP problem changes into JSP by using the route so I can merge the pickup and dropoff tasks into one for a better performance.

I am using small test instances from
L. Deroussi, "A Hybrid PSO Applied to the Flexible Job Shop with Transport," in Lecture Notes in Computer Science, 8472, Springer, Cham, 2014, 115-122.

So, the number of possible routes should not be too large. Please help me ^^

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: PhilippeLaborie

> The enclosed paper will appear on International Journal of Production Research

Did you attach the paper?

 

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: AndyHam

Enclosed here.

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: PhilippeLaborie

I would first try a formulation that is polynomial with the number of operations in a job. Did you try a formulation with optional interval variables for the possible transportations between each pair of consecutive machines on a precedence between successive operations, like depicted on the attached figure? (the grey lines are alternative constraints, the figure is of course missing some implication constraints, like presenceOf(Tr. (Mi->Mj)) => presenceOf(Op1 on Mi), and presenceOf(Tr. (Mi->Mj)) => presenceOf(Op2 on Mj)

Of course, for strengthening the formulation, it seems it would be a good idea to post a cumulative function on the transportation intervals (Tr.) that is always smaller than the total number of robots (by the way, the same redundant constraint could help on the JSSP version of the article too...)

 

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: AndyHam

I think I formulated the problem in a way you proposed above. The enclosed is a FJSP model.
The model works well, but I am trying to further improve a performance. When I merge pickup and dropoff into one transfer in JSP, the performance was greatly improved. So, I am trying to apply the same modeling technique into FJSP.

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: PhilippeLaborie

In the picture I attached, the intervals like "Tr. (Mi->Mj) by Rk" represent the transportation by robot Rk from machine Mi to machine Mj, they merge the pickup and delivery, they play exactly the same role as the transportation interval in your CP2 formulation for the JSP.

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: AndyHam

My apology! I am always slow to understand.
I think I finally got what you meant "optional interval variables for the possible transportation between each pair of consecutive machines".
I did never thought the way. I agree that it would work beautifully.
Let me come back to this forum after I have the model work in this way.
Thanks always for your insightful feedback!


 

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: AndyHam

The figure did not include the initial transfer from stocker to the first operation, so I have added it in addition to the transfers between normal operations. The proposed technique greatly improved the performance (see below). 

CP1 is the model which has separate pickup and dropoff transfers.
CP2 is the model which merged pickup and dropoff transfer.
model          t        inst    sec    obj
CP1.mod    120    js1    120.043    134
CP2.mod    120    js1    15.628      134
CP1.mod    120    js2    120.041    114
CP2.mod    120    js2    68.2          114
CP1.mod    120    js3    8.495        120
CP2.mod    120    js3    3.078        120
CP1.mod    120    js4    120.061    116
CP2.mod    120    js4    120.062    114
CP1.mod    120    js5    101.936      94
CP2.mod    120    js5    2.795          94

#DecisionOptimization
#OPLusingCPOptimizer