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 : spec(examples[opt.size()]),
00198 b(*this, (spec.n+spec.m-2)*spec.n*spec.m/2, 0,1),
00199 makespan(*this, 0, Int::Limits::max),
00200 _start(*this, spec.m*spec.n, 0, Int::Limits::max) {
00201
00202 Matrix<IntVarArray> start(_start, spec.m, spec.n);
00203 IntArgs _dur(spec.m*spec.n, spec.p);
00204 Matrix<IntArgs> dur(_dur, spec.m, spec.n);
00205
00206 int minmakespan;
00207 int maxmakespan;
00208 crosh(dur, minmakespan, maxmakespan);
00209 rel(*this, makespan <= maxmakespan);
00210 rel(*this, makespan >= minmakespan);
00211
00212 int k=0;
00213 for (int m=0; m<spec.m; m++)
00214 for (int j0=0; j0<spec.n-1; j0++)
00215 for (int j1=j0+1; j1<spec.n; j1++) {
00216
00217 rel(*this,
00218 b[k] == (start(m,j0) + dur(m,j0) <= start(m,j1)));
00219 rel(*this,
00220 b[k++] == (start(m,j1) + dur(m,j1) > start(m,j0)));
00221 }
00222
00223 for (int j=0; j<spec.n; j++)
00224 for (int m0=0; m0<spec.m-1; m0++)
00225 for (int m1=m0+1; m1<spec.m; m1++) {
00226
00227 rel(*this,
00228 b[k] == (start(m0,j) + dur(m0,j) <= start(m1,j)));
00229 rel(*this,
00230 b[k++] == (start(m1,j) + dur(m1,j) > start(m0,j)));
00231 }
00232
00233
00234 for (int m=0; m<spec.m; m++) {
00235 for (int j=0; j<spec.n; j++) {
00236 rel(*this, start(m,j) + dur(m,j) <= makespan);
00237 }
00238 }
00239
00240
00241 branch(*this, b, INT_VAR_AFC_MAX(opt.decay()), INT_VAL_MAX());
00242
00243 assign(*this, _start, INT_ASSIGN_MIN());
00244
00245 assign(*this, makespan, INT_ASSIGN_MIN());
00246 }
00247
00249 OpenShop(bool share, OpenShop& s) : IntMinimizeScript(share,s), spec(s.spec) {
00250 b.update(*this, share, s.b);
00251 makespan.update(*this, share, s.makespan);
00252 _start.update(*this, share, s._start);
00253 }
00254
00256 virtual Space*
00257 copy(bool share) {
00258 return new OpenShop(share,*this);
00259 }
00260
00262 virtual IntVar
00263 cost(void) const {
00264 return makespan;
00265 }
00266
00268 class PrintTask {
00269 public:
00270 int start;
00271 int job;
00272 int p;
00274 bool operator()(const PrintTask& t1, const PrintTask& t2) {
00275 return t1.start < t2.start;
00276 }
00277 };
00278
00280 virtual void
00281 print(std::ostream& os) const {
00282 Region re(*this);
00283 PrintTask* m = re.alloc<PrintTask>(spec.n);
00284 for (int i=0; i<spec.m; i++) {
00285 int k=0;
00286 for (int j=0; j<spec.n; j++) {
00287 m[k].start = _start[i*spec.n+j].val();
00288 m[k].job = j;
00289 m[k].p = spec.p[i*spec.n+j];
00290 k++;
00291 }
00292 Support::quicksort(m, spec.n, m[0]);
00293 os << "Machine " << i << ": ";
00294 for (int j=0; j<spec.n; j++)
00295 os << "\t" << m[j].job << "("<<m[j].p<<")";
00296 os << " = " << m[spec.n-1].start+m[spec.n-1].p << std::endl;
00297 }
00298 os << "Makespan: " << makespan << std::endl;
00299 }
00300
00301 };
00302
00306 int
00307 main(int argc, char* argv[]) {
00308 SizeOptions opt("OpenShop");
00309 opt.iterations(500);
00310 opt.size(0);
00311 opt.solutions(0);
00312 opt.parse(argc,argv);
00313 if (opt.size() >= n_examples) {
00314 std::cerr << "Error: size must be between 0 and "
00315 << n_examples-1 << std::endl;
00316 return 1;
00317 }
00318 IntMinimizeScript::run<OpenShop,BAB,SizeOptions>(opt);
00319 return 0;
00320 }
00321
00322 namespace {
00323
00332
00333 const int ex0_p[] = {
00334 661,6,333,
00335 168,489,343,
00336 171,505,324
00337 };
00338 OpenShopSpec ex0(3,3,ex0_p);
00339
00340 const int ex1_p[] = {
00341 54, 34, 61, 2,
00342 9, 15, 89, 70,
00343 38, 19, 28, 87,
00344 95, 34, 7, 29
00345 };
00346 OpenShopSpec ex1(4,4,ex1_p);
00347
00348 const int ex2_p[] = {
00349 5, 70, 45, 83,
00350 24, 80, 58, 45,
00351 29, 56, 29, 61,
00352 43, 64, 45, 74
00353 };
00354 OpenShopSpec ex2(4,4,ex2_p);
00355
00356 const int ex3_p[] = {
00357 89, 39, 54, 34, 71, 92, 56,
00358 19, 13, 81, 46, 91, 73, 27,
00359 66, 95, 48, 24, 96, 18, 14,
00360 48, 46, 78, 94, 19, 68, 63,
00361 60, 28, 91, 75, 52, 9, 7,
00362 33, 98, 37, 11, 2, 30, 38,
00363 83, 45, 37, 77, 52, 88, 52
00364 };
00365 OpenShopSpec ex3(7,7,ex3_p);
00366
00367 const int ex4_p[] = {
00368 49, 58, 37, 79, 16, 64, 71, 65, 6, 44, 17, 85, 99, 57, 89, 4, 16, 8, 40, 66,
00369 43, 65, 42, 35, 57, 3, 8, 65, 79, 76, 82, 80, 96, 82, 98, 57, 73, 43, 6, 20,
00370 82, 49, 7, 18, 94, 76, 41, 17, 43, 15, 53, 10, 83, 24, 79, 62, 53, 77, 23, 70,
00371 18, 30, 80, 7, 97, 84, 10, 27, 7, 91, 14, 12, 7, 31, 24, 97, 16, 33, 99, 15,
00372 31, 65, 51, 95, 45, 70, 57, 10, 84, 52, 28, 43, 54, 40, 83, 9, 21, 57, 45, 67,
00373 70, 45, 48, 39, 10, 37, 22, 53, 48, 50, 76, 48, 57, 6, 43, 13, 45, 93, 42, 11,
00374 80, 5, 53, 97, 75, 22, 10, 70, 79, 92, 96, 18, 57, 3, 82, 52, 1, 21, 23, 38,
00375 43, 79, 67, 57, 33, 52, 1, 44, 82, 10, 27, 23, 89, 9, 62, 6, 38, 33, 37, 22,
00376 68, 20, 5, 25, 16, 80, 13, 73, 35, 36, 13, 53, 97, 50, 17, 54, 35, 86, 24, 56,
00377 60, 83, 8, 81, 3, 4, 48, 14, 77, 10, 71, 57, 86, 94, 49, 36, 62, 62, 41, 56,
00378 31, 77, 5, 97, 19, 19, 31, 19, 26, 41, 77, 64, 74, 11, 98, 30, 22, 22, 33, 61,
00379 7, 89, 46, 13, 33, 55, 84, 16, 21, 45, 15, 71, 57, 42, 82, 13, 62, 98, 36, 45,
00380 84, 90, 20, 61, 24, 59, 8, 49, 53, 53, 83, 76, 28, 62, 59, 11, 41, 2, 58, 46,
00381 32, 23, 53, 5, 8, 91, 97, 53, 90, 90, 28, 16, 61, 27, 32, 74, 23, 11, 57, 20,
00382 62, 85, 79, 96, 62, 85, 43, 53, 12, 36, 95, 37, 2, 48, 46, 81, 97, 54, 5, 77,
00383 57, 35, 41, 55, 72, 98, 22, 81, 6, 8, 70, 64, 55, 53, 7, 38, 58, 30, 83, 81,
00384 15, 11, 24, 63, 27, 90, 35, 22, 53, 22, 66, 75, 59, 80, 31, 91, 63, 82, 99, 62,
00385 4, 18, 99, 6, 65, 21, 28, 93, 16, 26, 1, 16, 46, 59, 45, 90, 69, 76, 25, 53,
00386 50, 24, 66, 2, 17, 85, 5, 86, 4, 88, 44, 5, 29, 19, 27, 14, 36, 57, 59, 15,
00387 71, 79, 7, 61, 45, 72, 61, 45, 61, 54, 90, 33, 81, 5, 45, 64, 87, 82, 61, 8
00388 };
00389 OpenShopSpec ex4(20,20,ex4_p);
00390
00392 OpenShopSpec examples[] = { ex0, ex1, ex2, ex3, ex4 };
00394 const unsigned int n_examples = sizeof(examples) / sizeof(OpenShopSpec);
00395
00397 }
00398
00399