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