51 OpenShopSpec(
int m0,
int n0,
const int* p0) : m(m0),
n(n0),
p(p0) {}
84 Task(
int j0,
int m0,
int p0) :
j(j0),
m(m0),
p(p0) {}
102 for (
int j=0; j<
spec.n; j++)
103 maxmakespan += dur(
i,j);
109 for (
int j=0; j<
spec.n; j++) {
112 minmakespan =
std::max(minmakespan, ms);
114 for (
int j=0; j<
spec.n; j++) {
119 minmakespan =
std::max(minmakespan, ms);
128 for (
int j=
spec.n; j--;)
129 new (&tasks[k++])
Task(j,
i,dur(
i,j));
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;
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)
205 crosh(dur, minmakespan, maxmakespan);
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++) {
283 for (
int j=0; j<
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<<
")";
295 os <<
"Makespan: " <<
makespan << std::endl;
311 std::cerr <<
"Error: size must be between 0 and "
315 IntMinimizeScript::run<OpenShop,BAB,SizeOptions>(
opt);
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
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
union Gecode::@603::NNF::@65 u
Union depending on nodetype t.
int p
Number of positive literals for node type.
int n
Number of negative literals for node type.
const unsigned int n_examples
The number of examples.
Parametric base-class for scripts.
Passing integer arguments.
Matrix-interface for arrays.
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Options for scripts with additional size parameter
Template for linear congruential generators.
void update(Space &home, VarArray< Var > &a)
Update array to be a clone of array a.
void update(Space &home, VarImpVar< VarImp > &y)
Update this variable to be a clone of variable y.
const int * examples[]
Array of all examples.
Helper class for representing tasks when printing a solution.
bool operator()(const PrintTask &t1, const PrintTask &t2)
Comparison of tasks based on start time, used for sorting.
Task representation for CROSH heuristic
Task(int j0, int m0, int p0)
Constructor.
Task(void)
Default constructor.
Example: open-shop scheduling
void crosh(Matrix< IntArgs > &dur, int &minmakespan, int &maxmakespan)
Use Constructive Randomized Open-Shop Heuristics to compute lower and upper bounds.
int main(int argc, char *argv[])
Main-function.
OpenShopSpec ex3(7, 7, ex3_p)
The instances.
OpenShopSpec ex2(4, 4, ex2_p)
The instances.
OpenShop(const SizeOptions &opt)
The actual problem.
OpenShop(OpenShop &s)
Constructor for cloning s.
const int ex4_p[]
The instances.
OpenShopSpec ex1(4, 4, ex1_p)
The instances.
virtual void print(std::ostream &os) const
Print solution.
const int ex0_p[]
The instances.
OpenShopSpec examples[]
The instances.
virtual Space * copy(void)
Perform copying during cloning.
OpenShopSpec ex0(3, 3, ex0_p)
The instances.
virtual IntVar cost(void) const
Minimize the makespan.
const int ex3_p[]
The instances.
const int ex2_p[]
The instances.
const int ex1_p[]
The instances.
OpenShopSpec ex4(20, 20, ex4_p)
The instances.
BoolVarArray b
Precedences.
const OpenShopSpec & spec
The instance specification.
IntVarArray _start
Start times.
void parse(int argc, char *argv[])
Parse commandline arguments.
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 rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
void branch(Home home, const IntVarArgs &x, const BoolVarArgs &y, IntBoolVarBranch vars, IntValBranch vals)
Branch function for integer and Boolean variables.
const FloatNum max
Largest allowed float value.
const FloatNum min
Smallest allowed float value.
unsigned int size(I &i)
Size of all ranges of range iterator i.
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Gecode toplevel namespace
IntRelType swap(IntRelType irt)
Return swapped relation type of irt.
BoolValBranch BOOL_VAL_MAX(void)
Select largest value.
BoolVarBranch BOOL_VAR_AFC_MAX(double d=1.0, BranchTbl tbl=nullptr)
Select variable with largest accumulated failure count with decay factor d.
IntAssign INT_ASSIGN_MIN(void)
Select smallest value.
Gecode::IntArgs i({1, 2, 3, 4})