Generated on Sat Feb 7 2015 02:01:12 for Gecode by doxygen 1.8.9.1
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: 2013-07-08 14:22:40 +0200 (Mon, 08 Jul 2013) $ by $Author: schulte $
11  * $Revision: 13820 $
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  : spec(examples[opt.size()]),
198  b(*this, (spec.n+spec.m-2)*spec.n*spec.m/2, 0,1),
199  makespan(*this, 0, Int::Limits::max),
200  _start(*this, spec.m*spec.n, 0, Int::Limits::max) {
201 
202  Matrix<IntVarArray> start(_start, spec.m, spec.n);
203  IntArgs _dur(spec.m*spec.n, spec.p);
204  Matrix<IntArgs> dur(_dur, spec.m, spec.n);
205 
206  int minmakespan;
207  int maxmakespan;
208  crosh(dur, minmakespan, maxmakespan);
209  rel(*this, makespan <= maxmakespan);
210  rel(*this, makespan >= minmakespan);
211 
212  int k=0;
213  for (int m=0; m<spec.m; m++)
214  for (int j0=0; j0<spec.n-1; j0++)
215  for (int j1=j0+1; j1<spec.n; j1++) {
216  // The tasks on machine m of jobs j0 and j1 must be disjoint
217  rel(*this,
218  b[k] == (start(m,j0) + dur(m,j0) <= start(m,j1)));
219  rel(*this,
220  b[k++] == (start(m,j1) + dur(m,j1) > start(m,j0)));
221  }
222 
223  for (int j=0; j<spec.n; j++)
224  for (int m0=0; m0<spec.m-1; m0++)
225  for (int m1=m0+1; m1<spec.m; m1++) {
226  // The tasks in job j on machine m0 and m1 must be disjoint
227  rel(*this,
228  b[k] == (start(m0,j) + dur(m0,j) <= start(m1,j)));
229  rel(*this,
230  b[k++] == (start(m1,j) + dur(m1,j) > start(m0,j)));
231  }
232 
233  // The makespan is greater than the end time of the latest job
234  for (int m=0; m<spec.m; m++) {
235  for (int j=0; j<spec.n; j++) {
236  rel(*this, start(m,j) + dur(m,j) <= makespan);
237  }
238  }
239 
240  // First branch over the precedences
241  branch(*this, b, INT_VAR_AFC_MAX(opt.decay()), INT_VAL_MAX());
242  // When the precedences are fixed, simply assign the start times
243  assign(*this, _start, INT_ASSIGN_MIN());
244  // When the start times are fixed, use the tightest makespan
245  assign(*this, makespan, INT_ASSIGN_MIN());
246  }
247 
249  OpenShop(bool share, OpenShop& s) : IntMinimizeScript(share,s), spec(s.spec) {
250  b.update(*this, share, s.b);
251  makespan.update(*this, share, s.makespan);
252  _start.update(*this, share, s._start);
253  }
254 
256  virtual Space*
257  copy(bool share) {
258  return new OpenShop(share,*this);
259  }
260 
262  virtual IntVar
263  cost(void) const {
264  return makespan;
265  }
266 
268  class PrintTask {
269  public:
270  int start; //< Start time
271  int job; //< Job number
272  int p; //< Processing time
274  bool operator()(const PrintTask& t1, const PrintTask& t2) {
275  return t1.start < t2.start;
276  }
277  };
278 
280  virtual void
281  print(std::ostream& os) const {
282  Region re(*this);
283  PrintTask* m = re.alloc<PrintTask>(spec.n);
284  for (int i=0; i<spec.m; i++) {
285  int k=0;
286  for (int j=0; j<spec.n; j++) {
287  m[k].start = _start[i*spec.n+j].val();
288  m[k].job = j;
289  m[k].p = spec.p[i*spec.n+j];
290  k++;
291  }
292  Support::quicksort(m, spec.n, m[0]);
293  os << "Machine " << i << ": ";
294  for (int j=0; j<spec.n; j++)
295  os << "\t" << m[j].job << "("<<m[j].p<<")";
296  os << " = " << m[spec.n-1].start+m[spec.n-1].p << std::endl;
297  }
298  os << "Makespan: " << makespan << std::endl;
299  }
300 
301 };
302 
306 int
307 main(int argc, char* argv[]) {
308  SizeOptions opt("OpenShop");
309  opt.iterations(500);
310  opt.size(0);
311  opt.solutions(0);
312  opt.parse(argc,argv);
313  if (opt.size() >= n_examples) {
314  std::cerr << "Error: size must be between 0 and "
315  << n_examples-1 << std::endl;
316  return 1;
317  }
318  IntMinimizeScript::run<OpenShop,BAB,SizeOptions>(opt);
319  return 0;
320 }
321 
322 namespace {
323 
332 
333  const int ex0_p[] = {
334  661,6,333,
335  168,489,343,
336  171,505,324
337  };
338  OpenShopSpec ex0(3,3,ex0_p);
339 
340  const int ex1_p[] = {
341  54, 34, 61, 2,
342  9, 15, 89, 70,
343  38, 19, 28, 87,
344  95, 34, 7, 29
345  };
346  OpenShopSpec ex1(4,4,ex1_p);
347 
348  const int ex2_p[] = {
349  5, 70, 45, 83,
350  24, 80, 58, 45,
351  29, 56, 29, 61,
352  43, 64, 45, 74
353  };
354  OpenShopSpec ex2(4,4,ex2_p);
355 
356  const int ex3_p[] = {
357  89, 39, 54, 34, 71, 92, 56,
358  19, 13, 81, 46, 91, 73, 27,
359  66, 95, 48, 24, 96, 18, 14,
360  48, 46, 78, 94, 19, 68, 63,
361  60, 28, 91, 75, 52, 9, 7,
362  33, 98, 37, 11, 2, 30, 38,
363  83, 45, 37, 77, 52, 88, 52
364  };
365  OpenShopSpec ex3(7,7,ex3_p);
366 
367  const int ex4_p[] = {
368  49, 58, 37, 79, 16, 64, 71, 65, 6, 44, 17, 85, 99, 57, 89, 4, 16, 8, 40, 66,
369  43, 65, 42, 35, 57, 3, 8, 65, 79, 76, 82, 80, 96, 82, 98, 57, 73, 43, 6, 20,
370  82, 49, 7, 18, 94, 76, 41, 17, 43, 15, 53, 10, 83, 24, 79, 62, 53, 77, 23, 70,
371  18, 30, 80, 7, 97, 84, 10, 27, 7, 91, 14, 12, 7, 31, 24, 97, 16, 33, 99, 15,
372  31, 65, 51, 95, 45, 70, 57, 10, 84, 52, 28, 43, 54, 40, 83, 9, 21, 57, 45, 67,
373  70, 45, 48, 39, 10, 37, 22, 53, 48, 50, 76, 48, 57, 6, 43, 13, 45, 93, 42, 11,
374  80, 5, 53, 97, 75, 22, 10, 70, 79, 92, 96, 18, 57, 3, 82, 52, 1, 21, 23, 38,
375  43, 79, 67, 57, 33, 52, 1, 44, 82, 10, 27, 23, 89, 9, 62, 6, 38, 33, 37, 22,
376  68, 20, 5, 25, 16, 80, 13, 73, 35, 36, 13, 53, 97, 50, 17, 54, 35, 86, 24, 56,
377  60, 83, 8, 81, 3, 4, 48, 14, 77, 10, 71, 57, 86, 94, 49, 36, 62, 62, 41, 56,
378  31, 77, 5, 97, 19, 19, 31, 19, 26, 41, 77, 64, 74, 11, 98, 30, 22, 22, 33, 61,
379  7, 89, 46, 13, 33, 55, 84, 16, 21, 45, 15, 71, 57, 42, 82, 13, 62, 98, 36, 45,
380  84, 90, 20, 61, 24, 59, 8, 49, 53, 53, 83, 76, 28, 62, 59, 11, 41, 2, 58, 46,
381  32, 23, 53, 5, 8, 91, 97, 53, 90, 90, 28, 16, 61, 27, 32, 74, 23, 11, 57, 20,
382  62, 85, 79, 96, 62, 85, 43, 53, 12, 36, 95, 37, 2, 48, 46, 81, 97, 54, 5, 77,
383  57, 35, 41, 55, 72, 98, 22, 81, 6, 8, 70, 64, 55, 53, 7, 38, 58, 30, 83, 81,
384  15, 11, 24, 63, 27, 90, 35, 22, 53, 22, 66, 75, 59, 80, 31, 91, 63, 82, 99, 62,
385  4, 18, 99, 6, 65, 21, 28, 93, 16, 26, 1, 16, 46, 59, 45, 90, 69, 76, 25, 53,
386  50, 24, 66, 2, 17, 85, 5, 86, 4, 88, 44, 5, 29, 19, 27, 14, 36, 57, 59, 15,
387  71, 79, 7, 61, 45, 72, 61, 45, 61, 54, 90, 33, 81, 5, 45, 64, 87, 82, 61, 8
388  };
389  OpenShopSpec ex4(20,20,ex4_p);
390 
392  OpenShopSpec examples[] = { ex0, ex1, ex2, ex3, ex4 };
394  const unsigned int n_examples = sizeof(examples) / sizeof(OpenShopSpec);
395 
397 }
398 
399 // STATISTICS: example-any
void size(unsigned int s)
Set default size.
Definition: options.hpp:467
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:567
NodeType t
Type of node.
Definition: bool-expr.cpp:234
const FloatNum max
Largest allowed float value.
Definition: float.hh:831
void update(Space &home, bool share, VarImpVar< VarImp > &y)
Update this variable to be a clone of variable y.
Definition: var.hpp:128
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:435
OpenShop(bool share, OpenShop &s)
Constructor for cloning s.
Definition: open-shop.cpp:249
Integer variable array.
Definition: int.hh:741
Helper class for representing tasks when printing a solution.
Definition: open-shop.cpp:268
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:622
IntVar makespan
Makespan.
Definition: open-shop.cpp:75
void iterations(unsigned int i)
Set default number of iterations.
Definition: options.hpp:385
void decay(double d)
Set default decay factor.
Definition: options.hpp:216
IntAssign INT_ASSIGN_MIN(void)
Select smallest value.
Definition: assign.hpp:59
void update(Space &, bool share, VarArray< Var > &a)
Update array to be a clone of array a.
Definition: array.hpp:1072
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:307
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
Passing integer arguments.
Definition: int.hh:607
Boolean variable array.
Definition: int.hh:786
union Gecode::@518::NNF::@57 u
Union depending on nodetype t.
IntValBranch INT_VAL_MAX(void)
Select largest value.
Definition: val.hpp:78
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:281
void solutions(unsigned int n)
Set default number of solutions to search for.
Definition: options.hpp:243
Matrix-interface for arrays.
Definition: minimodel.hh:1924
Gecode toplevel namespace
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:257
bool operator()(const PrintTask &t1, const PrintTask &t2)
Comparison of tasks based on start time, used for sorting.
Definition: open-shop.cpp:274
virtual IntVar cost(void) const
Minimize the makespan.
Definition: open-shop.cpp:263
Task representation for CROSH heuristic
Definition: open-shop.cpp:80
Task(void)
Default constructor.
Definition: open-shop.cpp:86