/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ /* * Main authors: * Guido Tack <tack@gecode.org> * * Copyright: * Guido Tack, 2009 * * Last modified: * $Date: 2010-10-07 20:52:01 +1100 (Thu, 07 Oct 2010) $ by $Author: schulte $ * $Revision: 11473 $ * * This file is part of Gecode, the generic constraint * development environment: * http://www.gecode.org * * Permission is hereby granted, free of charge, to any person obtaining * a copy of this software and associated documentation files (the * "Software"), to deal in the Software without restriction, including * without limitation the rights to use, copy, modify, merge, publish, * distribute, sublicense, and/or sell copies of the Software, and to * permit persons to whom the Software is furnished to do so, subject to * the following conditions: * * The above copyright notice and this permission notice shall be * included in all copies or substantial portions of the Software. * * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. * */ #include <gecode/driver.hh> #include <gecode/int.hh> #include <gecode/minimodel.hh> using namespace Gecode; namespace { /** * \brief Specification of an open shop instance * */ class OpenShopSpec { public: const int m; //< number of machines const int n; //< number of jobs const int* p; //< processing times of the tasks /// Constructor OpenShopSpec(int m0, int n0, const int* p0) : m(m0), n(n0), p(p0) {} }; extern OpenShopSpec examples[]; extern const unsigned int n_examples; } /** * \brief %Example: open-shop scheduling * * \ingroup Example * */ class OpenShop : public MinimizeScript { protected: /// The instance specification const OpenShopSpec& spec; /// Precedences BoolVarArray b; /// Makespan IntVar makespan; /// Start times IntVarArray _start; /// %Task representation for CROSH heuristic class Task { public: int j; //< Job int m; //< Machine int p; //< Processing time /// Default constructor Task(void) {} /// Constructor Task(int j0, int m0, int p0) : j(j0), m(m0), p(p0) {} }; /** \brief Use Constructive Randomized Open-Shop Heuristics * to compute lower and upper bounds * * This heuristic is taken from the paper * A. Malapert, H. Cambazard, C. Gueret, N. Jussien, A. Langevin, * L.-M. Rousseau: An Optimal Constraint Programming Approach to the * Open-Shop Problem. Technical report, CIRRELT-2009-25. * */ void crosh(Matrix<IntArgs>& dur, int& minmakespan, int& maxmakespan) { Support::RandomGenerator rnd; // Compute maximum makespan as the sum of all production times. maxmakespan = 0; for (int i=0; i<spec.m; i++) for (int j=0; j<spec.n; j++) maxmakespan += dur(i,j); // Compute minimum makespan as the maximum of individual jobs and machines minmakespan = 0; for (int i=0; i<spec.m; i++) { int ms = 0; for (int j=0; j<spec.n; j++) { ms += dur(i,j); } minmakespan = std::max(minmakespan, ms); } for (int j=0; j<spec.n; j++) { int ms = 0; for (int i=0; i<spec.m; i++) { ms += dur(i,j); } minmakespan = std::max(minmakespan, ms); } Region re(*this); int* ct_j = re.alloc<int>(spec.n); // Job completion time int* ct_m = re.alloc<int>(spec.m); // Machine completion time Task* tasks = re.alloc<Task>(spec.n*spec.m); // Tasks int k=0; for (int i=spec.m; i--;) for (int j=spec.n; j--;) new (&tasks[k++]) Task(j,i,dur(i,j)); int* t0_tasks = re.alloc<int>(spec.n*spec.m); // Earliest possible tasks bool stopCROSH = false; int maxIterations; switch (spec.n) { case 3: maxIterations = 5; break; case 4: maxIterations = 25; break; case 5: maxIterations = 50; break; case 6: maxIterations = 1000; break; case 7: maxIterations = 10000; break; case 8: maxIterations = 10000; break; case 9: maxIterations = 10000; break; default: maxIterations = 25000; break; } int iteration = 0; while (!stopCROSH && maxmakespan > minmakespan) { for (int i=spec.n; i--;) ct_j[i] = 0; for (int i=spec.m; i--;) ct_m[i] = 0; int cmax = 0; // Current makespan int u = spec.n*spec.m; // Consider all tasks while (u > 0) { int u_t0 = 0; // Set of selectable tasks int t0 = maxmakespan; // Minimal head of unscheduled tasks for (int i=0; i<u; i++) { const Task& t = tasks[i]; int est = std::max(ct_j[t.j], ct_m[t.m]); // Head of T_jm if (est < t0) { t0 = est; t0_tasks[0] = i; u_t0 = 1; } else if (est == t0) { t0_tasks[u_t0++] = i; } } int t_j0m0; if (iteration == 0) { // In the first iteration, select tasks with longest processing time t_j0m0 = 0; for (int i=1; i<u_t0; i++) if (tasks[t0_tasks[i]].p > tasks[t0_tasks[t_j0m0]].p) t_j0m0 = i; } else { t_j0m0 = rnd(u_t0); // Select random task } const Task& t = tasks[t0_tasks[t_j0m0]]; int ect = t0 + t.p; ct_j[t.j] = ect; ct_m[t.m] = ect; std::swap(tasks[--u],tasks[t0_tasks[t_j0m0]]); // Remove task from u cmax = std::max(cmax, ect); if (cmax > maxmakespan) break; } maxmakespan = std::min(maxmakespan,cmax); if (iteration++ > maxIterations) stopCROSH = true; // Iterate a couple of times } } public: /// Search variants enum { SEARCH_BAB, ///< Use branch and bound to optimize SEARCH_RESTART ///< Use restart to optimize }; /// The actual problem OpenShop(const SizeOptions& opt) : spec(examples[opt.size()]), b(*this, (spec.n+spec.m-2)*spec.n*spec.m/2, 0,1), makespan(*this, 0, Int::Limits::max), _start(*this, spec.m*spec.n, 0, Int::Limits::max) { Matrix<IntVarArray> start(_start, spec.m, spec.n); IntArgs _dur(spec.m*spec.n, spec.p); Matrix<IntArgs> dur(_dur, spec.m, spec.n); int minmakespan; int maxmakespan; crosh(dur, minmakespan, maxmakespan); rel(*this, makespan <= maxmakespan); rel(*this, makespan >= minmakespan); int k=0; for (int m=0; m<spec.m; m++) for (int j0=0; j0<spec.n-1; j0++) for (int j1=j0+1; j1<spec.n; j1++) { // The tasks on machine m of jobs j0 and j1 must be disjoint rel(*this, b[k] == (start(m,j0) + dur(m,j0) <= start(m,j1))); rel(*this, b[k++] == (start(m,j1) + dur(m,j1) > start(m,j0))); } for (int j=0; j<spec.n; j++) for (int m0=0; m0<spec.m-1; m0++) for (int m1=m0+1; m1<spec.m; m1++) { // The tasks in job j on machine m0 and m1 must be disjoint rel(*this, b[k] == (start(m0,j) + dur(m0,j) <= start(m1,j))); rel(*this, b[k++] == (start(m1,j) + dur(m1,j) > start(m0,j))); } // The makespan is greater than the end time of the latest job for (int m=0; m<spec.m; m++) { for (int j=0; j<spec.n; j++) { rel(*this, start(m,j) + dur(m,j) <= makespan); } } // First branch over the precedences branch(*this, b, INT_VAR_AFC_MAX, INT_VAL_MAX); // When the precedences are fixed, simply assign the start times assign(*this, _start, INT_ASSIGN_MIN); // When the start times are fixed, use the tightest makespan assign(*this, makespan, INT_ASSIGN_MIN); } /// Constructor for cloning \a s OpenShop(bool share, OpenShop& s) : MinimizeScript(share,s), spec(s.spec) { b.update(*this, share, s.b); makespan.update(*this, share, s.makespan); _start.update(*this, share, s._start); } /// Perform copying during cloning virtual Space* copy(bool share) { return new OpenShop(share,*this); } /// Minimize the makespan virtual IntVar cost(void) const { return makespan; } /// Helper class for representing tasks when printing a solution class PrintTask { public: int start; //< Start time int job; //< Job number int p; //< Processing time /// Comparison of tasks based on start time, used for sorting bool operator()(const PrintTask& t1, const PrintTask& t2) { return t1.start < t2.start; } }; /// Print solution virtual void print(std::ostream& os) const { Region re(*this); PrintTask* m = re.alloc<PrintTask>(spec.n); for (int i=0; i<spec.m; i++) { int k=0; for (int j=0; j<spec.n; j++) { m[k].start = _start[i*spec.n+j].val(); m[k].job = j; m[k].p = spec.p[i*spec.n+j]; k++; } Support::quicksort(m, spec.n, m[0]); os << "Machine " << i << ": "; for (int j=0; j<spec.n; j++) os << "\t" << m[j].job << "("<<m[j].p<<")"; os << " = " << m[spec.n-1].start+m[spec.n-1].p << std::endl; } os << "Makespan: " << makespan << std::endl; } }; /** \brief Main-function * \relates OpenShop */ int main(int argc, char* argv[]) { SizeOptions opt("OpenShop"); opt.iterations(500); opt.size(0); opt.solutions(0); opt.search(OpenShop::SEARCH_BAB); opt.search(OpenShop::SEARCH_BAB, "bab"); opt.search(OpenShop::SEARCH_RESTART, "restart"); opt.parse(argc,argv); if (opt.size() >= n_examples) { std::cerr << "Error: size must be between 0 and " << n_examples-1 << std::endl; return 1; } switch (opt.search()) { case OpenShop::SEARCH_BAB: MinimizeScript::run<OpenShop,BAB,SizeOptions>(opt); break; case OpenShop::SEARCH_RESTART: MinimizeScript::run<OpenShop,Restart,SizeOptions>(opt); break; } return 0; } namespace { /** \name Open shop specifications * * Each specification gives the processing times of the tasks for each * job, as well as the number of jobs and machines. * * \relates OpenShop */ //@{ const int ex0_p[] = { 661,6,333, 168,489,343, 171,505,324 }; OpenShopSpec ex0(3,3,ex0_p); const int ex1_p[] = { 54, 34, 61, 2, 9, 15, 89, 70, 38, 19, 28, 87, 95, 34, 7, 29 }; OpenShopSpec ex1(4,4,ex1_p); const int ex2_p[] = { 5, 70, 45, 83, 24, 80, 58, 45, 29, 56, 29, 61, 43, 64, 45, 74 }; OpenShopSpec ex2(4,4,ex2_p); const int ex3_p[] = { 89, 39, 54, 34, 71, 92, 56, 19, 13, 81, 46, 91, 73, 27, 66, 95, 48, 24, 96, 18, 14, 48, 46, 78, 94, 19, 68, 63, 60, 28, 91, 75, 52, 9, 7, 33, 98, 37, 11, 2, 30, 38, 83, 45, 37, 77, 52, 88, 52 }; OpenShopSpec ex3(7,7,ex3_p); const int ex4_p[] = { 49, 58, 37, 79, 16, 64, 71, 65, 6, 44, 17, 85, 99, 57, 89, 4, 16, 8, 40, 66, 43, 65, 42, 35, 57, 3, 8, 65, 79, 76, 82, 80, 96, 82, 98, 57, 73, 43, 6, 20, 82, 49, 7, 18, 94, 76, 41, 17, 43, 15, 53, 10, 83, 24, 79, 62, 53, 77, 23, 70, 18, 30, 80, 7, 97, 84, 10, 27, 7, 91, 14, 12, 7, 31, 24, 97, 16, 33, 99, 15, 31, 65, 51, 95, 45, 70, 57, 10, 84, 52, 28, 43, 54, 40, 83, 9, 21, 57, 45, 67, 70, 45, 48, 39, 10, 37, 22, 53, 48, 50, 76, 48, 57, 6, 43, 13, 45, 93, 42, 11, 80, 5, 53, 97, 75, 22, 10, 70, 79, 92, 96, 18, 57, 3, 82, 52, 1, 21, 23, 38, 43, 79, 67, 57, 33, 52, 1, 44, 82, 10, 27, 23, 89, 9, 62, 6, 38, 33, 37, 22, 68, 20, 5, 25, 16, 80, 13, 73, 35, 36, 13, 53, 97, 50, 17, 54, 35, 86, 24, 56, 60, 83, 8, 81, 3, 4, 48, 14, 77, 10, 71, 57, 86, 94, 49, 36, 62, 62, 41, 56, 31, 77, 5, 97, 19, 19, 31, 19, 26, 41, 77, 64, 74, 11, 98, 30, 22, 22, 33, 61, 7, 89, 46, 13, 33, 55, 84, 16, 21, 45, 15, 71, 57, 42, 82, 13, 62, 98, 36, 45, 84, 90, 20, 61, 24, 59, 8, 49, 53, 53, 83, 76, 28, 62, 59, 11, 41, 2, 58, 46, 32, 23, 53, 5, 8, 91, 97, 53, 90, 90, 28, 16, 61, 27, 32, 74, 23, 11, 57, 20, 62, 85, 79, 96, 62, 85, 43, 53, 12, 36, 95, 37, 2, 48, 46, 81, 97, 54, 5, 77, 57, 35, 41, 55, 72, 98, 22, 81, 6, 8, 70, 64, 55, 53, 7, 38, 58, 30, 83, 81, 15, 11, 24, 63, 27, 90, 35, 22, 53, 22, 66, 75, 59, 80, 31, 91, 63, 82, 99, 62, 4, 18, 99, 6, 65, 21, 28, 93, 16, 26, 1, 16, 46, 59, 45, 90, 69, 76, 25, 53, 50, 24, 66, 2, 17, 85, 5, 86, 4, 88, 44, 5, 29, 19, 27, 14, 36, 57, 59, 15, 71, 79, 7, 61, 45, 72, 61, 45, 61, 54, 90, 33, 81, 5, 45, 64, 87, 82, 61, 8 }; OpenShopSpec ex4(20,20,ex4_p); /// The instances OpenShopSpec examples[] = { ex0, ex1, ex2, ex3, ex4 }; /// The number of instances const unsigned int n_examples = sizeof(examples) / sizeof(OpenShopSpec); //@} } // STATISTICS: example-any