00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 #include <gecode/driver.hh>
00039 #include <gecode/int.hh>
00040 #include <gecode/minimodel.hh>
00041
00042 using namespace Gecode;
00043
00044 namespace {
00049 class OpenShopSpec {
00050 public:
00051 const int m;
00052 const int n;
00053 const int* p;
00055 OpenShopSpec(int m0, int n0, const int* p0) : m(m0), n(n0), p(p0) {}
00056 };
00057
00058 extern OpenShopSpec examples[];
00059 extern const unsigned int n_examples;
00060 }
00061
00068 class OpenShop : public IntMinimizeScript {
00069 protected:
00071 const OpenShopSpec& spec;
00073 BoolVarArray b;
00075 IntVar makespan;
00077 IntVarArray _start;
00078
00080 class Task {
00081 public:
00082 int j;
00083 int m;
00084 int p;
00086 Task(void) {}
00088 Task(int j0, int m0, int p0) : j(j0), m(m0), p(p0) {}
00089 };
00090
00100 void crosh(Matrix<IntArgs>& dur, int& minmakespan, int& maxmakespan) {
00101 Support::RandomGenerator rnd;
00102
00103
00104 maxmakespan = 0;
00105 for (int i=0; i<spec.m; i++)
00106 for (int j=0; j<spec.n; j++)
00107 maxmakespan += dur(i,j);
00108
00109
00110 minmakespan = 0;
00111 for (int i=0; i<spec.m; i++) {
00112 int ms = 0;
00113 for (int j=0; j<spec.n; j++) {
00114 ms += dur(i,j);
00115 }
00116 minmakespan = std::max(minmakespan, ms);
00117 }
00118 for (int j=0; j<spec.n; j++) {
00119 int ms = 0;
00120 for (int i=0; i<spec.m; i++) {
00121 ms += dur(i,j);
00122 }
00123 minmakespan = std::max(minmakespan, ms);
00124 }
00125
00126 Region re(*this);
00127 int* ct_j = re.alloc<int>(spec.n);
00128 int* ct_m = re.alloc<int>(spec.m);
00129 Task* tasks = re.alloc<Task>(spec.n*spec.m);
00130 int k=0;
00131 for (int i=spec.m; i--;)
00132 for (int j=spec.n; j--;)
00133 new (&tasks[k++]) Task(j,i,dur(i,j));
00134 int* t0_tasks = re.alloc<int>(spec.n*spec.m);
00135
00136 bool stopCROSH = false;
00137
00138 int maxIterations;
00139 switch (spec.n) {
00140 case 3: maxIterations = 5; break;
00141 case 4: maxIterations = 25; break;
00142 case 5: maxIterations = 50; break;
00143 case 6: maxIterations = 1000; break;
00144 case 7: maxIterations = 10000; break;
00145 case 8: maxIterations = 10000; break;
00146 case 9: maxIterations = 10000; break;
00147 default: maxIterations = 25000; break;
00148 }
00149 int iteration = 0;
00150 while (!stopCROSH && maxmakespan > minmakespan) {
00151 for (int i=spec.n; i--;) ct_j[i] = 0;
00152 for (int i=spec.m; i--;) ct_m[i] = 0;
00153 int cmax = 0;
00154 int u = spec.n*spec.m;
00155 while (u > 0) {
00156 int u_t0 = 0;
00157 int t0 = maxmakespan;
00158 for (int i=0; i<u; i++) {
00159 const Task& t = tasks[i];
00160 int est = std::max(ct_j[t.j], ct_m[t.m]);
00161 if (est < t0) {
00162 t0 = est;
00163 t0_tasks[0] = i;
00164 u_t0 = 1;
00165 } else if (est == t0) {
00166 t0_tasks[u_t0++] = i;
00167 }
00168 }
00169 int t_j0m0;
00170 if (iteration == 0) {
00171
00172 t_j0m0 = 0;
00173 for (int i=1; i<u_t0; i++)
00174 if (tasks[t0_tasks[i]].p > tasks[t0_tasks[t_j0m0]].p)
00175 t_j0m0 = i;
00176 } else {
00177 t_j0m0 = rnd(u_t0);
00178 }
00179 const Task& t = tasks[t0_tasks[t_j0m0]];
00180 int ect = t0 + t.p;
00181 ct_j[t.j] = ect;
00182 ct_m[t.m] = ect;
00183 std::swap(tasks[--u],tasks[t0_tasks[t_j0m0]]);
00184 cmax = std::max(cmax, ect);
00185 if (cmax > maxmakespan)
00186 break;
00187 }
00188
00189 maxmakespan = std::min(maxmakespan,cmax);
00190 if (iteration++ > maxIterations)
00191 stopCROSH = true;
00192 }
00193 }
00194 public:
00196 OpenShop(const SizeOptions& opt)
00197 : IntMinimizeScript(opt),
00198 spec(examples[opt.size()]),
00199 b(*this, (spec.n+spec.m-2)*spec.n*spec.m/2, 0,1),
00200 makespan(*this, 0, Int::Limits::max),
00201 _start(*this, spec.m*spec.n, 0, Int::Limits::max) {
00202
00203 Matrix<IntVarArray> start(_start, spec.m, spec.n);
00204 IntArgs _dur(spec.m*spec.n, spec.p);
00205 Matrix<IntArgs> dur(_dur, spec.m, spec.n);
00206
00207 int minmakespan;
00208 int maxmakespan;
00209 crosh(dur, minmakespan, maxmakespan);
00210 rel(*this, makespan <= maxmakespan);
00211 rel(*this, makespan >= minmakespan);
00212
00213 int k=0;
00214 for (int m=0; m<spec.m; m++)
00215 for (int j0=0; j0<spec.n-1; j0++)
00216 for (int j1=j0+1; j1<spec.n; j1++) {
00217
00218 rel(*this,
00219 b[k] == (start(m,j0) + dur(m,j0) <= start(m,j1)));
00220 rel(*this,
00221 b[k++] == (start(m,j1) + dur(m,j1) > start(m,j0)));
00222 }
00223
00224 for (int j=0; j<spec.n; j++)
00225 for (int m0=0; m0<spec.m-1; m0++)
00226 for (int m1=m0+1; m1<spec.m; m1++) {
00227
00228 rel(*this,
00229 b[k] == (start(m0,j) + dur(m0,j) <= start(m1,j)));
00230 rel(*this,
00231 b[k++] == (start(m1,j) + dur(m1,j) > start(m0,j)));
00232 }
00233
00234
00235 for (int m=0; m<spec.m; m++) {
00236 for (int j=0; j<spec.n; j++) {
00237 rel(*this, start(m,j) + dur(m,j) <= makespan);
00238 }
00239 }
00240
00241
00242 branch(*this, b, BOOL_VAR_AFC_MAX(opt.decay()), BOOL_VAL_MAX());
00243
00244 assign(*this, _start, INT_ASSIGN_MIN());
00245
00246 assign(*this, makespan, INT_ASSIGN_MIN());
00247 }
00248
00250 OpenShop(bool share, OpenShop& s) : IntMinimizeScript(share,s), spec(s.spec) {
00251 b.update(*this, share, s.b);
00252 makespan.update(*this, share, s.makespan);
00253 _start.update(*this, share, s._start);
00254 }
00255
00257 virtual Space*
00258 copy(bool share) {
00259 return new OpenShop(share,*this);
00260 }
00261
00263 virtual IntVar
00264 cost(void) const {
00265 return makespan;
00266 }
00267
00269 class PrintTask {
00270 public:
00271 int start;
00272 int job;
00273 int p;
00275 bool operator()(const PrintTask& t1, const PrintTask& t2) {
00276 return t1.start < t2.start;
00277 }
00278 };
00279
00281 virtual void
00282 print(std::ostream& os) const {
00283 Region re(*this);
00284 PrintTask* m = re.alloc<PrintTask>(spec.n);
00285 for (int i=0; i<spec.m; i++) {
00286 int k=0;
00287 for (int j=0; j<spec.n; j++) {
00288 m[k].start = _start[i*spec.n+j].val();
00289 m[k].job = j;
00290 m[k].p = spec.p[i*spec.n+j];
00291 k++;
00292 }
00293 Support::quicksort(m, spec.n, m[0]);
00294 os << "Machine " << i << ": ";
00295 for (int j=0; j<spec.n; j++)
00296 os << "\t" << m[j].job << "("<<m[j].p<<")";
00297 os << " = " << m[spec.n-1].start+m[spec.n-1].p << std::endl;
00298 }
00299 os << "Makespan: " << makespan << std::endl;
00300 }
00301
00302 };
00303
00307 int
00308 main(int argc, char* argv[]) {
00309 SizeOptions opt("OpenShop");
00310 opt.iterations(500);
00311 opt.size(0);
00312 opt.solutions(0);
00313 opt.parse(argc,argv);
00314 if (opt.size() >= n_examples) {
00315 std::cerr << "Error: size must be between 0 and "
00316 << n_examples-1 << std::endl;
00317 return 1;
00318 }
00319 IntMinimizeScript::run<OpenShop,BAB,SizeOptions>(opt);
00320 return 0;
00321 }
00322
00323 namespace {
00324
00333
00334 const int ex0_p[] = {
00335 661,6,333,
00336 168,489,343,
00337 171,505,324
00338 };
00339 OpenShopSpec ex0(3,3,ex0_p);
00340
00341 const int ex1_p[] = {
00342 54, 34, 61, 2,
00343 9, 15, 89, 70,
00344 38, 19, 28, 87,
00345 95, 34, 7, 29
00346 };
00347 OpenShopSpec ex1(4,4,ex1_p);
00348
00349 const int ex2_p[] = {
00350 5, 70, 45, 83,
00351 24, 80, 58, 45,
00352 29, 56, 29, 61,
00353 43, 64, 45, 74
00354 };
00355 OpenShopSpec ex2(4,4,ex2_p);
00356
00357 const int ex3_p[] = {
00358 89, 39, 54, 34, 71, 92, 56,
00359 19, 13, 81, 46, 91, 73, 27,
00360 66, 95, 48, 24, 96, 18, 14,
00361 48, 46, 78, 94, 19, 68, 63,
00362 60, 28, 91, 75, 52, 9, 7,
00363 33, 98, 37, 11, 2, 30, 38,
00364 83, 45, 37, 77, 52, 88, 52
00365 };
00366 OpenShopSpec ex3(7,7,ex3_p);
00367
00368 const int ex4_p[] = {
00369 49, 58, 37, 79, 16, 64, 71, 65, 6, 44, 17, 85, 99, 57, 89, 4, 16, 8, 40, 66,
00370 43, 65, 42, 35, 57, 3, 8, 65, 79, 76, 82, 80, 96, 82, 98, 57, 73, 43, 6, 20,
00371 82, 49, 7, 18, 94, 76, 41, 17, 43, 15, 53, 10, 83, 24, 79, 62, 53, 77, 23, 70,
00372 18, 30, 80, 7, 97, 84, 10, 27, 7, 91, 14, 12, 7, 31, 24, 97, 16, 33, 99, 15,
00373 31, 65, 51, 95, 45, 70, 57, 10, 84, 52, 28, 43, 54, 40, 83, 9, 21, 57, 45, 67,
00374 70, 45, 48, 39, 10, 37, 22, 53, 48, 50, 76, 48, 57, 6, 43, 13, 45, 93, 42, 11,
00375 80, 5, 53, 97, 75, 22, 10, 70, 79, 92, 96, 18, 57, 3, 82, 52, 1, 21, 23, 38,
00376 43, 79, 67, 57, 33, 52, 1, 44, 82, 10, 27, 23, 89, 9, 62, 6, 38, 33, 37, 22,
00377 68, 20, 5, 25, 16, 80, 13, 73, 35, 36, 13, 53, 97, 50, 17, 54, 35, 86, 24, 56,
00378 60, 83, 8, 81, 3, 4, 48, 14, 77, 10, 71, 57, 86, 94, 49, 36, 62, 62, 41, 56,
00379 31, 77, 5, 97, 19, 19, 31, 19, 26, 41, 77, 64, 74, 11, 98, 30, 22, 22, 33, 61,
00380 7, 89, 46, 13, 33, 55, 84, 16, 21, 45, 15, 71, 57, 42, 82, 13, 62, 98, 36, 45,
00381 84, 90, 20, 61, 24, 59, 8, 49, 53, 53, 83, 76, 28, 62, 59, 11, 41, 2, 58, 46,
00382 32, 23, 53, 5, 8, 91, 97, 53, 90, 90, 28, 16, 61, 27, 32, 74, 23, 11, 57, 20,
00383 62, 85, 79, 96, 62, 85, 43, 53, 12, 36, 95, 37, 2, 48, 46, 81, 97, 54, 5, 77,
00384 57, 35, 41, 55, 72, 98, 22, 81, 6, 8, 70, 64, 55, 53, 7, 38, 58, 30, 83, 81,
00385 15, 11, 24, 63, 27, 90, 35, 22, 53, 22, 66, 75, 59, 80, 31, 91, 63, 82, 99, 62,
00386 4, 18, 99, 6, 65, 21, 28, 93, 16, 26, 1, 16, 46, 59, 45, 90, 69, 76, 25, 53,
00387 50, 24, 66, 2, 17, 85, 5, 86, 4, 88, 44, 5, 29, 19, 27, 14, 36, 57, 59, 15,
00388 71, 79, 7, 61, 45, 72, 61, 45, 61, 54, 90, 33, 81, 5, 45, 64, 87, 82, 61, 8
00389 };
00390 OpenShopSpec ex4(20,20,ex4_p);
00391
00393 OpenShopSpec examples[] = { ex0, ex1, ex2, ex3, ex4 };
00395 const unsigned int n_examples = sizeof(examples) / sizeof(OpenShopSpec);
00396
00398 }
00399
00400