Originally posted by: SatishKumarA

Hi All,

I am trying to solve a scheduling problem where one resource can process multiple jobs at a time. Suppose I have six jobs say 1,2,3,4,5 and 6 with different processing times 10,20,30,40,50 and 60 respectively and two machines 1 and 2 that can process maximum two jobs at a time. Condition is that if two jobs say 1 and 2 are loaded on machine 1 , then the start time for both the jobs should be same but the end times can be different. This requirement I could model. But another requirement that I could not model is that, machine 1 cannot be loaded until both the jobs are completed. For example, m1 started processing jobs 1 and 2  at t=0, the machine will be free only after t=20. Job 3 to job 6 can be loaded on machine 1 only after t=20.

In attached screenshot, job1 and Job 2are scheduled on machine 1, job 3 and 5 are scheduled on machine 2, job4 and job 6 are scheduled on machine 2 again.

Ideally, machine 2 will be free only after job 5 is completed at t=50. So, Job 6 should be loaded on machine 6 only after t=50 along with job 4 which I could not model.

Please help me on this specific problem.

Thanks,

Satish

Originally posted by: SatishKumarA

Hi All,
Please find the sample code attached. I defined a master task that will overlap with two slave tasks that are processed in parallel. 
Start time of master task and both slave tasks will be same,whereas end time of master task will be maximum of end time of both slave tasks.
However, this logic is not able to produce the desired result.
Please check the code and let me know what I missed. 


using CP;

int No_of_Tyres = 6;
int No_of_TMBs = 2;
range TyresList = 1..No_of_Tyres;
range TBMList = 1..No_of_TMBs;

{int} Tyres = {1,2,3,4,5,6};
{int} TBM = {1,2};

int Tyre_Type[TyresList] = [1,1,2,2,2,2];
int TBM_Capacity[TBMList] = [2,2];

 /* Tasks that can be processed at a time on a TBM with capacity 2 */
tuple ParallelTasks1 {
   int t1;
   int t2;
};

{ParallelTasks1} ParallelTasks = {
    <1, 2>, <3, 4>, <3,5>, <3,6>,
    <4, 5>, <4, 6> , <5,6>};
        
dvar interval tb_task[t1 in Tyres, t2 in TBM] optional in 0..1000 size 10*t1;

cumulFunction tbmUsage[t2 in TBM] = sum(t1 in Tyres) pulse(tb_task[t1][t2], 1);

dvar interval tyre_task[t1 in Tyres] in 0..1000 size 10*t1;

dvar interval master_tyre_task[t2 in TBM,p in ParallelTasks] optional in 0..1000 size 0..1000;

dvar sequence all_master_sequences[t2 in TBM,t in Tyres] in 
                                append(all(p in ParallelTasks:t!=p.t1 && t!=p.t2) master_tyre_task[t2][p],
                                                all(t1 in Tyres:t==t1) tb_task[t1][t2])
                                ;

execute {
   cp.param.timeLimit =5;
 }   

minimize max(t1 in Tyres, t2 in TBM) endOf(tb_task[t1][t2]) 

subject to {

  forall(t2 in TBM)
    tbmUsage[t2] <= TBM_Capacity[t2];  
 
  forall(t1 in Tyres) 
    alternative(tyre_task[t1], all (t2 in TBM) tb_task[t1][t2]);

        forall(p in ParallelTasks){
          sum(t2 in TBM) presenceOf(master_tyre_task[t2][p]) == 1;}

  forall(t2 in TBM,p in ParallelTasks)  {  
   ct3: presenceOf(tb_task[p.t1][t2])==1 && presenceOf(tb_task[p.t2][t2])==1 &&
   startOf(tb_task[p.t1][t2])==startOf(tb_task[p.t2][t2])
   => presenceOf(master_tyre_task[t2][p]) == 1 ;
   ct3_1: presenceOf(tb_task[p.t1][t2])==0 && presenceOf(tb_task[p.t2][t2])==1 => presenceOf(master_tyre_task[t2][p]) == 0;
   ct3_2: presenceOf(tb_task[p.t1][t2])==1 && presenceOf(tb_task[p.t2][t2])==0 => presenceOf(master_tyre_task[t2][p]) == 0; 
        
        ;}
 
   forall(t2 in TBM,t in Tyres)
        ct11: noOverlap(all_master_sequences[t2][t]);
   
}

Thanks,

Satish

Originally posted by: GGR

Hi Satish

For the first question, I suggest you have a look to state function. Those variable are able to synchronize interval variable that constrains it.

stateFunction s; //state aspect for a machine
/*..*/
subject to {
/*..*/
forall(i in ...) // map of the interval that are executed on s
  alwaysEqual(s, i, 0, true, false);
  /*..*/
}

Any interval sharing some time on the resource will start at the same date (case 1 and 2). Moreover, an intervarl that cannot start at this common date cannot share the resource whci answers your second question.

Hope that helps

Originally posted by: SatishKumarA

Hi GGR,

Thanks for the answer. it worked. I removed the complex equations I tried by this simple function you suggested. It makes the model simple.

Thanks,

Satish