/
rcpsp.mzn
122 lines (103 loc) · 3.86 KB
/
rcpsp.mzn
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
%-----------------------------------------------------------------------------%
% vim: ts=4 sw=4 et wm=0 tw=0
%-----------------------------------------------------------------------------%
% Copyright (C) 2009-2012 The University of Melbourne and NICTA.
% See the file COPYING for license information.
%-----------------------------------------------------------------------------%
% Model example for Resource-Constrained Project Scheduling Problems (RCPSP)
%
% A RCPSP consists of resources, tasks, and precedences between some tasks
% where resources have of a specific capacity and tasks need some capacity of
% some resource to be executed.
% Here, we consider resources with a constant discrete capacity over time and
% tasks with a constant discrete duration and resource requirements.
% The objective is to find a optimal schedule with respect to the earliest end
% time of the schedule where the tasks' resource requirements do not exceed
% the resource capacities to any time and each precedence is met.
%
%-----------------------------------------------------------------------------%
include "globals.mzn";
%-----------------------------------------------------------------------------%
% Model parameters.
% Resources
%
int: n_res; % The number of resources
set of int: Res = 1..n_res; % The set of all resources
array [Res] of int: rc; % The resource capabilities
% Tasks
%
int: n_tasks; % The number of tasks
set of int: Tasks = 1..n_tasks; % The set of all tasks
array [Tasks] of int : d ; % The task durations
array [Res, Tasks] of int : rr ; % The resource requirements
array [Tasks] of set of int: suc; % The task successors
% Planning horizon
%
int: t_max = sum(i in Tasks)(d[i]); % End time of the planning horizon
set of int: Times = 0..(t_max - 1); % Possible start times
%-----------------------------------------------------------------------------%
% Model variables.
array [Tasks] of var Times: s; % The start times
var 0..t_max: objective ; % The project duration (makespan)
%-----------------------------------------------------------------------------%
% Constraints.
% Precedence constraints
%
constraint
forall ( i in Tasks, j in suc[i] )
(
s[i] + d[i] <= s[j]
);
% Redundant non-overlapping constraints
%
constraint
forall ( i, j in Tasks where i < j )
(
if exists(r in Res)(rr[r, i] + rr[r, j] > rc[r]) then
s[i] + d[i] <= s[j] \/ s[j] + d[j] <= s[i]
else
true
endif
);
% Cumulative resource constraints
%
constraint
forall ( r in Res )
(
let {
set of int: RTasks =
{ i | i in Tasks
where rr[r, i] > 0 /\ d[i] > 0 },
int: sum_rr = sum(i in RTasks)(rr[r, i])
} in (
if RTasks != {} /\ sum_rr > rc[r] then
cumulative(
[ s[i] | i in RTasks ],
[ d[i] | i in RTasks ],
[ rr[r, i] | i in RTasks ],
rc[r]
)
else
true
endif
)
);
% Makespan constraints
%
constraint
forall ( i in Tasks where suc[i] == {} )
(
s[i] + d[i] <= objective
);
%-----------------------------------------------------------------------------%
% Objective.
solve
:: int_search( s ++ [objective], smallest, indomain_min, complete )
minimize objective;
%-----------------------------------------------------------------------------%
output [
"Start times = ", show(s), "\n",
"makespan = ", show(objective), "\n"
];
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%