Something went wrong. Try again.
This repository has no description
Something went wrong. Try again.
6.2 kB · 137 lines
at develop
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138% N-SITE problem% Road Network Maintenance Problem%% Determine which worksheets to execute on which day so that the road network is not perterbed too much% Each worksheet is a contiguous set of daily tasks on roads: specified by a road and number of workers% Worksheets have an importance defining how important they are to execute% % Constraints to satisfy are:% Earliest and latest start times of worksheets% Not too many workers from each work center on any day% For each of a number of given sets of roads never blocking more than a given amount % Some worksheets must be executed% Precedence rules between pairs of worksheets% PARAMETERSint: days; % number of daysoset of int: DAY = 0..days-1;int: roads; % number of roadsint: centers; % number of centersint: worksheets; % number of worksheetsint: activities; % number of activitiesset of int: ROAD = 0..roads-1;set of int: ROAD0 = -1..roads-1; array[ROAD0,DAY] of int: perterb; % perturbation cost of road on each dayset of int: CENTER = 0..centers-1; % index set for centersarray [CENTER] of int: c_id; % id of each centerarray [CENTER] of int: available_workers; % number of available workers per centerset of int: WORKSHEET = 0..worksheets-1; % index set for workseetsarray [WORKSHEET] of int: w_id; % id of each worksheetarray [WORKSHEET] of int: work_center; % id of the work center where used by each worksheet array [WORKSHEET] of 0..1: mandatory; % whether each worksheet is mandatoryarray [WORKSHEET] of int: importance; % importance of each worksheetarray [WORKSHEET] of int: est; % earliest starting time for each worksheetarray [WORKSHEET] of int: lst; % latest starting time for each worksheetarray [WORKSHEET] of int: duration; % duration in days of each worksheetset of int: ACTIVITY = 0..activities-1;array [WORKSHEET,ACTIVITY] of ROAD0: road; % road used by each worksheet on a given day -1 = nonearray [WORKSHEET,ACTIVITY] of int: workers; % number of workers used by each worksheet on a given dayint: blocked_max; % number of maximum blocked rules for this instanceset of int: BLOCKED = 1..blocked_max; % index set for maximum blocked rulesarray [BLOCKED] of ROAD: blocked_max_amount; % max amount of roads that can be blocked of a given setarray [BLOCKED] of set of ROAD: blocked_roads; % the set of roads that the max amount refers toint: precedences; % number of precedence rules for this instanceset of int: PREC = 1..precedences; % index set for the precedence rulesarray [PREC] of WORKSHEET: preceeds; % the predecessor worksheet in a given rulearray [PREC] of WORKSHEET: succeeds; % the successor worksheet in a given rule% DECISION VARIABLESarray [WORKSHEET] of var 0..1: g; % 1 if the worksheet is executedarray [WORKSHEET] of var DAY: d; % start time of worksheet array [WORKSHEET] of var DAY: e = array1d(WORKSHEET,[ d[w] + duration[w] | w in WORKSHEET ]); % end time of worksheet % Fixing unused variables constraint forall(w in WORKSHEET)(g[w] = 0 <-> d[w] = est[w]); % Fits in scheduleconstraint forall(w in WORKSHEET)(e[w] <= days);% CONSTRAINTS% Precedences within Worksheet% Worksheet Earliest Starting Timeconstraint forall (w in WORKSHEET) (est[w] <= d[w]);% Worksheet Latest Starting Timeconstraint forall (w in WORKSHEET) (d[w] <= lst[w]);% Complete WORKSHEET% Mandatory WORKSHEETconstraint forall (w in WORKSHEET) (g[w] >= mandatory[w]);% Precedence Between Worksheets% if both worksheets execute then the end of w1 is before the start of w2constraint forall (i in PREC) (let { WORKSHEET: w1 = preceeds[i]; WORKSHEET: w2 = succeeds[i]; } in g[w1] * e[w1] <= d[w2] + days * (1 - g[w2]));% Maximal Number of Roads Simultaneously Blockedinclude "global_cardinality_low_up.mzn";constraint forall(b in BLOCKED)( global_cardinality_low_up( [ (d[w] + a + 1)*g[w] %% add one to separate 0 = not executed | w in WORKSHEET, a in 0..duration[w]-1 where road[w,a] in blocked_roads[b]], [ d + 1 | d in DAY], %% looking for day + 1 [ 0 | d in DAY], [blocked_max_amount[b] |d in DAY] )); % Work Center Capacityinclude "cumulative.mzn";constraint forall(c in CENTER) ( if length([w | w in WORKSHEET where work_center[w] = c]) > 0 then cumulative([ d[w] + a | w in WORKSHEET where work_center[w] = c, a in 0..duration[w] - 1 ], [ g[w] | w in WORKSHEET where work_center[w] = c, a in 0..duration[w] - 1 ], [ workers[w,a] | w in WORKSHEET where work_center[w] = c, a in 0..duration[w]-1 ], available_workers[c]) else true endif);% OBJECTIVE var 0..worksheets * max(importance): importance_obj = sum (w in WORKSHEET) (g[w]*importance[w]);int: perterb_obj_ub = max(array1d(perterb)) * days;var 0..perterb_obj_ub: perterb_obj = max(i in DAY)( sum(w in WORKSHEET, a in 0..duration[w]-1)( g[w] * perterb[road[w,a], i] * (i = d[w]+a) )); var -ub(perterb_obj)..ub(importance_obj): objective; constraint objective = importance_obj - perterb_obj; array[int] of int: import_first = reverse(arg_sort(importance)); solve :: int_search( [ if j = 1 then g[import_first[i]] else -d[import_first[i]] endif | i in 1..worksheets, j in 1..2], input_order, indomain_max, complete) maximize objective;output [ "g = array1d(\(WORKSHEET), \(g));\n", "d = array1d(\(WORKSHEET), \(d));\n", "objective = \(objective);\n"];