Decision Optimization

 View Only
  • 1.  Using Docplex CP and Python

    Posted Tue January 07, 2025 12:05 AM

    I am building a production scheduling application. I have a number of production resources, and for each I have modelled a sequence_var with a transition matrices for each.

    These are "working" but I need to improve the solution, as too many transitions occur for the resource. If I let the solver run for a long time (eg 20 minutes) the solution improves, ie activities are scheduled "better" by improved grouping to reduce the number of transitions.
    How can I improve the model to reduce transitions. I have considered calculating total transition time (but don't know how) and using the objective to minimise transition time. Any suggestions on how to calculate transition time?

    Any other suggestions to improve "performance" of sequence vars? Can I try search phases or variable priorities with sequence_vars?

    Any other suggestion would be GREATLY appreciated

     

    Thanks  

     

    Ross Dye

     

     



  • 2.  RE: Using Docplex CP and Python

    Posted 28 days ago

    Hello,

    it suffices to add an objective to minimize the sum of the transition tasks lengths. 
    First, create an intervalVar associated with each transition. 
    Then add a constraint to set the length of this interval. This is the tricky part as it depends on the two tasks around it. 
    Also the case of the last task has to be handled, what can be done by introducing a fake type 0.
    You get:

    #include <ilcp/cp.h>
    
    IloInt NbTypes = 3; // real types are in [1..NbTypes-1], the additional type 0 is used for handling the last task
    
    IloInt Distances[] = {
      0, 0, 0,
      0, 0, 22,  
      0, 20, 20
    };
    
    
    IloInt NbTasks = 2;
    
    IloInt TaskDur[] = {
      3, 5
    };
    
    IloInt TaskType[] = {
      1,  2
    };
    
    IloInt StartMin[] = {
      10,  20
    };
    
    IloInt EndMax[] = {
      50,  1000
    };
    
    int main(int, const char*[]) {
      IloEnv env;
      try {
        IloModel model(env);
        IloTransitionDistance distances(env, NbTypes);
        for (IloInt i = 0; i < NbTypes; ++i) {
          for (IloInt j = 0; j < NbTypes; ++j) {
            distances.setValue(i, j, Distances[NbTypes*i+j]);
          }
        }
        
        IloIntArray distancesArray(env, NbTypes*NbTypes);
        for (IloInt i = 0; i < NbTypes; ++i) {
          for (IloInt j = 0; j < NbTypes; ++j) {
            distancesArray[i*NbTypes+j]= Distances[NbTypes*i+j];
          }
        }   
        IloIntArray tp(env, NbTasks);
        IloIntervalVarArray tasks(env, NbTasks);
        IloIntervalVarArray cleanupTasks(env, NbTasks);
        IloIntervalVarArray alltasks(env);
        IloIntExprArray transitionLengths(env);
        
        char name[100];
        for (IloInt i = 0; i < NbTasks; ++i) {
          IloInt type = TaskType[i];
          IloInt d    = TaskDur[i];
          tp[i] = type;
          sprintf(name, "tasks%ld_TP%ld", (long)i, (long)type);
          tasks[i] = IloIntervalVar(env, d, name);
          tasks[i].setStartMin(StartMin[i]);
          tasks[i].setEndMax(EndMax[i]);
          sprintf(name, "cleanup-%ld", (long)i);
          cleanupTasks[i] = IloIntervalVar(env, name);
          model.add(IloStartAtEnd(env, cleanupTasks[i], tasks[i]));
          alltasks.add(tasks[i]);
          alltasks.add(cleanupTasks[i]);
          transitionLengths.add(IloLengthOf(cleanupTasks[i]));
        }
           
        IloIntervalSequenceVar s1(env, tasks, tp);
        model.add(IloNoOverlap(env, s1, distances, IloTrue));
        
        IloIntervalSequenceVar s2(env, alltasks);
        model.add(IloNoOverlap(env, s2));
        for (IloInt i = 0; i < NbTasks; ++i) {
          model.add(IloLengthOf(cleanupTasks[i]) == distancesArray[NbTypes*tp[i]  + IloTypeOfNext(s1, tasks[i], 0)]);
        }
        model.add(IloMinimize(env, IloSum(transitionLengths)));
    
        IloCP cp(model);
        if (cp.solve()) {
          IloIntervalVar act;
          for (act = cp.getFirst(s2); act.getImpl() != 0; act = cp.getNext(s2, act))
            cp.out() << cp.domain(act) << 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;
    }


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



  • 3.  RE: Using Docplex CP and Python

    Posted 28 days ago

    Thanks Olivier
    I am using Docplex CP with Python
    Would it be possible to give Python equivalent??
    Thanks

     

     

    Ross Dye

    0400669880

     






  • 4.  RE: Using Docplex CP and Python

    Posted 28 days ago

    I am not fluent in Python, but if you do a translation I would be happy to see it!



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



  • 5.  RE: Using Docplex CP and Python

    Posted 28 days ago

    Hi Olivier
    and I'm not fluent in C++ ! ! 
    Could you simply describe the methodology please, then I will implement it in my code.

    You say you are creating "an intervalVar associated with each transition". Do you mean:

    a) one for every gap between production activities (intervalVar), or

    b) one where there is a transition created by the transition matrix between intervalVars with different types

    Thanks

    Ross



    ------------------------------
    Ross Dye
    ------------------------------



  • 6.  RE: Using Docplex CP and Python

    Posted 23 days ago

    Hello,

    the idea is to add a new interval, cleanupTasks[i] following each intervalVar tasks[i] in the sequence var associated with the resource. Then the length of cleanupTasks[i] is constrained to be the transition time between tasks[i] and the next task in the sequence, or to be 0 if tasks[i] is the last task of the sequence. 



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



  • 7.  RE: Using Docplex CP and Python

    Posted 16 days ago

    It sounds like you're working on a complex scheduling problem. Here are some simple ideas to help reduce transitions and make your model work better:

    1. Minimize Transition Time:
      You can calculate the total transition time by adding up the transition times between all activities in the sequence. Use this as part of your objective, telling the solver to focus on reducing it.

    2. Group Similar Activities:
      Encourage the solver to schedule similar activities together to avoid too many transitions. You can add constraints or priorities to make this happen.

    3. Set Search Phases:
      Use search phases to focus the solver on certain variables or parts of the solution first. For example, prioritize reducing transitions before optimizing other parts.

    4. Use Variable Priorities:
      Assign higher priorities to the sequence variables where transitions matter most. This helps the solver focus on the critical parts of the schedule.

    5. Experiment with Solver Settings:
      Try changing solver parameters like the time limit, branching strategy, or relaxation settings. Small tweaks can sometimes make a big difference.

    6. Test Different Objectives:
      If reducing transition time is key, make it the primary objective. You can still include other goals, but keep this one as the main focus.



    ------------------------------
    Denta Ku
    ------------------------------