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)
199 b(*this, (spec.
n+spec.m-2)*spec.
n*spec.m/2, 0,1),
200 makespan(*this, 0, Int::Limits::
max),
201 _start(*this, spec.m*spec.
n, 0, Int::Limits::
max) {
204 IntArgs _dur(spec.m*spec.n, spec.p);
209 crosh(dur, minmakespan, maxmakespan);
210 rel(*
this, makespan <= maxmakespan);
211 rel(*
this, makespan >= minmakespan);
214 for (
int m=0; m<spec.m; m++)
215 for (
int j0=0; j0<spec.n-1; j0++)
216 for (
int j1=j0+1; j1<spec.n; j1++) {
219 b[k] == (start(m,j0) + dur(m,j0) <= start(m,j1)));
221 b[k++] == (start(m,j1) + dur(m,j1) > start(m,j0)));
224 for (
int j=0; j<spec.n; j++)
225 for (
int m0=0; m0<spec.m-1; m0++)
226 for (
int m1=m0+1; m1<spec.m; m1++) {
229 b[k] == (start(m0,j) + dur(m0,j) <= start(m1,j)));
231 b[k++] == (start(m1,j) + dur(m1,j) > start(m0,j)));
235 for (
int m=0; m<spec.m; m++) {
236 for (
int j=0; j<spec.n; j++) {
237 rel(*
this, start(m,j) + dur(m,j) <= makespan);
251 b.update(*
this, share, s.
b);
285 for (
int i=0;
i<spec.m;
i++) {
287 for (
int j=0; j<spec.n; j++) {
288 m[k].
start = _start[
i*spec.n+j].val();
290 m[k].
p = spec.p[
i*spec.n+j];
294 os <<
"Machine " <<
i <<
": ";
295 for (
int j=0; j<spec.n; j++)
296 os <<
"\t" << m[j].job <<
"("<<m[j].
p<<
")";
297 os <<
" = " << m[spec.n-1].
start+m[spec.n-1].
p << std::endl;
299 os <<
"Makespan: " << makespan << std::endl;
314 if (
opt.size() >= n_examples) {
315 std::cerr <<
"Error: size must be between 0 and "
316 << n_examples-1 << std::endl;
319 IntMinimizeScript::run<OpenShop,BAB,SizeOptions>(
opt);
334 const int ex0_p[] = {
339 OpenShopSpec ex0(3,3,ex0_p);
341 const int ex1_p[] = {
347 OpenShopSpec ex1(4,4,ex1_p);
349 const int ex2_p[] = {
355 OpenShopSpec ex2(4,4,ex2_p);
357 const int ex3_p[] = {
358 89, 39, 54, 34, 71, 92, 56,
359 19, 13, 81, 46, 91, 73, 27,
360 66, 95, 48, 24, 96, 18, 14,
361 48, 46, 78, 94, 19, 68, 63,
362 60, 28, 91, 75, 52, 9, 7,
363 33, 98, 37, 11, 2, 30, 38,
364 83, 45, 37, 77, 52, 88, 52
366 OpenShopSpec ex3(7,7,ex3_p);
368 const int ex4_p[] = {
369 49, 58, 37, 79, 16, 64, 71, 65, 6, 44, 17, 85, 99, 57, 89, 4, 16, 8, 40, 66,
370 43, 65, 42, 35, 57, 3, 8, 65, 79, 76, 82, 80, 96, 82, 98, 57, 73, 43, 6, 20,
371 82, 49, 7, 18, 94, 76, 41, 17, 43, 15, 53, 10, 83, 24, 79, 62, 53, 77, 23, 70,
372 18, 30, 80, 7, 97, 84, 10, 27, 7, 91, 14, 12, 7, 31, 24, 97, 16, 33, 99, 15,
373 31, 65, 51, 95, 45, 70, 57, 10, 84, 52, 28, 43, 54, 40, 83, 9, 21, 57, 45, 67,
374 70, 45, 48, 39, 10, 37, 22, 53, 48, 50, 76, 48, 57, 6, 43, 13, 45, 93, 42, 11,
375 80, 5, 53, 97, 75, 22, 10, 70, 79, 92, 96, 18, 57, 3, 82, 52, 1, 21, 23, 38,
376 43, 79, 67, 57, 33, 52, 1, 44, 82, 10, 27, 23, 89, 9, 62, 6, 38, 33, 37, 22,
377 68, 20, 5, 25, 16, 80, 13, 73, 35, 36, 13, 53, 97, 50, 17, 54, 35, 86, 24, 56,
378 60, 83, 8, 81, 3, 4, 48, 14, 77, 10, 71, 57, 86, 94, 49, 36, 62, 62, 41, 56,
379 31, 77, 5, 97, 19, 19, 31, 19, 26, 41, 77, 64, 74, 11, 98, 30, 22, 22, 33, 61,
380 7, 89, 46, 13, 33, 55, 84, 16, 21, 45, 15, 71, 57, 42, 82, 13, 62, 98, 36, 45,
381 84, 90, 20, 61, 24, 59, 8, 49, 53, 53, 83, 76, 28, 62, 59, 11, 41, 2, 58, 46,
382 32, 23, 53, 5, 8, 91, 97, 53, 90, 90, 28, 16, 61, 27, 32, 74, 23, 11, 57, 20,
383 62, 85, 79, 96, 62, 85, 43, 53, 12, 36, 95, 37, 2, 48, 46, 81, 97, 54, 5, 77,
384 57, 35, 41, 55, 72, 98, 22, 81, 6, 8, 70, 64, 55, 53, 7, 38, 58, 30, 83, 81,
385 15, 11, 24, 63, 27, 90, 35, 22, 53, 22, 66, 75, 59, 80, 31, 91, 63, 82, 99, 62,
386 4, 18, 99, 6, 65, 21, 28, 93, 16, 26, 1, 16, 46, 59, 45, 90, 69, 76, 25, 53,
387 50, 24, 66, 2, 17, 85, 5, 86, 4, 88, 44, 5, 29, 19, 27, 14, 36, 57, 59, 15,
388 71, 79, 7, 61, 45, 72, 61, 45, 61, 54, 90, 33, 81, 5, 45, 64, 87, 82, 61, 8
390 OpenShopSpec ex4(20,20,ex4_p);
393 OpenShopSpec examples[] = { ex0, ex1, ex2, ex3, ex4 };
395 const unsigned int n_examples =
sizeof(examples) /
sizeof(OpenShopSpec);