this repo has no description
dekker.one
1/***
2!Test
3check_against: []
4expected:
5- !Result
6 solution: !Solution
7 last_step: 5
8extra_files: []
9markers: []
10options:
11 all_solutions: false
12solvers:
13- gecode
14- cbc
15- chuffed
16type: 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%
38int: n_machines; % The number of machines.
39int: n_products; % The number of products.
40int: n_attributes; % The number of attributes.
41int: n_steps; % The number of plan steps.
42
43set of int: machines = 1..n_machines;
44set of int: products = 1..n_products;
45set of int: attributes = 1..n_attributes;
46set 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%
56set of machines: input_machines;
57set of machines: output_machines;
58array [machines, machines] of 0..1: connected;
59array [machines, attributes] of 0..1: can_add_attr;
60array [products, attributes] of 0..1: prod_attr_goal;
61array [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%
68array [steps, products, attributes] of var 0..1: step_prod_attr;
69array [steps, products] of var machines: step_prod_mach;
70var steps: last_step;
71
72% Work machines are those that are neither input machines or output machines.
73%
74set of machines: work_machines =
75 machines diff (input_machines union output_machines);
76
77% Products start at particular machines.
78%
79constraint
80 forall (p in products) (
81 step_prod_mach[1, p] = prod_start_mach[p]
82 );
83
84% Products start with no attributes.
85%
86constraint
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%
94constraint
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%
101constraint
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%
110constraint
111 forall (p in products, a in attributes) (
112 step_prod_attr[last_step, p, a] = prod_attr_goal[p, a]
113 );
114
115constraint
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%
122constraint
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%
129constraint
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%
141last_step = n_steps;
142% solve satisfy;
143
144% Instance data
145
146n_machines = 5;
147n_products = 2;
148n_attributes = 3;
149n_steps = 5;
150
151input_machines = {1};
152
153output_machines = {5};
154
155% Connections:
156%
157% M1 --- M2 ----.
158% | | |
159% |----- M3 --- M5
160% | | |
161% '----- M4 ----'
162
163connected =
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
171can_add_attr =
172[| 0, 0, 0
173 | 1, 0, 0
174 | 0, 1, 0
175 | 0, 0, 1
176 | 0, 0, 0
177|];
178
179prod_start_mach = [
180 1,
181 1
182];
183
184prod_attr_goal =
185[| 1, 1, 0
186 | 1, 0, 1
187|];
188
189solve satisfy;
190
191output [
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];