open-shop.cpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Guido Tack <tack@gecode.org>
*
* Copyright:
* Guido Tack, 2009
*
* This file is part of Gecode, the generic constraint
* development environment:
* http://www.gecode.org
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
*/
#include <gecode/driver.hh>
#include <gecode/int.hh>
#include <gecode/minimodel.hh>
using namespace Gecode;
namespace {
class OpenShopSpec {
public:
const int m; //< number of machines
const int n; //< number of jobs
const int* p; //< processing times of the tasks
OpenShopSpec(int m0, int n0, const int* p0) : m(m0), n(n0), p(p0) {}
};
extern OpenShopSpec examples[];
extern const unsigned int n_examples;
}
class OpenShop : public IntMinimizeScript {
protected:
const OpenShopSpec& spec;
BoolVarArray b;
IntVar makespan;
IntVarArray _start;
class Task {
public:
int j; //< Job
int m; //< Machine
int p; //< Processing time
Task(void) {}
Task(int j0, int m0, int p0) : j(j0), m(m0), p(p0) {}
};
void crosh(Matrix<IntArgs>& dur, int& minmakespan, int& maxmakespan) {
Support::RandomGenerator rnd;
// Compute maximum makespan as the sum of all production times.
maxmakespan = 0;
for (int i=0; i<spec.m; i++)
for (int j=0; j<spec.n; j++)
maxmakespan += dur(i,j);
// Compute minimum makespan as the maximum of individual jobs and machines
minmakespan = 0;
for (int i=0; i<spec.m; i++) {
int ms = 0;
for (int j=0; j<spec.n; j++) {
ms += dur(i,j);
}
minmakespan = std::max(minmakespan, ms);
}
for (int j=0; j<spec.n; j++) {
int ms = 0;
for (int i=0; i<spec.m; i++) {
ms += dur(i,j);
}
minmakespan = std::max(minmakespan, ms);
}
Region re;
int* ct_j = re.alloc<int>(spec.n); // Job completion time
int* ct_m = re.alloc<int>(spec.m); // Machine completion time
Task* tasks = re.alloc<Task>(spec.n*spec.m); // Tasks
int k=0;
for (int i=spec.m; i--;)
for (int j=spec.n; j--;)
new (&tasks[k++]) Task(j,i,dur(i,j));
int* t0_tasks = re.alloc<int>(spec.n*spec.m); // Earliest possible tasks
bool stopCROSH = false;
int maxIterations;
switch (spec.n) {
case 3: maxIterations = 5; break;
case 4: maxIterations = 25; break;
case 5: maxIterations = 50; break;
case 6: maxIterations = 1000; break;
case 7: maxIterations = 10000; break;
case 8: maxIterations = 10000; break;
case 9: maxIterations = 10000; break;
default: maxIterations = 25000; break;
}
int iteration = 0;
while (!stopCROSH && maxmakespan > minmakespan) {
for (int i=spec.n; i--;) ct_j[i] = 0;
for (int i=spec.m; i--;) ct_m[i] = 0;
int cmax = 0; // Current makespan
int u = spec.n*spec.m; // Consider all tasks
while (u > 0) {
int u_t0 = 0; // Set of selectable tasks
int t0 = maxmakespan; // Minimal head of unscheduled tasks
for (int i=0; i<u; i++) {
const Task& t = tasks[i];
int est = std::max(ct_j[t.j], ct_m[t.m]); // Head of T_jm
if (est < t0) {
t0 = est;
t0_tasks[0] = i;
u_t0 = 1;
} else if (est == t0) {
t0_tasks[u_t0++] = i;
}
}
int t_j0m0;
if (iteration == 0) {
// In the first iteration, select tasks with longest processing time
t_j0m0 = 0;
for (int i=1; i<u_t0; i++)
if (tasks[t0_tasks[i]].p > tasks[t0_tasks[t_j0m0]].p)
t_j0m0 = i;
} else {
t_j0m0 = rnd(u_t0); // Select random task
}
const Task& t = tasks[t0_tasks[t_j0m0]];
int ect = t0 + t.p;
ct_j[t.j] = ect;
ct_m[t.m] = ect;
std::swap(tasks[--u],tasks[t0_tasks[t_j0m0]]); // Remove task from u
cmax = std::max(cmax, ect);
if (cmax > maxmakespan)
break;
}
maxmakespan = std::min(maxmakespan,cmax);
if (iteration++ > maxIterations)
stopCROSH = true; // Iterate a couple of times
}
}
public:
OpenShop(const SizeOptions& opt)
: IntMinimizeScript(opt),
spec(examples[opt.size()]),
b(*this, (spec.n+spec.m-2)*spec.n*spec.m/2, 0,1),
makespan(*this, 0, Int::Limits::max),
_start(*this, spec.m*spec.n, 0, Int::Limits::max) {
Matrix<IntVarArray> start(_start, spec.m, spec.n);
IntArgs _dur(spec.m*spec.n, spec.p);
Matrix<IntArgs> dur(_dur, spec.m, spec.n);
int minmakespan;
int maxmakespan;
crosh(dur, minmakespan, maxmakespan);
rel(*this, makespan <= maxmakespan);
rel(*this, makespan >= minmakespan);
int k=0;
for (int m=0; m<spec.m; m++)
for (int j0=0; j0<spec.n-1; j0++)
for (int j1=j0+1; j1<spec.n; j1++) {
// The tasks on machine m of jobs j0 and j1 must be disjoint
rel(*this,
b[k] == (start(m,j0) + dur(m,j0) <= start(m,j1)));
rel(*this,
b[k++] == (start(m,j1) + dur(m,j1) > start(m,j0)));
}
for (int j=0; j<spec.n; j++)
for (int m0=0; m0<spec.m-1; m0++)
for (int m1=m0+1; m1<spec.m; m1++) {
// The tasks in job j on machine m0 and m1 must be disjoint
rel(*this,
b[k] == (start(m0,j) + dur(m0,j) <= start(m1,j)));
rel(*this,
b[k++] == (start(m1,j) + dur(m1,j) > start(m0,j)));
}
// The makespan is greater than the end time of the latest job
for (int m=0; m<spec.m; m++) {
for (int j=0; j<spec.n; j++) {
rel(*this, start(m,j) + dur(m,j) <= makespan);
}
}
// First branch over the precedences
branch(*this, b, BOOL_VAR_AFC_MAX(opt.decay()), BOOL_VAL_MAX());
// When the precedences are fixed, simply assign the start times
assign(*this, _start, INT_ASSIGN_MIN());
// When the start times are fixed, use the tightest makespan
assign(*this, makespan, INT_ASSIGN_MIN());
}
OpenShop(OpenShop& s) : IntMinimizeScript(s), spec(s.spec) {
b.update(*this, s.b);
makespan.update(*this, s.makespan);
_start.update(*this, s._start);
}
virtual Space*
copy(void) {
return new OpenShop(*this);
}
virtual IntVar
cost(void) const {
return makespan;
}
class PrintTask {
public:
int start; //< Start time
int job; //< Job number
int p; //< Processing time
bool operator()(const PrintTask& t1, const PrintTask& t2) {
return t1.start < t2.start;
}
};
virtual void
print(std::ostream& os) const {
Region re;
PrintTask* m = re.alloc<PrintTask>(spec.n);
for (int i=0; i<spec.m; i++) {
int k=0;
for (int j=0; j<spec.n; j++) {
m[k].start = _start[i*spec.n+j].val();
m[k].job = j;
m[k].p = spec.p[i*spec.n+j];
k++;
}
Support::quicksort(m, spec.n, m[0]);
os << "Machine " << i << ": ";
for (int j=0; j<spec.n; j++)
os << "\t" << m[j].job << "("<<m[j].p<<")";
os << " = " << m[spec.n-1].start+m[spec.n-1].p << std::endl;
}
os << "Makespan: " << makespan << std::endl;
}
};
int
main(int argc, char* argv[]) {
SizeOptions opt("OpenShop");
opt.iterations(500);
opt.size(0);
opt.solutions(0);
opt.parse(argc,argv);
if (opt.size() >= n_examples) {
std::cerr << "Error: size must be between 0 and "
<< n_examples-1 << std::endl;
return 1;
}
IntMinimizeScript::run<OpenShop,BAB,SizeOptions>(opt);
return 0;
}
namespace {
const int ex0_p[] = {
661,6,333,
168,489,343,
171,505,324
};
OpenShopSpec ex0(3,3,ex0_p);
const int ex1_p[] = {
54, 34, 61, 2,
9, 15, 89, 70,
38, 19, 28, 87,
95, 34, 7, 29
};
OpenShopSpec ex1(4,4,ex1_p);
const int ex2_p[] = {
5, 70, 45, 83,
24, 80, 58, 45,
29, 56, 29, 61,
43, 64, 45, 74
};
OpenShopSpec ex2(4,4,ex2_p);
const int ex3_p[] = {
89, 39, 54, 34, 71, 92, 56,
19, 13, 81, 46, 91, 73, 27,
66, 95, 48, 24, 96, 18, 14,
48, 46, 78, 94, 19, 68, 63,
60, 28, 91, 75, 52, 9, 7,
33, 98, 37, 11, 2, 30, 38,
83, 45, 37, 77, 52, 88, 52
};
OpenShopSpec ex3(7,7,ex3_p);
const int ex4_p[] = {
49, 58, 37, 79, 16, 64, 71, 65, 6, 44, 17, 85, 99, 57, 89, 4, 16, 8, 40, 66,
43, 65, 42, 35, 57, 3, 8, 65, 79, 76, 82, 80, 96, 82, 98, 57, 73, 43, 6, 20,
82, 49, 7, 18, 94, 76, 41, 17, 43, 15, 53, 10, 83, 24, 79, 62, 53, 77, 23, 70,
18, 30, 80, 7, 97, 84, 10, 27, 7, 91, 14, 12, 7, 31, 24, 97, 16, 33, 99, 15,
31, 65, 51, 95, 45, 70, 57, 10, 84, 52, 28, 43, 54, 40, 83, 9, 21, 57, 45, 67,
70, 45, 48, 39, 10, 37, 22, 53, 48, 50, 76, 48, 57, 6, 43, 13, 45, 93, 42, 11,
80, 5, 53, 97, 75, 22, 10, 70, 79, 92, 96, 18, 57, 3, 82, 52, 1, 21, 23, 38,
43, 79, 67, 57, 33, 52, 1, 44, 82, 10, 27, 23, 89, 9, 62, 6, 38, 33, 37, 22,
68, 20, 5, 25, 16, 80, 13, 73, 35, 36, 13, 53, 97, 50, 17, 54, 35, 86, 24, 56,
60, 83, 8, 81, 3, 4, 48, 14, 77, 10, 71, 57, 86, 94, 49, 36, 62, 62, 41, 56,
31, 77, 5, 97, 19, 19, 31, 19, 26, 41, 77, 64, 74, 11, 98, 30, 22, 22, 33, 61,
7, 89, 46, 13, 33, 55, 84, 16, 21, 45, 15, 71, 57, 42, 82, 13, 62, 98, 36, 45,
84, 90, 20, 61, 24, 59, 8, 49, 53, 53, 83, 76, 28, 62, 59, 11, 41, 2, 58, 46,
32, 23, 53, 5, 8, 91, 97, 53, 90, 90, 28, 16, 61, 27, 32, 74, 23, 11, 57, 20,
62, 85, 79, 96, 62, 85, 43, 53, 12, 36, 95, 37, 2, 48, 46, 81, 97, 54, 5, 77,
57, 35, 41, 55, 72, 98, 22, 81, 6, 8, 70, 64, 55, 53, 7, 38, 58, 30, 83, 81,
15, 11, 24, 63, 27, 90, 35, 22, 53, 22, 66, 75, 59, 80, 31, 91, 63, 82, 99, 62,
4, 18, 99, 6, 65, 21, 28, 93, 16, 26, 1, 16, 46, 59, 45, 90, 69, 76, 25, 53,
50, 24, 66, 2, 17, 85, 5, 86, 4, 88, 44, 5, 29, 19, 27, 14, 36, 57, 59, 15,
71, 79, 7, 61, 45, 72, 61, 45, 61, 54, 90, 33, 81, 5, 45, 64, 87, 82, 61, 8
};
OpenShopSpec ex4(20,20,ex4_p);
OpenShopSpec examples[] = { ex0, ex1, ex2, ex3, ex4 };
const unsigned int n_examples = sizeof(examples) / sizeof(OpenShopSpec);
}
// STATISTICS: example-any
Gecode::BoolVarArray
Boolean variable array.
Definition int.hh:808
Gecode::Driver::ScriptBase< Driver::IgnoreStepOption< IntMinimizeSpace > >::run
static void run(const Options &opt, Script *s=NULL)
Gecode::IntArgs
Passing integer arguments.
Definition int.hh:628
Gecode::IntVarArray
Integer variable array.
Definition int.hh:763
Gecode::IntVar
Integer variables.
Definition int.hh:371
Gecode::Matrix
Matrix-interface for arrays.
Definition minimodel.hh:2161
Gecode::Region
Handle to region.
Definition region.hpp:55
Gecode::Region::alloc
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition region.hpp:386
Gecode::SizeOptions
Options for scripts with additional size parameter
Definition driver.hh:675
Gecode::Space
Computation spaces.
Definition core.hpp:1742
OpenShop::PrintTask
Helper class for representing tasks when printing a solution.
Definition open-shop.cpp:265
OpenShop::PrintTask::operator()
bool operator()(const PrintTask &t1, const PrintTask &t2)
Comparison of tasks based on start time, used for sorting.
Definition open-shop.cpp:271
OpenShop::PrintTask::start
int start
Definition open-shop.cpp:267
OpenShop::PrintTask::job
int job
Definition open-shop.cpp:268
OpenShop::PrintTask::p
int p
Definition open-shop.cpp:269
OpenShop::Task
Task representation for CROSH heuristic
Definition open-shop.cpp:76
OpenShop::Task::p
int p
Definition open-shop.cpp:80
OpenShop::Task::m
int m
Definition open-shop.cpp:79
OpenShop::Task::Task
Task(int j0, int m0, int p0)
Constructor.
Definition open-shop.cpp:84
OpenShop::Task::Task
Task(void)
Default constructor.
Definition open-shop.cpp:82
OpenShop::Task::j
int j
Definition open-shop.cpp:78
OpenShop::crosh
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:96
OpenShop::main
int main(int argc, char *argv[])
Main-function.
Definition open-shop.cpp:304
OpenShop::ex3
OpenShopSpec ex3(7, 7, ex3_p)
The instances.
OpenShop::ex2
OpenShopSpec ex2(4, 4, ex2_p)
The instances.
OpenShop::n_examples
const unsigned int n_examples
The number of instances.
Definition open-shop.cpp:391
OpenShop::OpenShop
OpenShop(const SizeOptions &opt)
The actual problem.
Definition open-shop.cpp:192
OpenShop::OpenShop
OpenShop(OpenShop &s)
Constructor for cloning s.
Definition open-shop.cpp:246
OpenShop::ex4_p
const int ex4_p[]
The instances.
Definition open-shop.cpp:364
OpenShop::ex1
OpenShopSpec ex1(4, 4, ex1_p)
The instances.
OpenShop::print
virtual void print(std::ostream &os) const
Print solution.
Definition open-shop.cpp:278
OpenShop::ex0_p
const int ex0_p[]
The instances.
Definition open-shop.cpp:330
OpenShop::examples
OpenShopSpec examples[]
The instances.
Definition open-shop.cpp:389
OpenShop::copy
virtual Space * copy(void)
Perform copying during cloning.
Definition open-shop.cpp:254
OpenShop::ex0
OpenShopSpec ex0(3, 3, ex0_p)
The instances.
OpenShop::cost
virtual IntVar cost(void) const
Minimize the makespan.
Definition open-shop.cpp:260
OpenShop::ex3_p
const int ex3_p[]
The instances.
Definition open-shop.cpp:353
OpenShop::ex2_p
const int ex2_p[]
The instances.
Definition open-shop.cpp:345
OpenShop::ex1_p
const int ex1_p[]
The instances.
Definition open-shop.cpp:337
OpenShop::ex4
OpenShopSpec ex4(20, 20, ex4_p)
The instances.
OpenShop::b
BoolVarArray b
Precedences.
Definition open-shop.cpp:69
OpenShop::makespan
IntVar makespan
Makespan.
Definition open-shop.cpp:71
OpenShop::spec
const OpenShopSpec & spec
The instance specification.
Definition open-shop.cpp:67
OpenShop::_start
IntVarArray _start
Start times.
Definition open-shop.cpp:73
Test::Options::parse
void parse(int argc, char *argv[])
Parse commandline arguments.
Definition test.cpp:120
driver.hh
int.hh
Gecode::Support::RandomGenerator
LinearCongruentialGenerator< 2147483647, 48271, 44488, 3399 > RandomGenerator
Default values for linear congruential generator.
Definition random.hpp:120
Gecode::IntMinimizeScript
Driver::ScriptBase< Driver::IgnoreStepOption< IntMinimizeSpace > > IntMinimizeScript
Base-class for scripts for finding solution of lowest integer cost.
Definition driver.hh:808
Gecode::assign
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
Gecode::branch
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
Gecode::rel
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
minimodel.hh
Gecode::Int::Limits
Numerical limits for integer variables.
Definition int.hh:114
Gecode::Int
Finite domain integers.
Gecode::Support::quicksort
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition sort.hpp:130
Gecode
Gecode toplevel namespace
Gecode::BOOL_VAL_MAX
BoolValBranch BOOL_VAL_MAX(void)
Select largest value.
Definition val.hpp:135
Gecode::BOOL_VAR_AFC_MAX
BoolVarBranch BOOL_VAR_AFC_MAX(double d=1.0, BranchTbl tbl=nullptr)
Select variable with largest accumulated failure count with decay factor d.
Definition var.hpp:404
Gecode::INT_ASSIGN_MIN
IntAssign INT_ASSIGN_MIN(void)
Select smallest value.
Definition assign.hpp:55
Gecode::max
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition arithmetic.cpp:49