this repo has no description
dekker.one
1%-----------------------------------------------------------------------------%
2% vim: ts=4 sw=4 et wm=0 tw=0
3%-----------------------------------------------------------------------------%
4% Copyright (C) 2009-2016 The University of Melbourne and NICTA.
5% See the file COPYING for license information.
6%-----------------------------------------------------------------------------%
7% Model example for Resource-Constrained Project Scheduling Problems with
8% Weighted Earliness/Tardiness objective (RCPSP/WET)
9%
10% A RCPSP consists of resources, tasks, and precedences between some tasks
11% where resources have of a specific capacity and tasks need some capacity of
12% some resource to be executed.
13% Here, we consider resources with a constant discrete capacity over time and
14% tasks with a constant discrete duration and resource requirements.
15% The objective is to find a optimal schedule so that tasks start as close as
16% possible to the given start time for each task, penalizing earliness or
17% tardiness according to the given weight for earliness and tardiness per task.
18%
19%-----------------------------------------------------------------------------%
20
21include "cumulative.mzn";
22
23%-----------------------------------------------------------------------------%
24% Model parameters.
25
26
27 % Resources
28 %
29int: n_res; % The number of resources
30set of int: Res = 1..n_res; % The set of all resources
31array [Res] of int: rc; % The resource capabilities
32
33 % Tasks
34 %
35int: n_tasks; % The number of tasks
36set of int: Tasks = 1..n_tasks; % The set of all tasks
37array [Tasks] of int : d ; % The task durations
38array [Res, Tasks] of int : rr ; % The resource requirements
39array [Tasks] of set of int: suc; % The task successors
40
41 % Deadlines
42 %
43 % deadline[i, 1] is the desired start time for task i,
44 % deadline[i, 2] is the earliness cost per time unit of earliness,
45 % deadline[i, 3] is the tardiness cost per time unit of tardiness.
46array [Tasks, 1..3] of int: deadline;
47
48 % Planning horizon
49 %
50 % Note that our RCPSP/WET instance generator requires a solution to the
51 % equivalent RCPSP problem in order to generate the instances, so it gives
52 % us a planning horizon = the makespan of the RCPSP problem, plus 20% slop
53int: t_max; %= sum(i in Tasks)(d[i]); % End time of the planning horizon
54set of int: Times = 0..(t_max - 1); % Possible start times
55
56%-----------------------------------------------------------------------------%
57% Model variables.
58
59array [Tasks] of var Times: s; % The start times
60var 0..sum(i in Tasks) (
61 max(
62 deadline[i, 2] * deadline[i, 1],
63 deadline[i, 3] * (t_max - deadline[i, 1])
64 )
65): objective;
66
67%-----------------------------------------------------------------------------%
68% Constraints.
69
70 % Precedence constraints
71 %
72constraint
73 forall ( i in Tasks, j in suc[i] )
74 (
75 s[i] + d[i] <= s[j]
76 );
77
78 % Redundant non-overlapping constraints
79 %
80constraint
81 redundant_constraint(
82 forall ( i, j in Tasks where i < j )
83 (
84 if exists(r in Res)(rr[r, i] + rr[r, j] > rc[r]) then
85 s[i] + d[i] <= s[j] \/ s[j] + d[j] <= s[i]
86 else
87 true
88 endif
89 )
90 );
91
92 % Cumulative resource constraints
93 %
94constraint
95 forall ( r in Res )
96 (
97 let {
98 set of int: RTasks =
99 { i | i in Tasks
100 where rr[r, i] > 0 /\ d[i] > 0 },
101 int: sum_rr = sum(i in RTasks)(rr[r, i])
102 } in (
103 if RTasks != {} /\ sum_rr > rc[r] then
104 cumulative(
105 [ s[i] | i in RTasks ],
106 [ d[i] | i in RTasks ],
107 [ rr[r, i] | i in RTasks ],
108 rc[r]
109 )
110 else
111 true
112 endif
113 )
114 );
115
116 % Weighted Earliness/Tardiness objective
117constraint
118 objective = sum (i in Tasks) (
119 % earliness
120 deadline[i, 2] * max(0, deadline[i, 1] - s[i]) +
121 % tardiness
122 deadline[i, 3] * max(0, s[i] - deadline[i, 1])
123 );
124
125%-----------------------------------------------------------------------------%
126% Objective.
127
128constraint trace("% init_area = \(ub(objective));\n", true);
129
130%-----------------------------------------------------------------------------%
131
132output [
133 "s = \(s);\n",
134 "objective = \(objective);\n",
135];
136
137%-----------------------------------------------------------------------------%
138%-----------------------------------------------------------------------------%
139