Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
open-shop.cpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Guido Tack <tack@gecode.org>
5 *
6 * Copyright:
7 * Guido Tack, 2009
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34#include <gecode/driver.hh>
35#include <gecode/int.hh>
36#include <gecode/minimodel.hh>
37
38using namespace Gecode;
39
40namespace {
45 class OpenShopSpec {
46 public:
47 const int m; //< number of machines
48 const int n; //< number of jobs
49 const int* p; //< processing times of the tasks
51 OpenShopSpec(int m0, int n0, const int* p0) : m(m0), n(n0), p(p0) {}
52 };
53
54 extern OpenShopSpec examples[];
55 extern const unsigned int n_examples;
56}
57
65protected:
67 const OpenShopSpec& spec;
74
76 class Task {
77 public:
78 int j; //< Job
79 int m; //< Machine
80 int p; //< Processing time
82 Task(void) {}
84 Task(int j0, int m0, int p0) : j(j0), m(m0), p(p0) {}
85 };
86
96 void crosh(Matrix<IntArgs>& dur, int& minmakespan, int& maxmakespan) {
98
99 // Compute maximum makespan as the sum of all production times.
100 maxmakespan = 0;
101 for (int i=0; i<spec.m; i++)
102 for (int j=0; j<spec.n; j++)
103 maxmakespan += dur(i,j);
104
105 // Compute minimum makespan as the maximum of individual jobs and machines
106 minmakespan = 0;
107 for (int i=0; i<spec.m; i++) {
108 int ms = 0;
109 for (int j=0; j<spec.n; j++) {
110 ms += dur(i,j);
111 }
112 minmakespan = std::max(minmakespan, ms);
113 }
114 for (int j=0; j<spec.n; j++) {
115 int ms = 0;
116 for (int i=0; i<spec.m; i++) {
117 ms += dur(i,j);
118 }
119 minmakespan = std::max(minmakespan, ms);
120 }
121
122 Region re;
123 int* ct_j = re.alloc<int>(spec.n); // Job completion time
124 int* ct_m = re.alloc<int>(spec.m); // Machine completion time
125 Task* tasks = re.alloc<Task>(spec.n*spec.m); // Tasks
126 int k=0;
127 for (int i=spec.m; i--;)
128 for (int j=spec.n; j--;)
129 new (&tasks[k++]) Task(j,i,dur(i,j));
130 int* t0_tasks = re.alloc<int>(spec.n*spec.m); // Earliest possible tasks
131
132 bool stopCROSH = false;
133
134 int maxIterations;
135 switch (spec.n) {
136 case 3: maxIterations = 5; break;
137 case 4: maxIterations = 25; break;
138 case 5: maxIterations = 50; break;
139 case 6: maxIterations = 1000; break;
140 case 7: maxIterations = 10000; break;
141 case 8: maxIterations = 10000; break;
142 case 9: maxIterations = 10000; break;
143 default: maxIterations = 25000; break;
144 }
145 int iteration = 0;
146 while (!stopCROSH && maxmakespan > minmakespan) {
147 for (int i=spec.n; i--;) ct_j[i] = 0;
148 for (int i=spec.m; i--;) ct_m[i] = 0;
149 int cmax = 0; // Current makespan
150 int u = spec.n*spec.m; // Consider all tasks
151 while (u > 0) {
152 int u_t0 = 0; // Set of selectable tasks
153 int t0 = maxmakespan; // Minimal head of unscheduled tasks
154 for (int i=0; i<u; i++) {
155 const Task& t = tasks[i];
156 int est = std::max(ct_j[t.j], ct_m[t.m]); // Head of T_jm
157 if (est < t0) {
158 t0 = est;
159 t0_tasks[0] = i;
160 u_t0 = 1;
161 } else if (est == t0) {
162 t0_tasks[u_t0++] = i;
163 }
164 }
165 int t_j0m0;
166 if (iteration == 0) {
167 // In the first iteration, select tasks with longest processing time
168 t_j0m0 = 0;
169 for (int i=1; i<u_t0; i++)
170 if (tasks[t0_tasks[i]].p > tasks[t0_tasks[t_j0m0]].p)
171 t_j0m0 = i;
172 } else {
173 t_j0m0 = rnd(u_t0); // Select random task
174 }
175 const Task& t = tasks[t0_tasks[t_j0m0]];
176 int ect = t0 + t.p;
177 ct_j[t.j] = ect;
178 ct_m[t.m] = ect;
179 std::swap(tasks[--u],tasks[t0_tasks[t_j0m0]]); // Remove task from u
180 cmax = std::max(cmax, ect);
181 if (cmax > maxmakespan)
182 break;
183 }
184
185 maxmakespan = std::min(maxmakespan,cmax);
186 if (iteration++ > maxIterations)
187 stopCROSH = true; // Iterate a couple of times
188 }
189 }
190public:
193 : IntMinimizeScript(opt),
194 spec(examples[opt.size()]),
195 b(*this, (spec.n+spec.m-2)*spec.n*spec.m/2, 0,1),
196 makespan(*this, 0, Int::Limits::max),
197 _start(*this, spec.m*spec.n, 0, Int::Limits::max) {
198
199 Matrix<IntVarArray> start(_start, spec.m, spec.n);
200 IntArgs _dur(spec.m*spec.n, spec.p);
201 Matrix<IntArgs> dur(_dur, spec.m, spec.n);
202
203 int minmakespan;
204 int maxmakespan;
205 crosh(dur, minmakespan, maxmakespan);
206 rel(*this, makespan <= maxmakespan);
207 rel(*this, makespan >= minmakespan);
208
209 int k=0;
210 for (int m=0; m<spec.m; m++)
211 for (int j0=0; j0<spec.n-1; j0++)
212 for (int j1=j0+1; j1<spec.n; j1++) {
213 // The tasks on machine m of jobs j0 and j1 must be disjoint
214 rel(*this,
215 b[k] == (start(m,j0) + dur(m,j0) <= start(m,j1)));
216 rel(*this,
217 b[k++] == (start(m,j1) + dur(m,j1) > start(m,j0)));
218 }
219
220 for (int j=0; j<spec.n; j++)
221 for (int m0=0; m0<spec.m-1; m0++)
222 for (int m1=m0+1; m1<spec.m; m1++) {
223 // The tasks in job j on machine m0 and m1 must be disjoint
224 rel(*this,
225 b[k] == (start(m0,j) + dur(m0,j) <= start(m1,j)));
226 rel(*this,
227 b[k++] == (start(m1,j) + dur(m1,j) > start(m0,j)));
228 }
229
230 // The makespan is greater than the end time of the latest job
231 for (int m=0; m<spec.m; m++) {
232 for (int j=0; j<spec.n; j++) {
233 rel(*this, start(m,j) + dur(m,j) <= makespan);
234 }
235 }
236
237 // First branch over the precedences
238 branch(*this, b, BOOL_VAR_AFC_MAX(opt.decay()), BOOL_VAL_MAX());
239 // When the precedences are fixed, simply assign the start times
240 assign(*this, _start, INT_ASSIGN_MIN());
241 // When the start times are fixed, use the tightest makespan
242 assign(*this, makespan, INT_ASSIGN_MIN());
243 }
244
247 b.update(*this, s.b);
248 makespan.update(*this, s.makespan);
249 _start.update(*this, s._start);
250 }
251
253 virtual Space*
254 copy(void) {
255 return new OpenShop(*this);
256 }
257
259 virtual IntVar
260 cost(void) const {
261 return makespan;
262 }
263
265 class PrintTask {
266 public:
267 int start; //< Start time
268 int job; //< Job number
269 int p; //< Processing time
271 bool operator()(const PrintTask& t1, const PrintTask& t2) {
272 return t1.start < t2.start;
273 }
274 };
275
277 virtual void
278 print(std::ostream& os) const {
279 Region re;
280 PrintTask* m = re.alloc<PrintTask>(spec.n);
281 for (int i=0; i<spec.m; i++) {
282 int k=0;
283 for (int j=0; j<spec.n; j++) {
284 m[k].start = _start[i*spec.n+j].val();
285 m[k].job = j;
286 m[k].p = spec.p[i*spec.n+j];
287 k++;
288 }
289 Support::quicksort(m, spec.n, m[0]);
290 os << "Machine " << i << ": ";
291 for (int j=0; j<spec.n; j++)
292 os << "\t" << m[j].job << "("<<m[j].p<<")";
293 os << " = " << m[spec.n-1].start+m[spec.n-1].p << std::endl;
294 }
295 os << "Makespan: " << makespan << std::endl;
296 }
297
298};
299
303int
304main(int argc, char* argv[]) {
305 SizeOptions opt("OpenShop");
306 opt.iterations(500);
307 opt.size(0);
308 opt.solutions(0);
309 opt.parse(argc,argv);
310 if (opt.size() >= n_examples) {
311 std::cerr << "Error: size must be between 0 and "
312 << n_examples-1 << std::endl;
313 return 1;
314 }
316 return 0;
317}
318
319namespace {
320
329
330 const int ex0_p[] = {
331 661,6,333,
332 168,489,343,
333 171,505,324
334 };
335 OpenShopSpec ex0(3,3,ex0_p);
336
337 const int ex1_p[] = {
338 54, 34, 61, 2,
339 9, 15, 89, 70,
340 38, 19, 28, 87,
341 95, 34, 7, 29
342 };
343 OpenShopSpec ex1(4,4,ex1_p);
344
345 const int ex2_p[] = {
346 5, 70, 45, 83,
347 24, 80, 58, 45,
348 29, 56, 29, 61,
349 43, 64, 45, 74
350 };
351 OpenShopSpec ex2(4,4,ex2_p);
352
353 const int ex3_p[] = {
354 89, 39, 54, 34, 71, 92, 56,
355 19, 13, 81, 46, 91, 73, 27,
356 66, 95, 48, 24, 96, 18, 14,
357 48, 46, 78, 94, 19, 68, 63,
358 60, 28, 91, 75, 52, 9, 7,
359 33, 98, 37, 11, 2, 30, 38,
360 83, 45, 37, 77, 52, 88, 52
361 };
362 OpenShopSpec ex3(7,7,ex3_p);
363
364 const int ex4_p[] = {
365 49, 58, 37, 79, 16, 64, 71, 65, 6, 44, 17, 85, 99, 57, 89, 4, 16, 8, 40, 66,
366 43, 65, 42, 35, 57, 3, 8, 65, 79, 76, 82, 80, 96, 82, 98, 57, 73, 43, 6, 20,
367 82, 49, 7, 18, 94, 76, 41, 17, 43, 15, 53, 10, 83, 24, 79, 62, 53, 77, 23, 70,
368 18, 30, 80, 7, 97, 84, 10, 27, 7, 91, 14, 12, 7, 31, 24, 97, 16, 33, 99, 15,
369 31, 65, 51, 95, 45, 70, 57, 10, 84, 52, 28, 43, 54, 40, 83, 9, 21, 57, 45, 67,
370 70, 45, 48, 39, 10, 37, 22, 53, 48, 50, 76, 48, 57, 6, 43, 13, 45, 93, 42, 11,
371 80, 5, 53, 97, 75, 22, 10, 70, 79, 92, 96, 18, 57, 3, 82, 52, 1, 21, 23, 38,
372 43, 79, 67, 57, 33, 52, 1, 44, 82, 10, 27, 23, 89, 9, 62, 6, 38, 33, 37, 22,
373 68, 20, 5, 25, 16, 80, 13, 73, 35, 36, 13, 53, 97, 50, 17, 54, 35, 86, 24, 56,
374 60, 83, 8, 81, 3, 4, 48, 14, 77, 10, 71, 57, 86, 94, 49, 36, 62, 62, 41, 56,
375 31, 77, 5, 97, 19, 19, 31, 19, 26, 41, 77, 64, 74, 11, 98, 30, 22, 22, 33, 61,
376 7, 89, 46, 13, 33, 55, 84, 16, 21, 45, 15, 71, 57, 42, 82, 13, 62, 98, 36, 45,
377 84, 90, 20, 61, 24, 59, 8, 49, 53, 53, 83, 76, 28, 62, 59, 11, 41, 2, 58, 46,
378 32, 23, 53, 5, 8, 91, 97, 53, 90, 90, 28, 16, 61, 27, 32, 74, 23, 11, 57, 20,
379 62, 85, 79, 96, 62, 85, 43, 53, 12, 36, 95, 37, 2, 48, 46, 81, 97, 54, 5, 77,
380 57, 35, 41, 55, 72, 98, 22, 81, 6, 8, 70, 64, 55, 53, 7, 38, 58, 30, 83, 81,
381 15, 11, 24, 63, 27, 90, 35, 22, 53, 22, 66, 75, 59, 80, 31, 91, 63, 82, 99, 62,
382 4, 18, 99, 6, 65, 21, 28, 93, 16, 26, 1, 16, 46, 59, 45, 90, 69, 76, 25, 53,
383 50, 24, 66, 2, 17, 85, 5, 86, 4, 88, 44, 5, 29, 19, 27, 14, 36, 57, 59, 15,
384 71, 79, 7, 61, 45, 72, 61, 45, 61, 54, 90, 33, 81, 5, 45, 64, 87, 82, 61, 8
385 };
386 OpenShopSpec ex4(20,20,ex4_p);
387
389 OpenShopSpec examples[] = { ex0, ex1, ex2, ex3, ex4 };
391 const unsigned int n_examples = sizeof(examples) / sizeof(OpenShopSpec);
392
394}
395
396// STATISTICS: example-any
Boolean variable array.
Definition int.hh:820
Passing integer arguments.
Definition int.hh:634
Integer variable array.
Definition int.hh:772
Integer variables.
Definition int.hh:371
Matrix-interface for arrays.
Handle to region.
Definition region.hpp:55
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition region.hpp:386
Options for scripts with additional size parameter
Definition driver.hh:675
Computation spaces.
Definition core.hpp:1744
Helper class for representing tasks when printing a solution.
bool operator()(const PrintTask &t1, const PrintTask &t2)
Comparison of tasks based on start time, used for sorting.
Task representation for CROSH heuristic
Definition open-shop.cpp:76
Task(int j0, int m0, int p0)
Constructor.
Definition open-shop.cpp:84
Task(void)
Default constructor.
Definition open-shop.cpp:82
void crosh(Matrix< IntArgs > &dur, int &minmakespan, int &maxmakespan)
Use Constructive Randomized Open-Shop Heuristics to compute lower and upper bounds.
Definition open-shop.cpp:96
int main(int argc, char *argv[])
Main-function.
OpenShopSpec ex3(7, 7, ex3_p)
The instances.
OpenShopSpec ex2(4, 4, ex2_p)
The instances.
const unsigned int n_examples
The number of instances.
OpenShop(const SizeOptions &opt)
The actual problem.
OpenShop(OpenShop &s)
Constructor for cloning s.
const int ex4_p[]
The instances.
OpenShopSpec ex1(4, 4, ex1_p)
The instances.
virtual void print(std::ostream &os) const
Print solution.
const int ex0_p[]
The instances.
OpenShopSpec examples[]
The instances.
virtual Space * copy(void)
Perform copying during cloning.
OpenShopSpec ex0(3, 3, ex0_p)
The instances.
virtual IntVar cost(void) const
Minimize the makespan.
const int ex3_p[]
The instances.
const int ex2_p[]
The instances.
const int ex1_p[]
The instances.
OpenShopSpec ex4(20, 20, ex4_p)
The instances.
BoolVarArray b
Precedences.
Definition open-shop.cpp:69
IntVar makespan
Makespan.
Definition open-shop.cpp:71
const OpenShopSpec & spec
The instance specification.
Definition open-shop.cpp:67
IntVarArray _start
Start times.
Definition open-shop.cpp:73
void parse(int argc, char *argv[])
Parse commandline arguments.
Definition test.cpp:120
LinearCongruentialGenerator< 2147483647, 48271, 44488, 3399 > RandomGenerator
Default values for linear congruential generator.
Definition random.hpp:120
Driver::ScriptBase< Driver::IgnoreStepOption< IntMinimizeSpace > > IntMinimizeScript
Base-class for scripts for finding solution of lowest integer cost.
Definition driver.hh:808
void assign(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatAssign vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Assign all x with variable selection vars and value selection vals.
Definition branch.cpp:111
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Branch over x with variable selection vars and value selection vals.
Definition branch.cpp:39
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
Numerical limits for integer variables.
Definition int.hh:114
Finite domain integers.
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition sort.hpp:130
Gecode toplevel namespace
BoolValBranch BOOL_VAL_MAX(void)
Select largest value.
Definition val.hpp:135
BoolVarBranch BOOL_VAR_AFC_MAX(double d=1.0, BranchTbl tbl=nullptr)
Select variable with largest accumulated failure count with decay factor d.
Definition var.hpp:404
IntAssign INT_ASSIGN_MIN(void)
Select smallest value.
Definition assign.hpp:55
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .