Something went wrong. Try again.
This repository has no description
Something went wrong. Try again.
9.7 kB · 277 lines
at develop
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278% 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' 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 weekarray [1..weeks,1..7] of var 1..5: roster; % flatroster is a one-dimensional array, which will contain exactly the same set of variablesarray [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 violationsconstraint 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];