Modeling sequence-dependent setup times

Setup times on disjunctive resources can be modeled by a no-overlap constraint with a transition distance.

It is quite common that a certain minimal amount of time must elapse between the execution of two successive operations on a resource (e.g. a machine), and, often, this amount of time depends on the types of the two successive operations. This is the notion of sequence-dependent setup time and can be captured in CP Optimizer by a no-overlap constraint with transition distance.

Operations on the machine are represented by interval variables a[i] and a sequence variable seq is created on these interval variables to model the sequence of operations on the machine. The type of the different operations (used to compute the setup time) are specified when building the sequence variable.

A transition distance is represented by a transition distance class and stored as a matrix of setup times. A no-overlap constraint must be posted with the sequence variable and the transition distance to state that interval variables of the sequence do not overlap and that the sequence-dependent setup time of the transition distance applies to the intervals of the sequence.

CP Optimizer distinguishes two kinds of behavior of the no-overlap constraint with respect to transition distances: (1) transition distance between immediate successors and (2) transition distances between all successors.

A transition distance between immediate successors is generally useful for modeling the duration of a setup activity to switch the state of the resource from one interval to the next interval in the sequence. Here, the state of the resource is represented by the type of the interval in the sequence. This is illustrated in Sample 1; the Boolean flag passed at the construction of the no-overlap constraint specifies if the transition distance must only be applied between immediate successors on the sequence variable. A complete example of transition distance between immediate successors is available in the delivered example <Install_dir>/cpoptimizer/examples/src/cpp/sched_setup.cpp. In some more complex cases, the setup activity will have to be explicitly modeled as an interval variable because, for instance, it requires some additional resource. In this case, you can use the expressions typeOfNext and typeOfPrev on the sequence variable to constrain the length of the setup activity as illustrated in Sample 2. See Modeling classical scheduling costs for modeling sequence-dependent setup costs.

In some specific cases, the transition distance must be applied between all pairs of intervals succeeding each other on the sequence, no matter if there are other intervals in between. For example, consider a set of movies to be scheduled on a TV channel. If a movie of type ti is scheduled after a movie of type tj (no matter which other movies are shown in between), depending on the types ti,tj, one would like a minimal amount of time to elapse between the two occurrences to avoid showing movies of similar types too close to each other. Sample 3 illustrates such a use-case using a minimal delay separationTime[ti] between movies of type ti; the Boolean flag passed at the construction of the no-overlap constraint specifies that the transition distance must be applied between all successors on the sequence variable.

SAMPLE 1: Sequence-dependent setup time on immediate successors

  IloEnv env;
  IloModel model(env);
  IloInt m = ...; // Number of types { 0, 1, ..., m-1 }

  IloTransitionDistance setupTimes(env, m);
  for (IloInt ti=0; ti<m; ++ti)
    for (IloInt tj=0; tj<m; ++tj)
      setupTimes.setValue(ti,tj, ...); // Setup time between types ti and tj

  IloInt n = ...;    // Number of activities on the machine
  IloIntervalVarArray act(env, n); // Activities on the machine
  IloIntArray        type(env, n); // Activity types
  // ...

  IloIntervalSequenceVar machine(env, act, type);
  // Transition distance applies between immediate successors
  model.add(IloNoOverlap(env, machine, setupTimes, IloTrue));

SAMPLE 2: Sequence-dependent setup activities

  IloEnv env;
  IloModel model(env);
  IloInt m = ...; // Number of types { 0, 1, ..., m-1 }

  IloInt n = ...;    // Number of activities on the machine
  IloIntervalVarArray act  (env, n); // Activities on the machine
  IloIntervalVarArray setup(env, n); // Setup activities on the machine
  IloIntervalVarArray cover(env, n); // Covering activities on the machine
  IloIntArray         type (env, n); // Activity types

  // ...
  for (IloInt i=0; i<n; ++i) {
    act  [i] = ...;
    type [i] = ...;
    cover[i] = IloIntervalVar(env);
    setup[i] = IloIntervalVar(env);
    IloIntervalVarArray dec(env); dec.add(act[i]); dec.add(setup[i]);
    model.add(IloSpan(env, cover[i], dec));
    model.add(IloEndBeforeStart(env, act[i], setup[i]));
  }

  IloIntervalSequenceVar machine(env, cover, type);
  model.add(IloNoOverlap(env, machine));  // Setup activities

  IloIntArray2 setupDuration(env, m);
  IloInt last = m;  // Type of next for the last activity on the machine
  for (IloInt ti=0; ti<m; ++ti) {
    setupDuration[ti]= IloIntArray(env, m+1);
    for (IloInt tj=0; tj<m; ++tj)
      setupDuration[ti][tj] = ...; // Length of setup activity between types ti and tj
    setupDuration[ti][last] = 0;   // Length of last setup activity
   }
  for (IloInt i=0; i<n; ++i)
   model.add(IloLengthOf(setup[i])==
                         setupDuration[type[i]][IloTypeOfNext(machine,cover[i],last)]);

SAMPLE 3: Sequence-dependent setup time on all successors

  IloEnv env;
  IloModel model(env);
  IloInt m = ...; // Number of types { 0, 1, ..., m-1 }

  IloTransitionDistance separationTimes(env, m);
  for (IloInt ti=0; ti<m; ++ti)
    separationTimes.setValue(ti,ti, ...); // Separation time between two movies of type ti

  IloInt n = ...;    // Number of movies
  IloIntervalVarArray movie(env, n); // Movies
  IloIntArray          type(env, n); // Types
  // ...

  // Transition distance applies between all successors
  IloIntervalSequenceVar movieSequence(env, movie, type);  
  model.add(IloNoOverlap(env, movieSequence, separationTimes, IloFalse));