Generated on Wed Nov 5 2014 05:18:15 for Gecode by doxygen 1.7.6.1
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: 2013-07-08 14:22:40 +0200 (Mon, 08 Jul 2013) $ by $Author: schulte $
00011  *     $Revision: 13820 $
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 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; //< 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   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           // The tasks on machine m of jobs j0 and j1 must be disjoint
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           // The tasks in job j on machine m0 and m1 must be disjoint
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     // The makespan is greater than the end time of the latest job
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     // First branch over the precedences
00241     branch(*this, b, INT_VAR_AFC_MAX(opt.decay()), INT_VAL_MAX());
00242     // When the precedences are fixed, simply assign the start times
00243     assign(*this, _start, INT_ASSIGN_MIN());
00244     // When the start times are fixed, use the tightest makespan
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; //< Start time
00271     int job;   //< Job number
00272     int p;     //< Processing time
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 // STATISTICS: example-any