Minizinc Roster constraints

Question

My problem is to create a roster with the following type of shifts:

• Morning (m): 7:30 to 14:45 • Early morning (m1): 6:45 to 14:00

• On call morning (im): 6:30 to 14:45

• Afternoon (t): 14:45 to 22:00

• On call afternoon (it): 13:45 to 22:00

• Night (n): 22:00 to 7:30 next day

• On call night (ino): 21:00 to 7:30 next day

• Office: 10 to 14

• Resting day (l): it is considered a resting day the day after a night even the worker finished at 7am that day

Rules to be applied: a cycle is composed of 6 or less of the above shifts (except office and rest) before needing a 48hours or 54 hours rest (see below)

If the cycle has 5 working days (m,m1,im,t,it,n,ino) the rest has to be of 48h or more
If the cycle has 6 working days (m,m1,im,t,it,n,ino) the rest has to be of 54h or more
There has to be at least 12 hours between the end of a shift and the start of the following shift (including office). So it is not possible to have n,t for instance
Nights: after a single night (n) or on call night (ino) there must be 48 hours rest unless there is another night (nn) or rest and night (nln) where you need 54 hours rest. So valid examples are nllm (48hours rest provided) or nnllt or nlnllt (54hours rest provided).
A maximum of 5 mornings/earlymornings/on call morning are accepted in a cycle.
The office is not considered working day but it does not count as rest, therefore it has to comply with the 12 hours rest as the other type of shifts but it does not count as a working day for the 5 or 6 days per cycle.
There is a maximum of 2 on calls shifts per cycle.

The roster has to meet a certain configuration given by number of workers for each shift (m,m1,t,n) every day. The on call shifts are not mandatory to comply with. No problems on this part.

So far rules from 3 to 7 are done. The problem that I have is for 1 and 2 as I am not able to do it with a regular constraint (it gets too complex). I was trying the approach of creating and array of resting hours between consecutive shifts which I did (third line of the image). Example:

The problem is the forth line: sum the consecutive rest (from the end of a shift + resting days + up to the start of the following shift), i.e. sum the zeros together with the left working day (1). Then count working days before >=48 hours to check if there are 5 or less; count working days before >=54 hours to check if there are 6 or less… just an idea. Thanks for your help!

This is the code so far (I included in the code a valid RosterCalculated that could be modify to test the code by changing it manually instead of the var RosterCalculated. In this case the constraint to test the Configuration should be removed as well). I believe this is better to test if the constraints are actually working...

include "globals.mzn";


%Definitions
enum TypeOfShift = {l,m1,m,t,n,im,it,ino,o};  %Types of shifts
array[TypeOfShift] of float: StartTypeOfShift=[10, 6.75, 7.5, 14.75, 22, 6.5, 13.75, 21, 10]; %Starting hour. The time for l is just to put something convenient
array[TypeOfShift] of float: DurationTypeOfShift=[0, 7.25, 7.25, 7.25, 9.5, 8.25, 8.25, 10.5, 6]; %Duration of shifts (hours)
enum Staff={AA,BB,CC,DD,EE,FF,GG,HH,II,JJ,KK,LL,MM};
array[int] of int: DaysInRoster=[28, 29, 30, 31, 1, 2, 3, 4, 5,6,7,8,9,10]; %Dias a los que corresponde el turnero


int: NumberWorkers = card(Staff); 
int: NumDaysInRoster=length(DaysInRoster);
array[1..NumDaysInRoster,TypeOfShift] of int: Configuration = array2d(1..NumDaysInRoster,TypeOfShift,[ (if (tu==m1) then 1 else
                                                                                                   if (tu==m) then 2 else
                                                                                                   if (tu==t) then 2 else
                                                                                                   if (tu==o) then 0 else
                                                                                                   if (tu==im) then 1 else
                                                                                                   if (tu==n) then 2 else 0
                                                                                                   endif endif endif endif endif endif)|  d in 1..NumDaysInRoster, tu in TypeOfShift ]); %Easy example of configuration

array[Staff, 1..NumDaysInRoster] of TypeOfShift: RosterCalculated = [|t, n, n, l, l, l, l, m, m1, m, t, l, m1, l|
m, l, l, n, l, l, t, t, n, l, l, l, m, l|
n, l, l, m, m1, m, m, n, l, l, m, m, l, m1|
l, t, l, n, l, l, m, m, t, n, l, l, t, l|
t, l, t, l, l, m, t, l, m, t, n, n, l, l|
m, m, m, l, l, m1, m1, n, l, l, m, l, l, t|
n, l, l, l, t, n, n, l, l, l, m1, t, n, n|
l, m, n, l, n, l, l, l, t, n, l, l, t, l|
l, t, l, m, m, l, l, l, m, m, l, m1, m, m|
l, l, m, m1, t, t, l, m1, n, l, l, n, l, m|
l, l, m1, t, l, l, l, t, l, t, t, t, n, l|
m1, m1, t, t, n, n, l, l, l, m1, l, m, l, n|
l, n, l, l, m, t, n, l, l, l, n, l, l, t|];



% Variables
%array[Staff, 1..NumDaysInRoster] of var TypeOfShift: RosterCalculated;  % To create the roster. Remove this line if what we want is to check if the code is working
var int: NumberWorkersNeeded =  sum (i in Staff) ((sum(d in 1..NumDaysInRoster) (RosterCalculated[i,d] != l)));                                       
array[Staff, 1..NumDaysInRoster-1] of var float: RosterCalculatedRests = array2d(Staff, 1..NumDaysInRoster-1,[(24*(d)+StartTypeOfShift[RosterCalculated[i,d+1]]) - (24*(d-1)+StartTypeOfShift[RosterCalculated[i,d]] + DurationTypeOfShift[RosterCalculated[i,d]]) | i in Staff, d in 1..NumDaysInRoster-1]);


% Satisfy configuration. Remove this constraint if what we want is to check if the code is working
/*
constraint forall(d in 1..NumDaysInRoster) 
              (((sum(i in Staff) (RosterCalculated[i,d] == m)) == Configuration[d,m]) /\ ((sum(i in Staff) (RosterCalculated[i,d] == m1)) == Configuration[d,m1]) /\ 
              ((sum(i in Staff) (RosterCalculated[i,d] == t)) == Configuration[d,t]) /\  ((sum(i in Staff) (RosterCalculated[i,d] == n)) == Configuration[d,n]));
*/

% Satisfy configuration on call not necessary to comply
constraint forall(d in 1..NumDaysInRoster) 
              (((sum(i in Staff) (RosterCalculated[i,d] == im)) <= Configuration[d,im]) /\ ((sum(i in Staff) (RosterCalculated[i,d] == it)) <= Configuration[d,it]) /\ 
              ((sum(i in Staff) (RosterCalculated[i,d] == ino)) <= Configuration[d,ino]) /\ ((sum(i in Staff) (RosterCalculated[i,d] == o)) <= Configuration[d,o]));            

% El tiempo transcurrido entre la salida de un turno y la entrada al siguiente tiene que ser igual o superior a 12h. NO NECESARIOS CON MATRIZ V4 (MAS LENTO)
constraint forall(i in Staff, d in 1..NumDaysInRoster-1)
              ((RosterCalculated[i,d+1] != l ) -> (24*(d-1)+StartTypeOfShift[RosterCalculated[i,d]] + DurationTypeOfShift[RosterCalculated[i,d]] + 12 <= 24*d+StartTypeOfShift[RosterCalculated[i,d+1]]));


% Rest after night or on call night (could be changed by regular constraint) 48h or more 
constraint forall(i in Staff, d in 1..NumDaysInRoster-3)
              (((RosterCalculated[i,d] == n) \/ (RosterCalculated[i,d] == ino)) -> ((RosterCalculated[i,d+1]==l \/ RosterCalculated[i,d+1]==n \/ RosterCalculated[i,d+1]==ino) /\
              (RosterCalculated[i,d+2]==l \/ RosterCalculated[i,d+2]==n \/ RosterCalculated[i,d+2]==ino) /\
              (StartTypeOfShift[RosterCalculated[i,d+3]] >= 7.5 \/ RosterCalculated[i,d+3]==l)));  


% Rest after double night has to be 54h or more (could be changed by regular constraint)
constraint forall(i in Staff, d in 1..NumDaysInRoster-4)
              ((((RosterCalculated[i,d] == n) \/ (RosterCalculated[i,d] == ino)) /\ ((RosterCalculated[i,d+1] == n) \/ (RosterCalculated[i,d+1] == ino))) -> ((RosterCalculated[i,d+2]==l) /\
              (RosterCalculated[i,d+3]==l) /\
              (StartTypeOfShift[RosterCalculated[i,d+4]] >= 13.5 \/ RosterCalculated[i,d+4]==l)));  

% Rest after a night free night has to be 54h or more (could be changed by regular constraint)
constraint forall(i in Staff, d in 1..NumDaysInRoster-5)
              ((((RosterCalculated[i,d] == n) \/ (RosterCalculated[i,d] == ino)) /\ (RosterCalculated[i,d+1] == l) /\ ((RosterCalculated[i,d+2] == n) \/ (RosterCalculated[i,d+2] == ino))) -> ((RosterCalculated[i,d+3]==l) /\
              (RosterCalculated[i,d+4]==l) /\
              (StartTypeOfShift[RosterCalculated[i,d+5]] >= 13.5 \/ RosterCalculated[i,d+5]==l)));


% Transition matrix not coping with all the cases...
predicate Max6WorkingDays(array[int] of var TypeOfShift: shift) =
    let {
        array[1..17, 1..5] of 0..17: transition_relation = % Transition matrix not coping with all the cases...
           [|8,   1,    2,  2,  2
            |9,   2,    3,  3,  3
            |10,    3,  4,  4,  4
            |11,    4,  5,  5,  5
            |12,    5,  6,  6,  6
            |13,    6,  7,  7,  15
            |14,    7,  0,  0,  0
            |1,   1,    2,  2,  2
            |1,   2,    3,  3,  3
            |1,   3,    4,  4,  4
            |1,   4,    5,  5,  5
            |1,   5,    6,  6,  6
            |1,   6,    7,  7,  15
            |1,   7,    0,  0,  0
            |16,    0,  0,  0,  0
            |17,    0,  0,  0,  0
            |1,   0,    0,  2,  2
          |];
    } in
        regular(
            [ if (s == l) then 1 else
              if s ==  o then 2 else
              if ((s == m) \/ (s == m1) \/(s == im)) then 3 else
              if ((s == t) \/ (s == it)) then 4 else
                              5 endif
                                endif
                                endif
                                endif
              | s in shift],                % sequence of input values
            17,                             % number of states
            5,                              % number of different input values of state machine
            transition_relation,            % transition relation
            1,                              % initial state
            1..17,                          % final states
         );                                                                                                                                                                                                                                          
constraint forall(i in Staff)
            (Max6WorkingDays([RosterCalculated[i,j] | j in 1..NumDaysInRoster]));                                                              


% Two on calls per cycle as max
predicate Max2OnCall(array[int] of var TypeOfShift: shift) =
    let {
        array[1..5, 1..4] of 0..5: transition_relation =
            [| 1, 2, 1, 1 % im0 (start)
             | 2, 4, 2, 3 % im1_l0
             | 2, 4, 2, 1 % im1_l1
             | 4, 0, 4, 5 % im2_l0
             | 4, 0, 4, 1 % im2_l1
            |];
    } in
        regular(
            [ if ((s == m1) \/ (s == m) \/ (s == t) \/ (s == n)) then 1 else
              if ((s == im) \/ (s == it) \/ (s == ino)) then 2 else
              if s ==  o then 3 else
                              4 endif
                                endif
                                endif
              | s in shift],                % sequence of input values
            5,                              % number of states
            4,                              % number of different input values of state machine
            transition_relation,            % transition relation
            1,                              % initial state
            1..5,                           % final states
         );

constraint forall(i in Staff)
            (Max2OnCall([RosterCalculated[i,j] | j in 1..NumDaysInRoster]));

% Max of 5 mornings per cycle
predicate MaxMsPerCycle(array[int] of var TypeOfShift: shift) =
    let {
        array[1..13, 1..4] of 0..13: transition_relation =
            [| 
              2,    7,  1,  1|
              3,    7,  8,  2|
              4,    7,  9,  3|
              5,    7,  10, 4|
              6,    7,  11, 5|
              0,    7,  12, 6|
              7,    7,  13, 7|
              3,    7,  1,  2|
              4,    7,  1,  3|
              5,    7,  1,  4|
              6,    7,  1,  5|
              0,    7,  1,  6|
              7,    7,  1,  7
            |];
    } in
        regular(
            [ if ((s == m1) \/ (s == m) \/ (s == im)) then 1 else
              if ((s == t) \/ (s == it) \/ (s == n) \/ (s == ino)) then 2 else
              if ((s ==  l)) then 3 else
                              4 endif
                                endif
                                endif
              | s in shift],                % sequence of input values
            13,                              % number of states
            4,                              % number of different input values of state machine
            transition_relation,            % transition relation
            1,                              % initial state
            1..13,                           % final states
         );

constraint forall(i in Staff)
            (MaxMsPerCycle([RosterCalculated[i,j] | j in 1..NumDaysInRoster]));



solve minimize NumberWorkersNeeded;
output[";;"]++["\(DaysInRoster[d]);" | d in 1..NumDaysInRoster];
output[if (d==1) then "\n"++"O3;\(i) " ++ ";" ++ show(RosterCalculated[i,d]) ++ ";" else show(RosterCalculated[i,d]) ++ ";" endif | i in Staff, d in 1..NumDaysInRoster];
output[if (d==1) then "\n"++"O3;\(i) " ++ ";" ++ show(RosterCalculatedRests[i,d]) ++ ";" else show(RosterCalculatedRests[i,d]) ++ ";" endif | i in Staff, d in 1..NumDaysInRoster-1];

StackOverflow is not a place to put challenges for other users, but a place to ask questions that you can't figure out. Could you rephrase your "challenge" to be a [Minimal Example](https://stackoverflow.com/help/minimal-reproducible-example) and ask a specific question? — Dekker1, Nov 08 '19 at 21:51
@Dekker1 Actually, this is my fault. OP asked very specific questions [here](https://stackoverflow.com/questions/58519660/minizinc-generate-a-valid-shift) and [here](https://stackoverflow.com/questions/58573379/minizinc-count-number-of-shifts-in-a-cycle). I thought that these questions were a bit too specific and that, without seeing the big picture, it was hard to provide suggestions that could scale better on the problem at hand. So I kindly asked him to provide the original problem in a separate question. Given your experience, would you have any better idea about how to deal with it? :) — Patrick Trentin, Nov 08 '19 at 22:19
Hi, I modify the question and the code. This one is giving results although with the same problems as already explained. I included as well a valid roster so it is easy to check if the constraints are working properly... Thanks a lot for your time, knowledge and good work! — trxw, Nov 09 '19 at 17:17
Hi, as suggested by @Dekker1 I have created another question [new post](https://stackoverflow.com/questions/58782794/minizinc-array-construction) with more precise question trying to avoid going through a big code... I might be missing other ways to solve the big picture but that's the way it is — trxw, Nov 09 '19 at 19:33
I would avoid using `float` use `int` instead (i.e. change the measurement unit). *AFAIK*, there are `MiniZinc` solvers that don't play well (or at all) with the `float` type, but are very good on `int`. The `12` hours distance should not require any computation, I think that one can pre-compute the valid successors. For many constraints the `on call` variant can be abstracted away (or the other way around) because it does not really change anything. — Patrick Trentin, Nov 10 '19 at 07:07
Thanks Patrick. I'll take the float thing into account once I have the model up and running. The 12 hours distance constraint works pretty well in fact, I believe better than the regular expression (in terms of computing time). Regarding the on call, you're right that in most cases on call shifts do not put more restrictions in relation to the standard shifts but there are a few important differences. For instance n,l,l,m is possible but n,l,l,im is not. My problem is being able to count the 5 or 6 days per cycle... That's where I'm stuck — trxw, Nov 10 '19 at 09:05
It looks like the problem can be broken down in two parts: **1.** find all possible and valid cycles and **2.** schedule the various cycles for each employee so that it covers 30+7 days, and then pick a value between 1-7 to choose the starting day of the 30-days month. — Patrick Trentin, Nov 11 '19 at 17:04
The rules in your post say *"A maximum of 5 mornings/earlymornings/on call morning are accepted in a cycle"*, but in the previous questions and in your code example you allow up to 6 mornings. Which one is correct? — Patrick Trentin, Nov 11 '19 at 18:12
My last explanation was the complete one. Max of 5 mornings. Max of 6 working days (therefore at least a non morning one) — trxw, Nov 11 '19 at 21:57
Regarding the other comment. It's more a matter of being able to validate that a generated roster fulfilled all the constraints. The only part missing in the puzzle is the rest in between cycles (5 or 6 days max). That's why I created the other post with minimal because I understood it was a possible way out. — trxw, Nov 11 '19 at 22:03
Have you tried with an explicit representation of cycles? e.g. `array [Staff, 1..15] of var 1..30: cycle_start; array[Staff, 1..15] of var 0..30: duration;`. You may get for free the array indexes required for computing the `delta_time` between the end of one cycle and the start of the next cycle. Today I started trying to automatically generate the transition relation for all wait `XX` hours constraints. It seems doable, but I am not sure the solvers will perform well with it. — Patrick Trentin, Nov 11 '19 at 22:54
even if you define those variables cycle_start and duration, you would need to calculate the rest as it is not the same to start/finish the cycles with one type of shift or another. Regarding the delta_time you are calculating, not sure if I understood what you're trying to accomplish. The delta_time between two consecutive days is already enforced in this constraint ((RosterCalculated[i,d+1] != l ) -> (24*(d-1)+StartTypeOfShift[RosterCalculated[i,d]] + DurationTypeOfShift[RosterCalculated[i,d]] + 12 <= 24*d+StartTypeOfShift[RosterCalculated[i,d+1]])); — trxw, Nov 12 '19 at 09:08
let's says `cycle_start[0] = 0, duration[0] = 3`, then we know that `shift[cycle_start[0] + duration[0] - 1]` is the last shift in the cycle and we can impose a constraint saying that the `start_time` of `shift[cycle_start[1]]` must be at least `48h` after. Not only that, we may be able to say that for each `i` between `cycle_start[0] + duration[0]` and `cycle_start[1]` we must have that `shift[i] = l`. Furthermore, we get a way to count how many `m/m1/im/t/it/n/ino` are there between `cycle_start[0]` and `cycle_start[0] + duration[0]`, that would solve the problem of the sliding window size. — Patrick Trentin, Nov 13 '19 at 07:34
The size of `cycle_start` and `duration` is `1..15` because there can be *at most* `15` cycles in one month (actually, fewer). It can be expected that the trailing values in these two arrays are meaningless (e.g. outside the `1..30` interval), so one must pay attention to how the constraints are encoded to avoid dummy `unsat` results. — Patrick Trentin, Nov 13 '19 at 07:39
Any smart idea on how can I enforce that every shift in the RosterCalculated has to belong to a cycle? Without that constraint, I am getting always cycle_start = 0 for all of them (which means cycle not used) — trxw, Nov 13 '19 at 16:58
An assignment s.t. for each `i` `cycle_start[i] = 0` should not be valid because of the requirement of there being at least `48h` between one cycle and the following one. An assignment s.t. each cycle is empty should also be made *invalid* by the requirement that the shifts of all employees taken together provide enough labor coverage throughout the day (I believe you expect that there is at least one person at work at any time, maybe more). — Patrick Trentin, Nov 13 '19 at 17:31
I am not following you... if we are defining 15 cycles as maximum, there are going to be some empty cycles. I have defined the array[Staff, 1..MaxNumCycles] of var 0..NumDaysInRoster: cycle_start; array[Staff, 1..MaxNumCycles] of var 0..14: duration; The zeros are for the unused cycles. I added a constraint that sort the cycle_start increasing and then the 48hours constraints. The problem is that I need a constraint that says that each shift in the RosterCalculated != l should belong to one and only one cycle — trxw, Nov 13 '19 at 17:54
Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/202283/discussion-between-user12262184-and-patrick-trentin). — trxw, Nov 13 '19 at 18:01

Minizinc Roster constraints

0 Answers0