Generated on Thu Mar 13 2014 04:39:27 for Gecode by doxygen 1.8.1.2
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: 2010-10-07 20:52:01 +1100 (Thu, 07 Oct 2010) $ by $Author: schulte $
11  * $Revision: 11473 $
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 MinimizeScript {
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:
196  enum {
198  SEARCH_RESTART
199  };
202  : spec(examples[opt.size()]),
203  b(*this, (spec.n+spec.m-2)*spec.n*spec.m/2, 0,1),
204  makespan(*this, 0, Int::Limits::max),
205  _start(*this, spec.m*spec.n, 0, Int::Limits::max) {
206 
207  Matrix<IntVarArray> start(_start, spec.m, spec.n);
208  IntArgs _dur(spec.m*spec.n, spec.p);
209  Matrix<IntArgs> dur(_dur, spec.m, spec.n);
210 
211  int minmakespan;
212  int maxmakespan;
213  crosh(dur, minmakespan, maxmakespan);
214  rel(*this, makespan <= maxmakespan);
215  rel(*this, makespan >= minmakespan);
216 
217  int k=0;
218  for (int m=0; m<spec.m; m++)
219  for (int j0=0; j0<spec.n-1; j0++)
220  for (int j1=j0+1; j1<spec.n; j1++) {
221  // The tasks on machine m of jobs j0 and j1 must be disjoint
222  rel(*this,
223  b[k] == (start(m,j0) + dur(m,j0) <= start(m,j1)));
224  rel(*this,
225  b[k++] == (start(m,j1) + dur(m,j1) > start(m,j0)));
226  }
227 
228  for (int j=0; j<spec.n; j++)
229  for (int m0=0; m0<spec.m-1; m0++)
230  for (int m1=m0+1; m1<spec.m; m1++) {
231  // The tasks in job j on machine m0 and m1 must be disjoint
232  rel(*this,
233  b[k] == (start(m0,j) + dur(m0,j) <= start(m1,j)));
234  rel(*this,
235  b[k++] == (start(m1,j) + dur(m1,j) > start(m0,j)));
236  }
237 
238  // The makespan is greater than the end time of the latest job
239  for (int m=0; m<spec.m; m++) {
240  for (int j=0; j<spec.n; j++) {
241  rel(*this, start(m,j) + dur(m,j) <= makespan);
242  }
243  }
244 
245  // First branch over the precedences
247  // When the precedences are fixed, simply assign the start times
248  assign(*this, _start, INT_ASSIGN_MIN);
249  // When the start times are fixed, use the tightest makespan
250  assign(*this, makespan, INT_ASSIGN_MIN);
251  }
252 
254  OpenShop(bool share, OpenShop& s) : MinimizeScript(share,s), spec(s.spec) {
255  b.update(*this, share, s.b);
256  makespan.update(*this, share, s.makespan);
257  _start.update(*this, share, s._start);
258  }
259 
261  virtual Space*
262  copy(bool share) {
263  return new OpenShop(share,*this);
264  }
265 
267  virtual IntVar
268  cost(void) const {
269  return makespan;
270  }
271 
273  class PrintTask {
274  public:
275  int start; //< Start time
276  int job; //< Job number
277  int p; //< Processing time
279  bool operator()(const PrintTask& t1, const PrintTask& t2) {
280  return t1.start < t2.start;
281  }
282  };
283 
285  virtual void
286  print(std::ostream& os) const {
287  Region re(*this);
288  PrintTask* m = re.alloc<PrintTask>(spec.n);
289  for (int i=0; i<spec.m; i++) {
290  int k=0;
291  for (int j=0; j<spec.n; j++) {
292  m[k].start = _start[i*spec.n+j].val();
293  m[k].job = j;
294  m[k].p = spec.p[i*spec.n+j];
295  k++;
296  }
297  Support::quicksort(m, spec.n, m[0]);
298  os << "Machine " << i << ": ";
299  for (int j=0; j<spec.n; j++)
300  os << "\t" << m[j].job << "("<<m[j].p<<")";
301  os << " = " << m[spec.n-1].start+m[spec.n-1].p << std::endl;
302  }
303  os << "Makespan: " << makespan << std::endl;
304  }
305 
306 };
307 
311 int
312 main(int argc, char* argv[]) {
313  SizeOptions opt("OpenShop");
314  opt.iterations(500);
315  opt.size(0);
316  opt.solutions(0);
318  opt.search(OpenShop::SEARCH_BAB, "bab");
319  opt.search(OpenShop::SEARCH_RESTART, "restart");
320  opt.parse(argc,argv);
321  if (opt.size() >= n_examples) {
322  std::cerr << "Error: size must be between 0 and "
323  << n_examples-1 << std::endl;
324  return 1;
325  }
326  switch (opt.search()) {
328  MinimizeScript::run<OpenShop,BAB,SizeOptions>(opt); break;
330  MinimizeScript::run<OpenShop,Restart,SizeOptions>(opt); break;
331  }
332  return 0;
333 }
334 
335 namespace {
336 
345 
346  const int ex0_p[] = {
347  661,6,333,
348  168,489,343,
349  171,505,324
350  };
351  OpenShopSpec ex0(3,3,ex0_p);
352 
353  const int ex1_p[] = {
354  54, 34, 61, 2,
355  9, 15, 89, 70,
356  38, 19, 28, 87,
357  95, 34, 7, 29
358  };
359  OpenShopSpec ex1(4,4,ex1_p);
360 
361  const int ex2_p[] = {
362  5, 70, 45, 83,
363  24, 80, 58, 45,
364  29, 56, 29, 61,
365  43, 64, 45, 74
366  };
367  OpenShopSpec ex2(4,4,ex2_p);
368 
369  const int ex3_p[] = {
370  89, 39, 54, 34, 71, 92, 56,
371  19, 13, 81, 46, 91, 73, 27,
372  66, 95, 48, 24, 96, 18, 14,
373  48, 46, 78, 94, 19, 68, 63,
374  60, 28, 91, 75, 52, 9, 7,
375  33, 98, 37, 11, 2, 30, 38,
376  83, 45, 37, 77, 52, 88, 52
377  };
378  OpenShopSpec ex3(7,7,ex3_p);
379 
380  const int ex4_p[] = {
381  49, 58, 37, 79, 16, 64, 71, 65, 6, 44, 17, 85, 99, 57, 89, 4, 16, 8, 40, 66,
382  43, 65, 42, 35, 57, 3, 8, 65, 79, 76, 82, 80, 96, 82, 98, 57, 73, 43, 6, 20,
383  82, 49, 7, 18, 94, 76, 41, 17, 43, 15, 53, 10, 83, 24, 79, 62, 53, 77, 23, 70,
384  18, 30, 80, 7, 97, 84, 10, 27, 7, 91, 14, 12, 7, 31, 24, 97, 16, 33, 99, 15,
385  31, 65, 51, 95, 45, 70, 57, 10, 84, 52, 28, 43, 54, 40, 83, 9, 21, 57, 45, 67,
386  70, 45, 48, 39, 10, 37, 22, 53, 48, 50, 76, 48, 57, 6, 43, 13, 45, 93, 42, 11,
387  80, 5, 53, 97, 75, 22, 10, 70, 79, 92, 96, 18, 57, 3, 82, 52, 1, 21, 23, 38,
388  43, 79, 67, 57, 33, 52, 1, 44, 82, 10, 27, 23, 89, 9, 62, 6, 38, 33, 37, 22,
389  68, 20, 5, 25, 16, 80, 13, 73, 35, 36, 13, 53, 97, 50, 17, 54, 35, 86, 24, 56,
390  60, 83, 8, 81, 3, 4, 48, 14, 77, 10, 71, 57, 86, 94, 49, 36, 62, 62, 41, 56,
391  31, 77, 5, 97, 19, 19, 31, 19, 26, 41, 77, 64, 74, 11, 98, 30, 22, 22, 33, 61,
392  7, 89, 46, 13, 33, 55, 84, 16, 21, 45, 15, 71, 57, 42, 82, 13, 62, 98, 36, 45,
393  84, 90, 20, 61, 24, 59, 8, 49, 53, 53, 83, 76, 28, 62, 59, 11, 41, 2, 58, 46,
394  32, 23, 53, 5, 8, 91, 97, 53, 90, 90, 28, 16, 61, 27, 32, 74, 23, 11, 57, 20,
395  62, 85, 79, 96, 62, 85, 43, 53, 12, 36, 95, 37, 2, 48, 46, 81, 97, 54, 5, 77,
396  57, 35, 41, 55, 72, 98, 22, 81, 6, 8, 70, 64, 55, 53, 7, 38, 58, 30, 83, 81,
397  15, 11, 24, 63, 27, 90, 35, 22, 53, 22, 66, 75, 59, 80, 31, 91, 63, 82, 99, 62,
398  4, 18, 99, 6, 65, 21, 28, 93, 16, 26, 1, 16, 46, 59, 45, 90, 69, 76, 25, 53,
399  50, 24, 66, 2, 17, 85, 5, 86, 4, 88, 44, 5, 29, 19, 27, 14, 36, 57, 59, 15,
400  71, 79, 7, 61, 45, 72, 61, 45, 61, 54, 90, 33, 81, 5, 45, 64, 87, 82, 61, 8
401  };
402  OpenShopSpec ex4(20,20,ex4_p);
403 
405  OpenShopSpec examples[] = { ex0, ex1, ex2, ex3, ex4 };
407  const unsigned int n_examples = sizeof(examples) / sizeof(OpenShopSpec);
408 
410 }
411 
412 // STATISTICS: example-any