Decision Optimization

 View Only
Expand all | Collapse all

Two different jobs (one w/ overlap and the other /w noOverlap) in a same sequence

  • 1.  Two different jobs (one w/ overlap and the other /w noOverlap) in a same sequence

    Posted Thu February 11, 2021 05:18 PM
    Edited by System Fri January 20, 2023 04:48 PM

    Suppose there are two types of products: A and B. The type "A" must be scheduled, but type "B" can be optionally scheduled. The goal is to schedule as much as jobs with minimum completion time. Now, the type "A" jobs cannot be overlapped, but type "B" jobs can be overlapped among the same type "B".
    In the following illustration, job 9 was not scheduled, but the job could be scheduled by overlapping with job 10 (note both jobs 9 and 10 are type "B").
    Assume there is no way to pre-batch jobs during a pre-processing. I have tried "SPAN" method to contain multiple overlapping jobs and assigned those representing jobs to machine while still utilizing NoOverlap. This approach worked well, but when a size of problem gets bigger, the approach got slower. Is there better way to capture two different types of jobs (one allowing overlap and the other not allowing overlap) in a same sequence?

    using CP;
    tuple t_job {
    key int id;
    string ptype;
    int sz; //size
    int est; //early start time
    int let; //latest end time

    };
    {t_job} Jobs = {
    <1, "A", 20, 0, 200>,
    <2, "A", 10, 0, 200>,
    <3, "A", 30, 30, 200>,
    <4, "A", 20, 40, 100>,
    <5, "A", 10, 0, 50>,
    <6, "B", 20, 10, 100>,
    <7, "B", 20, 0, 100>,
    <8, "B", 10, 10, 100>,
    <9, "B", 20, 50, 100>,
    <10, "B", 20, 50, 100>
    };

    dvar interval itv[j in Jobs] optional (j.ptype=="B") in j.est..j.let size j.sz;
    dvar sequence seqMch in all(j in Jobs) itv[j];
    dexpr int cmax =max(j in Jobs) endOf(itv[j]);
    dexpr int cntJob=sum(j in Jobs) presenceOf(itv[j]);

    maximize staticLex(cntJob,-cmax);
    subject to {
    noOverlap(seqMch);
    }

    I made it work with the following codes by utilizing duplicated sequence. However, this method is still not fast for a large-scale problem. Is there better way?

    range copies = 0..1;
    dvar interval itv[j in Jobs][copies] optional in j.est..j.let size j.sz;
    dvar sequence seqMch[c in copies] in all(j in Jobs) itv[j][c];
    dexpr int cmax =max(j in Jobs,c in copies) endOf(itv[j][c]);
    dexpr int cntJob=sum(j in Jobs,c in copies) presenceOf(itv[j][c]);

    maximize staticLex(cntJob,-cmax);
    subject to {
    forall(c in copies)
    noOverlap(seqMch[c]);

    forall (j in Jobs:j.ptype=="B")
    sum(c in copies) presenceOf(itv[j][c]) <= 1;

    }


    #DecisionOptimization


  • 2.  RE: Two different jobs (one w/ overlap and the other /w noOverlap) in a same sequence
    Best Answer

    Posted Thu February 18, 2021 11:56 AM
    Hi,
    those type of compatibility constraints are better handled with state functions.
    Additionally, as a redundant constraint, noOverlap on the A tasks could add a bit more propagation.

    For example, with your specific data:
    dvar interval itv[j in Jobs] optional (j.ptype=="B") in j.est..j.let size j.sz;
    stateFunction f;
    dexpr int cmax  = max(j in Jobs) endOf(itv[j]);
    dexpr int cntJob = sum(j in Jobs) presenceOf(itv[j]);
    maximize staticLex(cntJob,-cmax);
    subject to {
      forall(j in Jobs) {
        if (j.ptype=="A") alwaysEqual(f,itv[j],j.id);
        if (j.ptype=="B") alwaysEqual(f,itv[j],0);
       }
       noOverlap(all(j in Jobs: j.ptype=="A") itv[j]); // Redundant
    }
    




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