Originally posted by: andrea.taverna

Hello everyone,

I have started using OPL script for solving a scheduling problem. I have experience with MP with CPLEX + GAMS/AMPL/SCIP...but I have just had some exposure to CP with OR/tools and gecode for a summer school during the PhD a couple of years ago.

I am a bit confused on how to model the following problem

A set of jobs J is given. Each job j as one or more phases k_j. To be completed, the phases of each job have to be completed in order. There are earliest starting time for the whole job. Each phase has a duration, measured in equivalent man-hours and a minimum and maximum number of allowed operators working on it.

A set of internal workers  is given. For each time period t in T, which corresponds to a 4 hour time slot, a worker has an "effort", expressed as a number of equivalent work-hours. The effort can be 0, to mean the worker is absent, 4, to mean the worker completes 4 man-hours of equivalent work, and 5, to represent 1 additional hour of over time.

The company can also employ external workers, which have an effort of 4 hours. They are not identified. WHat we want to know is how many external workers are used in each period for each phase.

Every worker, internal or external, can change his task at every time period. So worker o can be assigned to phase k_j at time t and to phase k'_j' at time t+1

The main goal is reducing the employment of external workers.

After some iterations, I wrote this model:

1. each phase is an interval. There are startBeforeStart, endBeforeStart and similar constraints to impose an ordering on the phases
2. to represent the choice of assigning an internal worker o to a phase k_j at a given period t I declared an optional interval int_worker[<o,j,k,t>] in t..t+1
3. I did the same for external workers.
4. for each phase I defined a cumulFunction (stepAtStaet) that counts the amount of work hours performed by each worker (stepAtStart(int_worker[<o,j,k,t>], e[<o,t>]) where e is the "efficiency"
5. same for the amount of operators for the phase in each time slot: a cumulFunction (pulse) for each worker, phase and period that increases by 1 when the worker starts the slot (at time t) and decreases when it ends it (at time t+1)
6. Then I put a span constraint that states that a phase needs to span the set of its assigned workers, and then I'll need an alternative constraints (for the internal workers only), that states for each internal worker in each period only one interval has to be present.

Here is a simplified sketch:

{int} ExtOperators = asSet(1..max(<j,k> in Jobs2Phase) PhaseData[<j,k>].max_operators);

/* for each time period have 1.. PhaseData[<j,k>].max_operators ids to assign to phase k of job j*/
{extopSlot} ExtOperatorsSlots = {<o,j,k,t>| ...}

tuple opSlot  {
  string operator;
  string job;
  string type;
  string phase;
  int t;
};

/* time periods in which worker o can be assigned to phase k of job j*/
{opSlot} OperatorsSlots = {<o,j,k,t>};

/*
 * Variables
 */

dvar interval phase[<j,k> in Jobs2Phase];
dvar interval int_worker[<o,j,k,t> in OperatorsSlots] optional in t..t+1;
dvar interval ext_worker[<o,j,k,t> in ExtOperatorsSlots] optional in t..t+1;

/* OperatorEffort[<o,t>] is either 4 hours (base) or 5 hours (+1 overtime) */
cumulFunction internalEffort[<j,k> in Jobs2Phase] =
  sum (o in Operators, t in Time: <o,j,k,t> in OperatorsSlots) stepAtStart(int_worker[<o,j,k,t>], OperatorEffort[<o,t>]);

cumulFunction internalOperators[<j,k> in Jobs2Phase][t in Time] =
  sum (o in Operators: <o,j,k,t> in OperatorsSlots) pulse(int_worker[<o,j,k,t>],1);

cumulFunction externalEffort[<j,k> in Jobs2Phase] =
  /* BaseEffort = 4 hours*/
  sum(o in ExtOperators, t in Time : <o,j,k,t> in ExtOperatorsSlots) stepAtStart(ext_worker[<o,j,k,t>], BaseEffort);

cumulFunction externalOperators[<j,k> in Jobs2Phase][t in Time] =
  sum(o in ExtOperators, t in Time : <o,j,k,t> in ExtOperatorsSlots) pulse(ext_worker[<o,j,k,t>],1);


/*
 *  Objectives
 *
 *
 */
...

/*
 * Constraints
 */
subject to {
        forall(<j,k> in Jobs2Phase) {
        CompleteAll: internalEffort[<j,k>] + externalEffort[<j,k>] >=  PhaseData[<j,k>].processing_time;
        };

        forall(<j,k> in Jobs2Phase, t in Time) {
        MinOperators: internalOperators[<j,k>][t] + externalOperators[<j,k>][t] >=  PhaseData[<j,k>].min_operators;
        };
        
        forall(<j,k> in Jobs2Phase, t in Time) {
        MaxOperators: internalOperators[<j,k>][t] + externalOperators[<j,k>][t] <=  PhaseData[<j,k>].max_operators;
        };

        forall(<o,j,k,t> in ExtOperatorsSlots: o < last(ExtOperators)) {
        Sort: presenceOf(ext_worker[<o,j,k,t>]) >= presenceOf(ext_worker[<o+1,j,k,t>]);
        };
        
        forall(<j,k> in Jobs2Phase) {
        Synch:  span(phase[<j,k>],
                     append( (all(o in Operators, t in Time : <o,j,k,t> in OperatorsSlots) int_worker[<o,j,k,t>]),
                             (all(o in ExtOperators, t in Time : <o,j,k,t> in ExtOperatorsSlots) ext_worker[<o,j,k,t>])));
        };

    // Order phases for each job        
        forall(<j,k> in Jobs2Phase : ord(Phases,k) >= 1) {
        PhaseStart: startBeforeStart(phase[<j,prev(Phases,k)>],phase[<j,k>],PhaseData[<j,k>].start_delay);
        };

        forall(<j,k> in Jobs2Phase : ord(Phases,k) >= 1) {
        PhaseEnd: endBeforeEnd(phase[<j,prev(Phases,k)>],phase[<j,k>],PhaseData[<j,k>].end_delay);
        };

        forall(<j,k> in Jobs2Phase : ord(Phases,k) >= 1) {
        PhaseConsist: endBeforeStart(phase[<j,prev(Phases,k)>], phase[<j,k>], PhaseData[<j,k>].inter_delay);
        };

        forall(j in Jobs) {
        StartRelease: forbidStart(phase[<j,first(Phases)>], afterRelease[j]);
        };

  };

It currently does not work, as it returns infeasibility. I wrote a MP model before, with the same data, which did work, hence I think the data is correct, but the model isn't. 

Before venturing further, however, I would like to have some suggestions. Is my approach correct? Am I missing something obvious?

TIA

Originally posted by: rdumeur

Dear Andrea,

Having the data to test your model may help to see infeasibility (or you can use the conflictRefiner).

At first sight  you could model each job phase using the alternative constraint:

https://www.ibm.com/support/knowledgecenter/SSSA5P_12.7.0/ilog.odms.ide.help/refcppopl/html/constraints_groups.html

using :

alternative(phase[<j,k>], worker[<o,j,k>], num_workers[j])

where:

  - phase[<j,k>] is the interval representing phase k of job j.

  - num_workers[j] argument is a variable whose domain constrain the number of worker simultaneously active during a phase of job j.

  - worker[<o,j,k>] are optional intervals denoting the presence of any worker o in phase k of job j (including both internal and external workers).

I understand that in your model, each job has a fixed number of phase which must be all executed. So your problem is to allocate workers so that the number of jobs performed in parallel is maximized, right?

I hope this helps,

            Renaud

Originally posted by: andrea.taverna

Dear Renaud,

thanks for your answer. Unfortunately, I see a problem with your suggestion.

In my case a solution consists of a worker-phase-time period assignment such that:

1. workers are assigned to compatible phases in time periods when they are available
2. phases are completed, i.e. total effort== size, in the proper order, and in each period t the number of assigned operators to each phase is between the phase's respective min and max
3. workers can change phases at each period. Hence, if a worker is assigned to a phase at t, it can then change to another at time t+1.

The alternative constraint you suggest would enforce choosing at most num_workers for the whole phase, preventing them to change phases from one time to another.

As for the feasibility problem, I agree with you. I should check the data. I want to verify the following at least, that the span constraint enforces that a phase has to span the set of assigned workers. Could you tell me whether I used it right?

thanks.

Originally posted by: PhilippeLaborie

Hello Andrea,

General comments

My first comment is that one of the main advantages of Constraint-Based scheduling is to avoid, when possible, the enumeration of time because some continuity condition has to be enforced during the execution of the tasks (for instance the same worker is used). Here, as you can change worker allocation at each time-point (I'm assuming time granularity is 4h), you need to model a decision at each time-point, so it is not clear that a CP model will be better than a MIP model.

Comments on your model

If I understand it well, your model is very close to a MIP model because you have a boolean decision for each tuple <time value, operator, task>. Of course it depends on the size of the problem but it could lead to a very large model with poor propagation.

Now I think the reason why it is infeasible is because of these type of constraints:

cumulFunction internalOperators[<j,k> in Jobs2Phase][t in Time] =
  sum (o in Operators: <o,j,k,t> in OperatorsSlots) pulse(int_worker[<o,j,k,t>],1);

forall(<j,k> in Jobs2Phase, t in Time) {
        internalOperators[<j,k>][t] + externalOperators[<j,k>][t] >= PhaseData[<j,k>].min_operators;
};

Of course,  as Renaud said, you could use the conflict refiner to validate this hypothesis. 

The constraints above state that the cumul functions are "everywhere" (for each time value) greater than a non-negative value. But here, for a given t, you have a set of cumul functions xxxOperators[<j,k>][t] that have a value 0 "everywhere" except at time value 't'. So they cannot satisfy the minimal value at times other than 't'. In fact here as you are considering the total worker usage at a given time 't', you should not use a cumul function but just a scalar (similarly to the corresponding MIP model): a sum over the presenceOf(x) of the interval variables x representing the allocation of a worker on the task at time 't'. As said above, I'm not sure of the advantages of modeling this in CP compared to a MIP.

A possible alternative model

This being said, there is an alternative way for modeling the problem that takes (slightly) more into account the advantages of CP. You could define for each phase <j,k> a set of contiguous interval variables of size 4h that represent the working time of workers *relative to the phase interval*, meaning that the first of these intervals would represent the first 4h period when the phase is started. Given your min/max number of workers and the man-hours required by the phase, I suppose you can compute a min/max duration DMIN,DMAX for the task in terms of 4h time slots. So the first DMIN intervals would be present, the other DMAX-DMIN intervals would be optional. They contiguous intervals would be linked with endAtStart(itv_i,itv_{i+1}) and presenceOf(itv_{i+1})=>presenceOf(itv_i). The phase interval would span these internal itv's.
Then each worker candidate to work for an interval itv_i would have an optional interval var and you would post an alternative on itv_i to select between min and max workers for this sub-phase: alternative(itv_i, [...], card_i), with card_i an integer variable between min and max.
Then you post a noOverlap constraint between all the intervals of a given worker.
The advantage of this model is that if you have an horizon H for your schedule, instead of H*nbPhases*nbWorkers interval vars, you "only" have PhaseDurMax*nbPhases*nbWorkers interval. This can be ok if the duration of phases, in terms of number of 4h slots is not too big.