trxw
Reputation: 93
Minizinc Roster constraints
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];
Upvotes: 1
Views: 330
Answers (0)
Related Questions
- Task scheduling on multiple facilities - cumulative 'var opt error'
- Optimizing MiniZinc constraints for a scheduling problem
- Minizinc Constraint Formulation
- Constraint to select certain items in MiniZinc
- Minizinc. Count number of shifts in a cycle
- Constraint Programming: Scheduling with multiple workers
- MiniZinc does not find a solution to the scheduling problem
- minizinc sitting-friends-at-a-table-far-from-furius ones
- Minizinc: How to apply this constraint for scheduling model?
- Schedule minizinc no overlapping