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