%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % FIT3022 % Assignment 1 % Rostering Problem % Efficient Solution % 5th May 2009 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % 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 "globals.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 0..2*flatsize: objective :: is_output = 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 :: is_output ; % flatroster is a one-dimensional array, which will contain exactly the same set of variables array [1..flatsize] of var 1..5: flatroster ; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Constraints %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% constraint objective >= minobj ; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % 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 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Note the use of ((d2-1) mod flatsize)+1 % which has the same value as d2 except when d2 is greater than flatsize. % When d2 = flatsize+1 (equivalent to Monday of week 1), it takes the value 1 % When d2 = flatize+n (for any n less than flatsize), it takes the value n % ... but see note ALTERNATIVE below constraint forall (d in 1..flatsize) (at_least(1,[flatroster[((d2-1) mod flatsize)+1]|d2 in d..d+6],Rest)) ; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % ALTERNATIVE % Some answers have used a more elegant solution: appending the first 6 days of the roster % onto the end to make an extended roster. The total length of the extended roster is 7*weeks+6. % This avoids any need for the formula ((d2-1) mod flatsize)+1. The simple variable d2 can be used. % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Too Much Rest Constraint % % Description: % Ensure that there is no sequence of more than three Rest days in a row % % Example violation: % roster = [1,1,4,2,2,2,2, % 3,3,4,3,3,1,1] % This solution has four Rest days in a row, starting on the Saturday of % week 2 and ending on the Monday of week 1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % We associate a count with each day recording the number of % consecutive rest days. On each rest day we increment the count by 1. % The count is not allowed to be larger than 3. % Note again the use of ((d-2) mod flatsize)+1 array [1..flatsize] of var 0..3: restseq; constraint forall (d in 1..flatsize) ( (flatroster[d] = Rest -> restseq[d] = 1+restseq[((d-2) mod flatsize)+1] ) /\ ( restseq[d] = 0 <-> flatroster[d] != 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 /\ flatroster[(d mod flatsize)+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. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % The propositional formula % flatroster[d] = Rest -> flatroster[d-1] = Rest \/ flatroster[d+1] = Rest % holds UNLESS d is an isolated Rest day. % To handle cyclic rosters this constraint uses ((Expr-1) mod flatsize)+1 instead of Expr throughout constraint isolated = sum(d in 1..flatsize) ( bool2int( flatroster[d] = Rest /\ not (flatroster[((d-2) mod flatsize)+1] = Rest \/ flatroster[(d mod flatsize)+1] = 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. %%%%%%%%%%%%%%%%% Search Optimisation %%%%%%%%%%%%%%%%%%%%%%%%%%%%% int: restshiftct = sum(day in 1..7)(reqt[Rest,day]) ; % These are the (unknown) days which will be assigned as rest days array [ 1.. restshiftct ] of var 1..flatsize: restdays ; % The flat array linearises the roster column by column % (viz. d1w1, d1w2, ...,d2w1,d2w2,...) % to ensure that when searching on restdays, the rests are assigned day by day array [1..flatsize] of var 1..5: flat2 ; constraint forall (d in 1..7,w in 1..weeks) (flat2[weeks*(d-1)+w] = roster[w,d]) ; % We list the roster days when the rest days will occur in increasing order. constraint forall (x in 1..restshiftct-1) (restdays[x+1]>restdays[x]) ; % A roster day can ONLY be a rest day if it occurs in restdays constraint forall (x in 1..flatsize) ( (flat2[x] = Rest) <-> (exists (y in 1..restshiftct) (x = restdays[y])) ) ; %% Symmetry % Suppose the whole roster is complete % We can simply choose week1 to be any week (since the roster is cyclic). % Let's arbitrarily choose a week which starts with a rest day % This avoids searching among similar rosters. constraint roster[1,1] = Rest ; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% solve % Try first to find rosters with a minimum number of isolated rest days % :: int_search([isolated],"input_order","indomain_min","complete") :: seq_search([ int_search(restdays, input_order, indomain_min, complete), int_search(flat2, input_order, indomain_min, complete) ]) minimize objective ;