So i'm working on my school project and The problem is described as follow:

we have 31 baths and 4 cranes '1 axis of movement'. enter image description here

figure 1: a crane imageimagen_2021-06-01_120450.png

enter image description here figure 2: baths and cranes

1,2: are for load and unload the material 4,5: are similar baths 29,30,31,32: are similar baths

the process is this:

1 or 2 => 16 => 18=> 19 => 20 => 22 => 23 => 24 => 25 => 29 or 30 or 31or 32 => 28 => 27=> 26=> 13 => 10=> 9 => 8 => 6=> 4 or 5 => 1 or 2.

the 'or' word significate if one of the baths is free we use it.

the non colusion condition: -we should have 1 bath between two cranes -in baths 29,30,31,32: we have 30 min of processing time -in baths 21,22: we have 5 min of processing time loading and unloading time is 2s. for each crane moving from one bath to next one takes 2s. so from 1 to 10 is 20s and vice versa.

the objectif is to optimize the cycle time and process max products.

can you please give me some hints on how can i solve this problem.

  • $\begingroup$ As this is a school assignment please include your attempts at solving the problem. $\endgroup$
    – TheSimpliFire
    Jun 3, 2021 at 9:45

2 Answers 2


The problem is a combination of two problems: The first is the transport with the cranes and the non crossing constraints (non colusion condition). Check out this paper:

N. Boysen, D. Briskorn, S. Emde Parts-to-picker based order processing in a rack- moving mobile robots environment Eur J Oper Res, 262 (2) (2017), pp. 550-562

as a good starting point into non-crossing constraints.

The other part is a machine scheduling problem with the baths being your machines. You probably don't even need google scholar and can just use regular google to find introductory information.

If you want to go into very fast techniques but very complicated techniques, I imagine modelling this as a CVRP and dynamically generating the non-crossing constraints will get you very far.


As far as I know, this is a special type of blocking job shop problem. Take a look at this paper: https://link.springer.com/article/10.1007/s10878-014-9723-3 If you search for BJS-RT you will find more literature that is freely available.

Once you have formulated it as BJS, there are different ways of solving it. Heuristics or for smaller instances CP or even MIP will work fine.


Not the answer you're looking for? Browse other questions tagged or ask your own question.