51 OpenShopSpec(
int m0,
int n0,
const int* p0) : m(m0), n(n0), p(p0) {}
54 extern OpenShopSpec examples[];
55 extern const unsigned int n_examples;
84 Task(
int j0,
int m0,
int p0) : j(j0), m(m0), p(p0) {}
101 for (
int i=0;
i<spec.m;
i++)
102 for (
int j=0; j<spec.n; j++)
103 maxmakespan += dur(
i,j);
107 for (
int i=0;
i<spec.m;
i++) {
109 for (
int j=0; j<spec.n; j++) {
112 minmakespan =
std::max(minmakespan, ms);
114 for (
int j=0; j<spec.n; j++) {
116 for (
int i=0;
i<spec.m;
i++) {
119 minmakespan =
std::max(minmakespan, ms);
123 int* ct_j = re.
alloc<
int>(spec.n);
124 int* ct_m = re.
alloc<
int>(spec.m);
127 for (
int i=spec.m;
i--;)
128 for (
int j=spec.n; j--;)
129 new (&tasks[k++])
Task(j,
i,dur(
i,j));
130 int* t0_tasks = re.
alloc<
int>(spec.n*spec.m);
132 bool stopCROSH =
false;
136 case 3: maxIterations = 5;
break;
137 case 4: maxIterations = 25;
break;
138 case 5: maxIterations = 50;
break;
139 case 6: maxIterations = 1000;
break;
140 case 7: maxIterations = 10000;
break;
141 case 8: maxIterations = 10000;
break;
142 case 9: maxIterations = 10000;
break;
143 default: maxIterations = 25000;
break;
146 while (!stopCROSH && maxmakespan > minmakespan) {
147 for (
int i=spec.n;
i--;) ct_j[
i] = 0;
148 for (
int i=spec.m;
i--;) ct_m[
i] = 0;
150 int u = spec.n*spec.m;
153 int t0 = maxmakespan;
154 for (
int i=0;
i<
u;
i++) {
161 }
else if (est == t0) {
162 t0_tasks[u_t0++] =
i;
166 if (iteration == 0) {
169 for (
int i=1;
i<u_t0;
i++)
170 if (tasks[t0_tasks[
i]].
p > tasks[t0_tasks[t_j0m0]].
p)
175 const Task&
t = tasks[t0_tasks[t_j0m0]];
179 std::swap(tasks[--u],tasks[t0_tasks[t_j0m0]]);
181 if (cmax > maxmakespan)
185 maxmakespan =
std::min(maxmakespan,cmax);
186 if (iteration++ > maxIterations)
194 spec(examples[opt.
size()]),
195 b(*this, (spec.
n+spec.m-2)*spec.
n*spec.m/2, 0,1),
196 makespan(*this, 0, Int::Limits::
max),
197 _start(*this, spec.m*spec.
n, 0, Int::Limits::
max) {
200 IntArgs _dur(spec.m*spec.n, spec.p);
205 crosh(dur, minmakespan, maxmakespan);
206 rel(*
this, makespan <= maxmakespan);
207 rel(*
this, makespan >= minmakespan);
210 for (
int m=0; m<spec.m; m++)
211 for (
int j0=0; j0<spec.n-1; j0++)
212 for (
int j1=j0+1; j1<spec.n; j1++) {
215 b[k] == (start(m,j0) + dur(m,j0) <= start(m,j1)));
217 b[k++] == (start(m,j1) + dur(m,j1) > start(m,j0)));
220 for (
int j=0; j<spec.n; j++)
221 for (
int m0=0; m0<spec.m-1; m0++)
222 for (
int m1=m0+1; m1<spec.m; m1++) {
225 b[k] == (start(m0,j) + dur(m0,j) <= start(m1,j)));
227 b[k++] == (start(m1,j) + dur(m1,j) > start(m0,j)));
231 for (
int m=0; m<spec.m; m++) {
232 for (
int j=0; j<spec.n; j++) {
233 rel(*
this, start(m,j) + dur(m,j) <= makespan);
281 for (
int i=0;
i<spec.m;
i++) {
283 for (
int j=0; j<spec.n; j++) {
284 m[k].
start = _start[
i*spec.n+j].val();
286 m[k].
p = spec.p[
i*spec.n+j];
290 os <<
"Machine " <<
i <<
": ";
291 for (
int j=0; j<spec.n; j++)
292 os <<
"\t" << m[j].job <<
"("<<m[j].
p<<
")";
293 os <<
" = " << m[spec.n-1].
start+m[spec.n-1].
p << std::endl;
295 os <<
"Makespan: " << makespan << std::endl;
309 opt.
parse(argc,argv);
310 if (opt.
size() >= n_examples) {
311 std::cerr <<
"Error: size must be between 0 and " 312 << n_examples-1 << std::endl;
315 IntMinimizeScript::run<OpenShop,BAB,SizeOptions>(
opt);
330 const int ex0_p[] = {
335 OpenShopSpec ex0(3,3,ex0_p);
337 const int ex1_p[] = {
343 OpenShopSpec ex1(4,4,ex1_p);
345 const int ex2_p[] = {
351 OpenShopSpec ex2(4,4,ex2_p);
353 const int ex3_p[] = {
354 89, 39, 54, 34, 71, 92, 56,
355 19, 13, 81, 46, 91, 73, 27,
356 66, 95, 48, 24, 96, 18, 14,
357 48, 46, 78, 94, 19, 68, 63,
358 60, 28, 91, 75, 52, 9, 7,
359 33, 98, 37, 11, 2, 30, 38,
360 83, 45, 37, 77, 52, 88, 52
362 OpenShopSpec ex3(7,7,ex3_p);
364 const int ex4_p[] = {
365 49, 58, 37, 79, 16, 64, 71, 65, 6, 44, 17, 85, 99, 57, 89, 4, 16, 8, 40, 66,
366 43, 65, 42, 35, 57, 3, 8, 65, 79, 76, 82, 80, 96, 82, 98, 57, 73, 43, 6, 20,
367 82, 49, 7, 18, 94, 76, 41, 17, 43, 15, 53, 10, 83, 24, 79, 62, 53, 77, 23, 70,
368 18, 30, 80, 7, 97, 84, 10, 27, 7, 91, 14, 12, 7, 31, 24, 97, 16, 33, 99, 15,
369 31, 65, 51, 95, 45, 70, 57, 10, 84, 52, 28, 43, 54, 40, 83, 9, 21, 57, 45, 67,
370 70, 45, 48, 39, 10, 37, 22, 53, 48, 50, 76, 48, 57, 6, 43, 13, 45, 93, 42, 11,
371 80, 5, 53, 97, 75, 22, 10, 70, 79, 92, 96, 18, 57, 3, 82, 52, 1, 21, 23, 38,
372 43, 79, 67, 57, 33, 52, 1, 44, 82, 10, 27, 23, 89, 9, 62, 6, 38, 33, 37, 22,
373 68, 20, 5, 25, 16, 80, 13, 73, 35, 36, 13, 53, 97, 50, 17, 54, 35, 86, 24, 56,
374 60, 83, 8, 81, 3, 4, 48, 14, 77, 10, 71, 57, 86, 94, 49, 36, 62, 62, 41, 56,
375 31, 77, 5, 97, 19, 19, 31, 19, 26, 41, 77, 64, 74, 11, 98, 30, 22, 22, 33, 61,
376 7, 89, 46, 13, 33, 55, 84, 16, 21, 45, 15, 71, 57, 42, 82, 13, 62, 98, 36, 45,
377 84, 90, 20, 61, 24, 59, 8, 49, 53, 53, 83, 76, 28, 62, 59, 11, 41, 2, 58, 46,
378 32, 23, 53, 5, 8, 91, 97, 53, 90, 90, 28, 16, 61, 27, 32, 74, 23, 11, 57, 20,
379 62, 85, 79, 96, 62, 85, 43, 53, 12, 36, 95, 37, 2, 48, 46, 81, 97, 54, 5, 77,
380 57, 35, 41, 55, 72, 98, 22, 81, 6, 8, 70, 64, 55, 53, 7, 38, 58, 30, 83, 81,
381 15, 11, 24, 63, 27, 90, 35, 22, 53, 22, 66, 75, 59, 80, 31, 91, 63, 82, 99, 62,
382 4, 18, 99, 6, 65, 21, 28, 93, 16, 26, 1, 16, 46, 59, 45, 90, 69, 76, 25, 53,
383 50, 24, 66, 2, 17, 85, 5, 86, 4, 88, 44, 5, 29, 19, 27, 14, 36, 57, 59, 15,
384 71, 79, 7, 61, 45, 72, 61, 45, 61, 54, 90, 33, 81, 5, 45, 64, 87, 82, 61, 8
386 OpenShopSpec ex4(20,20,ex4_p);
389 OpenShopSpec examples[] = { ex0, ex1, ex2, ex3, ex4 };
391 const unsigned int n_examples =
sizeof(examples) /
sizeof(OpenShopSpec);
void size(unsigned int s)
Set default size.
void crosh(Matrix< IntArgs > &dur, int &minmakespan, int &maxmakespan)
Use Constructive Randomized Open-Shop Heuristics to compute lower and upper bounds.
BoolVarArray b
Precedences.
Options for scripts with additional size parameter
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf, FloatVarValPrint vvp)
Branch over x with variable selection vars and value selection vals.
const FloatNum max
Largest allowed float value.
void update(Space &home, VarArray< Var > &a)
Update array to be a clone of array a.
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
virtual Space * copy(void)
Perform copying during cloning.
Helper class for representing tasks when printing a solution.
Example: open-shop scheduling
Parametric base-class for scripts.
void iterations(unsigned int i)
Set default number of iterations.
void decay(double d)
Set default decay factor.
IntAssign INT_ASSIGN_MIN(void)
Select smallest value.
int p
Number of positive literals for node type.
const FloatNum min
Smallest allowed float value.
Gecode::IntArgs i(4, 1, 2, 3, 4)
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
BoolValBranch BOOL_VAL_MAX(void)
Select largest value.
int n
Number of negative literals for node type.
int main(int argc, char *argv[])
Main-function.
OpenShop(const SizeOptions &opt)
The actual problem.
IntVarArray _start
Start times.
Task(int j0, int m0, int p0)
Constructor.
unsigned int size(I &i)
Size of all ranges of range iterator i.
virtual IntVar cost(void) const
Minimize the makespan.
void update(Space &home, VarImpVar< VarImp > &y)
Update this variable to be a clone of variable y.
Template for linear congruential generators.
union Gecode::@585::NNF::@62 u
Union depending on nodetype t.
Passing integer arguments.
BoolVarBranch BOOL_VAR_AFC_MAX(double d, BranchTbl tbl)
Select variable with largest accumulated failure count with decay factor d.
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
void solutions(unsigned int n)
Set default number of solutions to search for.
Matrix-interface for arrays.
Gecode toplevel namespace
const OpenShopSpec & spec
The instance specification.
OpenShop(OpenShop &s)
Constructor for cloning s.
void assign(Home home, const FloatVarArgs &x, FloatAssign fa, FloatBranchFilter bf, FloatVarValPrint vvp)
Assign all x with value selection vals.
bool operator()(const PrintTask &t1, const PrintTask &t2)
Comparison of tasks based on start time, used for sorting.
Task representation for CROSH heuristic
virtual void print(std::ostream &os) const
Print solution.
IntRelType swap(IntRelType irt)
Return swapped relation type of irt.
Task(void)
Default constructor.