title: Minizinc Roster constraints
body: <p>My problem is to create a roster with the following type of shifts:</p>
  
  <p>•   Morning (m): 7:30 to 14:45
  •   Early morning (m1): 6:45 to 14:00</p>
  
  <p>•   On call morning (im): 6:30 to 14:45</p>
  
  <p>•   Afternoon (t): 14:45 to 22:00</p>
  
  <p>•   On call afternoon (it): 13:45 to 22:00</p>
  
  <p>•   Night (n): 22:00 to 7:30 next day</p>
  
  <p>•   On call night (ino): 21:00 to 7:30 next day</p>
  
  <p>•   Office: 10 to 14</p>
  
  <p>•   Resting day (l): it is considered a resting day the day after a night even the worker finished at 7am that day</p>
  
  <p>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)</p>
  
  <ol>
  <li>If the cycle has 5 working days (m,m1,im,t,it,n,ino) the rest has to be of 48h or more</li>
  <li>If the cycle has 6 working days (m,m1,im,t,it,n,ino) the rest has to be of 54h or more</li>
  <li>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</li>
  <li>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).</li>
  <li>A maximum of 5 mornings/earlymornings/on call morning  are accepted in a cycle.</li>
  <li>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.</li>
  <li>There is a maximum of 2 on calls shifts per cycle.</li>
  </ol>
  
  <p>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.</p>
  
  <p>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:</p>
  
  <p><a href="https://i.stack.imgur.com/5HGQr.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/5HGQr.png" alt="Desired behaviour"></a></p>
  
  <p>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!</p>
  
  <p>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...</p>
  
  <pre><code>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)) &lt;= Configuration[d,im]) /\ ((sum(i in Staff) (RosterCalculated[i,d] == it)) &lt;= Configuration[d,it]) /\ 
                ((sum(i in Staff) (RosterCalculated[i,d] == ino)) &lt;= Configuration[d,ino]) /\ ((sum(i in Staff) (RosterCalculated[i,d] == o)) &lt;= 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 ) -&gt; (24*(d-1)+StartTypeOfShift[RosterCalculated[i,d]] + DurationTypeOfShift[RosterCalculated[i,d]] + 12 &lt;= 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)) -&gt; ((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]] &gt;= 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))) -&gt; ((RosterCalculated[i,d+2]==l) /\
                (RosterCalculated[i,d+3]==l) /\
                (StartTypeOfShift[RosterCalculated[i,d+4]] &gt;= 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))) -&gt; ((RosterCalculated[i,d+3]==l) /\
                (RosterCalculated[i,d+4]==l) /\
                (StartTypeOfShift[RosterCalculated[i,d+5]] &gt;= 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];
  </code></pre>