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