this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.org>
5 *
6 * Copyright:
7 * Christian Schulte, 2019
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
36#include <gecode/int.hh>
37#include <gecode/minimodel.hh>
38
39#include <algorithm>
40#include <iostream>
41#include <iomanip>
42#include <fstream>
43
44using namespace Gecode;
45
46/*
47 * The paper uses ideas from: D. Grimes and E. Hebrard, Solving Variants
48 * of the Job Shop Scheduling Problem through Conflict-Directed Search,
49 * INFORMS Journal of Computing, Volume 27, Issue 2, 2015.
50 *
51 * Warning: this solution is a sketch and not competitive as not all
52 * techniques from the paper have been implemented.
53 *
54 */
55
56/// Default configuration settings
57namespace JobShopConfig {
58 /// Whether to print verbose information
59 static const bool verbose = false;
60
61 /// How many probes to perform
62 static const unsigned int probes = 50U;
63 /// How many failures maximal per probe
64 static const unsigned int fail_probe = 10000U;
65
66 /// How much time to spend on probing
67 static const unsigned int time_probe = 30U * 1000U;
68 /// How much time to spend on adjusting
69 static const unsigned int time_adjust = 30U * 1000U;
70 /// How much time to spend on solving
71 static const unsigned int time_solve = 60U * 1000U;
72
73 /// Restart scale factor
74 static const double restart_scale = 5000.0;
75 /// Restart base
76 static const double restart_base = 1.3;
77}
78
79// Instance data
80namespace {
81
82 // Instances
83 extern const int* js[];
84 // Instance names
85 extern const char* name[];
86
87 /// A wrapper class for instance data
88 class Spec {
89 protected:
90 /// Raw instance data
91 const int* data;
92 /// Lower and upper bound
93 int l, u;
94 /// Name
95 const char* n;
96 public:
97 /// Whether a valid specification has been found
98 bool valid(void) const {
99 return data != nullptr;
100 }
101 /// Return number of jobs
102 int jobs(void) const {
103 return data[0];
104 }
105 /// Return number of machines
106 int machines(void) const {
107 return data[1];
108 }
109 /// Return machine of step \a j in job \a i
110 int machine(int i, int j) const {
111 return data[2 + i*machines()*2 + j*2];
112 }
113 /// Return duration of step \a j in job \a i
114 int duration(int i, int j) const {
115 return data[2 + i*machines()*2 + j*2 + 1];
116 }
117 protected:
118 /// Find instance by name \a s
119 static const int* find(const char* s) {
120 for (int i=0; ::name[i] != nullptr; i++)
121 if (!strcmp(s,::name[i]))
122 return js[i];
123 return nullptr;
124 }
125 /// Compute lower bound
126 int clower(void) const {
127 int l = 0;
128 Region r;
129 int* mach = r.alloc<int>(machines());
130 for (int j=0; j<machines(); j++)
131 mach[j]=0;
132 for (int i=0; i<jobs(); i++) {
133 int job = 0;
134 for (int j=0; j<machines(); j++) {
135 mach[machine(i,j)] += duration(i,j);
136 job += duration(i,j);
137 }
138 l = std::max(l,job);
139 }
140 for (int j=0; j<machines(); j++)
141 l = std::max(l,mach[j]);
142 return l;
143 }
144 /// Compute naive upper bound
145 int cupper(void) const {
146 int u = 0;
147 for (int i=0; i<jobs(); i++)
148 for (int j=0; j<machines(); j++)
149 u += duration(i,j);
150 return u;
151 }
152 public:
153 /// Initialize
154 Spec(const char* s) : data(find(s)), l(0), u(0), n(s) {
155 if (valid()) {
156 l = clower(); u = cupper();
157 }
158 }
159 /// Return lower bound
160 int lower(void) const {
161 return l;
162 }
163 /// Return upper bound
164 int upper(void) const {
165 return u;
166 }
167 /// Return name
168 const char* name(void) const {
169 return n;
170 }
171 };
172
173}
174
175/**
176 * \brief %Options for %JobShop problems
177 *
178 */
179class JobShopOptions : public InstanceOptions {
180private:
181 /// Whether to print schedule
182 Driver::BoolOption _verbose;
183 /// How many probes
184 Driver::UnsignedIntOption _probes;
185 /// How many failures per probe
186 Driver::UnsignedIntOption _fail_probe;
187 /// Time for probing
188 Driver::UnsignedIntOption _time_probe;
189 /// Time for adjusting
190 Driver::UnsignedIntOption _time_adjust;
191 /// Time for solving
192 Driver::UnsignedIntOption _time_solve;
193 /// Tie-breaking factor
194 Driver::DoubleOption _tbf;
195public:
196 /// Initialize options for example with name \a s
197 JobShopOptions(const char* s)
198 : InstanceOptions(s),
199 _verbose("verbose","whether to print schedule",
200 JobShopConfig::verbose),
201 _probes("probes","how many probes to perform",
202 JobShopConfig::probes),
203 _fail_probe("fail-probe","failure limit per probe",
204 JobShopConfig::fail_probe),
205 _time_probe("time-probe","time-out for probing (in milliseconds)",
206 JobShopConfig::time_probe),
207 _time_adjust("time-adjust","time-out for adjusting (in milliseconds)",
208 JobShopConfig::time_adjust),
209 _time_solve("time-solve","time-out for solving (in milliseconds)",
210 JobShopConfig::time_solve),
211 _tbf("tbf", "tie-breaking factor", 0.0) {
212 add(_verbose);
213 add(_probes);
214 add(_fail_probe);
215 add(_time_probe);
216 add(_time_adjust);
217 add(_time_solve);
218 add(_tbf);
219 }
220 /// Return whether to print schedule
221 bool verbose(void) const {
222 return _verbose.value();
223 }
224 /// Return number of probes
225 unsigned int probes(void) const {
226 return _probes.value();
227 }
228 /// Return number of failures per probe
229 unsigned int fail_probe(void) const {
230 return _fail_probe.value();
231 }
232 /// Return time-out for probe
233 unsigned int time_probe(void) const {
234 return _time_probe.value();
235 }
236 /// Return time-out for adjust
237 unsigned int time_adjust(void) const {
238 return _time_adjust.value();
239 }
240 /// Return time-out for solve
241 unsigned int time_solve(void) const {
242 return _time_solve.value();
243 }
244 /// Return tie-breaking factor
245 double tbf(void) const {
246 return _tbf.value();
247 }
248 /// Print help text for list of instances
249 virtual void help(void) {
250 InstanceOptions::help();
251 std::cerr << "\tAvailable instances:" << std::endl << "\t\t";
252 for (int i=1; ::name[i] != nullptr; i++) {
253 std::cerr << ::name[i] << ", ";
254 if (i % 4 == 0)
255 std::cerr << std::endl << "\t\t";
256 }
257 std::cerr << std::endl;
258 }
259};
260
261
262/**
263 * \brief %Example: Job Shop Scheduling
264 *
265 * \ingroup Example
266 *
267 */
268class JobShopBase : public IntMinimizeScript {
269protected:
270 /// Options
271 const JobShopOptions& opt;
272 /// Specification
273 const Spec spec;
274 /// Start times for each step in a job
275 IntVarArray start;
276 /// Makespan
277 IntVar makespan;
278public:
279 /// Actual model
280 JobShopBase(const JobShopOptions& o)
281 : IntMinimizeScript(o), opt(o), spec(opt.instance()),
282 start(*this, spec.machines() * spec.jobs(), 0, spec.upper()),
283 makespan(*this, spec.lower(), spec.upper()) {
284 // Number of jobs and machines/steps
285 int n = spec.jobs(), m = spec.machines();
286 // Endtimes for each job
287 IntVarArgs end(*this, n, 0, spec.upper());
288
289 // Precedence constraints and makespan
290 for (int i=0; i<n; i++) {
291 for (int j=1; j<m; j++)
292 rel(*this, start[i*m+j-1] + spec.duration(i,j) <= start[i*m+j]);
293 rel(*this, start[i*m+m-1] + spec.duration(i,m-1) <= makespan);
294 }
295 }
296 /// Do not overload machines
297 void nooverload(void) {
298 // Number of jobs and machines/steps
299 int n = spec.jobs(), m = spec.machines();
300
301 IntVarArgs jobs(m*n);
302 IntArgs dur(m*n);
303
304 for (int i=0; i<n; i++)
305 for (int j=0; j<m; j++) {
306 jobs[spec.machine(i,j)*n+i] = start[i*m+j];
307 dur[spec.machine(i,j)*n+i] = spec.duration(i,j);
308 }
309
310 for (int j=0; j<m; j++) {
311 IntVarArgs jpm(n);
312 IntArgs dpm(n);
313 for (int i=0; i<n; i++) {
314 jpm[i] = jobs[j*n+i]; dpm[i] = dur[j*n+i];
315 }
316 unary(*this, jpm, dpm);
317 }
318 }
319 /// Return cost
320 virtual IntVar cost(void) const {
321 return makespan;
322 }
323 /// Constructor for cloning \a s
324 JobShopBase(JobShopBase& s)
325 : IntMinimizeScript(s), opt(s.opt), spec(s.spec) {
326 start.update(*this, s.start);
327 makespan.update(*this, s.makespan);
328 }
329 /// Print solution
330 virtual void
331 print(std::ostream& os) const {
332 os << "\t\t" << spec.name()
333 << " [makespan: " << makespan << "]" << std::endl;
334 if (opt.verbose()) {
335 // Number of jobs
336 int n = spec.jobs();
337 // Number of machines/steps
338 int m = spec.machines();
339 for (int i=0; i<n; i++) {
340 os << "\t\t\t[" << i << "]: ";
341 for (int j=0; j<m; j++)
342 os << start[i*m+j] << " ";
343 os << std::endl;
344 }
345 }
346 }
347};
348
349/// Common command line options
350class CommonOptions : public Search::Options {
351public:
352 /// Initialize
353 CommonOptions(const JobShopOptions& opt) {
354 clone = false;
355 threads = opt.threads();
356 c_d = opt.c_d();
357 a_d = opt.a_d();
358 nogoods_limit = opt.nogoods() ? opt.nogoods_limit() : 0U;
359 }
360};
361
362/// Model for probing
363class JobShopProbe : public JobShopBase {
364public:
365 /// Actual model
366 JobShopProbe(const JobShopOptions& o)
367 : JobShopBase(o) {
368 nooverload();
369 }
370 void branch(unsigned int p, Rnd r) {
371 switch (p) {
372 case 0U:
373 Gecode::branch(*this, start, INT_VAR_MIN_MIN(), INT_VAL_MIN());
374 break;
375 case 1U:
376 Gecode::branch(*this, start, INT_VAR_MAX_MIN(), INT_VAL_MIN());
377 break;
378 case 2U:
379 Gecode::branch(*this, start, INT_VAR_SIZE_MIN(), INT_VAL_MIN());
380 break;
381 case 3U:
382 Gecode::branch(*this, start, tiebreak(INT_VAR_MIN_MIN(),
383 INT_VAR_RND(r)), INT_VAL_MIN());
384 break;
385 case 4U:
386 Gecode::branch(*this, start, tiebreak(INT_VAR_MAX_MIN(),
387 INT_VAR_RND(r)), INT_VAL_MIN());
388 break;
389 default:
390 if (p & 1U)
391 Gecode::branch(*this, start, INT_VAR_RND(r), INT_VAL_MIN());
392 else
393 Gecode::branch(*this, start, INT_VAR_RND(r), INT_VAL_SPLIT_MIN());
394 break;
395 }
396 assign(*this, makespan, INT_ASSIGN_MIN());
397 }
398 /// Constructor for cloning \a s
399 JobShopProbe(JobShopProbe& s)
400 : JobShopBase(s) {}
401 /// Copy during cloning
402 virtual Space*
403 copy(void) {
404 return new JobShopProbe(*this);
405 }
406};
407
408/// Model for solving
409class JobShopSolve : public JobShopBase {
410protected:
411 /// Step order variables
412 BoolVarArray sorder;
413 /// Record which step is first in order
414 IntSharedArray fst;
415 /// Record which step is second in order
416 IntSharedArray snd;
417 /// AFC information
418 IntAFC iafc;
419 /// AFC-based cost
420 double afc(BoolVar x, int i) const {
421 return ((x.afc() + start[fst[i]].afc() + start[snd[i]].afc()) /
422 (start[fst[i]].size() + start[fst[i]].size()));
423 }
424 /// Trampoline function for AFC-based cost
425 static double afcmerit(const Space& home, BoolVar x, int i) {
426 return static_cast<const JobShopSolve&>(home).afc(x,i);
427 }
428 /// Action information
429 IntAction iaction; BoolAction baction;
430 /// Action-based cost
431 double action(int i) const {
432 return ((baction[i] + iaction[fst[i]] + iaction[snd[i]]) /
433 (start[fst[i]].size() + start[fst[i]].size()));
434 }
435 /// Trampoline function for Action-based cost
436 static double actionmerit(const Space& home, BoolVar, int i) {
437 return static_cast<const JobShopSolve&>(home).action(i);
438 }
439 /// CHB information
440 IntCHB ichb; BoolCHB bchb;
441 /// CHB-based cost
442 double chb(int i) const {
443 return ((bchb[i] + ichb[fst[i]] + ichb[snd[i]]) /
444 (start[fst[i]].size() + start[fst[i]].size()));
445 }
446 /// Trampoline function for CHB-based cost
447 static double chbmerit(const Space& home, BoolVar, int i) {
448 return static_cast<const JobShopSolve&>(home).chb(i);
449 }
450 /// Random number generator for probing and relaxation
451 Rnd rnd;
452public:
453 /// Branching to use
454 enum {
455 BRANCH_AFC, ///< Branch using AFC
456 BRANCH_ACTION, ///< Branch using action
457 BRANCH_CHB ///< Branch using CHB
458 };
459 /// Propagation to use
460 enum {
461 PROP_ORDER, ///< Only propagate order constraints
462 PROP_UNARY ///< Also post unary constraints
463 };
464 /// Actual model
465 JobShopSolve(const JobShopOptions& o)
466 : JobShopBase(o),
467 sorder(*this, spec.machines()*spec.jobs()*(spec.jobs()-1)/2, 0, 1),
468 rnd(o.seed()) {
469 if (opt.propagation() == PROP_UNARY)
470 nooverload();
471
472 // Number of jobs and machines/steps
473 int n = spec.jobs(), m = spec.machines();
474
475 fst.init(m*n*(n-1)/2);
476 snd.init(m*n*(n-1)/2);
477
478 IntArgs jobs(m*n), dur(m*n);
479
480 for (int i=0; i<n; i++)
481 for (int j=0; j<m; j++) {
482 jobs[spec.machine(i,j)*n+i] = i*m+j;
483 dur[spec.machine(i,j)*n+i] = spec.duration(i,j);
484 }
485
486 int l=0;
487 for (int j=0; j<m; j++) {
488 for (int i1=0; i1<n; i1++)
489 for (int i2=i1+1; i2<n; i2++) {
490 if (dur[j*n+i1] > dur[j*n+i2]) {
491 order(*this,
492 start[jobs[j*n+i1]], dur[j*n+i1],
493 start[jobs[j*n+i2]], dur[j*n+i2],
494 sorder[l]);
495 fst[l] = j*n+i1; snd[l] = j*n+i2;
496 } else {
497 order(*this,
498 start[jobs[j*n+i2]], dur[j*n+i2],
499 start[jobs[j*n+i1]], dur[j*n+i1],
500 sorder[l]);
501 fst[l] = j*n+i2; snd[l] = j*n+i1;
502 }
503 l++;
504 }
505 assert(l == (j+1)*n*(n-1)/2);
506 }
507
508 double tbf = opt.tbf();
509 switch (opt.branching()) {
510 case BRANCH_AFC:
511 iafc.init(*this,start,opt.decay());
512 if (tbf > 0.0) {
513 auto tbl =
514 [tbf] (const Space&, double w, double b) {
515 assert(b >= w);
516 return b - (b - w) * tbf;
517 };
518 branch(*this, sorder, tiebreak(BOOL_VAR_MERIT_MAX(&afcmerit,tbl),
519 BOOL_VAR_RND(rnd)),
520 BOOL_VAL_MIN());
521 } else {
522 branch(*this, sorder, BOOL_VAR_MERIT_MAX(&afcmerit),
523 BOOL_VAL_MIN());
524 }
525 break;
526 case BRANCH_ACTION:
527 iaction.init(*this,start,opt.decay());
528 baction.init(*this,sorder,opt.decay());
529 if (tbf > 0.0) {
530 auto tbl =
531 [tbf] (const Space&, double w, double b) {
532 assert(b >= w);
533 return b - (b - w) * tbf;
534 };
535 branch(*this, sorder, tiebreak(BOOL_VAR_MERIT_MAX(&actionmerit,tbl),
536 BOOL_VAR_RND(rnd)),
537 BOOL_VAL_MIN());
538 } else {
539 branch(*this, sorder, BOOL_VAR_MERIT_MAX(&actionmerit),
540 BOOL_VAL_MIN());
541 }
542 break;
543 case BRANCH_CHB:
544 ichb.init(*this,start);
545 bchb.init(*this,sorder);
546 if (tbf > 0.0) {
547 auto tbl =
548 [tbf] (const Space&, double w, double b) {
549 assert(b >= w);
550 return b - (b - w) * tbf;
551 };
552 branch(*this, sorder, tiebreak(BOOL_VAR_MERIT_MAX(&chbmerit,tbl),
553 BOOL_VAR_RND(rnd)),
554 BOOL_VAL_MIN());
555 } else {
556 branch(*this, sorder, BOOL_VAR_MERIT_MAX(&chbmerit),
557 BOOL_VAL_MIN());
558 }
559 break;
560 }
561 assign(*this, start, INT_VAR_MIN_MIN(), INT_ASSIGN_MIN());
562 assign(*this, makespan, INT_ASSIGN_MIN());
563 }
564 /// Constructor for cloning \a s
565 JobShopSolve(JobShopSolve& s)
566 : JobShopBase(s), sorder(s.sorder), fst(s.fst), snd(s.snd),
567 iafc(s.iafc), iaction(s.iaction), baction(s.baction),
568 ichb(s.ichb), bchb(s.bchb), rnd(s.rnd) {}
569 /// Copy during cloning
570 virtual Space*
571 copy(void) {
572 return new JobShopSolve(*this);
573 }
574};
575
576/// Stop object combining time and failuresa
577class FailTimeStop : public Search::Stop {
578protected:
579 Search::FailStop* fs; ///< Used fail stop object
580 Search::TimeStop* ts; ///< Used time stop object
581public:
582 /// Initialize stop object
583 FailTimeStop(unsigned int fail, unsigned int time)
584 : fs(new Search::FailStop(fail)),
585 ts(new Search::TimeStop(time)) {}
586 /// Test whether search must be stopped
587 virtual bool stop(const Search::Statistics& s, const Search::Options& o) {
588 return fs->stop(s,o) || ts->stop(s,o);
589 }
590 /// Whether the stop was due to failures
591 bool fail(const Search::Statistics& s, const Search::Options& o) const {
592 return fs->stop(s,o);
593 }
594 /// Whether the stop was due to time
595 bool time(const Search::Statistics& s, const Search::Options& o) const {
596 return ts->stop(s,o);
597 }
598 /// Destructor
599 ~FailTimeStop(void) {
600 delete fs; delete ts;
601 }
602};
603
604/// Print statistics
605void
606print(const Search::Statistics& stat, bool restart) {
607 using namespace std;
608 cout << "\t\t\tnodes: " << stat.node << endl
609 << "\t\t\tfailures: " << stat.fail << endl;
610 if (restart)
611 cout << "\t\t\trestarts: " << stat.restart << endl
612 << "\t\t\tno-goods: " << stat.nogood << endl;
613 cout << "\t\t\tpeak depth: " << stat.depth << endl;
614}
615
616/// Solver
617void
618solve(const JobShopOptions& opt) {
619 Rnd rnd(opt.seed());
620
621 /*
622 * Invariant:
623 * - There is a solution with makespan u,
624 * - There is no solution with makespan l
625 */
626
627 int l, u;
628
629 {
630 Support::Timer t; t.start();
631 Search::Statistics stat;
632 JobShopProbe* master = new JobShopProbe(opt);
633
634 if (master->status() != SS_SOLVED) {
635 delete master;
636 std::cerr << "Error: has no solution..." << std::endl;
637 return;
638 }
639
640 l = master->cost().min();
641 u = master->cost().max();
642
643 FailTimeStop fts(opt.fail_probe(),opt.time_probe());
644 CommonOptions so(opt);
645 so.stop = &fts;
646 bool stopped = false;
647
648 std::cout << "\tProbing..." << std::endl;
649
650 std::cout << "\t\tBounds: [" << l << "," << u << "]"
651 << std::endl;
652
653 for (unsigned int p=0; p<opt.probes(); p++) {
654 JobShopProbe* jsp = static_cast<JobShopProbe*>(master->clone());
655 jsp->branch(p,rnd);
656 DFS<JobShopProbe> dfs(jsp,so);
657 JobShopProbe* s = dfs.next();
658 Search::Statistics statj = dfs.statistics();
659
660 if (s != nullptr) {
661 if (u > s->cost().val()) {
662 u = s->cost().val();
663 s->print(std::cout);
664 }
665 delete s;
666 } else if (fts.time(statj,so)) {
667 stopped = true;
668 break;
669 }
670 stat += statj;
671 }
672 delete master;
673
674 print(stat,false);
675 std::cout << "\t\t\truntime: ";
676 Driver::stop(t,std::cout);
677 std::cout << std::endl;
678
679 if (stopped) {
680 std::cout << "\t\t\t\tstopped due to time-out..." << std::endl;
681 }
682 }
683
684 std::cout << std::endl << "\tAdjusting..." << std::endl;
685
686 // Dichotomic search
687 {
688 JobShopSolve* master = new JobShopSolve(opt);
689
690
691 if (master->status() == SS_FAILED) {
692 delete master;
693 std::cerr << "Error: has no solution..." << std::endl;
694 return;
695 }
696
697 {
698 Support::Timer t; t.start();
699 Search::Statistics stat;
700 CommonOptions so(opt);
701 if (opt.time_adjust() > 0U)
702 so.stop = Search::Stop::time(opt.time_adjust());
703 bool stopped = false;
704 while (l < u) {
705 std::cout << "\t\tBounds: [" << l << "," << u << "]"
706 << std::endl;
707 JobShopSolve* jss = static_cast<JobShopSolve*>(master->clone());
708 int m = (l + u) / 2;
709 rel(*jss, jss->cost() >= l);
710 rel(*jss, jss->cost() <= m);
711 so.cutoff = Search::Cutoff::geometric(JobShopConfig::restart_scale,
712 JobShopConfig::restart_base);
713 RBS<JobShopSolve,DFS> rbs(jss,so);
714 JobShopSolve* s = rbs.next();
715
716 stat += rbs.statistics();
717
718 if (s != nullptr) {
719 s->print(std::cout);
720 u = s->cost().val();
721 delete s;
722 } else if (rbs.stopped()) {
723 stopped = true;
724 break;
725 } else {
726 l = m+1;
727 }
728 }
729
730 print(stat,true);
731 std::cout << "\t\t\truntime: ";
732 Driver::stop(t,std::cout);
733 std::cout << std::endl;
734
735 if (stopped) {
736 std::cout << "\t\t\t\tstopped due to time-out..." << std::endl;
737 }
738
739 }
740
741 if (l == u) {
742 delete master;
743 std::cout << std::endl
744 << "\tFound best solution and proved optimality."
745 << std::endl;
746 return;
747 }
748
749
750 {
751 Support::Timer t; t.start();
752 std::cout << std::endl << "\tSolving..." << std::endl;
753
754 rel(*master, master->cost() >= l);
755 rel(*master, master->cost() < u);
756
757 CommonOptions so(opt);
758 if (opt.time_solve() > 0U)
759 so.stop = Search::Stop::time(opt.time_solve());
760 so.cutoff = Search::Cutoff::geometric(JobShopConfig::restart_scale,
761 JobShopConfig::restart_base);
762 RBS<JobShopSolve,BAB> rbs(master,so);
763 while (JobShopSolve* s = rbs.next()) {
764 s->print(std::cout);
765 u = s->cost().val();
766 delete s;
767 }
768
769 print(rbs.statistics(),true);
770 std::cout << "\t\t\truntime: ";
771 Driver::stop(t,std::cout);
772 std::cout << std::endl;
773
774 if (rbs.stopped()) {
775 std::cout << "\t\t\t\tstopped due to time-out..." << std::endl;
776 std::cout << std::endl
777 << "\tSolution at most ";
778 double a = (static_cast<double>(u-l+1) / u) * 100.0;
779 std::cout << std::setprecision(2) << a
780 << "% away from optimum."
781 << std::endl;
782
783 } else {
784 std::cout << std::endl
785 << "\tFound best solution and proved optimality."
786 << std::endl;
787 }
788 }
789
790 }
791}
792
793
794
795
796
797/** \brief Main-function
798 * \relates JobShop
799 */
800int
801main(int argc, char* argv[]) {
802 JobShopOptions opt("JobShop");
803
804 opt.branching(JobShopSolve::BRANCH_AFC);
805 opt.branching(JobShopSolve::BRANCH_AFC, "afc");
806 opt.branching(JobShopSolve::BRANCH_ACTION, "action");
807 opt.branching(JobShopSolve::BRANCH_CHB, "chb");
808
809 opt.propagation(JobShopSolve::PROP_UNARY);
810 opt.propagation(JobShopSolve::PROP_ORDER,"order");
811 opt.propagation(JobShopSolve::PROP_UNARY,"unary");
812
813 opt.instance("ft06");
814
815 opt.restart_base(JobShopConfig::restart_base);
816 opt.restart_scale(JobShopConfig::restart_scale);
817 opt.nogoods(true);
818
819 opt.parse(argc,argv);
820 if (!Spec(opt.instance()).valid()) {
821 std::cerr << "Error: unkown instance" << std::endl;
822 return 1;
823 }
824 solve(opt);
825 return 0;
826}
827
828#include "examples/job-shop-instances.hpp"
829
830// STATISTICS: example-any
831