open-shop.cpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Guido Tack <tack@gecode.org> 00005 * 00006 * Copyright: 00007 * Guido Tack, 2009 00008 * 00009 * Last modified: 00010 * $Date: 2010-10-07 11:52:01 +0200 (Thu, 07 Oct 2010) $ by $Author: schulte $ 00011 * $Revision: 11473 $ 00012 * 00013 * This file is part of Gecode, the generic constraint 00014 * development environment: 00015 * http://www.gecode.org 00016 * 00017 * Permission is hereby granted, free of charge, to any person obtaining 00018 * a copy of this software and associated documentation files (the 00019 * "Software"), to deal in the Software without restriction, including 00020 * without limitation the rights to use, copy, modify, merge, publish, 00021 * distribute, sublicense, and/or sell copies of the Software, and to 00022 * permit persons to whom the Software is furnished to do so, subject to 00023 * the following conditions: 00024 * 00025 * The above copyright notice and this permission notice shall be 00026 * included in all copies or substantial portions of the Software. 00027 * 00028 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00029 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00030 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00031 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00032 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00033 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00034 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 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; //< number of machines 00052 const int n; //< number of jobs 00053 const int* p; //< processing times of the tasks 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 MinimizeScript { 00069 protected: 00071 const OpenShopSpec& spec; 00073 BoolVarArray b; 00075 IntVar makespan; 00077 IntVarArray _start; 00078 00080 class Task { 00081 public: 00082 int j; //< Job 00083 int m; //< Machine 00084 int p; //< Processing time 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 // Compute maximum makespan as the sum of all production times. 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 // Compute minimum makespan as the maximum of individual jobs and machines 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); // Job completion time 00128 int* ct_m = re.alloc<int>(spec.m); // Machine completion time 00129 Task* tasks = re.alloc<Task>(spec.n*spec.m); // Tasks 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); // Earliest possible tasks 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; // Current makespan 00154 int u = spec.n*spec.m; // Consider all tasks 00155 while (u > 0) { 00156 int u_t0 = 0; // Set of selectable tasks 00157 int t0 = maxmakespan; // Minimal head of unscheduled tasks 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]); // Head of T_jm 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 // In the first iteration, select tasks with longest processing time 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); // Select random task 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]]); // Remove task from u 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; // Iterate a couple of times 00192 } 00193 } 00194 public: 00196 enum { 00197 SEARCH_BAB, 00198 SEARCH_RESTART 00199 }; 00201 OpenShop(const SizeOptions& opt) 00202 : spec(examples[opt.size()]), 00203 b(*this, (spec.n+spec.m-2)*spec.n*spec.m/2, 0,1), 00204 makespan(*this, 0, Int::Limits::max), 00205 _start(*this, spec.m*spec.n, 0, Int::Limits::max) { 00206 00207 Matrix<IntVarArray> start(_start, spec.m, spec.n); 00208 IntArgs _dur(spec.m*spec.n, spec.p); 00209 Matrix<IntArgs> dur(_dur, spec.m, spec.n); 00210 00211 int minmakespan; 00212 int maxmakespan; 00213 crosh(dur, minmakespan, maxmakespan); 00214 rel(*this, makespan <= maxmakespan); 00215 rel(*this, makespan >= minmakespan); 00216 00217 int k=0; 00218 for (int m=0; m<spec.m; m++) 00219 for (int j0=0; j0<spec.n-1; j0++) 00220 for (int j1=j0+1; j1<spec.n; j1++) { 00221 // The tasks on machine m of jobs j0 and j1 must be disjoint 00222 rel(*this, 00223 b[k] == (start(m,j0) + dur(m,j0) <= start(m,j1))); 00224 rel(*this, 00225 b[k++] == (start(m,j1) + dur(m,j1) > start(m,j0))); 00226 } 00227 00228 for (int j=0; j<spec.n; j++) 00229 for (int m0=0; m0<spec.m-1; m0++) 00230 for (int m1=m0+1; m1<spec.m; m1++) { 00231 // The tasks in job j on machine m0 and m1 must be disjoint 00232 rel(*this, 00233 b[k] == (start(m0,j) + dur(m0,j) <= start(m1,j))); 00234 rel(*this, 00235 b[k++] == (start(m1,j) + dur(m1,j) > start(m0,j))); 00236 } 00237 00238 // The makespan is greater than the end time of the latest job 00239 for (int m=0; m<spec.m; m++) { 00240 for (int j=0; j<spec.n; j++) { 00241 rel(*this, start(m,j) + dur(m,j) <= makespan); 00242 } 00243 } 00244 00245 // First branch over the precedences 00246 branch(*this, b, INT_VAR_AFC_MAX, INT_VAL_MAX); 00247 // When the precedences are fixed, simply assign the start times 00248 assign(*this, _start, INT_ASSIGN_MIN); 00249 // When the start times are fixed, use the tightest makespan 00250 assign(*this, makespan, INT_ASSIGN_MIN); 00251 } 00252 00254 OpenShop(bool share, OpenShop& s) : MinimizeScript(share,s), spec(s.spec) { 00255 b.update(*this, share, s.b); 00256 makespan.update(*this, share, s.makespan); 00257 _start.update(*this, share, s._start); 00258 } 00259 00261 virtual Space* 00262 copy(bool share) { 00263 return new OpenShop(share,*this); 00264 } 00265 00267 virtual IntVar 00268 cost(void) const { 00269 return makespan; 00270 } 00271 00273 class PrintTask { 00274 public: 00275 int start; //< Start time 00276 int job; //< Job number 00277 int p; //< Processing time 00279 bool operator()(const PrintTask& t1, const PrintTask& t2) { 00280 return t1.start < t2.start; 00281 } 00282 }; 00283 00285 virtual void 00286 print(std::ostream& os) const { 00287 Region re(*this); 00288 PrintTask* m = re.alloc<PrintTask>(spec.n); 00289 for (int i=0; i<spec.m; i++) { 00290 int k=0; 00291 for (int j=0; j<spec.n; j++) { 00292 m[k].start = _start[i*spec.n+j].val(); 00293 m[k].job = j; 00294 m[k].p = spec.p[i*spec.n+j]; 00295 k++; 00296 } 00297 Support::quicksort(m, spec.n, m[0]); 00298 os << "Machine " << i << ": "; 00299 for (int j=0; j<spec.n; j++) 00300 os << "\t" << m[j].job << "("<<m[j].p<<")"; 00301 os << " = " << m[spec.n-1].start+m[spec.n-1].p << std::endl; 00302 } 00303 os << "Makespan: " << makespan << std::endl; 00304 } 00305 00306 }; 00307 00311 int 00312 main(int argc, char* argv[]) { 00313 SizeOptions opt("OpenShop"); 00314 opt.iterations(500); 00315 opt.size(0); 00316 opt.solutions(0); 00317 opt.search(OpenShop::SEARCH_BAB); 00318 opt.search(OpenShop::SEARCH_BAB, "bab"); 00319 opt.search(OpenShop::SEARCH_RESTART, "restart"); 00320 opt.parse(argc,argv); 00321 if (opt.size() >= n_examples) { 00322 std::cerr << "Error: size must be between 0 and " 00323 << n_examples-1 << std::endl; 00324 return 1; 00325 } 00326 switch (opt.search()) { 00327 case OpenShop::SEARCH_BAB: 00328 MinimizeScript::run<OpenShop,BAB,SizeOptions>(opt); break; 00329 case OpenShop::SEARCH_RESTART: 00330 MinimizeScript::run<OpenShop,Restart,SizeOptions>(opt); break; 00331 } 00332 return 0; 00333 } 00334 00335 namespace { 00336 00345 00346 const int ex0_p[] = { 00347 661,6,333, 00348 168,489,343, 00349 171,505,324 00350 }; 00351 OpenShopSpec ex0(3,3,ex0_p); 00352 00353 const int ex1_p[] = { 00354 54, 34, 61, 2, 00355 9, 15, 89, 70, 00356 38, 19, 28, 87, 00357 95, 34, 7, 29 00358 }; 00359 OpenShopSpec ex1(4,4,ex1_p); 00360 00361 const int ex2_p[] = { 00362 5, 70, 45, 83, 00363 24, 80, 58, 45, 00364 29, 56, 29, 61, 00365 43, 64, 45, 74 00366 }; 00367 OpenShopSpec ex2(4,4,ex2_p); 00368 00369 const int ex3_p[] = { 00370 89, 39, 54, 34, 71, 92, 56, 00371 19, 13, 81, 46, 91, 73, 27, 00372 66, 95, 48, 24, 96, 18, 14, 00373 48, 46, 78, 94, 19, 68, 63, 00374 60, 28, 91, 75, 52, 9, 7, 00375 33, 98, 37, 11, 2, 30, 38, 00376 83, 45, 37, 77, 52, 88, 52 00377 }; 00378 OpenShopSpec ex3(7,7,ex3_p); 00379 00380 const int ex4_p[] = { 00381 49, 58, 37, 79, 16, 64, 71, 65, 6, 44, 17, 85, 99, 57, 89, 4, 16, 8, 40, 66, 00382 43, 65, 42, 35, 57, 3, 8, 65, 79, 76, 82, 80, 96, 82, 98, 57, 73, 43, 6, 20, 00383 82, 49, 7, 18, 94, 76, 41, 17, 43, 15, 53, 10, 83, 24, 79, 62, 53, 77, 23, 70, 00384 18, 30, 80, 7, 97, 84, 10, 27, 7, 91, 14, 12, 7, 31, 24, 97, 16, 33, 99, 15, 00385 31, 65, 51, 95, 45, 70, 57, 10, 84, 52, 28, 43, 54, 40, 83, 9, 21, 57, 45, 67, 00386 70, 45, 48, 39, 10, 37, 22, 53, 48, 50, 76, 48, 57, 6, 43, 13, 45, 93, 42, 11, 00387 80, 5, 53, 97, 75, 22, 10, 70, 79, 92, 96, 18, 57, 3, 82, 52, 1, 21, 23, 38, 00388 43, 79, 67, 57, 33, 52, 1, 44, 82, 10, 27, 23, 89, 9, 62, 6, 38, 33, 37, 22, 00389 68, 20, 5, 25, 16, 80, 13, 73, 35, 36, 13, 53, 97, 50, 17, 54, 35, 86, 24, 56, 00390 60, 83, 8, 81, 3, 4, 48, 14, 77, 10, 71, 57, 86, 94, 49, 36, 62, 62, 41, 56, 00391 31, 77, 5, 97, 19, 19, 31, 19, 26, 41, 77, 64, 74, 11, 98, 30, 22, 22, 33, 61, 00392 7, 89, 46, 13, 33, 55, 84, 16, 21, 45, 15, 71, 57, 42, 82, 13, 62, 98, 36, 45, 00393 84, 90, 20, 61, 24, 59, 8, 49, 53, 53, 83, 76, 28, 62, 59, 11, 41, 2, 58, 46, 00394 32, 23, 53, 5, 8, 91, 97, 53, 90, 90, 28, 16, 61, 27, 32, 74, 23, 11, 57, 20, 00395 62, 85, 79, 96, 62, 85, 43, 53, 12, 36, 95, 37, 2, 48, 46, 81, 97, 54, 5, 77, 00396 57, 35, 41, 55, 72, 98, 22, 81, 6, 8, 70, 64, 55, 53, 7, 38, 58, 30, 83, 81, 00397 15, 11, 24, 63, 27, 90, 35, 22, 53, 22, 66, 75, 59, 80, 31, 91, 63, 82, 99, 62, 00398 4, 18, 99, 6, 65, 21, 28, 93, 16, 26, 1, 16, 46, 59, 45, 90, 69, 76, 25, 53, 00399 50, 24, 66, 2, 17, 85, 5, 86, 4, 88, 44, 5, 29, 19, 27, 14, 36, 57, 59, 15, 00400 71, 79, 7, 61, 45, 72, 61, 45, 61, 54, 90, 33, 81, 5, 45, 64, 87, 82, 61, 8 00401 }; 00402 OpenShopSpec ex4(20,20,ex4_p); 00403 00405 OpenShopSpec examples[] = { ex0, ex1, ex2, ex3, ex4 }; 00407 const unsigned int n_examples = sizeof(examples) / sizeof(OpenShopSpec); 00408 00410 } 00411 00412 // STATISTICS: example-any