Decision Optimization

  • 1.  Flexible Job Shop Problem

    Posted Fri October 25, 2019 11:31 AM

    Originally posted by: kcapt


    Hello,

    I'm a beginner at programing and at using cplex. I've analyzed most of the examples of Flowshops and Jobshops. However the problem I have at hands it's a job shop with parallel machine problem.

    I want to schedule jobs that consist in strictly ordered sequence of operations, so they have to go through Stage1(Extruction)>Stage2(painting)>Stage3(finishing).To make job on the second stage, it must be completed on the first stage and so on...

    In the factory floor there are 3 production lines, each production line has one machine of every stage. Every job can use whatever machine he wants.(See the image below)

     

    The example "sched_jobshopflex" almost resolves this problem. In "sched_jobshopflex" you have to MANUALLY  introduze in which machine that operation will be processed. Is there a way to only introduze the job id, position in job, processing time, ect... But let the Cplex choose it's machines path? To conclude, I want Cplex to choose a certain machine in a certain phase automatically and giving me the gantt chart just like "sched_jobshopflex".

    Thank you!

     

    Note: One article that represents what I'm talking about is in the Attachments.

    Any help would be appreciated, thank you!



  • 2.  Re: Flexible Job Shop Problem

    Posted Fri October 25, 2019 11:50 AM

    Originally posted by: kcapt


    I may not have made myself clear. The only problem found with the "sched_jobshopflex" is that I have to write the exactly machine (<operation ID, Machine, Processing time>). Otherwise it would be perfect!

    I want the Cplex to choose it's machines given a certain machines in that phase.



  • 3.  Re: Flexible Job Shop Problem

    Posted Fri October 25, 2019 01:17 PM

    Originally posted by: Petr Vilím


    Hello,

    I believe that sched_jobshopflex is exactly what you're looking for. It is the solver (CP Optimizer) who will choose which machine will be used by each task, you only have list all allowed allocations of an operation to a machine.

    The trick behind is "optionality" of interval variables. An interval variable can be specified as optional (see setOptional calls in sched_jobshopflex) and in this case they do not have to be performed (they could be "absent" in the solution). Then a constraint called "alternative" can bind such optional activities together and specify that exactly one of them must be "present" in the solution, the rest of them must be "absent". This forces the solver to choose exactly one of the alternatives. And the solver will look for such allocation that is the best considering the objective function.

    The optionality of interval variables and constraint "alternative" is a bit more complicated. I recommend you to have a look on mathematical semantics behind all this. Optionality is defined here:

    https://www.ibm.com/support/knowledgecenter/SSSA5P_12.9.0/ilog.odms.ide.help/refcppopl/html/interval_variables.html

    And alternative constraint here:

    https://www.ibm.com/support/knowledgecenter/SSSA5P_12.9.0/ilog.odms.ide.help/refcppopl/html/constraints_groups.html

    If you want to know more about the algorithms behind then I recommend the paper "Reasoning with Conditional Time-intervals" by Laborie and Rogerie.

    Petr



  • 4.  Re: Flexible Job Shop Problem

    Posted Sat October 26, 2019 12:34 PM

    Originally posted by: kcapt


    Hi, sorry I didn't get what you told me.

    What about this situation, would it be easier?

    --> Refering to the sched_jobshopflex:

                      When the  Position in job is equal to 0 ( Ops = {<1,1,0>} ) it has to be processed in either machine 1,2 or 3.  

                      When the  Position in job is equal to 1 ( Ops = {<1,1,1>} ) it has to be processed in either machine 4,5 or 6.  

                      When the  Position in job is equal to 2 ( Ops = {<1,1,2>} ) it has to be processed in either machine 7,8 o r9.  



  • 5.  Re: Flexible Job Shop Problem

    Posted Sun October 27, 2019 09:07 AM

    Originally posted by: Petr Vilím


    Hello,

    so when Position is 0 then it is necessary to create three optional intervals for the operation: one will represent the case when the operation is performed by machine 1, second by machine 2 and third by machine 3. And then you need to combine those three sub-operations by constraint "alternative".

    I'm guessing that you're referring to OPL example sched_jobshopflex (there is also C++ example with the same name). And it seems to me that you don't understand the data format. So let me explain:

    Operations are defined as in sched_jobshopflex.dat as:

    tuple Operation {
      int id;    // Operation id
      int jobId; // Job id
      int pos;   // Position in job
    };
    {Operation} Ops   = ...;
    

    So each operation has a unique id, it is used later to specify possible modes for the operation. The id could be any number, but in our case it is simply number of the operation counted from 1. Jobs has also unique ids, again it is just simply a number starting to from 1. Each operation specifies to which job it belongs (by jobId) and its position within the job (by pos). Positions seems to be counted from 0. For example, here is part of sched_jobshop.dat file:

    Ops = {
      <1,1,0>,
      <2,1,1>,
      <3,1,2>,
      <4,1,3>,
      <5,1,4>,
    

    All the operations above are from the same job (jobId=1). First line specifies first operation of the job 1 (position=0), second line second operation (position=1) etc. Notice the operation ids are really unique, for example there is only one operation with id=1, the same operation id cannot be reused another operation (even in another job).

    Now Modes specifies possible machine allocations for operations. It is defined as:

    tuple Mode {
      int opId; // Operation id
      int mch;  // Machine
      int pt;   // Processing time
    };
    {Mode}      Modes = ...;
    

    For given operation (specified by opId) there could be multiple records in Modes, each record specifies a machine and processing time. From the data file:

    Modes = {
      <1,3,13>,
      <1,7,12>,
      <2,8,9>,
      <2,9,17>,
    

    So for operation with id=1 there are two modes. First mode is using machine 3 and has duration 13, second mode is using machine 7 and has duration 12. Considering the model, the solver will have to chose one of the modes (and therefore one of those machines and accordingly the duration). Similarly for operation with id=2 there also two modes: machine 8 and duration 8 or machine 9 and duration 17.

    I hope it helps.

    Petr



  • 6.  Re: Flexible Job Shop Problem

    Posted Sun October 27, 2019 05:31 PM

    Originally posted by: kcapt


    Sir, I trully apreciatted your time. It totally answered my question!!!!! I just wasn't getting how it all worked.

    Just two more questions: 

    1- Is it possible to find the mathematical heuristic/article behind "sched_jobshopflex"? 

    2- Is there any method to help me read the gantt chart better, instead of the names like "modes[<4,2,5>]".

    Again, much thanks!



  • 7.  Re: Flexible Job Shop Problem

    Posted Tue October 29, 2019 08:53 AM

    Originally posted by: Petr Vilím


    Hello,

    I'm glad it helps. Regarding question 1, you can have a look at the following articles:

    Vilim, Laborie, Shaw: Failure-directed Search for Constraint-based Scheduling

    Laborie, Godard: Self-adapting large neighborhood search: Application to single-mode scheduling problems

    And regarding question 2, you may change the Mode tuple to include some additional information. Then you will see "modes[<4,2,5,xxx>]" where xxx is value of the additional field.

    Regards, Petr