Generated on Sat Oct 20 2018 12:43:45 for Gecode by doxygen 1.8.13
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 
38 using namespace Gecode;
39 
40 namespace {
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 
64 class OpenShop : public IntMinimizeScript {
65 protected:
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  }
190 public:
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 
246  OpenShop(OpenShop& s) : IntMinimizeScript(s), spec(s.spec) {
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 
303 int
304 main(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  }
315  IntMinimizeScript::run<OpenShop,BAB,SizeOptions>(opt);
316  return 0;
317 }
318 
319 namespace {
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
void size(unsigned int s)
Set default size.
Definition: options.hpp:586
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
BoolVarArray b
Precedences.
Definition: open-shop.cpp:69
Options for scripts with additional size parameter
Definition: driver.hh:675
NodeType t
Type of node.
Definition: bool-expr.cpp:230
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf, FloatVarValPrint vvp)
Branch over x with variable selection vars and value selection vals.
Definition: branch.cpp:39
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
void update(Space &home, VarArray< Var > &a)
Update array to be a clone of array a.
Definition: array.hpp:995
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:386
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:49
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
Definition: options.cpp:666
virtual Space * copy(void)
Perform copying during cloning.
Definition: open-shop.cpp:254
Integer variable array.
Definition: int.hh:763
Helper class for representing tasks when printing a solution.
Definition: open-shop.cpp:265
Example: open-shop scheduling
Definition: open-shop.cpp:64
Handle to region.
Definition: region.hpp:55
Computation spaces.
Definition: core.hpp:1701
Parametric base-class for scripts.
Definition: driver.hh:729
IntVar makespan
Makespan.
Definition: open-shop.cpp:71
void iterations(unsigned int i)
Set default number of iterations.
Definition: options.hpp:461
void decay(double d)
Set default decay factor.
Definition: options.hpp:238
IntAssign INT_ASSIGN_MIN(void)
Select smallest value.
Definition: assign.hpp:55
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
const FloatNum min
Smallest allowed float value.
Definition: float.hh:846
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition: sort.hpp:130
BoolValBranch BOOL_VAL_MAX(void)
Select largest value.
Definition: val.hpp:135
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
int main(int argc, char *argv[])
Main-function.
Definition: open-shop.cpp:304
OpenShop(const SizeOptions &opt)
The actual problem.
Definition: open-shop.cpp:192
Options opt
The options.
Definition: test.cpp:97
Gecode::IntArgs i({1, 2, 3, 4})
IntVarArray _start
Start times.
Definition: open-shop.cpp:73
Task(int j0, int m0, int p0)
Constructor.
Definition: open-shop.cpp:84
unsigned int size(I &i)
Size of all ranges of range iterator i.
virtual IntVar cost(void) const
Minimize the makespan.
Definition: open-shop.cpp:260
void update(Space &home, VarImpVar< VarImp > &y)
Update this variable to be a clone of variable y.
Definition: var.hpp:116
Template for linear congruential generators.
Definition: random.hpp:46
Passing integer arguments.
Definition: int.hh:628
Boolean variable array.
Definition: int.hh:808
union Gecode::@593::NNF::@62 u
Union depending on nodetype t.
BoolVarBranch BOOL_VAR_AFC_MAX(double d, BranchTbl tbl)
Select variable with largest accumulated failure count with decay factor d.
Definition: var.hpp:404
Integer variables.
Definition: int.hh:371
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:43
void solutions(unsigned int n)
Set default number of solutions to search for.
Definition: options.hpp:283
Matrix-interface for arrays.
Definition: minimodel.hh:2048
Gecode toplevel namespace
const OpenShopSpec & spec
The instance specification.
Definition: open-shop.cpp:67
OpenShop(OpenShop &s)
Constructor for cloning s.
Definition: open-shop.cpp:246
void assign(Home home, const FloatVarArgs &x, FloatAssign fa, FloatBranchFilter bf, FloatVarValPrint vvp)
Assign all x with value selection vals.
Definition: branch.cpp:111
bool operator()(const PrintTask &t1, const PrintTask &t2)
Comparison of tasks based on start time, used for sorting.
Definition: open-shop.cpp:271
Task representation for CROSH heuristic
Definition: open-shop.cpp:76
virtual void print(std::ostream &os) const
Print solution.
Definition: open-shop.cpp:278
IntRelType swap(IntRelType irt)
Return swapped relation type of irt.
Definition: irt.hpp:37
Task(void)
Default constructor.
Definition: open-shop.cpp:82