basic.hpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Christian Schulte <schulte@gecode.org> 00005 * 00006 * Copyright: 00007 * Christian Schulte, 2010 00008 * 00009 * Last modified: 00010 * $Date: 2010-07-15 13:39:19 +0200 (Thu, 15 Jul 2010) $ by $Author: tack $ 00011 * $Revision: 11201 $ 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 namespace Gecode { namespace Scheduling { namespace Cumulative { 00039 00041 class Event { 00042 public: 00044 enum Type { 00045 LRT = 0, 00046 LCT = 1, 00047 EST = 2, 00048 ZRO = 3, 00049 ERT = 4, 00050 END = 5 00051 }; 00052 Type e; 00053 int t; 00054 int i; 00055 00056 void init(Type e, int t, int i); 00058 bool operator <(const Event& e) const; 00059 }; 00060 00062 template<class Task> 00063 class TaskByDecCap { 00064 public: 00066 bool operator ()(const Task& t1, const Task& t2) const; 00067 }; 00068 00069 forceinline void 00070 Event::init(Event::Type e0, int t0, int i0) { 00071 e=e0; t=t0; i=i0; 00072 } 00073 00074 forceinline bool 00075 Event::operator <(const Event& e) const { 00076 if (this->t == e.t) 00077 return this->e < e.e; 00078 return this->t < e.t; 00079 } 00080 00081 template<class Task> 00082 forceinline bool 00083 TaskByDecCap<Task>::operator ()(const Task& t1, const Task& t2) const { 00084 return t1.c() > t2.c(); 00085 } 00086 00087 00088 // Basic propagation 00089 template<class Task> 00090 ExecStatus 00091 basic(Space& home, Propagator& p, int c, TaskArray<Task>& t) { 00092 // Sort tasks by decreasing capacity 00093 TaskByDecCap<Task> tbdc; 00094 Support::quicksort(&t[0], t.size(), tbdc); 00095 00096 Region r(home); 00097 00098 Event* e = r.alloc<Event>(4*t.size()+1); 00099 00100 // Initialize events 00101 bool assigned=true; 00102 { 00103 bool required=false; 00104 int n=0; 00105 for (int i=t.size(); i--; ) 00106 if (t[i].assigned()) { 00107 // Only add required part 00108 if (t[i].pmin() > 0) { 00109 required = true; 00110 e[n++].init(Event::ERT,t[i].lst(),i); 00111 e[n++].init(Event::LRT,t[i].ect(),i); 00112 } else if (t[i].pmax() == 0) { 00113 required = true; 00114 e[n++].init(Event::ZRO,t[i].lst(),i); 00115 } 00116 } else { 00117 assigned = false; 00118 e[n++].init(Event::EST,t[i].est(),i); 00119 e[n++].init(Event::LCT,t[i].lct(),i); 00120 // Check whether task has required part 00121 if (t[i].lst() < t[i].ect()) { 00122 required = true; 00123 e[n++].init(Event::ERT,t[i].lst(),i); 00124 e[n++].init(Event::LRT,t[i].ect(),i); 00125 } 00126 } 00127 00128 // Check whether no task has a required part 00129 if (!required) 00130 return assigned ? home.ES_SUBSUMED(p) : ES_FIX; 00131 00132 // Write end marker 00133 e[n++].init(Event::END,Int::Limits::infinity,-1); 00134 00135 // Sort events 00136 Support::quicksort(e, n); 00137 } 00138 00139 // Set of current but not required tasks 00140 Support::BitSet<Region> tasks(r,static_cast<unsigned int>(t.size())); 00141 00142 // Process events, use c as the capacity that is still free 00143 while (e->e != Event::END) { 00144 // Current time 00145 int time = e->t; 00146 00147 // Process events for completion of required part 00148 for ( ; (e->t == time) && (e->e == Event::LRT); e++) 00149 if (t[e->i].mandatory()) { 00150 tasks.set(static_cast<unsigned int>(e->i)); c += t[e->i].c(); 00151 } 00152 // Process events for completion of task 00153 for ( ; (e->t == time) && (e->e == Event::LCT); e++) 00154 tasks.clear(static_cast<unsigned int>(e->i)); 00155 // Process events for start of task 00156 for ( ; (e->t == time) && (e->e == Event::EST); e++) 00157 tasks.set(static_cast<unsigned int>(e->i)); 00158 // Process events for zero-length task 00159 for ( ; (e->t == time) && (e->e == Event::ZRO); e++) 00160 if (c < t[e->i].c()) 00161 return ES_FAILED; 00162 00163 // norun start time for 0-length tasks 00164 int zltime = time; 00165 // Process events for start of required part 00166 for ( ; (e->t == time) && (e->e == Event::ERT); e++) 00167 if (t[e->i].mandatory()) { 00168 tasks.clear(static_cast<unsigned int>(e->i)); 00169 c -= t[e->i].c(); zltime = time+1; 00170 if (c < 0) 00171 return ES_FAILED; 00172 } else if (t[e->i].optional() && (t[e->i].c() > c)) { 00173 GECODE_ME_CHECK(t[e->i].excluded(home)); 00174 } 00175 00176 // Exploit that tasks are sorted according to capacity 00177 for (Iter::Values::BitSet<Support::BitSet<Region> > j(tasks); 00178 j() && (t[j.val()].c() > c); ++j) 00179 // Task j cannot run from time to next time - 1 00180 if (t[j.val()].mandatory()) 00181 if (t[j.val()].pmin() > 0) { 00182 GECODE_ME_CHECK(t[j.val()].norun(home, time, e->t - 1)); 00183 } else { 00184 GECODE_ME_CHECK(t[j.val()].norun(home, zltime, e->t - 1)); 00185 } 00186 } 00187 00188 return assigned ? home.ES_SUBSUMED(p) : ES_NOFIX; 00189 } 00190 00191 }}} 00192 00193 // STATISTICS: scheduling-prop