Generated on for Gecode by doxygen 1.17.0
job-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 * Christian Schulte <schulte@gecode.dev>
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.dev
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
57namespace JobShopConfig {
59 static const bool verbose = false;
60
62 static const unsigned int probes = 50U;
64 static const unsigned int fail_probe = 10000U;
65
67 static const unsigned int time_probe = 30U * 1000U;
69 static const unsigned int time_adjust = 30U * 1000U;
71 static const unsigned int time_solve = 60U * 1000U;
72
74 static const double restart_scale = 5000.0;
76 static const double restart_base = 1.3;
77}
78
79// Instance data
80namespace {
81
94 const char* instance_spec = R"(format jobshop
95
96comment "#" "+++"
97instances {
98 sections skip other {
99 "instance {name:word}" optional
100 "{n_jobs:1..} {n_machines:1..}" last {
101 check n_jobs <= (gecode.int_max - 2) / 2 / n_machines "there are too many jobs and machines"
102
103 repeat n_jobs as jobs {
104 each job
105 repeat n_machines as steps {
106 each step
107 machine: 0..<n_machines
108 duration: 0..
109 }
110 }
111 }
112 }
113
114 check distinct(job.machine) "a job uses a machine twice; each job must use every machine once"
115 check sum(j in jobs: sum(j.duration)) <= gecode.int_max "the total duration is too large"
116}
117)";
118
119 // Instances
120 extern const int* js[];
121 // Instance names
122 extern const char* name[];
123
125 class Spec {
126 protected:
128 const int* data;
130 IntSharedArray file;
132 int l, u;
134 const char* n;
135 public:
137 bool valid(void) const {
138 return data != nullptr;
139 }
141 int jobs(void) const {
142 return data[0];
143 }
145 int machines(void) const {
146 return data[1];
147 }
149 int machine(int i, int j) const {
150 return data[2 + i*machines()*2 + j*2];
151 }
153 int duration(int i, int j) const {
154 return data[2 + i*machines()*2 + j*2 + 1];
155 }
156 protected:
158 static const int* find(const char* s) {
159 if (s == nullptr)
160 return nullptr;
161 for (int i=0; ::name[i] != nullptr; i++)
162 if (!strcmp(s,::name[i]))
163 return js[i];
164 return nullptr;
165 }
167 int clower(void) const {
168 int l = 0;
169 Region r;
170 int* mach = r.alloc<int>(machines());
171 for (int j=0; j<machines(); j++)
172 mach[j]=0;
173 for (int i=0; i<jobs(); i++) {
174 int job = 0;
175 for (int j=0; j<machines(); j++) {
176 mach[machine(i,j)] += duration(i,j);
177 job += duration(i,j);
178 }
179 l = std::max(l,job);
180 }
181 for (int j=0; j<machines(); j++)
182 l = std::max(l,mach[j]);
183 return l;
184 }
186 int cupper(void) const {
187 int u = 0;
188 for (int i=0; i<jobs(); i++)
189 for (int j=0; j<machines(); j++)
190 u += duration(i,j);
191 return u;
192 }
194 void read(const InstanceOptions& opt) {
195 // The spec has checked the data
196 Instance::Data d = opt.data();
197 int j = static_cast<int>(d.integer("n_jobs")), m = static_cast<int>(d.integer("n_machines"));
198 IntArgs mach = d.ints("machine"), dur = d.ints("duration");
199 IntArgs a(2 + 2*j*m);
200 a[0] = j; a[1] = m;
201 for (int i=0; i<j*m; i++) {
202 a[2 + 2*i] = mach[i];
203 a[2 + 2*i + 1] = dur[i];
204 }
205 file = IntSharedArray(a);
206 data = &file[0];
207 }
208 public:
215 Spec(const InstanceOptions& opt) : data(find(opt.instance())), l(0), u(0), n(opt.instance()) {
216 if ((data == nullptr) && opt.is_file())
217 read(opt);
218 if (valid()) {
219 l = clower(); u = cupper();
220 }
221 }
223 int lower(void) const {
224 return l;
225 }
227 int upper(void) const {
228 return u;
229 }
231 const char* name(void) const {
232 return n;
233 }
234 };
235
236}
237
243private:
245 Driver::BoolOption _verbose;
249 Driver::UnsignedIntOption _fail_probe;
251 Driver::UnsignedIntOption _time_probe;
253 Driver::UnsignedIntOption _time_adjust;
255 Driver::UnsignedIntOption _time_solve;
258public:
260 JobShopOptions(const char* s)
261 : InstanceOptions(s, instance_spec),
262 _verbose("verbose","whether to print schedule",
264 _probes("probes","how many probes to perform",
266 _fail_probe("fail-probe","failure limit per probe",
268 _time_probe("time-probe","time-out for probing (in milliseconds)",
270 _time_adjust("time-adjust","time-out for adjusting (in milliseconds)",
272 _time_solve("time-solve","time-out for solving (in milliseconds)",
274 _tbf("tbf", "tie-breaking factor", 0.0) {
275 add(_verbose);
276 add(_probes);
277 add(_fail_probe);
278 add(_time_probe);
279 add(_time_adjust);
280 add(_time_solve);
281 add(_tbf);
282 }
283
284 bool verbose(void) const {
285 return _verbose.value();
286 }
287
288 unsigned int probes(void) const {
289 return _probes.value();
290 }
291
292 unsigned int fail_probe(void) const {
293 return _fail_probe.value();
294 }
295
296 unsigned int time_probe(void) const {
297 return _time_probe.value();
298 }
299
300 unsigned int time_adjust(void) const {
301 return _time_adjust.value();
302 }
303
304 unsigned int time_solve(void) const {
305 return _time_solve.value();
306 }
307
308 double tbf(void) const {
309 return _tbf.value();
310 }
311
312 virtual void help(void) {
314 std::cerr << "\tAvailable instances:" << std::endl << "\t\t";
315 for (int i=1; ::name[i] != nullptr; i++) {
316 std::cerr << ::name[i] << ", ";
317 if (i % 4 == 0)
318 std::cerr << std::endl << "\t\t";
319 }
320 std::cerr << std::endl;
321 }
322};
323
324
340protected:
344 const Spec spec;
349public:
352 : IntMinimizeScript(o), opt(o), spec(opt),
353 start(*this, spec.machines() * spec.jobs(), 0, spec.upper()),
354 makespan(*this, spec.lower(), spec.upper()) {
355 // Number of jobs and machines/steps
356 int n = spec.jobs(), m = spec.machines();
357 // Endtimes for each job
358 IntVarArgs end(*this, n, 0, spec.upper());
359
360 // Precedence constraints and makespan
361 for (int i=0; i<n; i++) {
362 for (int j=1; j<m; j++)
363 rel(*this, start[i*m+j-1] + spec.duration(i,j) <= start[i*m+j]);
364 rel(*this, start[i*m+m-1] + spec.duration(i,m-1) <= makespan);
365 }
366 }
367
368 void nooverload(void) {
369 // Number of jobs and machines/steps
370 int n = spec.jobs(), m = spec.machines();
371
372 IntVarArgs jobs(m*n);
373 IntArgs dur(m*n);
374
375 for (int i=0; i<n; i++)
376 for (int j=0; j<m; j++) {
377 jobs[spec.machine(i,j)*n+i] = start[i*m+j];
378 dur[spec.machine(i,j)*n+i] = spec.duration(i,j);
379 }
380
381 for (int j=0; j<m; j++) {
382 IntVarArgs jpm(n);
383 IntArgs dpm(n);
384 for (int i=0; i<n; i++) {
385 jpm[i] = jobs[j*n+i]; dpm[i] = dur[j*n+i];
386 }
387 unary(*this, jpm, dpm);
388 }
389 }
390
391 virtual IntVar cost(void) const {
392 return makespan;
393 }
394
396 : IntMinimizeScript(s), opt(s.opt), spec(s.spec) {
397 start.update(*this, s.start);
398 makespan.update(*this, s.makespan);
399 }
400
401 virtual void
402 print(std::ostream& os) const {
403 os << "\t\t" << spec.name()
404 << " [makespan: " << makespan << "]" << std::endl;
405 if (opt.verbose()) {
406 // Number of jobs
407 int n = spec.jobs();
408 // Number of machines/steps
409 int m = spec.machines();
410 for (int i=0; i<n; i++) {
411 os << "\t\t\t[" << i << "]: ";
412 for (int j=0; j<m; j++)
413 os << start[i*m+j] << " ";
414 os << std::endl;
415 }
416 }
417 }
418};
419
422public:
425 clone = false;
426 threads = opt.threads();
427 c_d = opt.c_d();
428 a_d = opt.a_d();
429 nogoods_limit = opt.nogoods() ? opt.nogoods_limit() : 0U;
430 }
431};
432
434class JobShopProbe : public JobShopBase {
435public:
438 : JobShopBase(o) {
439 nooverload();
440 }
441 void branch(unsigned int p, Rnd r) {
442 switch (p) {
443 case 0U:
445 break;
446 case 1U:
448 break;
449 case 2U:
451 break;
452 case 3U:
454 INT_VAR_RND(r)), INT_VAL_MIN());
455 break;
456 case 4U:
458 INT_VAR_RND(r)), INT_VAL_MIN());
459 break;
460 default:
461 if (p & 1U)
463 else
465 break;
466 }
467 assign(*this, makespan, INT_ASSIGN_MIN());
468 }
469
472
473 virtual Space*
474 copy(void) {
475 return new JobShopProbe(*this);
476 }
477};
478
480class JobShopSolve : public JobShopBase {
481protected:
491 double afc(BoolVar x, int i) const {
492 return ((x.afc() + start[fst[i]].afc() + start[snd[i]].afc()) /
493 (start[fst[i]].size() + start[fst[i]].size()));
494 }
495
496 static double afcmerit(const Space& home, BoolVar x, int i) {
497 return static_cast<const JobShopSolve&>(home).afc(x,i);
498 }
499
502 double action(int i) const {
503 return ((baction[i] + iaction[fst[i]] + iaction[snd[i]]) /
504 (start[fst[i]].size() + start[fst[i]].size()));
505 }
506
507 static double actionmerit(const Space& home, BoolVar, int i) {
508 return static_cast<const JobShopSolve&>(home).action(i);
509 }
510
513 double chb(int i) const {
514 return ((bchb[i] + ichb[fst[i]] + ichb[snd[i]]) /
515 (start[fst[i]].size() + start[fst[i]].size()));
516 }
517
518 static double chbmerit(const Space& home, BoolVar, int i) {
519 return static_cast<const JobShopSolve&>(home).chb(i);
520 }
521
523public:
525 enum {
529 };
531 enum {
534 };
537 : JobShopBase(o),
538 sorder(*this, spec.machines()*spec.jobs()*(spec.jobs()-1)/2, 0, 1),
539 rnd(o.seed()) {
540 if (opt.propagation() == PROP_UNARY)
541 nooverload();
542
543 // Number of jobs and machines/steps
544 int n = spec.jobs(), m = spec.machines();
545
546 fst.init(m*n*(n-1)/2);
547 snd.init(m*n*(n-1)/2);
548
549 IntArgs jobs(m*n), dur(m*n);
550
551 for (int i=0; i<n; i++)
552 for (int j=0; j<m; j++) {
553 jobs[spec.machine(i,j)*n+i] = i*m+j;
554 dur[spec.machine(i,j)*n+i] = spec.duration(i,j);
555 }
556
557 int l=0;
558 for (int j=0; j<m; j++) {
559 for (int i1=0; i1<n; i1++)
560 for (int i2=i1+1; i2<n; i2++) {
561 if (dur[j*n+i1] > dur[j*n+i2]) {
562 order(*this,
563 start[jobs[j*n+i1]], dur[j*n+i1],
564 start[jobs[j*n+i2]], dur[j*n+i2],
565 sorder[l]);
566 fst[l] = j*n+i1; snd[l] = j*n+i2;
567 } else {
568 order(*this,
569 start[jobs[j*n+i2]], dur[j*n+i2],
570 start[jobs[j*n+i1]], dur[j*n+i1],
571 sorder[l]);
572 fst[l] = j*n+i2; snd[l] = j*n+i1;
573 }
574 l++;
575 }
576 assert(l == (j+1)*n*(n-1)/2);
577 }
578
579 double tbf = opt.tbf();
580 switch (opt.branching()) {
581 case BRANCH_AFC:
582 iafc.init(*this,start,opt.decay());
583 if (tbf > 0.0) {
584 auto tbl =
585 [tbf] (const Space&, double w, double b) {
586 assert(b >= w);
587 return b - (b - w) * tbf;
588 };
589 branch(*this, sorder, tiebreak(BOOL_VAR_MERIT_MAX(&afcmerit,tbl),
590 BOOL_VAR_RND(rnd)),
591 BOOL_VAL_MIN());
592 } else {
593 branch(*this, sorder, BOOL_VAR_MERIT_MAX(&afcmerit),
594 BOOL_VAL_MIN());
595 }
596 break;
597 case BRANCH_ACTION:
598 iaction.init(*this,start,opt.decay());
599 baction.init(*this,sorder,opt.decay());
600 if (tbf > 0.0) {
601 auto tbl =
602 [tbf] (const Space&, double w, double b) {
603 assert(b >= w);
604 return b - (b - w) * tbf;
605 };
608 BOOL_VAL_MIN());
609 } else {
611 BOOL_VAL_MIN());
612 }
613 break;
614 case BRANCH_CHB:
615 ichb.init(*this,start);
616 bchb.init(*this,sorder);
617 if (tbf > 0.0) {
618 auto tbl =
619 [tbf] (const Space&, double w, double b) {
620 assert(b >= w);
621 return b - (b - w) * tbf;
622 };
625 BOOL_VAL_MIN());
626 } else {
628 BOOL_VAL_MIN());
629 }
630 break;
631 }
633 assign(*this, makespan, INT_ASSIGN_MIN());
634 }
635
637 : JobShopBase(s), sorder(s.sorder), fst(s.fst), snd(s.snd),
639 ichb(s.ichb), bchb(s.bchb), rnd(s.rnd) {}
640
641 virtual Space*
642 copy(void) {
643 return new JobShopSolve(*this);
644 }
645};
646
649protected:
652public:
654 FailTimeStop(unsigned int fail, unsigned int time)
655 : fs(new Search::FailStop(fail)),
656 ts(new Search::TimeStop(time)) {}
657
658 virtual bool stop(const Search::Statistics& s, const Search::Options& o) {
659 return fs->stop(s,o) || ts->stop(s,o);
660 }
661
662 bool fail(const Search::Statistics& s, const Search::Options& o) const {
663 return fs->stop(s,o);
664 }
665
666 bool time(const Search::Statistics& s, const Search::Options& o) const {
667 return ts->stop(s,o);
668 }
669
671 delete fs; delete ts;
672 }
673};
674
676void
677print(const Search::Statistics& stat, bool restart) {
678 using namespace std;
679 cout << "\t\t\tnodes: " << stat.node << endl
680 << "\t\t\tfailures: " << stat.fail << endl;
681 if (restart)
682 cout << "\t\t\trestarts: " << stat.restart << endl
683 << "\t\t\tno-goods: " << stat.nogood << endl;
684 cout << "\t\t\tpeak depth: " << stat.depth << endl;
685}
686
688void
690 Rnd rnd(opt.seed());
691
692 /*
693 * Invariant:
694 * - There is a solution with makespan u,
695 * - There is no solution with makespan l
696 */
697
698 int l, u;
699
700 {
701 Support::Timer t; t.start();
703 JobShopProbe* master = new JobShopProbe(opt);
704
705 if (master->status() != SS_SOLVED) {
706 delete master;
707 std::cerr << "Error: has no solution..." << std::endl;
708 return;
709 }
710
711 l = master->cost().min();
712 u = master->cost().max();
713
714 FailTimeStop fts(opt.fail_probe(),opt.time_probe());
715 CommonOptions so(opt);
716 so.stop = &fts;
717 bool stopped = false;
718
719 std::cout << "\tProbing..." << std::endl;
720
721 std::cout << "\t\tBounds: [" << l << "," << u << "]"
722 << std::endl;
723
724 for (unsigned int p=0; p<opt.probes(); p++) {
725 JobShopProbe* jsp = static_cast<JobShopProbe*>(master->clone());
726 jsp->branch(p,rnd);
727 DFS<JobShopProbe> dfs(jsp,so);
728 JobShopProbe* s = dfs.next();
729 Search::Statistics statj = dfs.statistics();
730
731 if (s != nullptr) {
732 if (u > s->cost().val()) {
733 u = s->cost().val();
734 s->print(std::cout);
735 }
736 delete s;
737 } else if (fts.time(statj,so)) {
738 stopped = true;
739 break;
740 }
741 stat += statj;
742 }
743 delete master;
744
745 print(stat,false);
746 std::cout << "\t\t\truntime: ";
747 Driver::stop(t,std::cout);
748 std::cout << std::endl;
749
750 if (stopped) {
751 std::cout << "\t\t\t\tstopped due to time-out..." << std::endl;
752 }
753 }
754
755 std::cout << std::endl << "\tAdjusting..." << std::endl;
756
757 // Dichotomic search
758 {
759 JobShopSolve* master = new JobShopSolve(opt);
760
761
762 if (master->status() == SS_FAILED) {
763 delete master;
764 std::cerr << "Error: has no solution..." << std::endl;
765 return;
766 }
767
768 {
769 Support::Timer t; t.start();
771 CommonOptions so(opt);
772 if (opt.time_adjust() > 0U)
773 so.stop = Search::Stop::time(opt.time_adjust());
774 bool stopped = false;
775 while (l < u) {
776 std::cout << "\t\tBounds: [" << l << "," << u << "]"
777 << std::endl;
778 JobShopSolve* jss = static_cast<JobShopSolve*>(master->clone());
779 int m = (l + u) / 2;
780 rel(*jss, jss->cost() >= l);
781 rel(*jss, jss->cost() <= m);
782 so.cutoff = Search::Cutoff::geometric(JobShopConfig::restart_scale,
783 JobShopConfig::restart_base);
785 JobShopSolve* s = rbs.next();
786
787 stat += rbs.statistics();
788
789 if (s != nullptr) {
790 s->print(std::cout);
791 u = s->cost().val();
792 delete s;
793 } else if (rbs.stopped()) {
794 stopped = true;
795 break;
796 } else {
797 l = m+1;
798 }
799 }
800
801 print(stat,true);
802 std::cout << "\t\t\truntime: ";
803 Driver::stop(t,std::cout);
804 std::cout << std::endl;
805
806 if (stopped) {
807 std::cout << "\t\t\t\tstopped due to time-out..." << std::endl;
808 }
809
810 }
811
812 if (l == u) {
813 delete master;
814 std::cout << std::endl
815 << "\tFound best solution and proved optimality."
816 << std::endl;
817 return;
818 }
819
820
821 {
822 Support::Timer t; t.start();
823 std::cout << std::endl << "\tSolving..." << std::endl;
824
825 rel(*master, master->cost() >= l);
826 rel(*master, master->cost() < u);
827
828 CommonOptions so(opt);
829 if (opt.time_solve() > 0U)
830 so.stop = Search::Stop::time(opt.time_solve());
831 so.cutoff = Search::Cutoff::geometric(JobShopConfig::restart_scale,
832 JobShopConfig::restart_base);
833 RBS<JobShopSolve,BAB> rbs(master,so);
834 while (JobShopSolve* s = rbs.next()) {
835 s->print(std::cout);
836 u = s->cost().val();
837 delete s;
838 }
839
840 print(rbs.statistics(),true);
841 std::cout << "\t\t\truntime: ";
842 Driver::stop(t,std::cout);
843 std::cout << std::endl;
844
845 if (rbs.stopped()) {
846 std::cout << "\t\t\t\tstopped due to time-out..." << std::endl;
847 std::cout << std::endl
848 << "\tSolution at most ";
849 double a = (static_cast<double>(u-l+1) / u) * 100.0;
850 std::cout << std::setprecision(2) << a
851 << "% away from optimum."
852 << std::endl;
853
854 } else {
855 std::cout << std::endl
856 << "\tFound best solution and proved optimality."
857 << std::endl;
858 }
859 }
860
861 }
862}
863
864
865
866
867
871int
872main(int argc, char* argv[]) {
873 JobShopOptions opt("JobShop");
874
875 opt.branching(JobShopSolve::BRANCH_AFC);
876 opt.branching(JobShopSolve::BRANCH_AFC, "afc");
877 opt.branching(JobShopSolve::BRANCH_ACTION, "action");
878 opt.branching(JobShopSolve::BRANCH_CHB, "chb");
879
880 opt.propagation(JobShopSolve::PROP_UNARY);
881 opt.propagation(JobShopSolve::PROP_ORDER,"order");
882 opt.propagation(JobShopSolve::PROP_UNARY,"unary");
883
884 opt.instance("ft06");
885
886 opt.restart_base(JobShopConfig::restart_base);
887 opt.restart_scale(JobShopConfig::restart_scale);
888 opt.nogoods(true);
889
890 opt.parse(argc,argv);
891 try {
892 if (!Spec(opt).valid()) {
893 std::cerr << "Error: unknown instance" << std::endl;
894 return 1;
895 }
896 } catch (const Instance::Error& e) {
897 std::cerr << e.what() << std::endl;
898 return 1;
899 }
900 solve(opt);
901 return 0;
902}
903
905
906// STATISTICS: example-any
907
Common command line options.
Definition job-shop.cpp:421
CommonOptions(const JobShopOptions &opt)
Initialize.
Definition job-shop.cpp:424
Stop object combining time and failuresa.
Definition job-shop.cpp:648
bool fail(const Search::Statistics &s, const Search::Options &o) const
Whether the stop was due to failures.
Definition job-shop.cpp:662
virtual bool stop(const Search::Statistics &s, const Search::Options &o)
Test whether search must be stopped.
Definition job-shop.cpp:658
~FailTimeStop(void)
Destructor.
Definition job-shop.cpp:670
Search::FailStop * fs
Used fail stop object.
Definition job-shop.cpp:650
FailTimeStop(unsigned int fail, unsigned int time)
Initialize stop object.
Definition job-shop.cpp:654
Search::TimeStop * ts
Used time stop object.
Definition job-shop.cpp:651
bool time(const Search::Statistics &s, const Search::Options &o) const
Whether the stop was due to time.
Definition job-shop.cpp:666
void add(Driver::BaseOption &o)
Add new option o.
Definition options.cpp:537
const char * name(void) const
Return name of script.
Definition options.hpp:204
Recording actions for Boolean variables.
Definition int.hh:5516
Recording CHB for Boolean variables.
Definition int.hh:5617
Boolean variable array.
Definition int.hh:840
Boolean integer variables.
Definition int.hh:534
Depth-first search engine.
Definition search.hh:1211
Boolean option.
Definition driver.hh:305
Unsigned integer option.
Definition driver.hh:244
virtual void help(void)
Print help text.
Definition options.cpp:826
InstanceOptions(const char *s)
Initialize options for script with name s.
Definition options.cpp:783
Exception for errors in specs and instance files
Definition instance.hh:337
virtual const char * what(void) const noexcept override
Return the full message.
Definition data.cpp:56
Recording AFC information for integer variables.
Definition int.hh:5379
Recording actions for integer variables.
Definition int.hh:5465
Passing integer arguments.
Definition int.hh:653
Recording CHB for integer variables.
Definition int.hh:5573
Passing integer variables.
Definition int.hh:681
Integer variable array.
Definition int.hh:792
Integer variables.
Definition int.hh:390
int min(void) const
Return minimum of domain.
Definition int.hpp:62
int val(void) const
Return assigned value.
Definition int.hpp:56
int max(void) const
Return maximum of domain.
Definition int.hpp:70
Meta-engine performing restart-based search.
Definition search.hh:1471
Random number generator.
Definition rnd.hpp:42
static Cutoff * geometric(unsigned long long int scale=Config::slice, double base=Config::base)
Definition cutoff.cpp:160
Stop-object based on number of failures
Definition search.hh:978
Search engine options
Definition search.hh:848
unsigned int c_d
Create a clone after every c_d commits (commit distance).
Definition search.hh:863
bool clone
Whether engines create a clone when being initialized.
Definition search.hh:851
Cutoff * cutoff
Cutoff for restart-based search.
Definition search.hh:877
unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance).
Definition search.hh:865
Stop * stop
Stop object for stopping search.
Definition search.hh:875
unsigned int nogoods_limit
Depth limit for extraction of no-goods.
Definition search.hh:873
double threads
Number of threads to use.
Definition search.hh:853
Search engine statistics
Definition search.hh:155
unsigned long int restart
Number of restarts.
Definition search.hh:164
unsigned long int depth
Maximum depth of search stack.
Definition search.hh:162
unsigned long long int fail
Number of failed nodes in search tree.
Definition search.hh:158
unsigned long long int node
Number of nodes expanded.
Definition search.hh:160
unsigned long int nogood
Number of no-goods posted.
Definition search.hh:166
Base-class for Stop-object.
Definition search.hh:919
static Stop * time(double l)
Stop if time limit l (in milliseconds) has been exceeded.
Definition stop.cpp:55
Stop-object based on time
Definition search.hh:1006
Computation spaces.
Definition core.hpp:1787
void start(void)
Start timer.
Definition timer.hpp:58
double afc(void) const
Return accumulated failure count.
Definition var.hpp:106
virtual void print(std::ostream &os) const
Print solution.
Definition job-shop.cpp:402
const JobShopOptions & opt
Options.
Definition job-shop.cpp:342
IntVarArray start
Start times for each step in a job.
Definition job-shop.cpp:346
JobShopBase(JobShopBase &s)
Constructor for cloning s.
Definition job-shop.cpp:395
IntVar makespan
Makespan.
Definition job-shop.cpp:348
virtual IntVar cost(void) const
Return cost.
Definition job-shop.cpp:391
const Spec spec
Specification.
Definition job-shop.cpp:344
void nooverload(void)
Do not overload machines.
Definition job-shop.cpp:368
JobShopBase(const JobShopOptions &o)
Actual model.
Definition job-shop.cpp:351
Options for JobShop problems
Definition job-shop.cpp:242
unsigned int fail_probe(void) const
Return number of failures per probe.
Definition job-shop.cpp:292
JobShopOptions(const char *s)
Initialize options for example with name s.
Definition job-shop.cpp:260
unsigned int time_probe(void) const
Return time-out for probe.
Definition job-shop.cpp:296
unsigned int time_adjust(void) const
Return time-out for adjust.
Definition job-shop.cpp:300
virtual void help(void)
Print help text for list of instances.
Definition job-shop.cpp:312
bool verbose(void) const
Return whether to print schedule.
Definition job-shop.cpp:284
unsigned int time_solve(void) const
Return time-out for solve.
Definition job-shop.cpp:304
unsigned int probes(void) const
Return number of probes.
Definition job-shop.cpp:288
double tbf(void) const
Return tie-breaking factor.
Definition job-shop.cpp:308
Model for probing.
Definition job-shop.cpp:434
void branch(unsigned int p, Rnd r)
Definition job-shop.cpp:441
JobShopProbe(JobShopProbe &s)
Constructor for cloning s.
Definition job-shop.cpp:470
virtual Space * copy(void)
Copy during cloning.
Definition job-shop.cpp:474
JobShopProbe(const JobShopOptions &o)
Actual model.
Definition job-shop.cpp:437
Model for solving.
Definition job-shop.cpp:480
IntCHB ichb
CHB information.
Definition job-shop.cpp:511
virtual Space * copy(void)
Copy during cloning.
Definition job-shop.cpp:642
IntSharedArray snd
Record which step is second in order.
Definition job-shop.cpp:487
JobShopSolve(const JobShopOptions &o)
Actual model.
Definition job-shop.cpp:536
static double chbmerit(const Space &home, BoolVar, int i)
Trampoline function for CHB-based cost.
Definition job-shop.cpp:518
@ PROP_UNARY
Also post unary constraints.
Definition job-shop.cpp:533
@ PROP_ORDER
Only propagate order constraints.
Definition job-shop.cpp:532
static double afcmerit(const Space &home, BoolVar x, int i)
Trampoline function for AFC-based cost.
Definition job-shop.cpp:496
IntAFC iafc
AFC information.
Definition job-shop.cpp:489
IntAction iaction
Action information.
Definition job-shop.cpp:500
BoolVarArray sorder
Step order variables.
Definition job-shop.cpp:483
double chb(int i) const
CHB-based cost.
Definition job-shop.cpp:513
double action(int i) const
Action-based cost.
Definition job-shop.cpp:502
Rnd rnd
Random number generator for probing and relaxation.
Definition job-shop.cpp:522
BoolAction baction
Definition job-shop.cpp:500
double afc(BoolVar x, int i) const
AFC-based cost.
Definition job-shop.cpp:491
BoolCHB bchb
Definition job-shop.cpp:511
IntSharedArray fst
Record which step is first in order.
Definition job-shop.cpp:485
@ BRANCH_AFC
Branch using AFC.
Definition job-shop.cpp:526
@ BRANCH_ACTION
Branch using action.
Definition job-shop.cpp:527
@ BRANCH_CHB
Branch using CHB.
Definition job-shop.cpp:528
static double actionmerit(const Space &home, BoolVar, int i)
Trampoline function for Action-based cost.
Definition job-shop.cpp:507
JobShopSolve(JobShopSolve &s)
Constructor for cloning s.
Definition job-shop.cpp:636
void parse(int argc, char *argv[])
Parse commandline arguments.
Definition test.cpp:177
unsigned int seed
The random seed to be used.
Definition test.hh:138
unsigned int threads
Number of threads to use.
Definition test.hh:136
Driver::ScriptBase< Driver::IgnoreStepOption< IntMinimizeSpace > > IntMinimizeScript
Base-class for scripts for finding solution of lowest integer cost.
Definition driver.hh:1009
void assign(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatAssign vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Assign all x with variable selection vars and value selection vals.
Definition branch.cpp:111
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Branch over x with variable selection vars and value selection vals.
Definition branch.cpp:39
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
T * rbs(T *s, const Search::Options &o)
Perform restart-based search.
Definition rbs.hpp:132
@ SS_SOLVED
Space is solved (no brancher left)
Definition core.hpp:1728
@ SS_FAILED
Space is failed
Definition core.hpp:1727
void solve(const JobShopOptions &opt)
Solver.
Definition job-shop.cpp:689
int main(void)
Definition main.cpp:15
void stop(Support::Timer &timer, std::ostream &os)
Get time since start of timer and print user friendly time information.
Definition script.cpp:42
bool valid(const FloatVal &n)
Return whether float n is a valid number.
Definition limits.hpp:39
Search engines
void print(std::basic_ostream< Char, Traits > &s, bool assigned, IL &lb, IU &ub, unsigned int cardMin, unsigned int cardMax)
Print set view.
Definition print.hpp:63
Gecode toplevel namespace
IntValBranch INT_VAL_SPLIT_MIN(void)
Select values not greater than mean of smallest and largest value.
Definition val.hpp:75
void order(Home home, IntVar s0, int p0, IntVar s1, int p1, BoolVar b, IntPropLevel ipl=IPL_DEF)
Post propagators for ordering two tasks.
Definition order.cpp:41
SharedArray< int > IntSharedArray
Arrays of integers that can be shared among several element constraints.
Definition int.hh:1813
TieBreak< VarBranch > tiebreak(VarBranch a, VarBranch b)
Combine variable selection criteria a and b for tie-breaking.
Definition tiebreak.hpp:80
BoolValBranch BOOL_VAL_MIN(void)
Select smallest value.
Definition val.hpp:130
BoolVarBranch BOOL_VAR_RND(Rnd r)
Select random variable (uniform distribution, for tie breaking).
Definition var.hpp:369
IntVarBranch INT_VAR_MAX_MIN(BranchTbl tbl=nullptr)
Select variable with smallest max.
Definition var.hpp:196
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition val.hpp:55
T * dfs(T *s, const Search::Options &o=Search::Options::def)
Invoke depth-first search engine for subclass T of space s with options o.
Definition dfs.hpp:73
IntAssign INT_ASSIGN_MIN(void)
Select smallest value.
Definition assign.hpp:55
IntVarBranch INT_VAR_RND(Rnd r)
Select random variable (uniform distribution, for tie breaking).
Definition var.hpp:101
void unary(Home home, const IntVarArgs &s, const IntArgs &p, IntPropLevel ipl=IPL_DEF)
Post propagators for scheduling tasks on unary resources.
Definition unary.cpp:44
IntVarBranch INT_VAR_SIZE_MIN(BranchTbl tbl=nullptr)
Select variable with smallest domain size.
Definition var.hpp:206
BoolVarBranch BOOL_VAR_MERIT_MAX(BoolBranchMerit bm, BranchTbl tbl=nullptr)
Select variable with highest merit according to branch merit function bm.
Definition var.hpp:379
IntVarBranch INT_VAR_MIN_MIN(BranchTbl tbl=nullptr)
Select variable with smallest min.
Definition var.hpp:186
Default configuration settings.
Definition job-shop.cpp:57
Gecode::FloatVal a(-8, 5)
Data read(const char *spec, const char *text, const Params &p=Params())
Read text with the spec spec.
Definition instance.cpp:64
Gecode::IntArgs i({1, 2, 3, 4})
Gecode::IntSet d(v, 7)
const int r[4][2]
Definition dom.cpp:152
Options opt
The options.
Definition test.cpp:163