279 lines
9.5 KiB
MiniZinc
279 lines
9.5 KiB
MiniZinc
% NOTE: the formulation of this problem that was used in the 2009
|
|
% MiniZinc challenge is in the file roster_model.old. (That formulation
|
|
% is not compatible with MiniZinc 1.1 and above.)
|
|
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
% FIT3022
|
|
% Assignment 1
|
|
% Rostering Problem
|
|
% Example Solution
|
|
% 6th May 2008
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
|
% This model should be paired with a data file, viz.
|
|
% mzn_run(chicroster,data_A, fzn_ic)
|
|
|
|
% An example data file data_A is as follows:
|
|
% reqt = [3,2,1,0,1,1,5,
|
|
% 1,0,1,0,1,2,0,
|
|
% 1,2,0,1,1,1,0,
|
|
% 0,1,2,2,2,1,0,
|
|
% 0,0,1,2,0,0,0] ;
|
|
%
|
|
% weeks = 5 ;
|
|
|
|
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
% Model
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
|
% Import predicates 'exactly', at_most', 'at_least'
|
|
% which are defined in "globals.mzn"
|
|
include "exactly.mzn";
|
|
include "at_most.mzn";
|
|
include "at_least.mzn";
|
|
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
% Parameters
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
|
% "weeks" and "reqt" are imported from the data file.
|
|
% "flatsize" is a constant computed from the parameter "weeks", which is used
|
|
% in the model.
|
|
%
|
|
int: weeks ;
|
|
int: flatsize = 7 * weeks ;
|
|
array [1..5,1..7] of int: reqt ;
|
|
int: minobj;
|
|
|
|
% The following parameters aid readability of the model.
|
|
%
|
|
int:Rest=1;
|
|
int:Morn=2;
|
|
int:Day=3;
|
|
int:Eve=4;
|
|
int:Joker=5;
|
|
|
|
% The following two variables will hold the costs due to violated soft
|
|
% constraints.
|
|
%
|
|
var 0..flatsize: evemorn ;
|
|
var 0..flatsize: isolated ;
|
|
|
|
var minobj..2*flatsize: objective = evemorn + isolated;
|
|
|
|
% The roster is an array of decision variables: each variable has domain 1..5
|
|
% representing possible shifts Rest,Morn,Day,Eve or Joker roster is a
|
|
% two-dimensional array with a row for each week
|
|
array [1..weeks,1..7] of var 1..5: roster;
|
|
|
|
% flatroster is a one-dimensional array, which will contain exactly the same set of variables
|
|
array [1..flatsize] of var 1..5: flatroster ;
|
|
array [1..flatsize+6] of var 1..5: longflatroster ;
|
|
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
% Constraints
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
|
constraint
|
|
forall (d in 1..6) (longflatroster[flatsize+d] = flatroster[d]);
|
|
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
% Hard Constraints
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
% Roster Flat-Roster constraint
|
|
%
|
|
% Description:
|
|
% This constraint ensures that roster and flatroster contain the same set of
|
|
% variables. The first seven variables in flatroster correspond to the first
|
|
% row (week) in roster. The 8th to the 14th variables in flatroster correspond
|
|
% to the second row in roster, etc. The total number of variables is the
|
|
% number of weeks times 7.
|
|
%
|
|
% Example violation:
|
|
% This constraint is violated if a variable in flatroster is different from the corresponding
|
|
% variable in roster, e.g.
|
|
%
|
|
% flatroster = [1,2,2,2,2,2,2,2,2,2,2,2,2,2]
|
|
% roster = [2,2,2,2,2,2,2,
|
|
% 2,2,2,2,2,2,2]
|
|
%
|
|
% The first day of week one is different in flatroster and roster
|
|
%
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
|
constraint
|
|
forall (w in 1..weeks, d in 1..7) (flatroster[7*(w-1)+d] = roster[w,d]) ; %:: defines_var(roster) ;
|
|
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
% Requirement Constraint
|
|
%
|
|
% Description:
|
|
% The roster shifts must meet the requirement specified in the data
|
|
% Each day of the week, the sum of the sifts of each type must match the
|
|
% required number for the given shift type on the given day of the week
|
|
%
|
|
% Example violation:
|
|
%
|
|
% % M T W T F S S
|
|
% reqt = [0,0,0,0,0,2,2,
|
|
% 1,1,0,1,1,0,0,
|
|
% 1,1,0,1,1,0,0,
|
|
% 0,0,2,0,0,0,0,
|
|
% 0,0,0,0,0,0,0] ;
|
|
%
|
|
% weeks = 2 ;
|
|
%
|
|
%
|
|
%
|
|
% roster = [3,2,4,2,2,1,1,
|
|
% 3,3,4,3,3,1,1]
|
|
% This solution does not match the requirement for Monday
|
|
% (two Day shifts instead of a Morning and a Day shift).
|
|
%
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
|
constraint
|
|
forall (shift in 1..5)
|
|
(forall (day in 1..7)
|
|
(exactly(reqt[shift,day],[roster[week,day] | week in 1..weeks],shift))
|
|
);
|
|
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
% Enough Rest Constraint
|
|
%
|
|
% Description:
|
|
% Ensure that in any sequence of 7 days, at least one of them is a Rest day.
|
|
%
|
|
% Example violation:
|
|
% roster = [1,2,4,2,2,2,2,
|
|
% 3,3,4,3,3,1,1]
|
|
% This solution has 11 working days in a row, starting on Tuesday in week 1
|
|
% and ending on Saturday in week 2
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
|
constraint
|
|
forall (d in 1..flatsize)
|
|
(at_least(1,[longflatroster[d2]|d2 in d..d+6],Rest)) ;
|
|
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
% Too Much Rest Constraint
|
|
%
|
|
% Description:
|
|
% Ensure that there is no sequence of three Rest days in a row
|
|
%
|
|
% Example violation:
|
|
% roster = [1,2,4,2,2,2,2,
|
|
% 3,3,4,3,3,1,1]
|
|
% This solution has three Rest days in a row, starting on the Saturday of
|
|
% week 2 and ending on the Monday of week 1
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
|
constraint
|
|
forall (d in 1..flatsize)
|
|
(at_most(3,[longflatroster[d2]|d2 in d..d+3],Rest)) ;
|
|
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
% Soft Constraints
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
|
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
% Not Evening before Morning Constraint
|
|
%
|
|
% Description:
|
|
% For every occurrence in the roster of an Eve shift (4) followed by a Morn
|
|
% shift (2) incur a cost of 1. Sum up these costs over the whole roster
|
|
%
|
|
% Example Violation:
|
|
% roster = [1,2,4,2,2,2,2,
|
|
% 3,3,4,3,3,1,1]
|
|
%
|
|
% On Tuesday of week 1 there is an Eve shift followed by a Morn shift on
|
|
% Wednesday.
|
|
%
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
|
% The proposition condition
|
|
% flatroster[d]=Eve /\ flatroster[(d mod flatsize)+1] = Morn
|
|
% is true whenever an Eve is followed by a Morn.
|
|
% bool2int converts true to a cost of 1. If the proposition is false
|
|
% (i.e. the constraint is not violated), then bool2int returns 0.
|
|
% The sum over all sequences is therefore the number of violations
|
|
constraint
|
|
evemorn = sum(d in 1..flatsize)
|
|
(bool2int(flatroster[d]=Eve /\
|
|
longflatroster[d+1] = Morn )
|
|
);
|
|
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
% No Isolated Rest Day Constraint
|
|
%
|
|
% Description:
|
|
% An isolated Rest day is a Rest day with a non-Rest-day on the day before and
|
|
% on the day after. Each such isolated Rest day incurs a cost of 1, and the
|
|
% costs are summed up over the whole roster.
|
|
%
|
|
% Example Violation:
|
|
% roster = [1,2,4,2,2,2,2,
|
|
% 1,3,4,3,3,1,1]
|
|
% The Monday of week 2 is preceded by a Morn shift and followed by a Day shift.
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
|
% Using the syntax != for 'not-equals', the propositional formula
|
|
% flatroster[d-1] != Rest /\ flatroster[d] = Rest /\ flatroster[d+1] != Rest
|
|
% holds if and only if d is an isolated Rest day.
|
|
|
|
constraint
|
|
isolated = sum(d in 1..flatsize)
|
|
(bool2int( (longflatroster[d+1] = Rest /\
|
|
not(flatroster[d] = Rest \/ longflatroster[d+2] = Rest)))
|
|
) ;
|
|
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
% Solve Item
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
% A solution with minimal cost (evemorn+isolated) due to violations is sought.
|
|
% There may be different solutions with the same, minimal, cost.
|
|
% Only one solution is found by this model
|
|
|
|
% Unfortunately the facilities for controlling search, which are necessary for
|
|
% getting good solving performance on most problems, have not been covered in FIT3022
|
|
% This model works well on all the data instances provided, but unfortunately
|
|
% small changes to the model can unpredictably, and dramatically, impact performance.
|
|
|
|
solve
|
|
:: int_search(flatroster, first_fail, indomain_min, complete)
|
|
minimize objective;
|
|
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
% Output of the solution
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
% The roster is displayed as numbers - not unfortunately shift type names - with
|
|
% one row for each week.
|
|
% The number of isolated rests and morning after evening violations is also shown.
|
|
|
|
output [
|
|
"roster = array2d(1..\(weeks), 1..7, \(roster));\n",
|
|
"evemorn = \(evemorn);\n",
|
|
"isolated = \(isolated);\n",
|
|
"objective = \(objective);\n"
|
|
] ++ [
|
|
"% Roster: \n",
|
|
"% Week: M T W T F S S\n"
|
|
] ++ [
|
|
if j = 1 then "% \(i): " else "" endif ++
|
|
"\(roster[i,j])" ++
|
|
if j = 7 then "\n" else " " endif
|
|
| i in 1..weeks, j in 1..7
|
|
];
|
|
|