Originally posted by: qtbgo

Hi, I wonder how to model the following scenario. Consider a simple 3 stages flowshop, there are no buffers in between. The interesting point here is that jobs can be processed in two directions, e.g., jobs of type t1 flow from machine A to B to C, while jobs of type t2 flow from machine C to B to A.

Suppose that machine B is a Truck and machine C is a Crane, jobs are containers. Now, consider a situation, job1 of type t1 just finished its operation on B(i.e., it is transported to location of B by a truck), and at the same time job2 of type t2  finished its opeation on C(it is lifted by the Crane). Here, a deadlock occurs, because we cannot exchange the two jobs instantly.

So, how to build a CP model to avoid this deadlock?

If it becomes a hybrid flowshop with block, it will be even more complicated.

Thanks in advance.

Originally posted by: Petr Vilím

Hello,

if I understand right then it is not possible to process any jobs of type t1 and simultaneously with type t2 because otherwise deadlock will occur sooner or later. For example, it is not possible to process t1 job on machine A and at the same time process t2 job on machine C, because such schedule is heading toward the deadlock, either before A dn B or before B and C. In another words, at any time it is possible to to process only type t1 jobs or only type t2 jobs.

This can be modeled by adding one (global) state function: state 1 means that only processing of t1 jobs is allowed (on any machine), state 2 means that only processing of t2 jobs is allowed (on any machine). At any time, only one value of the state is allowed. This can be achieved by alwaysEqual constraint. Type t1 jobs will require the state to be 1, t2 jobs will require state 2.

Best regards, Petr

Originally posted by: qtbgo

Thank you Petr, your understand is right. In fact, I simplified the problem, there are actually multiple machines in each stage, I'll think if your suggestion works in this situation.

Originally posted by: qtbgo

Hi, Petr, I still cannot figure out a solution for my problem, if there are multiple machines in each stage, how can the deadlock be avoid?