Topic
  • 3 replies
  • Latest Post - ‏2014-03-13T01:03:30Z by qtbgo
qtbgo
qtbgo
134 Posts

Pinned topic deadlock in a bidirectional flowshop with block

‏2013-10-25T13:05:11Z |

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.

Updated on 2013-10-26T11:21:04Z at 2013-10-26T11:21:04Z by qtbgo
  • Petr Vilím
    Petr Vilím
    13 Posts

    Re: deadlock in a bidirectional flowshop with block

    ‏2013-11-07T15:52:19Z  

    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

  • qtbgo
    qtbgo
    134 Posts

    Re: deadlock in a bidirectional flowshop with block

    ‏2013-11-08T00:29:55Z  

    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

    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.

  • qtbgo
    qtbgo
    134 Posts

    Re: deadlock in a bidirectional flowshop with block

    ‏2014-03-13T01:03:30Z  

    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

    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?