59 static const bool verbose =
false;
62 static const unsigned int probes = 50U;
64 static const unsigned int fail_probe = 10000U;
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;
74 static const double restart_scale = 5000.0;
76 static const double restart_base = 1.3;
94 const char* instance_spec = R
"(format jobshop
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"
103 repeat n_jobs as jobs {
105 repeat n_machines as steps {
107 machine: 0..<n_machines
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"
120 extern const int* js[];
122 extern const char* name[];
137 bool valid(
void)
const {
138 return data !=
nullptr;
141 int jobs(
void)
const {
145 int machines(
void)
const {
149 int machine(
int i,
int j)
const {
150 return data[2 +
i*machines()*2 + j*2];
153 int duration(
int i,
int j)
const {
154 return data[2 +
i*machines()*2 + j*2 + 1];
158 static const int* find(
const char* s) {
161 for (
int i=0; ::name[
i] !=
nullptr;
i++)
162 if (!strcmp(s,::name[i]))
167 int clower(
void)
const {
170 int* mach =
r.alloc<
int>(machines());
171 for (
int j=0; j<machines(); j++)
173 for (
int i=0;
i<jobs();
i++) {
175 for (
int j=0; j<machines(); j++) {
176 mach[machine(i,j)] += duration(i,j);
177 job += duration(i,j);
181 for (
int j=0; j<machines(); j++)
182 l = std::max(l,mach[j]);
186 int cupper(
void)
const {
188 for (
int i=0;
i<jobs();
i++)
189 for (
int j=0; j<machines(); j++)
194 void read(
const InstanceOptions& opt) {
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);
201 for (
int i=0;
i<j*m;
i++) {
202 a[2 + 2*
i] = mach[
i];
203 a[2 + 2*
i + 1] = dur[
i];
215 Spec(
const InstanceOptions& opt) : data(find(
opt.instance())), l(0), u(0), n(
opt.instance()) {
216 if ((data ==
nullptr) &&
opt.is_file())
219 l = clower(); u = cupper();
223 int lower(
void)
const {
227 int upper(
void)
const {
231 const char* name(
void)
const {
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) {
285 return _verbose.value();
289 return _probes.value();
293 return _fail_probe.value();
297 return _time_probe.value();
301 return _time_adjust.value();
305 return _time_solve.value();
314 std::cerr <<
"\tAvailable instances:" << std::endl <<
"\t\t";
315 for (
int i=1;
::name[i] !=
nullptr; i++) {
316 std::cerr <<
::name[i] <<
", ";
318 std::cerr << std::endl <<
"\t\t";
320 std::cerr << std::endl;
356 int n =
spec.jobs(), m =
spec.machines();
361 for (
int i=0; i<n; i++) {
362 for (
int j=1; j<m; j++)
370 int n =
spec.jobs(), m =
spec.machines();
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);
381 for (
int j=0; j<m; j++) {
384 for (
int i=0; i<n; i++) {
385 jpm[i] = jobs[j*n+i]; dpm[i] = dur[j*n+i];
387 unary(*
this, jpm, dpm);
403 os <<
"\t\t" <<
spec.name()
404 <<
" [makespan: " <<
makespan <<
"]" << std::endl;
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] <<
" ";
544 int n =
spec.jobs(), m =
spec.machines();
546 fst.init(m*n*(n-1)/2);
547 snd.init(m*n*(n-1)/2);
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);
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]) {
563 start[jobs[j*n+i1]], dur[j*n+i1],
564 start[jobs[j*n+i2]], dur[j*n+i2],
566 fst[l] = j*n+i1;
snd[l] = j*n+i2;
569 start[jobs[j*n+i2]], dur[j*n+i2],
570 start[jobs[j*n+i1]], dur[j*n+i1],
572 fst[l] = j*n+i2;
snd[l] = j*n+i1;
576 assert(l == (j+1)*n*(n-1)/2);
579 double tbf =
opt.tbf();
580 switch (
opt.branching()) {
582 iafc.init(*this,start,opt.decay());
585 [tbf] (const Space&, double w, double b) {
587 return b - (b - w) * tbf;
589 branch(*this, sorder, tiebreak(BOOL_VAR_MERIT_MAX(&afcmerit,tbl),
593 branch(*this, sorder, BOOL_VAR_MERIT_MAX(&afcmerit),
602 [tbf] (
const Space&,
double w,
double b) {
604 return b - (b - w) * tbf;
619 [tbf] (
const Space&,
double w,
double b) {
621 return b - (b - w) * tbf;
659 return fs->stop(s,o) ||
ts->stop(s,o);
663 return fs->stop(s,o);
667 return ts->stop(s,o);
671 delete fs;
delete ts;
679 cout <<
"\t\t\tnodes: " << stat.
node << endl
680 <<
"\t\t\tfailures: " << stat.
fail << endl;
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;
707 std::cerr <<
"Error: has no solution..." << std::endl;
717 bool stopped =
false;
719 std::cout <<
"\tProbing..." << std::endl;
721 std::cout <<
"\t\tBounds: [" << l <<
"," << u <<
"]"
724 for (
unsigned int p=0; p<opt.probes(); p++) {
737 }
else if (fts.
time(statj,so)) {
746 std::cout <<
"\t\t\truntime: ";
748 std::cout << std::endl;
751 std::cout <<
"\t\t\t\tstopped due to time-out..." << std::endl;
755 std::cout << std::endl <<
"\tAdjusting..." << std::endl;
764 std::cerr <<
"Error: has no solution..." << std::endl;
772 if (opt.time_adjust() > 0U)
774 bool stopped =
false;
776 std::cout <<
"\t\tBounds: [" << l <<
"," << u <<
"]"
783 JobShopConfig::restart_base);
787 stat +=
rbs.statistics();
793 }
else if (
rbs.stopped()) {
802 std::cout <<
"\t\t\truntime: ";
804 std::cout << std::endl;
807 std::cout <<
"\t\t\t\tstopped due to time-out..." << std::endl;
814 std::cout << std::endl
815 <<
"\tFound best solution and proved optimality."
823 std::cout << std::endl <<
"\tSolving..." << std::endl;
825 rel(*master, master->
cost() >= l);
826 rel(*master, master->
cost() < u);
829 if (opt.time_solve() > 0U)
832 JobShopConfig::restart_base);
841 std::cout <<
"\t\t\truntime: ";
843 std::cout << std::endl;
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."
855 std::cout << std::endl
856 <<
"\tFound best solution and proved optimality."
872main(
int argc,
char* argv[]) {
884 opt.instance(
"ft06");
886 opt.restart_base(JobShopConfig::restart_base);
887 opt.restart_scale(JobShopConfig::restart_scale);
892 if (!Spec(opt).
valid()) {
893 std::cerr <<
"Error: unknown instance" << std::endl;
897 std::cerr << e.
what() << std::endl;
Common command line options.
CommonOptions(const JobShopOptions &opt)
Initialize.
Stop object combining time and failuresa.
bool fail(const Search::Statistics &s, const Search::Options &o) const
Whether the stop was due to failures.
virtual bool stop(const Search::Statistics &s, const Search::Options &o)
Test whether search must be stopped.
~FailTimeStop(void)
Destructor.
Search::FailStop * fs
Used fail stop object.
FailTimeStop(unsigned int fail, unsigned int time)
Initialize stop object.
Search::TimeStop * ts
Used time stop object.
bool time(const Search::Statistics &s, const Search::Options &o) const
Whether the stop was due to time.
void add(Driver::BaseOption &o)
Add new option o.
const char * name(void) const
Return name of script.
Recording actions for Boolean variables.
Recording CHB for Boolean variables.
Boolean integer variables.
Depth-first search engine.
virtual void help(void)
Print help text.
InstanceOptions(const char *s)
Initialize options for script with name s.
Exception for errors in specs and instance files
virtual const char * what(void) const noexcept override
Return the full message.
Recording AFC information for integer variables.
Recording actions for integer variables.
Passing integer arguments.
Recording CHB for integer variables.
Passing integer variables.
int min(void) const
Return minimum of domain.
int val(void) const
Return assigned value.
int max(void) const
Return maximum of domain.
Meta-engine performing restart-based search.
static Cutoff * geometric(unsigned long long int scale=Config::slice, double base=Config::base)
Stop-object based on number of failures
unsigned int c_d
Create a clone after every c_d commits (commit distance).
bool clone
Whether engines create a clone when being initialized.
Cutoff * cutoff
Cutoff for restart-based search.
unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance).
Stop * stop
Stop object for stopping search.
unsigned int nogoods_limit
Depth limit for extraction of no-goods.
double threads
Number of threads to use.
unsigned long int restart
Number of restarts.
unsigned long int depth
Maximum depth of search stack.
unsigned long long int fail
Number of failed nodes in search tree.
unsigned long long int node
Number of nodes expanded.
unsigned long int nogood
Number of no-goods posted.
Base-class for Stop-object.
static Stop * time(double l)
Stop if time limit l (in milliseconds) has been exceeded.
Stop-object based on time
void start(void)
Start timer.
double afc(void) const
Return accumulated failure count.
virtual void print(std::ostream &os) const
Print solution.
const JobShopOptions & opt
Options.
IntVarArray start
Start times for each step in a job.
JobShopBase(JobShopBase &s)
Constructor for cloning s.
virtual IntVar cost(void) const
Return cost.
const Spec spec
Specification.
void nooverload(void)
Do not overload machines.
JobShopBase(const JobShopOptions &o)
Actual model.
Options for JobShop problems
unsigned int fail_probe(void) const
Return number of failures per probe.
JobShopOptions(const char *s)
Initialize options for example with name s.
unsigned int time_probe(void) const
Return time-out for probe.
unsigned int time_adjust(void) const
Return time-out for adjust.
virtual void help(void)
Print help text for list of instances.
bool verbose(void) const
Return whether to print schedule.
unsigned int time_solve(void) const
Return time-out for solve.
unsigned int probes(void) const
Return number of probes.
double tbf(void) const
Return tie-breaking factor.
void branch(unsigned int p, Rnd r)
JobShopProbe(JobShopProbe &s)
Constructor for cloning s.
virtual Space * copy(void)
Copy during cloning.
JobShopProbe(const JobShopOptions &o)
Actual model.
IntCHB ichb
CHB information.
virtual Space * copy(void)
Copy during cloning.
IntSharedArray snd
Record which step is second in order.
JobShopSolve(const JobShopOptions &o)
Actual model.
static double chbmerit(const Space &home, BoolVar, int i)
Trampoline function for CHB-based cost.
@ PROP_UNARY
Also post unary constraints.
@ PROP_ORDER
Only propagate order constraints.
static double afcmerit(const Space &home, BoolVar x, int i)
Trampoline function for AFC-based cost.
IntAFC iafc
AFC information.
IntAction iaction
Action information.
BoolVarArray sorder
Step order variables.
double chb(int i) const
CHB-based cost.
double action(int i) const
Action-based cost.
Rnd rnd
Random number generator for probing and relaxation.
double afc(BoolVar x, int i) const
AFC-based cost.
IntSharedArray fst
Record which step is first in order.
@ BRANCH_AFC
Branch using AFC.
@ BRANCH_ACTION
Branch using action.
@ BRANCH_CHB
Branch using CHB.
static double actionmerit(const Space &home, BoolVar, int i)
Trampoline function for Action-based cost.
JobShopSolve(JobShopSolve &s)
Constructor for cloning s.
void parse(int argc, char *argv[])
Parse commandline arguments.
unsigned int seed
The random seed to be used.
unsigned int threads
Number of threads to use.
Driver::ScriptBase< Driver::IgnoreStepOption< IntMinimizeSpace > > IntMinimizeScript
Base-class for scripts for finding solution of lowest integer cost.
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.
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.
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
T * rbs(T *s, const Search::Options &o)
Perform restart-based search.
@ SS_SOLVED
Space is solved (no brancher left)
@ SS_FAILED
Space is failed
void solve(const JobShopOptions &opt)
Solver.
void stop(Support::Timer &timer, std::ostream &os)
Get time since start of timer and print user friendly time information.
bool valid(const FloatVal &n)
Return whether float n is a valid number.
void print(std::basic_ostream< Char, Traits > &s, bool assigned, IL &lb, IU &ub, unsigned int cardMin, unsigned int cardMax)
Print set view.
Gecode toplevel namespace
IntValBranch INT_VAL_SPLIT_MIN(void)
Select values not greater than mean of smallest and largest value.
void order(Home home, IntVar s0, int p0, IntVar s1, int p1, BoolVar b, IntPropLevel ipl=IPL_DEF)
Post propagators for ordering two tasks.
SharedArray< int > IntSharedArray
Arrays of integers that can be shared among several element constraints.
TieBreak< VarBranch > tiebreak(VarBranch a, VarBranch b)
Combine variable selection criteria a and b for tie-breaking.
BoolValBranch BOOL_VAL_MIN(void)
Select smallest value.
BoolVarBranch BOOL_VAR_RND(Rnd r)
Select random variable (uniform distribution, for tie breaking).
IntVarBranch INT_VAR_MAX_MIN(BranchTbl tbl=nullptr)
Select variable with smallest max.
IntValBranch INT_VAL_MIN(void)
Select smallest value.
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.
IntAssign INT_ASSIGN_MIN(void)
Select smallest value.
IntVarBranch INT_VAR_RND(Rnd r)
Select random variable (uniform distribution, for tie breaking).
void unary(Home home, const IntVarArgs &s, const IntArgs &p, IntPropLevel ipl=IPL_DEF)
Post propagators for scheduling tasks on unary resources.
IntVarBranch INT_VAR_SIZE_MIN(BranchTbl tbl=nullptr)
Select variable with smallest domain size.
BoolVarBranch BOOL_VAR_MERIT_MAX(BoolBranchMerit bm, BranchTbl tbl=nullptr)
Select variable with highest merit according to branch merit function bm.
IntVarBranch INT_VAR_MIN_MIN(BranchTbl tbl=nullptr)
Select variable with smallest min.
Default configuration settings.
Gecode::FloatVal a(-8, 5)
Data read(const char *spec, const char *text, const Params &p=Params())
Read text with the spec spec.
Gecode::IntArgs i({1, 2, 3, 4})