Topic
  • 6 replies
  • Latest Post - ‏2014-05-08T06:40:58Z by Chawalit
Chawalit
Chawalit
4 Posts

Pinned topic How to model the Batch job

‏2014-05-01T16:42:48Z |

Dear all;

 

I have a production of batch process. The work order come with the number of demand, with start time and due date and its processing time.

There are several machines and each machines contain 10 slots for the jobs. The capacity of the slots depend on the type of product. 

There are limited number of stainless to use with the machine and it specify by work order. After using the stainless, it will be clean for some fixed time. 

The question is how can I model this batch process that I could assign the work order into slot and all of this slot in the machine must be process with the same time and same processing time. The demand can be 1000 units and the capacity of the slot is around 10 units each time.

 

As far as I look through all examples with IBM, there is a job and it will be processed once by the machine and the time require would be enough for that job. Any help would be greatly appreciate.

 

Thank you very much,

Chawalit

Updated on 2014-05-03T04:10:23Z at 2014-05-03T04:10:23Z by Chawalit
  • PhilippeLaborie
    PhilippeLaborie
    68 Posts
    ACCEPTED ANSWER

    Re: How to model the Batch job

    ‏2014-05-05T07:38:03Z  

    Hello,

    The part of the problem consisting of the allocation of jobs to the machines can probably be modeled using a combination of cumulFunction (for modeling the limited capacity of slots) and stateFunction (for modeling the batches: jobs in the same batch must be processed together, same start time and same processing time).

    Here is for instance a small example related with what you want to do. A set of tasks has to be processed by some ovens at a particular task-dependent temperature. An oven o can process several tasks simultaneously (provided its capacity ovenCapacity[o] is not exceeded). When processed in the same batch, tasks must start and end at the same time (this is modeled by the "alwaysEqual" constraint with start and end alignment (more information in the documentation about state functions).

    ...
    
    /*********************
    * Decision variables *
    **********************/
    
    dvar interval tasks[t in allTasks] in preparationTime..maxTime size t.duration;
    dvar interval taskOvenAlts[t in allTasks][o in ovens] optional;
    
    cumulFunction ovenUsage[o in ovens] = sum(t in allTasks) pulse(taskOvenAlts[t][o], 1);
    stateFunction ovenTemperature[o in ovens] with transitionTimes;
    
    /************
    * Objective *
    *************/
    
    minimize max(t in allTasks) endOf(tasks[t]);
    
    /**************
    * Constraints *
    ***************/
    
    subject to {
      // for each oven, ovenUsage cannot exceed oven capacity
      forall(o in ovens)
        ovenUsage[o] <= ovenCapacity[o];  
     
      // each task can be executed on at most one oven
      forall(t in allTasks) 
        alternative(tasks[t], all (o in ovens) taskOvenAlts[t][o]);
      
      // the temperatureCode on an oven should correspond to the temperature of the task scheduled on the oven at any point in time
      forall(t in allTasks, o in ovens)
        alwaysEqual(ovenTemperature[o], taskOvenAlts[t][o], t.temperatureCode, true, true);  
    }
    

    Hope it helps,

    Philippe

  • PhilippeLaborie
    PhilippeLaborie
    68 Posts
    ACCEPTED ANSWER

    Re: How to model the Batch job

    ‏2014-05-07T09:34:23Z  
    • Chawalit
    • ‏2014-05-06T14:09:53Z

     

    Dear Philippe;

    Here is the more formal mathematical ways I have for the problem.

    ​I am coming from MIP and this is my first time using CP.

    â€

    ​We have some of the data:

    tuple panel_tuple{
      key int partnumber;
      float width;
      float height;
      int processingtime;

      };

    ​{panel_tuple} PanelData;

    tuple WorkOrder_tuple{
      key int WOnumber;
      int partnumber;
      int ReleaseDate; 
      int DeliveryDate; 
      int Demand; // unit
      int processingtime; 
      };

    {WorkOrder_tuple} WorkOrderData;

     tuple stainless_tuple{
       key int stainlessindex;
       float width;
       float height;
       int capacity;

       int CleaningTime;

       };
     
    {stainless_tuple} StainlessData; 

     

    tuple group_tuple{
      key int GroupNumber;
      int layout;
      {int} panel_set; // group of the panel can be process on the same machine
      int processingtime; 
      int stainlessindex; 
       float Waste;
       int ProductionOutput; // number of production per machine slot
    };

    {group_tuple} GroupData;

    tuple machine_tuple{
      key int machinenumber;
      int NumberOfSlot;
      {int} stainless_set;
      int machine_cost;
      };
      
      {machine_tuple} MachineData;

    int cycles; // number of machine cycle consider per day

    dvar int PanelAssignment[PanelData][Slot_Range][GroupData][m  in MachineData][cycles] in 0..1; // to assign the panel into each slot for each machine
    dvar int GroupAssignment[GroupData][Slot_Range][MachineData][cycles] in 0..1; // to assign the group into each slot for each machine

     

    //Objective function

    minimize the total Waste 

     

    //Constraint

    //1. Demand constraint

    //each of the work order, the demand must be satisfied within the given time interval (releasedate, duedate)

    //The PanelAssignment will assign the panel to the machine, slot, for each cycle (panel can use machine many cycles, many slots)

    sum( p in PanelData, g in GroupData, m  in MachineData,  s in m.NumberOfSlot, c in cycles, w in WorkOrder: w.partnumber == p) PanelAssignment  [p][s][g][m][c] * g.ProductionOutput >= w.Demand; // with the specified period given

    // the total PanelAssignment on the same machine, same cycle must be less than NumberOfSlot available on the machine

    // 2. Group assignment constraint

    // There is only 1 group can be assigned to the machine on the same cycle

    // The panel within the same group can be assigned to the machine on the same cycle

     

    //3. Time interval for each machine and cycle must have the same size as the panel processing time but must be within the release date and due date

     

    //4. the assignment of the stainless must be the same as in the group specify. The time interval for the stainless is the same as the time interval of the machine + CleaningTime

    //5. There is the capacity of each stainless

     

    End;

     

    I hope it is much clear now.

    Thank you very much in advance for your help.

    Chawalit

    I think a CP model will be efficient on this problem only if you can group a set of consecutive and contiguous processing of a part of a work order on a given machine/slot. If the problem is fully elastic, that is: at any time-point/cycle you can freely decide to change the allocation of the work orders on the machine/slots (provided of course the capacity is not exceeded and the compatibility relations are satisfied), then a MIP model should be ok.

    This being said, if you cannot freely allocate the work-order on the machines/slots, typically because it would incur some cost for a machine/slot to switch too often from a given work-order to a different one  (you mentioned some cleaning times), then it could make sense to define (a priori, of after solving a relaxed or approximated MIP model) an envelope of possible time-intervals with a given minimal duration that represents the partial execution of a given work-order on a given machine/slot (in CPO, interval variables can have variable length and can be optional). The assumption here is that if a machine/slots starts to process part of a work order, it must at least process it for a minimal amount of time.

    Philippe

  • PhilippeLaborie
    PhilippeLaborie
    68 Posts

    Re: How to model the Batch job

    ‏2014-05-05T07:38:03Z  

    Hello,

    The part of the problem consisting of the allocation of jobs to the machines can probably be modeled using a combination of cumulFunction (for modeling the limited capacity of slots) and stateFunction (for modeling the batches: jobs in the same batch must be processed together, same start time and same processing time).

    Here is for instance a small example related with what you want to do. A set of tasks has to be processed by some ovens at a particular task-dependent temperature. An oven o can process several tasks simultaneously (provided its capacity ovenCapacity[o] is not exceeded). When processed in the same batch, tasks must start and end at the same time (this is modeled by the "alwaysEqual" constraint with start and end alignment (more information in the documentation about state functions).

    ...
    
    /*********************
    * Decision variables *
    **********************/
    
    dvar interval tasks[t in allTasks] in preparationTime..maxTime size t.duration;
    dvar interval taskOvenAlts[t in allTasks][o in ovens] optional;
    
    cumulFunction ovenUsage[o in ovens] = sum(t in allTasks) pulse(taskOvenAlts[t][o], 1);
    stateFunction ovenTemperature[o in ovens] with transitionTimes;
    
    /************
    * Objective *
    *************/
    
    minimize max(t in allTasks) endOf(tasks[t]);
    
    /**************
    * Constraints *
    ***************/
    
    subject to {
      // for each oven, ovenUsage cannot exceed oven capacity
      forall(o in ovens)
        ovenUsage[o] <= ovenCapacity[o];  
     
      // each task can be executed on at most one oven
      forall(t in allTasks) 
        alternative(tasks[t], all (o in ovens) taskOvenAlts[t][o]);
      
      // the temperatureCode on an oven should correspond to the temperature of the task scheduled on the oven at any point in time
      forall(t in allTasks, o in ovens)
        alwaysEqual(ovenTemperature[o], taskOvenAlts[t][o], t.temperatureCode, true, true);  
    }
    

    Hope it helps,

    Philippe

  • Chawalit
    Chawalit
    4 Posts

    Re: How to model the Batch job

    ‏2014-05-06T09:58:13Z  

    Hello,

    The part of the problem consisting of the allocation of jobs to the machines can probably be modeled using a combination of cumulFunction (for modeling the limited capacity of slots) and stateFunction (for modeling the batches: jobs in the same batch must be processed together, same start time and same processing time).

    Here is for instance a small example related with what you want to do. A set of tasks has to be processed by some ovens at a particular task-dependent temperature. An oven o can process several tasks simultaneously (provided its capacity ovenCapacity[o] is not exceeded). When processed in the same batch, tasks must start and end at the same time (this is modeled by the "alwaysEqual" constraint with start and end alignment (more information in the documentation about state functions).

    <pre class="html dw" data-editor-lang="js" data-pbcklang="html" dir="ltr">... /********************* * Decision variables * **********************/ dvar interval tasks[t in allTasks] in preparationTime..maxTime size t.duration; dvar interval taskOvenAlts[t in allTasks][o in ovens] optional; cumulFunction ovenUsage[o in ovens] = sum(t in allTasks) pulse(taskOvenAlts[t][o], 1); stateFunction ovenTemperature[o in ovens] with transitionTimes; /************ * Objective * *************/ minimize max(t in allTasks) endOf(tasks[t]); /************** * Constraints * ***************/ subject to { // for each oven, ovenUsage cannot exceed oven capacity forall(o in ovens) ovenUsage[o] <= ovenCapacity[o]; // each task can be executed on at most one oven forall(t in allTasks) alternative(tasks[t], all (o in ovens) taskOvenAlts[t][o]); // the temperatureCode on an oven should correspond to the temperature of the task scheduled on the oven at any point in time forall(t in allTasks, o in ovens) alwaysEqual(ovenTemperature[o], taskOvenAlts[t][o], t.temperatureCode, true, true); } </pre>

    Hope it helps,

    Philippe

    Dear Philippe;

     

    Thank you very much for your help. 

    If I have a work order with 1000 units and I do not want to break it down into smaller task, how could we model this one?

    Otherwise it would blow up a lot of interval variables which could take a long time for solving it.

     

    best,

    Chawalit

  • PhilippeLaborie
    PhilippeLaborie
    68 Posts

    Re: How to model the Batch job

    ‏2014-05-06T11:02:54Z  
    • Chawalit
    • ‏2014-05-06T09:58:13Z

    Dear Philippe;

     

    Thank you very much for your help. 

    If I have a work order with 1000 units and I do not want to break it down into smaller task, how could we model this one?

    Otherwise it would blow up a lot of interval variables which could take a long time for solving it.

     

    best,

    Chawalit

    Yes, my answer was focusing on the allocation and scheduling of the jobs on the machines, assuming you know the jobs (even if they may have variable processing time and variable number of units) and need to find their start/end dates (and maybe their number of units) and machines/slots they are allocated to.

    If your problem is different, could you describe it in a more formal/mathematical way? What are the decision variables of your problem? what are the constraints on these variables? Do you need to schedule several of these work orders together ? Can they be interleaved on the machines?

    Regards,

    Philippe

     

  • Chawalit
    Chawalit
    4 Posts

    Re: How to model the Batch job

    ‏2014-05-06T14:09:53Z  

    Yes, my answer was focusing on the allocation and scheduling of the jobs on the machines, assuming you know the jobs (even if they may have variable processing time and variable number of units) and need to find their start/end dates (and maybe their number of units) and machines/slots they are allocated to.

    If your problem is different, could you describe it in a more formal/mathematical way? What are the decision variables of your problem? what are the constraints on these variables? Do you need to schedule several of these work orders together ? Can they be interleaved on the machines?

    Regards,

    Philippe

     

     

    Dear Philippe;

    Here is the more formal mathematical ways I have for the problem.

    ​I am coming from MIP and this is my first time using CP.

    â€

    ​We have some of the data:

    tuple panel_tuple{
      key int partnumber;
      float width;
      float height;
      int processingtime;

      };

    ​{panel_tuple} PanelData;

    tuple WorkOrder_tuple{
      key int WOnumber;
      int partnumber;
      int ReleaseDate; 
      int DeliveryDate; 
      int Demand; // unit
      int processingtime; 
      };

    {WorkOrder_tuple} WorkOrderData;

     tuple stainless_tuple{
       key int stainlessindex;
       float width;
       float height;
       int capacity;

       int CleaningTime;

       };
     
    {stainless_tuple} StainlessData; 

     

    tuple group_tuple{
      key int GroupNumber;
      int layout;
      {int} panel_set; // group of the panel can be process on the same machine
      int processingtime; 
      int stainlessindex; 
       float Waste;
       int ProductionOutput; // number of production per machine slot
    };

    {group_tuple} GroupData;

    tuple machine_tuple{
      key int machinenumber;
      int NumberOfSlot;
      {int} stainless_set;
      int machine_cost;
      };
      
      {machine_tuple} MachineData;

    int cycles; // number of machine cycle consider per day

    dvar int PanelAssignment[PanelData][Slot_Range][GroupData][m  in MachineData][cycles] in 0..1; // to assign the panel into each slot for each machine
    dvar int GroupAssignment[GroupData][Slot_Range][MachineData][cycles] in 0..1; // to assign the group into each slot for each machine

     

    //Objective function

    minimize the total Waste 

     

    //Constraint

    //1. Demand constraint

    //each of the work order, the demand must be satisfied within the given time interval (releasedate, duedate)

    //The PanelAssignment will assign the panel to the machine, slot, for each cycle (panel can use machine many cycles, many slots)

    sum( p in PanelData, g in GroupData, m  in MachineData,  s in m.NumberOfSlot, c in cycles, w in WorkOrder: w.partnumber == p) PanelAssignment  [p][s][g][m][c] * g.ProductionOutput >= w.Demand; // with the specified period given

    // the total PanelAssignment on the same machine, same cycle must be less than NumberOfSlot available on the machine

    // 2. Group assignment constraint

    // There is only 1 group can be assigned to the machine on the same cycle

    // The panel within the same group can be assigned to the machine on the same cycle

     

    //3. Time interval for each machine and cycle must have the same size as the panel processing time but must be within the release date and due date

     

    //4. the assignment of the stainless must be the same as in the group specify. The time interval for the stainless is the same as the time interval of the machine + CleaningTime

    //5. There is the capacity of each stainless

     

    End;

     

    I hope it is much clear now.

    Thank you very much in advance for your help.

    Chawalit

  • PhilippeLaborie
    PhilippeLaborie
    68 Posts

    Re: How to model the Batch job

    ‏2014-05-07T09:34:23Z  
    • Chawalit
    • ‏2014-05-06T14:09:53Z

     

    Dear Philippe;

    Here is the more formal mathematical ways I have for the problem.

    ​I am coming from MIP and this is my first time using CP.

    â€

    ​We have some of the data:

    tuple panel_tuple{
      key int partnumber;
      float width;
      float height;
      int processingtime;

      };

    ​{panel_tuple} PanelData;

    tuple WorkOrder_tuple{
      key int WOnumber;
      int partnumber;
      int ReleaseDate; 
      int DeliveryDate; 
      int Demand; // unit
      int processingtime; 
      };

    {WorkOrder_tuple} WorkOrderData;

     tuple stainless_tuple{
       key int stainlessindex;
       float width;
       float height;
       int capacity;

       int CleaningTime;

       };
     
    {stainless_tuple} StainlessData; 

     

    tuple group_tuple{
      key int GroupNumber;
      int layout;
      {int} panel_set; // group of the panel can be process on the same machine
      int processingtime; 
      int stainlessindex; 
       float Waste;
       int ProductionOutput; // number of production per machine slot
    };

    {group_tuple} GroupData;

    tuple machine_tuple{
      key int machinenumber;
      int NumberOfSlot;
      {int} stainless_set;
      int machine_cost;
      };
      
      {machine_tuple} MachineData;

    int cycles; // number of machine cycle consider per day

    dvar int PanelAssignment[PanelData][Slot_Range][GroupData][m  in MachineData][cycles] in 0..1; // to assign the panel into each slot for each machine
    dvar int GroupAssignment[GroupData][Slot_Range][MachineData][cycles] in 0..1; // to assign the group into each slot for each machine

     

    //Objective function

    minimize the total Waste 

     

    //Constraint

    //1. Demand constraint

    //each of the work order, the demand must be satisfied within the given time interval (releasedate, duedate)

    //The PanelAssignment will assign the panel to the machine, slot, for each cycle (panel can use machine many cycles, many slots)

    sum( p in PanelData, g in GroupData, m  in MachineData,  s in m.NumberOfSlot, c in cycles, w in WorkOrder: w.partnumber == p) PanelAssignment  [p][s][g][m][c] * g.ProductionOutput >= w.Demand; // with the specified period given

    // the total PanelAssignment on the same machine, same cycle must be less than NumberOfSlot available on the machine

    // 2. Group assignment constraint

    // There is only 1 group can be assigned to the machine on the same cycle

    // The panel within the same group can be assigned to the machine on the same cycle

     

    //3. Time interval for each machine and cycle must have the same size as the panel processing time but must be within the release date and due date

     

    //4. the assignment of the stainless must be the same as in the group specify. The time interval for the stainless is the same as the time interval of the machine + CleaningTime

    //5. There is the capacity of each stainless

     

    End;

     

    I hope it is much clear now.

    Thank you very much in advance for your help.

    Chawalit

    I think a CP model will be efficient on this problem only if you can group a set of consecutive and contiguous processing of a part of a work order on a given machine/slot. If the problem is fully elastic, that is: at any time-point/cycle you can freely decide to change the allocation of the work orders on the machine/slots (provided of course the capacity is not exceeded and the compatibility relations are satisfied), then a MIP model should be ok.

    This being said, if you cannot freely allocate the work-order on the machines/slots, typically because it would incur some cost for a machine/slot to switch too often from a given work-order to a different one  (you mentioned some cleaning times), then it could make sense to define (a priori, of after solving a relaxed or approximated MIP model) an envelope of possible time-intervals with a given minimal duration that represents the partial execution of a given work-order on a given machine/slot (in CPO, interval variables can have variable length and can be optional). The assumption here is that if a machine/slots starts to process part of a work order, it must at least process it for a minimal amount of time.

    Philippe

  • Chawalit
    Chawalit
    4 Posts

    Re: How to model the Batch job

    ‏2014-05-08T06:40:58Z  

    I think a CP model will be efficient on this problem only if you can group a set of consecutive and contiguous processing of a part of a work order on a given machine/slot. If the problem is fully elastic, that is: at any time-point/cycle you can freely decide to change the allocation of the work orders on the machine/slots (provided of course the capacity is not exceeded and the compatibility relations are satisfied), then a MIP model should be ok.

    This being said, if you cannot freely allocate the work-order on the machines/slots, typically because it would incur some cost for a machine/slot to switch too often from a given work-order to a different one  (you mentioned some cleaning times), then it could make sense to define (a priori, of after solving a relaxed or approximated MIP model) an envelope of possible time-intervals with a given minimal duration that represents the partial execution of a given work-order on a given machine/slot (in CPO, interval variables can have variable length and can be optional). The assumption here is that if a machine/slots starts to process part of a work order, it must at least process it for a minimal amount of time.

    Philippe

    Dear Phillippe;

     

    Thank you very much. 

    I am trying to get away by simply finding the time interval for each machine cycle and stainless cycle instead.

    The assignment of the Panel will use the same style as in MIP.  

     

    Chawalit