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++) {
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)
197 : spec(examples[opt.
size()]),
198 b(*this, (spec.
n+spec.m-2)*spec.
n*spec.m/2, 0,1),
199 makespan(*this, 0, Int::Limits::
max),
200 _start(*this, spec.m*spec.
n, 0, Int::Limits::
max) {
203 IntArgs _dur(spec.m*spec.n, spec.p);
208 crosh(dur, minmakespan, maxmakespan);
209 rel(*
this, makespan <= maxmakespan);
210 rel(*
this, makespan >= minmakespan);
213 for (
int m=0; m<spec.m; m++)
214 for (
int j0=0; j0<spec.n-1; j0++)
215 for (
int j1=j0+1; j1<spec.n; j1++) {
218 b[k] == (start(m,j0) + dur(m,j0) <= start(m,j1)));
220 b[k++] == (start(m,j1) + dur(m,j1) > start(m,j0)));
223 for (
int j=0; j<spec.n; j++)
224 for (
int m0=0; m0<spec.m-1; m0++)
225 for (
int m1=m0+1; m1<spec.m; m1++) {
228 b[k] == (start(m0,j) + dur(m0,j) <= start(m1,j)));
230 b[k++] == (start(m1,j) + dur(m1,j) > start(m0,j)));
234 for (
int m=0; m<spec.m; m++) {
235 for (
int j=0; j<spec.n; j++) {
236 rel(*
this, start(m,j) + dur(m,j) <= makespan);
250 b.update(*
this, share, s.
b);
251 makespan.update(*
this, share, s.
makespan);
252 _start.update(*
this, share, s.
_start);
284 for (
int i=0;
i<spec.m;
i++) {
286 for (
int j=0; j<spec.n; j++) {
287 m[k].
start = _start[
i*spec.
n+j].val();
289 m[k].
p = spec.p[
i*spec.
n+j];
293 os <<
"Machine " <<
i <<
": ";
294 for (
int j=0; j<spec.n; j++)
295 os <<
"\t" << m[j].job <<
"("<<m[j].
p<<
")";
296 os <<
" = " << m[spec.n-1].
start+m[spec.n-1].
p << std::endl;
298 os <<
"Makespan: " << makespan << std::endl;
312 opt.
parse(argc,argv);
313 if (opt.
size() >= n_examples) {
314 std::cerr <<
"Error: size must be between 0 and "
315 << n_examples-1 << std::endl;
318 MinimizeScript::run<OpenShop,BAB,SizeOptions>(
opt);
333 const int ex0_p[] = {
338 OpenShopSpec ex0(3,3,ex0_p);
340 const int ex1_p[] = {
346 OpenShopSpec ex1(4,4,ex1_p);
348 const int ex2_p[] = {
354 OpenShopSpec ex2(4,4,ex2_p);
356 const int ex3_p[] = {
357 89, 39, 54, 34, 71, 92, 56,
358 19, 13, 81, 46, 91, 73, 27,
359 66, 95, 48, 24, 96, 18, 14,
360 48, 46, 78, 94, 19, 68, 63,
361 60, 28, 91, 75, 52, 9, 7,
362 33, 98, 37, 11, 2, 30, 38,
363 83, 45, 37, 77, 52, 88, 52
365 OpenShopSpec ex3(7,7,ex3_p);
367 const int ex4_p[] = {
368 49, 58, 37, 79, 16, 64, 71, 65, 6, 44, 17, 85, 99, 57, 89, 4, 16, 8, 40, 66,
369 43, 65, 42, 35, 57, 3, 8, 65, 79, 76, 82, 80, 96, 82, 98, 57, 73, 43, 6, 20,
370 82, 49, 7, 18, 94, 76, 41, 17, 43, 15, 53, 10, 83, 24, 79, 62, 53, 77, 23, 70,
371 18, 30, 80, 7, 97, 84, 10, 27, 7, 91, 14, 12, 7, 31, 24, 97, 16, 33, 99, 15,
372 31, 65, 51, 95, 45, 70, 57, 10, 84, 52, 28, 43, 54, 40, 83, 9, 21, 57, 45, 67,
373 70, 45, 48, 39, 10, 37, 22, 53, 48, 50, 76, 48, 57, 6, 43, 13, 45, 93, 42, 11,
374 80, 5, 53, 97, 75, 22, 10, 70, 79, 92, 96, 18, 57, 3, 82, 52, 1, 21, 23, 38,
375 43, 79, 67, 57, 33, 52, 1, 44, 82, 10, 27, 23, 89, 9, 62, 6, 38, 33, 37, 22,
376 68, 20, 5, 25, 16, 80, 13, 73, 35, 36, 13, 53, 97, 50, 17, 54, 35, 86, 24, 56,
377 60, 83, 8, 81, 3, 4, 48, 14, 77, 10, 71, 57, 86, 94, 49, 36, 62, 62, 41, 56,
378 31, 77, 5, 97, 19, 19, 31, 19, 26, 41, 77, 64, 74, 11, 98, 30, 22, 22, 33, 61,
379 7, 89, 46, 13, 33, 55, 84, 16, 21, 45, 15, 71, 57, 42, 82, 13, 62, 98, 36, 45,
380 84, 90, 20, 61, 24, 59, 8, 49, 53, 53, 83, 76, 28, 62, 59, 11, 41, 2, 58, 46,
381 32, 23, 53, 5, 8, 91, 97, 53, 90, 90, 28, 16, 61, 27, 32, 74, 23, 11, 57, 20,
382 62, 85, 79, 96, 62, 85, 43, 53, 12, 36, 95, 37, 2, 48, 46, 81, 97, 54, 5, 77,
383 57, 35, 41, 55, 72, 98, 22, 81, 6, 8, 70, 64, 55, 53, 7, 38, 58, 30, 83, 81,
384 15, 11, 24, 63, 27, 90, 35, 22, 53, 22, 66, 75, 59, 80, 31, 91, 63, 82, 99, 62,
385 4, 18, 99, 6, 65, 21, 28, 93, 16, 26, 1, 16, 46, 59, 45, 90, 69, 76, 25, 53,
386 50, 24, 66, 2, 17, 85, 5, 86, 4, 88, 44, 5, 29, 19, 27, 14, 36, 57, 59, 15,
387 71, 79, 7, 61, 45, 72, 61, 45, 61, 54, 90, 33, 81, 5, 45, 64, 87, 82, 61, 8
389 OpenShopSpec ex4(20,20,ex4_p);
392 OpenShopSpec examples[] = { ex0, ex1, ex2, ex3, ex4 };
394 const unsigned int n_examples =
sizeof(examples) /
sizeof(OpenShopSpec);