Decision Optimization

 View Only
  • 1.  cumulative work-hour limitation

    Posted Wed June 08, 2022 01:50 PM

    Suppose the cumulative processing time of each machine must be no more than 10 h within any consecutive 24 h in a job shop environment. For illustration, I ran the example model (sched_job_shop). For example, machine 0 is cumulating 15 h work at time 26, violating the cumulative work-hour limitation. Similarly, machine 1 is cumulating 22 h work at time 23. I am familiar with CP cumFunction, but I could not figure out how to model this problem. Would you please help me? Thanks!

    m  j  s  e  sz cumSz
    0 1 3 11 8 8
    0 2 19 26 7 15
    0 5 26 30 4 19
    0 4 32 35 3 22
    0 0 35 36 1 23
    0 3 36 45 9 32
    1 1 0 3 3 3
    1 4 3 9 6 9
    1 2 10 19 9 18
    1 3 19 20 1 19
    1 0 20 23 3 22
    1 5 35 37 2 24



    ------------------------------
    Andy Ham
    ------------------------------



  • 2.  RE: cumulative work-hour limitation

    Posted Fri June 10, 2022 12:12 PM
    Hello Andy,
    an idea is to introduce an interval of length 24 starting at the start of each task A, and then enforce that over this interval, there is no more than 10 hours used. You can use overlapLength to get the length of the overlapping between this new interval and another task. Then by summing the length of the task A and the overlapping lengths of all the other tasks sharing the same resource, you have the usage of the resource on this 24h interval.
    Modifying the sched_openshop.cpp example we get the code below.
    Regards


    #include <ilcp/cp.h>
    
    #define WINDOW 24
    #define LIMIT 10
    
    class FileError: public IloException {
    public:
      FileError() : IloException("Cannot open data file") {}
    };
    
    int main(int argc, const char* argv[]) {
      IloEnv env;
      try {
        const char* filename = "../../../examples/data/jobshop_default.data";
        if (argc > 1)
          filename = argv[1];
        std::ifstream file(filename);
        if (!file) {
          env.out() << "usage: " << argv[0] << " <file>" << std::endl;
          throw FileError();
        }
    
        IloModel model(env);
        IloInt nbJobs, nbMachines;
        file >> nbJobs;
        file >> nbMachines;
        IloIntervalVarArray2 machines(env, nbMachines);
        for (IloInt j = 0; j < nbMachines; j++)
          machines[j] = IloIntervalVarArray(env);
        IloIntExprArray ends(env);
        IloInt totald = 0;
        for (IloInt i = 0; i < nbJobs; i++) {
          IloIntervalVar prec;
          for (IloInt j = 0; j < nbMachines; j++) {
            IloInt m, d;
            file >> m;
            file >> d;
            totald += d;
            IloIntervalVar ti(env, d);
            machines[m].add(ti);
            if (0 != prec.getImpl())
              model.add(IloEndBeforeStart(env, prec, ti));
            prec = ti;
          }
          ends.add(IloEndOf(prec));
        }
        for (IloInt j = 0; j < nbMachines; j++)
          model.add(IloNoOverlap(env, machines[j]));
    
        IloObjective objective = IloMinimize(env, IloMax(ends));
        model.add(objective);
    
        // Sliding window energy limit
        for (IloInt m = 0; m < nbMachines; m++) {
          for (IloInt t = 0; t < machines[m].getSize(); t++) {
            IloIntervalVar itv = machines[m][t];
            IloIntervalVar shadow(env, WINDOW);
            model.add(IloStartAtStart(env, shadow, itv));
            IloIntExpr over(env, 0);
            for (IloInt other = 0; other < machines[m].getSize(); other++) {
              if (other != t) {
                over += IloOverlapLength(env, machines[m][other], shadow);
              }
            }
            model.add(IloLengthOf(itv) + over <= LIMIT);
          }
        }
    
        IloCP cp(model);
        cp.out() << "Instance \t: " << filename << std::endl;
        cp.out() << "Total duration \t: " << totald << std::endl;
        if (cp.solve()) {
          cp.out() << "Makespan \t: " << cp.getObjValue() << std::endl;
          IloInt ms = (IloInt)cp.getObjValue();
    
          // Check energy limit
          for (IloInt m = 0; m < nbMachines; m++) {
            cp.out() << "Machine " << m << std::endl;
            IloIntArray igral(env, ms);
            for (IloInt k = 0; k < ms; k++)
              igral[k] = 0;
            for (IloInt t = 0; t < machines[m].getSize(); t++) {
              IloIntervalVar itv = machines[m][t];
              IloInt s = cp.getStart(itv);
              IloInt e = cp.getEnd(itv);
              for (IloInt k = s; k < e; k++)
                igral[k] += k - s + 1;
              for (IloInt k = e; k < ms; k++)
                igral[k] += (e - s);
            }
            for (IloInt k = WINDOW; k < ms; k++) {
              if (igral[k] - igral[k-WINDOW] > LIMIT) {
                cp.out() << "VIOLATION on machine " << m << " in window [" << k - 24 << ", " << k << ")" << std::endl;
              }
            }
            igral.end();
          }
        }
        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: cumulative work-hour limitation

    Posted Tue June 14, 2022 02:12 PM

    Thanks! I could not come up with this method. It works well. One issue I noticed is the scalability. It became very slow for large scale problem.



    ------------------------------
    Andy Ham
    ------------------------------



  • 4.  RE: cumulative work-hour limitation

    Posted Mon June 13, 2022 10:14 AM
    Hy Andy

    Olivier proposal is the most generic way. If your problem is not too complicated, you can some other but more efficient modélisation.

    A first idea only requires that the shop works continuously during 10 hours shifts


    In such a case add to each job a (24-10) interval variable bounds to belongs to each [0, 24) segment that will exclude from the resources the operations.



    To remove the shift hypothesis another way is to constraint the operation to not use more than (10/24) capacity of the resources in a homogenous way. that is to apply a temporal dilation factor 10/24


    • define an efficiency flat function (constant 10/24 function).
    • The processing time of each interval is subject to this efficiency.
    • Any delay (transition delay, delay of precedences, earllness tardiness function )  length (alwaysXXX, setup constraint) are reduced by the dilation

    Once you have solve this model, apply the inverse dilation.

    Hope that helps


    ------------------------------
    Jerome Rogerie
    ------------------------------



  • 5.  RE: cumulative work-hour limitation

    Posted Mon June 13, 2022 10:24 AM
    Hi Andy,

    There is two "bugs" in my proposal. In case of continuous shift you may add between forbidden processing interval precedence startBeforeEnd(rp_i, rp_{I+1}, 16) to relax the condition shift in same day which is wrong on my onion.

    About the dilation base model, my wording was not clear. replace the sentence:
    • "Any delay (transition delay, delay of precedences, earllness tardiness function )  length (alwaysXXX, setup constraint) are reduced by the dilation"
    • by 
    • "Any delay (transition delay, delay of precedences, earllness tardiness function )  length (alwaysXXX, setup constraint) are increase by a factor 20/14"


    ------------------------------
    Jerome Rogerie
    ------------------------------



  • 6.  RE: cumulative work-hour limitation

    Posted Tue June 14, 2022 02:19 PM
    Thanks for all your feedbacks. For the large scale problem, I need to do something similar to what you are suggesting. But, for now, I could not grasp your idea. I will spend more time in meditating your feedback :)

    ------------------------------
    Andy Ham
    ------------------------------