Generated on Fri Oct 19 11:24:49 2018 for Gecode by doxygen 1.6.3

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  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
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;  //< number of machines
00048     const int n;  //< number of jobs
00049     const int* p; //< processing times of the tasks
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; //< Job
00079     int m; //< Machine
00080     int p; //< Processing time
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     // Compute maximum makespan as the sum of all production times.
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     // Compute minimum makespan as the maximum of individual jobs and machines
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); // Job completion time
00124     int* ct_m = re.alloc<int>(spec.m); // Machine completion time
00125     Task* tasks = re.alloc<Task>(spec.n*spec.m); // Tasks
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); // Earliest possible tasks
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; // Current makespan
00150       int u = spec.n*spec.m; // Consider all tasks
00151       while (u > 0) {
00152         int u_t0 = 0; // Set of selectable tasks
00153         int t0 = maxmakespan; // Minimal head of unscheduled tasks
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]); // Head of T_jm
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           // In the first iteration, select tasks with longest processing time
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); // Select random task
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]]); // Remove task from u
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; // Iterate a couple of times
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           // The tasks on machine m of jobs j0 and j1 must be disjoint
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           // The tasks in job j on machine m0 and m1 must be disjoint
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     // The makespan is greater than the end time of the latest job
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     // First branch over the precedences
00238     branch(*this, b, BOOL_VAR_AFC_MAX(opt.decay()), BOOL_VAL_MAX());
00239     // When the precedences are fixed, simply assign the start times
00240     assign(*this, _start, INT_ASSIGN_MIN());
00241     // When the start times are fixed, use the tightest makespan
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; //< Start time
00268     int job;   //< Job number
00269     int p;     //< Processing time
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 // STATISTICS: example-any