Originally posted by: Matt_sev

Dear all,

I am a student working on a scheduling project. I am quite new to this sort of language and also have read the scheduling manual and the examples displayed there. I have already tried to relate the problem to current examples, but without any succes.

The objective of our project is to find the optimal shift combination to minimize the number of workers in one day (consists of 54 timeslots). There are three possible shifts types with different duration size: 32,42 and 50 timeslots.

Furthermore there are 54 timeslots in total and we know for each timeslot 1..54 the number of required workers for that timeslot (see attached excel file). The goal is thus to know how many shifts we need from each shift type to cover the required amount of workers for each timeslot, while minimizing the total number of shifts. If this could be displayed in a gantt chart, as well like a cumul function like in the examples that would be great!

Thank you in advance for anyone willing to help me, the problem seems fairly easy which makes me quite frustrated that I am not able to program it.

Kind regards,

Matt_sev

Originally posted by: ol

Hello,

first, you need to express the problem mathematically.
For each time t, you have to respect a lower bound for the number of workers.
Thus, you need to have a way to express the number of workers at time t.
Furthermore, you need to express that a worker can work either 32, 42 or 50 consecutive slots, or be absent.

The elements of the language you may find useful are:
- cumul functions, that is functions over time.
- interval variables, that can be optional, i.e. present or absent, with a duration (maybe 32, 42 or 50, why not?), a starting time and an ending time.
- pulse functions, which is an elementary function over time: a pulse over an interval variable is a function over time with value h inside the interval, and value 0 outside the interval. You may sum different pulse functions to form a more interesting cumul function.
- alternatives, typically to express that a given interval variable is one of a set of alternative interval variables.

Try first to formalize your problem with these elements, and do not bother with the syntax. Feel free to contact us if you still have a question.

Regards,
ol

Originally posted by: Matt_sev

Hi Ol,

I'm very happy with your reply which sure was interesting. I'm only now picking up the project again (as I had exams the past months).
I was able to define the intervals, I also defined a cumulfunction workersUsage with a pulse and used this to set to equal or greater than the predefined number of workers at each timeslot.
However, there are still some problems, can't you use the minimze function on a cumul function? At this moment I am quite stuck as I don't know what to do, I think I've defined all the elements but that a big link is somewhere missing.

For convenience, I've attached the .mod and .dat file with the necessary comments.

Thank you in advance for your help,

Matt_Sev

Originally posted by: ol

Hello,
the files in the zip you sent are encrypted.

Anyway, if you want to minimize the number of shifts, you can build an expression that represents the number of shifts. An expression myExp can be integer or floating point and you can minimize it by adding to the model an objective:

model.add(IloMaximize(env, myExp));

I do not know your model, but let us assume you used an optional interval W[i] for each possible worker i. The interval is present means that the worker is involved in the planning. Then, the expression:
   IloPresenceOf(W[1]) + ... + IloPresenceOf(W[n])
is the number of shifts.
If you prefer to minimize the number of hours, you can weight each term IloPresenceOf(W[i]) by its length.

Regards,

ol

Originally posted by: Matt_sev

Dear Ol, 

Thank you very much for your reply! I'm sorry, I forgot the files were encrypted.

I tried the last few days to implement the presenceOf() function, As I made my model, I encounter now a 'circular dependency', even after googling, I still don't quite understand what this means.

I also have a few other errors in my code, but i don't quite know how to solve them, could you maybe take a look at the code to see if I am going in the right direction?

Thanks in advance,

Matt_Sev

PS: if the file won't open for some reason I'll paste here the model code, sorry for the inconvenience from last time.

using CP;

//Define intervals: number of shifts and n = number of timeslots
int NbShifts = ...; 
int n=...;
int i;

//Range of number of slots
range NumberOfSlots=1..n;
range Shifts = 1..NbShifts;

// The required number of workers for 1 timeslot
int Required[NumberOfSlots]=...;
//Assign duration to each possible shift
int Duration [s in Shifts] = ...;
int worker[i];

//Create decision variables, shift with certain duration is assigned to a worker
dvar interval itvs  [i in worker][s in Shifts] optional size Duration[s];
// Keep track of the number of workers
cumulFunction workersUsage = 
   sum(n in NumberOfSlots, i in worker) pulse(itvs[n][i],1);
   
//Mnimize the number of workers
minimize sum(i in worker)(presenceOf(worker[i]));

subject to{
 //for each timeslot, a required number of workers is needed
forall(n in NumberOfSlots)
  workerUsage[n] >= Required[n]; 

}

Originally posted by: ChrisBr

Hello Matt,

I'm not sure I understand your model, but anyway I'll try to help you with syntax.

First of all it is necessary to pay attention on any possible confusion between constants, ranges, arrays of data and so on.
To make things clearer it would be a nice idea to rename a few elements (but of course you are free to keep yours if you are more comfortable with)

//Define intervals: number of shifts and number of timeslots
int NbShiftTypes = ...; 
int NumberOfSlots=...;
//Range of number of slots and number of shifts
range Slots=1..NumberOfSlots;
range ShiftTypes = 1..NbShiftTypes;

More important: you cannot declare

int worker[i];

Because you use worker in expressions like "i in worker" I think you wanted to define something like:

int NbWorkers = ...;
range worker = 1..NbWorkers;

Be careful to always use the right index.
For example, the use of "itvs" which is define as

dvar interval itvs  [i in worker][s in Shifts] optional size Duration[s];

and used as:

   sum(n in NumberOfSlots, i in worker) pulse(itvs[n][i],1);

This cannot work.
Whatever you wanted to state, the indices must match the definition.
Here we could have

  sum(i in worker, s in Shift) pulse(itvs[i][s],1);

presenceOf is an expression which requires an interval-var as argument.

Do you need one cumulFunction or an array of cumulFunctions?
You define one

cumulFunction workersUsage =

and try to use an array

workerUsage[n] >= Required[n];

I hope these few tips help.

Chris.

Originally posted by: Matt_sev

Hi Chris,

Thank you very much for your reply! 

In the end I thought that a cumulFunction was necessary because in that way one could define that on that specific timeslot the number of required workers must be greater than the one defined in an array (required in the data file). What I would like to have as an output is a Gantt-chart where the  shifts are displayed, does that require an array of cumulfunctions? As you probably noticed, I am quite confused on what to use. I added a picture of the desired output for clarification, as I am not sure if I am still going in the right direction. And in the end, 1 shift is done by 1 person.

Kind regards,

Matthijs

Originally posted by: PhilippeLaborie

Hello. 

Here is how I would formulate the problem if I get it well:

You can assume a maximum number of shifts for each shift type SMax (in the model below, I used SMax=50).

Then for each shift type 's', you create SMax optional interval variables itv[s][i] with i in 1..SMax of duration equal to the duration of shift type s.

You use a single cumul function 'workersUsage' that will represent the number of workers over time and that is the sum of pulse of height 1 over all the interval variables itv[s][i].

A set of alwaysIn constraints state the minimal value of this cumul function over time (for each time slot).

And the objective is to minimize the number of present shifts.

You can use some symmetry breaking constraint among the intervals representing shifts of the same type.

The attached model on your data finds an optimal solution with 33 shifts.

using CP;

//Define intervals: number of shifts and n = number of timeslots
int NbShifts = ...; 
int n = ...;

//Range of number of slots
range NumberOfSlots = 1..n;
range Shifts = 1..NbShifts;

// The required number of workers for 1 timeslot
int Required[NumberOfSlots]=...;
//Assign duration to each possible shift
int Duration [s in Shifts] = ...;

// Maximal number of shifts per shift type
int SMax = 50;

dvar interval itvs[s in Shifts][i in 1..SMax] optional in 1..n+1 size Duration[s];

// Keep track of the number of workers
cumulFunction workersUsage = 
   sum(s in Shifts, i in 1..SMax) pulse(itvs[s][i],1);

execute {
  cp.param.TimeLimit = 30;
}

//Mnimize the number of workers
minimize sum(s in Shifts, i in 1..SMax) presenceOf(itvs[s][i]);

subject to{
  // for each timeslot, a required number of workers is needed
  forall(n in NumberOfSlots)
    alwaysIn(workersUsage, n, n+1, Required[n], NbShifts*SMax); 
  // Symmetry breaking
  forall(s in Shifts) {
    forall(i in 2..SMax) {
      startBeforeStart(itvs[s][i-1],itvs[s][i]);
      presenceOf(itvs[s][i]) => presenceOf(itvs[s][i-1]);
    }
  }    
}

And the resulting worker's profile is as shown on the attached figure.

Originally posted by: Matt_sev

Dear Philippe,

This is exactly what I was looking for. Although the symmetry breaking is still not yet very clear to me.

Can you maybe explain what this exactly means? I looked up the functions separately, but it is difficult to translate it into the code you wrote.

Thank you very much for providing this answer,

Kind regards,

Matthijs

Originally posted by: PhilippeLaborie

About the symmetry constraints:

In general these symmetry constraints are not necessary, in the sense that the model is correct even without them. There are used for performance reason because they permit to decrease the size of the search space by removing some equivalent solutions.

If you look on a particular shift type s, the model introduces SMax optional intervals itv[s][i] with i in 1..SMax. Among these optional interval variables only a subset will be selected by the search to be present (and as few as possible while still covering the demand). Suppose that in a solution you select k shifts for this shift type s. You have (k SMax) combinations (I denote (k n) the binomial coefficient). But all these (k SMax) combinations are basically the same. The symmetry constraints will ensure that you have only one representative of these equivalent combinations in the solution. This is done thanks to a chain of implication constraints: presenceOf(itvs[s][i]) => presenceOf(itvs[s][i-1]). If you select k shift of type s, necessarily, only the first k ones (with i in 1..k) will be present. The startBeforeStart(itvs[s][i-1],itvs[s][i]) constraints also break some temporal symmetries: the k selected shifts will be the ones with i in 1..k AND the start times of these interval variables has to be non decreasing.

In general breaking symmetries help for proving optimality (this is the case here, at least on this instance) because it reduces the size of the search space to be explored. But it does not always help to produce good solutions faster.

Originally posted by: Matt_sev

Hi Philippe,

Thank you very much to make this symmetry aspect more understandable. I was also trying to put a maximum on each type of shift. For example, i would want to limit the longest shift to 5 (because they don't like that shift), while the others can be for example at 20 and 25. I tried with implementing an array, but I can't seem to couple that to the shift type.

Kind regards,

Matt_Sev

Originally posted by: PhilippeLaborie

Well, it is very easy, you only need to add some constraints saying that for each shift type, the total number of shifts used (which is equal to the number of present intervals for this shift) does not exceed the limit. As illustrated in this model:

using CP;

//Define intervals: number of shifts and n = number of timeslots
int NbShifts = ...; 
int n = ...;

//Range of number of slots
range NumberOfSlots = 1..n;
range Shifts = 1..NbShifts;

// The required number of workers for 1 timeslot
int Required[NumberOfSlots]=...;
// Assign duration to each possible shift
int Duration [s in Shifts] = ...;

int ShiftMaxNumber[Shifts] = [25,20,5];

// Maximal number of shifts per shift type
int SMax = 50;

dvar interval itvs[s in Shifts][i in 1..SMax] optional in 1..n+1 size Duration[s];

// Keep track of the number of workers
cumulFunction workersUsage = 
   sum(s in Shifts, i in 1..SMax) pulse(itvs[s][i],1);

// Minimize the number of workers
minimize sum(s in Shifts, i in 1..SMax) presenceOf(itvs[s][i]);

subject to {
  // For each timeslot, a required number of workers is needed
  forall(n in NumberOfSlots)
    alwaysIn(workersUsage, n, n+1, Required[n], NbShifts*SMax); 
  // Symmetry breaking
  forall(s in Shifts) {
    forall(i in 2..SMax) {
      startBeforeStart(itvs[s][i-1],itvs[s][i]);
      presenceOf(itvs[s][i]) => presenceOf(itvs[s][i-1]);
    }
  }
  // Maximal number of shifts
  forall(s in Shifts) {
    sum(i in 1..SMax) presenceOf(itvs[s][i]) <= ShiftMaxNumber[s];
  }
}

Originally posted by: Matt_sev

Hi Philippe,

We have still a small question to ask. We have to modify the minimization criteria. Everything in the model should remain the same, but instead of limiting the number of shifts with ShiftMaxNumber and minimizing the total number of shifts, we would like to minimize the total number of hours  (each timeslot is 15 minutes, meaning shift 1 equals 8 hours, shift 2 equals 10.5 and shift 3 equals 12.5 hours). This is because the persons are paid per hour.

As the problem is now solved, we get the minimal amount of shifts but not the minimal amount of hours. What we would desire now, is to minimize the total number of hours in the final schedule.

I already tried to alter the the 'minimize sum(s in Shifts, i in 1..Smax) by the h in hours (and appropriate array), but the model just keeps running without giving any errors. 

We were hoping you could provide some help and insight in this matter.

Kind regards,

Matt_sev
 

Originally posted by: PhilippeLaborie

I think 'ol' already mentioned this variant of the objective in one of his answers.

All you need to do is to replace the current objective with:

minimize sum(s in Shifts, i in 1..SMax) (Duration[s]*presenceOf(itvs[s][i]));

Or even shorter:

minimize sum(s in Shifts, i in 1..SMax) lengthOf(itvs[s][i]);