| 1 |
/*** |
| 2 |
!Test |
| 3 |
check_against: [] |
| 4 |
expected: |
| 5 |
- !Result |
| 6 |
solution: !Solution |
| 7 |
last_step: 5 |
| 8 |
extra_files: [] |
| 9 |
markers: [] |
| 10 |
options: |
| 11 |
all_solutions: false |
| 12 |
solvers: |
| 13 |
- gecode |
| 14 |
- cbc |
| 15 |
- chuffed |
| 16 |
type: solve |
| 17 |
|
| 18 |
***/ |
| 19 |
|
| 20 |
% A factory has three kinds of machines: |
| 21 |
% - input machines, where products enter the factory; |
| 22 |
% - output machines, where finished products leave the factory; |
| 23 |
% - work machines, which can hold at most one product and which may |
| 24 |
% add some attributes to that product. |
| 25 |
% |
| 26 |
% A product can move from one machine to another iff there is a direct |
| 27 |
% connection between the two machines (we model staying at a particular |
| 28 |
% machine by making the connection graph reflexive). |
| 29 |
% |
| 30 |
% In this model all actions are assumed to take the same amount of time. |
| 31 |
% |
| 32 |
% The goal is to complete a set of products in the shortest time. |
| 33 |
% XXX Optimisation is currently very expensive; we settle instead |
| 34 |
% for merely finding a consistent solution. |
| 35 |
|
| 36 |
% These values must be supplied by a data file. |
| 37 |
% |
| 38 |
int: n_machines; % The number of machines. |
| 39 |
int: n_products; % The number of products. |
| 40 |
int: n_attributes; % The number of attributes. |
| 41 |
int: n_steps; % The number of plan steps. |
| 42 |
|
| 43 |
set of int: machines = 1..n_machines; |
| 44 |
set of int: products = 1..n_products; |
| 45 |
set of int: attributes = 1..n_attributes; |
| 46 |
set of int: steps = 1..n_steps; |
| 47 |
|
| 48 |
% These values must be supplied by a data file: |
| 49 |
% - input_machines - the set of machines where products can start; |
| 50 |
% - output_machines - the set of machines where products may finish; |
| 51 |
% - connected - the (reflexive) graph of inter-machine connections; |
| 52 |
% - can_add_attr - table of which machines can add which attributes; |
| 53 |
% - prod_attr_goal - table of goal attributes for each product; |
| 54 |
% - prod_start_mach - table of starting machines for each product. |
| 55 |
% |
| 56 |
set of machines: input_machines; |
| 57 |
set of machines: output_machines; |
| 58 |
array [machines, machines] of 0..1: connected; |
| 59 |
array [machines, attributes] of 0..1: can_add_attr; |
| 60 |
array [products, attributes] of 0..1: prod_attr_goal; |
| 61 |
array [products] of input_machines: prod_start_mach; |
| 62 |
|
| 63 |
% Decision variables: |
| 64 |
% - step_prod_attr[s, p, a] - at step s, product p has attribute a; |
| 65 |
% - step_prod_mach[s, p] = m - at step s, product p is at machine m; |
| 66 |
% - last_step - the step at which the goal is achieved. |
| 67 |
% |
| 68 |
array [steps, products, attributes] of var 0..1: step_prod_attr; |
| 69 |
array [steps, products] of var machines: step_prod_mach; |
| 70 |
var steps: last_step; |
| 71 |
|
| 72 |
% Work machines are those that are neither input machines or output machines. |
| 73 |
% |
| 74 |
set of machines: work_machines = |
| 75 |
machines diff (input_machines union output_machines); |
| 76 |
|
| 77 |
% Products start at particular machines. |
| 78 |
% |
| 79 |
constraint |
| 80 |
forall (p in products) ( |
| 81 |
step_prod_mach[1, p] = prod_start_mach[p] |
| 82 |
); |
| 83 |
|
| 84 |
% Products start with no attributes. |
| 85 |
% |
| 86 |
constraint |
| 87 |
forall (p in products, a in attributes) ( |
| 88 |
step_prod_attr[1, p, a] = 0 |
| 89 |
); |
| 90 |
|
| 91 |
% The attributes of a product at step s are a subset of its |
| 92 |
% attributes at step s+1. |
| 93 |
% |
| 94 |
constraint |
| 95 |
forall (s in steps, p in products, a in attributes where s < n_steps) ( |
| 96 |
step_prod_attr[s, p, a] <= step_prod_attr[s + 1, p, a] |
| 97 |
); |
| 98 |
|
| 99 |
% No two products can occupy the same work machine at the same step. |
| 100 |
% |
| 101 |
constraint |
| 102 |
forall (s in steps, p, q in products, m in work_machines where p < q) ( |
| 103 |
step_prod_mach[s, p] = m -> step_prod_mach[s, q] != m |
| 104 |
); |
| 105 |
|
| 106 |
% At t = last_step all goals should be achieved: |
| 107 |
% - each product should have (precisely) its goal set of attributes; |
| 108 |
% - each product should be in an output machine. |
| 109 |
% |
| 110 |
constraint |
| 111 |
forall (p in products, a in attributes) ( |
| 112 |
step_prod_attr[last_step, p, a] = prod_attr_goal[p, a] |
| 113 |
); |
| 114 |
|
| 115 |
constraint |
| 116 |
forall (p in products) ( |
| 117 |
step_prod_mach[last_step, p] in output_machines |
| 118 |
); |
| 119 |
|
| 120 |
% Products can only move between directly connected machines. |
| 121 |
% |
| 122 |
constraint |
| 123 |
forall (s in steps, p in products where s < n_steps) ( |
| 124 |
connected[step_prod_mach[s, p], step_prod_mach[s + 1, p]] = 1 |
| 125 |
); |
| 126 |
|
| 127 |
% A product can have an attribute added while at a particular machine. |
| 128 |
% |
| 129 |
constraint |
| 130 |
forall (s in steps, p in products, a in attributes where s < n_steps) ( |
| 131 |
step_prod_attr[s + 1, p, a] <= |
| 132 |
step_prod_attr[s, p, a] |
| 133 |
+ can_add_attr[step_prod_mach[s, p], a] |
| 134 |
); |
| 135 |
|
| 136 |
% XXX Trying to optimize for last_step currently takes forever, even for |
| 137 |
% relatively simple problems. |
| 138 |
% |
| 139 |
% solve minimize last_step; |
| 140 |
% |
| 141 |
last_step = n_steps; |
| 142 |
% solve satisfy; |
| 143 |
|
| 144 |
% Instance data |
| 145 |
|
| 146 |
n_machines = 5; |
| 147 |
n_products = 2; |
| 148 |
n_attributes = 3; |
| 149 |
n_steps = 5; |
| 150 |
|
| 151 |
input_machines = {1}; |
| 152 |
|
| 153 |
output_machines = {5}; |
| 154 |
|
| 155 |
% Connections: |
| 156 |
% |
| 157 |
% M1 --- M2 ----. |
| 158 |
% | | | |
| 159 |
% |----- M3 --- M5 |
| 160 |
% | | | |
| 161 |
% '----- M4 ----' |
| 162 |
|
| 163 |
connected = |
| 164 |
[| 1, 1, 1, 1, 0, |
| 165 |
| 1, 1, 1, 0, 1, |
| 166 |
| 1, 1, 1, 1, 1, |
| 167 |
| 1, 0, 1, 1, 1, |
| 168 |
| 0, 1, 1, 1, 1 |
| 169 |
|]; |
| 170 |
|
| 171 |
can_add_attr = |
| 172 |
[| 0, 0, 0 |
| 173 |
| 1, 0, 0 |
| 174 |
| 0, 1, 0 |
| 175 |
| 0, 0, 1 |
| 176 |
| 0, 0, 0 |
| 177 |
|]; |
| 178 |
|
| 179 |
prod_start_mach = [ |
| 180 |
1, |
| 181 |
1 |
| 182 |
]; |
| 183 |
|
| 184 |
prod_attr_goal = |
| 185 |
[| 1, 1, 0 |
| 186 |
| 1, 0, 1 |
| 187 |
|]; |
| 188 |
|
| 189 |
solve satisfy; |
| 190 |
|
| 191 |
output [ |
| 192 |
"factory planning instance\n", |
| 193 |
"step | product | location | a1 a2 a3\n", |
| 194 |
"-----+---------+----------+---------\n", |
| 195 |
" 1 | 1 | ", show(step_prod_mach[1, 1]), " | ", |
| 196 |
show(step_prod_attr[1, 1, 1]), " ", |
| 197 |
show(step_prod_attr[1, 1, 2]), " ", |
| 198 |
show(step_prod_attr[1, 1, 3]), "\n", |
| 199 |
" | 2 | ", show(step_prod_mach[1, 2]), " | ", |
| 200 |
show(step_prod_attr[1, 2, 1]), " ", |
| 201 |
show(step_prod_attr[1, 2, 2]), " ", |
| 202 |
show(step_prod_attr[1, 2, 3]), "\n", |
| 203 |
"-----+---------+----------+---------\n", |
| 204 |
" 2 | 1 | ", show(step_prod_mach[2, 1]), " | ", |
| 205 |
show(step_prod_attr[2, 1, 1]), " ", |
| 206 |
show(step_prod_attr[2, 1, 2]), " ", |
| 207 |
show(step_prod_attr[2, 1, 3]), "\n", |
| 208 |
" | 2 | ", show(step_prod_mach[2, 2]), " | ", |
| 209 |
show(step_prod_attr[2, 2, 1]), " ", |
| 210 |
show(step_prod_attr[2, 2, 2]), " ", |
| 211 |
show(step_prod_attr[2, 2, 3]), "\n", |
| 212 |
"-----+---------+----------+---------\n", |
| 213 |
" 3 | 1 | ", show(step_prod_mach[3, 1]), " | ", |
| 214 |
show(step_prod_attr[3, 1, 1]), " ", |
| 215 |
show(step_prod_attr[3, 1, 2]), " ", |
| 216 |
show(step_prod_attr[3, 1, 3]), "\n", |
| 217 |
" | 2 | ", show(step_prod_mach[3, 2]), " | ", |
| 218 |
show(step_prod_attr[3, 2, 1]), " ", |
| 219 |
show(step_prod_attr[3, 2, 2]), " ", |
| 220 |
show(step_prod_attr[3, 2, 3]), "\n", |
| 221 |
"-----+---------+----------+---------\n", |
| 222 |
" 4 | 1 | ", show(step_prod_mach[4, 1]), " | ", |
| 223 |
show(step_prod_attr[4, 1, 1]), " ", |
| 224 |
show(step_prod_attr[4, 1, 2]), " ", |
| 225 |
show(step_prod_attr[4, 1, 3]), "\n", |
| 226 |
" | 2 | ", show(step_prod_mach[4, 2]), " | ", |
| 227 |
show(step_prod_attr[4, 2, 1]), " ", |
| 228 |
show(step_prod_attr[4, 2, 2]), " ", |
| 229 |
show(step_prod_attr[4, 2, 3]), "\n", |
| 230 |
"-----+---------+----------+---------\n", |
| 231 |
" 5 | 1 | ", show(step_prod_mach[5, 1]), " | ", |
| 232 |
show(step_prod_attr[5, 1, 1]), " ", |
| 233 |
show(step_prod_attr[5, 1, 2]), " ", |
| 234 |
show(step_prod_attr[5, 1, 3]), "\n", |
| 235 |
" | 2 | ", show(step_prod_mach[5, 2]), " | ", |
| 236 |
show(step_prod_attr[5, 2, 1]), " ", |
| 237 |
show(step_prod_attr[5, 2, 2]), " ", |
| 238 |
show(step_prod_attr[5, 2, 3]), "\n", |
| 239 |
"-----+---------+----------+---------\n" |
| 240 |
]; |