Decision Optimization

Expand all | Collapse all

Reducing Transition time as cost in parallel sequencing problem

  • 1.  Reducing Transition time as cost in parallel sequencing problem

    Posted Thu August 26, 2021 09:30 AM
    Edited by Avinash Kumar Fri August 27, 2021 07:12 AM
    Is there a way to include the total transition time in the cost function?
    My objective is to reduce transition time irrespective of how long it takes to execute tasks by a worker. So if a worker takes even a week to execute the tasks in 0 transition time, then all the work should be allocated to him.

    Earlier I tried to reduce the total time span of all the intervals (which in turn should have reduced the transition time) but it didn't give the exact solution which I am looking for. I added up the time span from all the workers.

    I am working in Python. Any advice will be helpful.

    ------------------------------
    Avinash Kumar
    ------------------------------


    Edit: Hi I have solved it in Python now.

    The thing which I changed was the cost function.
    Earlier I was trying to reduce the overall end time (the length of the span which consisted of all the tasks). Now, I am trying to reduce the sum of the length of all the spans where each span is all the tasks that can be executed on a machine.


  • 2.  RE: Reducing Transition time as cost in parallel sequencing problem

    Posted Thu August 26, 2021 10:50 AM
    Hello,
    so you want to minimize the sum of the setup times for all the workers?
    You can set the objective to be an expression summing the transition times for all the workers for all their tasks.
    For example, for 2 workers (in C++, sorry, quicker for me):
    #include <ilcp/cp.h>
    
    IloInt NbTypes = 5;
    
    IloInt SetupM1[] = {
      22, 24,  7, 10, 9, 
      63, 21, 42,  1, 24, 
      60, 70, 37, 70, 39, 
      77, 57, 65, 33, 81, 
      51, 31, 18, 32, 48
    };
    
    IloInt SetupM2[] = {
      27, 48, 44, 0, 21,
      42, 44, 42, 40, 17, 
      36, 53, 31, 56, 50, 
      6, 43, 46, 38, 16, 
      25, 27, 45, 67, 37
    };
    
    IloInt NbTasks = 10;
    
    IloInt TaskDur[] = {
      19, 18, 16, 11, 16, 15, 19, 18, 17, 17
    };
    
    IloInt TaskType[] = {
      3,  1,  1,  3,  4,  2,  0,  4,  3,  0
    };
    
    int main(int, const char*[]) {
      IloEnv env;
      try {
        IloModel model(env);
        IloTransitionDistance setup1(env, NbTypes);
        IloTransitionDistance setup2(env, NbTypes);
        for (IloInt i = 0; i < NbTypes; ++i) {
          for (IloInt j = 0; j < NbTypes; ++j) {
            setup1.setValue(i, j, SetupM1[NbTypes*i+j]);
            setup2.setValue(i, j, SetupM2[NbTypes*i+j]);
          }
        }
        IloIntArray tp(env, NbTasks);
        IloIntervalVarArray a (env, NbTasks);
        IloIntervalVarArray a1(env, NbTasks);
        IloIntervalVarArray a2(env, NbTasks);
        char name[100];
        for (IloInt i = 0; i < NbTasks; ++i) {
          IloInt type = TaskType[i];
          IloInt d    = TaskDur [i];
          tp[i] = type;
          sprintf(name, "A%ld_TP%ld", (long)i, (long)type);
          a[i] = IloIntervalVar(env, d, name);
          IloIntervalVarArray alt(env, 2);
          sprintf(name, "A%ld_M1_TP%ld", (long)i, (long)type);
          a1[i] = IloIntervalVar(env, name);
          a1[i].setOptional();
          alt[0] = a1[i];
          sprintf(name, "A%ld_M2_TP%ld", (long)i, (long)type);
          a2[i] = IloIntervalVar(env, name);
          a2[i].setOptional();
          alt[1] = a2[i];
          model.add(IloAlternative(env, a[i], alt));
        }
    
        IloIntervalSequenceVar s1(env, a1, tp);
        IloIntervalSequenceVar s2(env, a2, tp);
        model.add(IloNoOverlap(env, s1, setup1, IloTrue));
        model.add(IloNoOverlap(env, s2, setup2, IloTrue));
    
        IloIntExpr setupsSum(env);
        for (IloInt i = 0; i < NbTasks; ++i) {
          IloInt tpi = TaskType[i];
          IloIntArray setup1Array(env, NbTypes+1);
          IloIntArray setup2Array(env, NbTypes+1);
          for (IloInt j = 0; j < NbTypes; ++j) {
            setup1Array[j] = SetupM1[NbTypes*tpi+j];
            setup2Array[j] = SetupM2[NbTypes*tpi+j];
          }
          setup1Array[NbTypes] = 0; // Last on resource or resource not selected
          setup2Array[NbTypes] = 0; // Last on resource or resource not selected
          setupsSum += setup1Array[IloTypeOfNext(s1, a1[i], NbTypes, NbTypes)];
          setupsSum += setup2Array[IloTypeOfNext(s2, a2[i], NbTypes, NbTypes)];
        }
        IloObjective objective = IloMinimize(env, setupsSum);
        model.add(objective);
    
        IloCP cp(model);
    
        cp.setParameter(IloCP::LogPeriod, 10000);
        cp.setParameter(IloCP::TimeLimit, 2);
    
        if (cp.solve()) {
          cp.out() << "Worker 1: " << std::endl;
          IloIntervalVar act;
          for (act = cp.getFirst(s1); act.getImpl() != 0; act = cp.getNext(s1, act))
            cp.out() << cp.domain(act) << std::endl;
          cp.out() << "Worker 2: " << std::endl;
          for (act = cp.getFirst(s2); act.getImpl() != 0; act = cp.getNext(s2, act))
            cp.out() << cp.domain(act) << std::endl;
          cp.out() << "Sum of transition times \t: " << cp.getObjValue() << std::endl;
        }
        else {
          cp.out() << "No solution found."  << std::endl;
        }
        cp.end();
      }
      catch (IloException& ex) {
        env.out() << "Caught: " << ex << std::endl;
      }
      env.end();
      return 0;
    }​

    It gives:

     ! ----------------------------------------------------------------------------
     ! Search terminated by limit, 11 solutions found.
     ! Best objective           : 91 (gap is 100.0%)
     ! Best bound               : 0
     ! ----------------------------------------------------------------------------
     ! Number of branches       : 619750
     ! Number of fails          : 296263
     ! Total memory usage       : 6.2 MB (6.1 MB CP Optimizer + 0.1 MB Concert)
     ! Time spent in solve      : 2.03s (2.02s engine + 0.01s extraction)
     ! Search speed (br. / s)   : 306958.9
     ! ----------------------------------------------------------------------------
    Worker 1:
    A2_M1_TP1[1: 0 -- 16 --> 16]
    A1_M1_TP1[1: 37 -- 18 --> 55]
    A4_M1_TP4[1: 79 -- 16 --> 95]
    A5_M1_TP2[1: 113 -- 15 --> 128]
    Worker 2:
    A3_M2_TP3[1: 0 -- 11 --> 11]
    A9_M2_TP0[1: 17 -- 17 --> 34]
    A0_M2_TP3[1: 34 -- 19 --> 53]
    A6_M2_TP0[1: 59 -- 19 --> 78]
    A8_M2_TP3[1: 78 -- 17 --> 95]
    A7_M2_TP4[1: 111 -- 18 --> 129]
    Sum of transition times         : 91

    Regards,
    ol



    ------------------------------
    Olivier Lhomme
    ------------------------------