42 using namespace Gecode;
55 OpenShopSpec(
int m0,
int n0,
const int* p0) :
m(m0), n(n0), p(p0) {}
58 extern OpenShopSpec examples[];
59 extern const unsigned int n_examples;
88 Task(
int j0,
int m0,
int p0) : j(j0),
m(m0), p(p0) {}
105 for (
int i=0;
i<spec.m;
i++)
106 for (
int j=0; j<spec.n; j++)
107 maxmakespan += dur(
i,j);
111 for (
int i=0;
i<spec.m;
i++) {
113 for (
int j=0; j<spec.n; j++) {
116 minmakespan =
std::max(minmakespan, ms);
118 for (
int j=0; j<spec.n; j++) {
120 for (
int i=0;
i<spec.m;
i++) {
123 minmakespan =
std::max(minmakespan, ms);
127 int* ct_j = re.
alloc<
int>(spec.n);
128 int* ct_m = re.
alloc<
int>(spec.m);
131 for (
int i=spec.m;
i--;)
132 for (
int j=spec.n; j--;)
133 new (&tasks[k++])
Task(j,
i,dur(
i,j));
134 int* t0_tasks = re.
alloc<
int>(spec.n*spec.m);
136 bool stopCROSH =
false;
140 case 3: maxIterations = 5;
break;
141 case 4: maxIterations = 25;
break;
142 case 5: maxIterations = 50;
break;
143 case 6: maxIterations = 1000;
break;
144 case 7: maxIterations = 10000;
break;
145 case 8: maxIterations = 10000;
break;
146 case 9: maxIterations = 10000;
break;
147 default: maxIterations = 25000;
break;
150 while (!stopCROSH && maxmakespan > minmakespan) {
151 for (
int i=spec.
n;
i--;) ct_j[
i] = 0;
152 for (
int i=spec.m;
i--;) ct_m[
i] = 0;
154 int u = spec.n*spec.m;
157 int t0 = maxmakespan;
158 for (
int i=0;
i<u;
i++) {
159 const Task& t = tasks[
i];
165 }
else if (est == t0) {
166 t0_tasks[u_t0++] =
i;
170 if (iteration == 0) {
173 for (
int i=1;
i<u_t0;
i++)
174 if (tasks[t0_tasks[
i]].p > tasks[t0_tasks[t_j0m0]].p)
179 const Task& t = tasks[t0_tasks[t_j0m0]];
183 std::swap(tasks[--u],tasks[t0_tasks[t_j0m0]]);
185 if (cmax > maxmakespan)
189 maxmakespan =
std::min(maxmakespan,cmax);
190 if (iteration++ > maxIterations)
202 : spec(examples[opt.
size()]),
203 b(*this, (spec.n+spec.
m-2)*spec.n*spec.
m/2, 0,1),
204 makespan(*this, 0, Int::Limits::
max),
205 _start(*this, spec.
m*spec.n, 0, Int::Limits::
max) {
208 IntArgs _dur(spec.m*spec.n, spec.p);
213 crosh(dur, minmakespan, maxmakespan);
214 rel(*
this, makespan <= maxmakespan);
215 rel(*
this, makespan >= minmakespan);
218 for (
int m=0;
m<spec.m;
m++)
219 for (
int j0=0; j0<spec.n-1; j0++)
220 for (
int j1=j0+1; j1<spec.n; j1++) {
223 b[k] == (start(
m,j0) + dur(
m,j0) <= start(
m,j1)));
225 b[k++] == (start(
m,j1) + dur(
m,j1) > start(
m,j0)));
228 for (
int j=0; j<spec.n; j++)
229 for (
int m0=0; m0<spec.m-1; m0++)
230 for (
int m1=m0+1; m1<spec.m; m1++) {
233 b[k] == (start(m0,j) + dur(m0,j) <= start(m1,j)));
235 b[k++] == (start(m1,j) + dur(m1,j) > start(m0,j)));
239 for (
int m=0;
m<spec.m;
m++) {
240 for (
int j=0; j<spec.n; j++) {
241 rel(*
this, start(
m,j) + dur(
m,j) <= makespan);
256 makespan.update(*
this, share, s.
makespan);
257 _start.update(*
this, share, s.
_start);
289 for (
int i=0;
i<spec.m;
i++) {
291 for (
int j=0; j<spec.n; j++) {
292 m[k].
start = _start[
i*spec.
n+j].val();
294 m[k].
p = spec.p[
i*spec.
n+j];
298 os <<
"Machine " <<
i <<
": ";
299 for (
int j=0; j<spec.n; j++)
300 os <<
"\t" << m[j].job <<
"("<<m[j].p<<
")";
301 os <<
" = " << m[spec.n-1].
start+m[spec.n-1].
p << std::endl;
303 os <<
"Makespan: " << makespan << std::endl;
320 opt.
parse(argc,argv);
321 if (opt.
size() >= n_examples) {
322 std::cerr <<
"Error: size must be between 0 and "
323 << n_examples-1 << std::endl;
328 MinimizeScript::run<OpenShop,BAB,SizeOptions>(
opt);
break;
330 MinimizeScript::run<OpenShop,Restart,SizeOptions>(
opt);
break;
346 const int ex0_p[] = {
351 OpenShopSpec ex0(3,3,ex0_p);
353 const int ex1_p[] = {
359 OpenShopSpec ex1(4,4,ex1_p);
361 const int ex2_p[] = {
367 OpenShopSpec ex2(4,4,ex2_p);
369 const int ex3_p[] = {
370 89, 39, 54, 34, 71, 92, 56,
371 19, 13, 81, 46, 91, 73, 27,
372 66, 95, 48, 24, 96, 18, 14,
373 48, 46, 78, 94, 19, 68, 63,
374 60, 28, 91, 75, 52, 9, 7,
375 33, 98, 37, 11, 2, 30, 38,
376 83, 45, 37, 77, 52, 88, 52
378 OpenShopSpec ex3(7,7,ex3_p);
380 const int ex4_p[] = {
381 49, 58, 37, 79, 16, 64, 71, 65, 6, 44, 17, 85, 99, 57, 89, 4, 16, 8, 40, 66,
382 43, 65, 42, 35, 57, 3, 8, 65, 79, 76, 82, 80, 96, 82, 98, 57, 73, 43, 6, 20,
383 82, 49, 7, 18, 94, 76, 41, 17, 43, 15, 53, 10, 83, 24, 79, 62, 53, 77, 23, 70,
384 18, 30, 80, 7, 97, 84, 10, 27, 7, 91, 14, 12, 7, 31, 24, 97, 16, 33, 99, 15,
385 31, 65, 51, 95, 45, 70, 57, 10, 84, 52, 28, 43, 54, 40, 83, 9, 21, 57, 45, 67,
386 70, 45, 48, 39, 10, 37, 22, 53, 48, 50, 76, 48, 57, 6, 43, 13, 45, 93, 42, 11,
387 80, 5, 53, 97, 75, 22, 10, 70, 79, 92, 96, 18, 57, 3, 82, 52, 1, 21, 23, 38,
388 43, 79, 67, 57, 33, 52, 1, 44, 82, 10, 27, 23, 89, 9, 62, 6, 38, 33, 37, 22,
389 68, 20, 5, 25, 16, 80, 13, 73, 35, 36, 13, 53, 97, 50, 17, 54, 35, 86, 24, 56,
390 60, 83, 8, 81, 3, 4, 48, 14, 77, 10, 71, 57, 86, 94, 49, 36, 62, 62, 41, 56,
391 31, 77, 5, 97, 19, 19, 31, 19, 26, 41, 77, 64, 74, 11, 98, 30, 22, 22, 33, 61,
392 7, 89, 46, 13, 33, 55, 84, 16, 21, 45, 15, 71, 57, 42, 82, 13, 62, 98, 36, 45,
393 84, 90, 20, 61, 24, 59, 8, 49, 53, 53, 83, 76, 28, 62, 59, 11, 41, 2, 58, 46,
394 32, 23, 53, 5, 8, 91, 97, 53, 90, 90, 28, 16, 61, 27, 32, 74, 23, 11, 57, 20,
395 62, 85, 79, 96, 62, 85, 43, 53, 12, 36, 95, 37, 2, 48, 46, 81, 97, 54, 5, 77,
396 57, 35, 41, 55, 72, 98, 22, 81, 6, 8, 70, 64, 55, 53, 7, 38, 58, 30, 83, 81,
397 15, 11, 24, 63, 27, 90, 35, 22, 53, 22, 66, 75, 59, 80, 31, 91, 63, 82, 99, 62,
398 4, 18, 99, 6, 65, 21, 28, 93, 16, 26, 1, 16, 46, 59, 45, 90, 69, 76, 25, 53,
399 50, 24, 66, 2, 17, 85, 5, 86, 4, 88, 44, 5, 29, 19, 27, 14, 36, 57, 59, 15,
400 71, 79, 7, 61, 45, 72, 61, 45, 61, 54, 90, 33, 81, 5, 45, 64, 87, 82, 61, 8
402 OpenShopSpec ex4(20,20,ex4_p);
405 OpenShopSpec examples[] = { ex0, ex1, ex2, ex3, ex4 };
407 const unsigned int n_examples =
sizeof(examples) /
sizeof(OpenShopSpec);