00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 #include <algorithm>
00039
00040
00041
00042
00043
00044
00045
00046
00047 namespace Gecode { namespace Scheduling { namespace Cumulatives {
00048
00049 template<class ViewM, class ViewD, class ViewH, class View>
00050 forceinline
00051 Val<ViewM,ViewD,ViewH,View>::Val(Home home,
00052 const ViewArray<ViewM>& _machine,
00053 const ViewArray<View>& _start,
00054 const ViewArray<ViewD>& _duration,
00055 const ViewArray<View>& _end,
00056 const ViewArray<ViewH>& _height,
00057 const SharedArray<int>& _limit,
00058 bool _at_most) :
00059 Propagator(home),
00060 machine(_machine), start(_start), duration(_duration),
00061 end(_end), height(_height), limit(_limit), at_most(_at_most) {
00062 home.notice(*this,AP_DISPOSE);
00063
00064 machine.subscribe(home,*this,Int::PC_INT_DOM);
00065 start.subscribe(home,*this,Int::PC_INT_BND);
00066 duration.subscribe(home,*this,Int::PC_INT_BND);
00067 end.subscribe(home,*this,Int::PC_INT_BND);
00068 height.subscribe(home,*this,Int::PC_INT_BND);
00069 }
00070
00071 template<class ViewM, class ViewD, class ViewH, class View>
00072 ExecStatus
00073 Val<ViewM,ViewD,ViewH,View>
00074 ::post(Home home, const ViewArray<ViewM>& machine,
00075 const ViewArray<View>& start, const ViewArray<ViewD>& duration,
00076 const ViewArray<View>& end, const ViewArray<ViewH>& height,
00077 const SharedArray<int>& limit, bool at_most) {
00078 (void) new (home) Val(home, machine, start, duration,
00079 end, height, limit, at_most);
00080
00081 return ES_OK;
00082 }
00083
00084 template<class ViewM, class ViewD, class ViewH, class View>
00085 forceinline
00086 Val<ViewM,ViewD,ViewH,View>::Val(Space& home, bool share,
00087 Val<ViewM,ViewD,ViewH,View>& p)
00088 : Propagator(home,share,p), at_most(p.at_most) {
00089 machine.update(home,share,p.machine);
00090 start.update(home, share, p.start);
00091 duration.update(home, share, p.duration);
00092 end.update(home, share, p.end);
00093 height.update(home, share, p.height);
00094 limit.update(home, share, p.limit);
00095 }
00096
00097 template<class ViewM, class ViewD, class ViewH, class View>
00098 size_t
00099 Val<ViewM,ViewD,ViewH,View>::dispose(Space& home) {
00100 home.ignore(*this,AP_DISPOSE);
00101 if (!home.failed()) {
00102 machine.cancel(home,*this,Int::PC_INT_DOM);
00103 start.cancel(home,*this,Int::PC_INT_BND);
00104 duration.cancel(home,*this,Int::PC_INT_BND);
00105 end.cancel(home,*this,Int::PC_INT_BND);
00106 height.cancel(home,*this,Int::PC_INT_BND);
00107 }
00108 limit.~SharedArray();
00109 (void) Propagator::dispose(home);
00110 return sizeof(*this);
00111 }
00112
00113 template<class ViewM, class ViewD, class ViewH, class View>
00114 PropCost
00115 Val<ViewM,ViewD,ViewH,View>::cost(const Space&, const ModEventDelta&) const {
00116 return PropCost::quadratic(PropCost::LO, start.size());
00117 }
00118
00119 template<class ViewM, class ViewD, class ViewH, class View>
00120 Actor*
00121 Val<ViewM,ViewD,ViewH,View>::copy(Space& home, bool share) {
00122 return new (home) Val<ViewM,ViewD,ViewH,View>(home,share,*this);
00123 }
00124
00126 typedef enum {EVENT_CHCK, EVENT_PROF, EVENT_PRUN} ev_t;
00128 class Event
00129 {
00130 public:
00132 ev_t e;
00134 int task;
00136 int date;
00138 int inc;
00143 bool first_prof;
00144
00146 Event(ev_t _e, int _task, int _date, int _inc = 0, bool _first_prof = false)
00147 : e(_e), task(_task), date(_date), inc(_inc), first_prof(_first_prof)
00148 {}
00149
00150
00151 Event(void) {}
00152
00154 bool operator <(const Event& ev) const {
00155 if (date == ev.date) {
00156 if (e == EVENT_PROF && ev.e != EVENT_PROF) return true;
00157 if (e == EVENT_CHCK && ev.e == EVENT_PRUN) return true;
00158 return false;
00159 }
00160 return date < ev.date;
00161 }
00162 };
00163
00164 template<class ViewM, class ViewD, class ViewH, class View>
00165 ExecStatus
00166 Val<ViewM,ViewD,ViewH,View>::prune(Space& home, int low, int up, int r,
00167 int ntask, int sheight,
00168 int* contribution,
00169 int* prune_tasks, int& prune_tasks_size) {
00170
00171 if (ntask > 0 &&
00172 (at_most ? sheight > limit[r]
00173 : sheight < limit[r])) {
00174 return ES_FAILED;
00175 }
00176
00177 int pti = 0;
00178 while (pti != prune_tasks_size) {
00179 int t = prune_tasks[pti];
00180
00181
00182
00183
00184 if (ntask != 0 &&
00185 (at_most ? height[t].min() < 0
00186 : height[t].max() > 0) &&
00187 (at_most ? sheight-contribution[t] > limit[r]
00188 : sheight-contribution[t] < limit[r])) {
00189 if (me_failed(machine[t].eq(home, r))||
00190 me_failed(start[t].gq(home, up-duration[t].max()+1))||
00191 me_failed(start[t].lq(home, low))||
00192 me_failed(end[t].lq(home,low+duration[t].max()))||
00193 me_failed(end[t].gq(home, up+1))||
00194 me_failed(duration[t].gq(home,std::min(up-start[t].max()+1,
00195 end[t].min()-low)))
00196 ) {
00197 return ES_FAILED;
00198 }
00199 }
00200
00201
00202
00203 if (at_most ? height[t].min() > std::min(0, limit[r])
00204 : height[t].max() < std::max(0, limit[r])) {
00205 if (at_most ? sheight-contribution[t]+height[t].min() > limit[r]
00206 : sheight-contribution[t]+height[t].max() < limit[r]) {
00207 if (end[t].min() > low &&
00208 start[t].max() <= up &&
00209 duration[t].min() > 0) {
00210 if (me_failed(machine[t].nq(home, r))) {
00211 return ES_FAILED;
00212 }
00213 } else if (machine[t].assigned()) {
00214 int dtmin = duration[t].min();
00215 if (dtmin > 0) {
00216 Iter::Ranges::Singleton
00217 a(low-dtmin+1, up), b(low+1, up+dtmin);
00218 if (me_failed(start[t].minus_r(home,a,false)) ||
00219 me_failed(end[t].minus_r(home, b,false)))
00220 return ES_FAILED;
00221 }
00222 if (me_failed(duration[t].lq(home,
00223 std::max(std::max(low-start[t].min(),
00224 end[t].max()-up-1),
00225 0)))) {
00226 return ES_FAILED;
00227 }
00228 }
00229 }
00230 }
00231
00232
00233
00234
00235
00236
00237
00238 if (machine[t].assigned() &&
00239 machine[t].val() == r &&
00240 end[t].min() > low &&
00241 start[t].max() <= up &&
00242 duration[t].min() > 0 ) {
00243 if (me_failed(at_most
00244 ? height[t].lq(home, limit[r]-sheight+contribution[t])
00245 : height[t].gq(home, limit[r]-sheight+contribution[t]))) {
00246 return ES_FAILED;
00247 }
00248 }
00249
00250
00251 if (!machine[t].in(r) || (end[t].max() <= up+1)) {
00252 prune_tasks[pti] = prune_tasks[--prune_tasks_size];
00253 } else {
00254 ++pti;
00255 }
00256 }
00257
00258 return ES_OK;
00259 }
00260
00261 namespace {
00262 template<class C>
00263 class Less {
00264 public:
00265 bool operator ()(const C& lhs, const C& rhs) {
00266 return lhs < rhs;
00267 }
00268 };
00269 }
00270
00271 template<class ViewM, class ViewD, class ViewH, class View>
00272 ExecStatus
00273 Val<ViewM,ViewD,ViewH,View>::propagate(Space& home, const ModEventDelta&) {
00274
00275 bool subsumed = true;
00276 for (int t = start.size(); t--; )
00277 if (!(duration[t].assigned() && end[t].assigned() &&
00278 machine[t].assigned() && start[t].assigned() &&
00279 height[t].assigned())) {
00280 subsumed = false;
00281 break;
00282 }
00283
00284 Region region(home);
00285 Event *events = region.alloc<Event>(start.size()*8);
00286 int events_size;
00287 int *prune_tasks = region.alloc<int>(start.size());
00288 int prune_tasks_size;
00289 int *contribution = region.alloc<int>(start.size());
00290 for (int r = limit.size(); r--; ) {
00291 events_size = 0;
00292 #define GECODE_PUSH_EVENTS(E) assert(events_size < start.size()*8); \
00293 events[events_size++] = E
00294
00295
00296 for (int t = start.size(); t--; ) {
00297 if (machine[t].assigned() &&
00298 machine[t].val() == r &&
00299 start[t].max() < end[t].min()) {
00300 if (at_most
00301 ? height[t].min() > std::min(0, limit[r])
00302 : height[t].max() < std::max(0, limit[r])) {
00303 GECODE_PUSH_EVENTS(Event(EVENT_CHCK, t, start[t].max(), 1));
00304 GECODE_PUSH_EVENTS(Event(EVENT_CHCK, t, end[t].min(), -1));
00305 }
00306 if (at_most
00307 ? height[t].min() > 0
00308 : height[t].max() < 0) {
00309 GECODE_PUSH_EVENTS(Event(EVENT_PROF, t, start[t].max(),
00310 at_most ? height[t].min()
00311 : height[t].max(), true));
00312 GECODE_PUSH_EVENTS(Event(EVENT_PROF, t, end[t].min(),
00313 at_most ? -height[t].min()
00314 : -height[t].max()));
00315 }
00316 }
00317
00318 if (machine[t].in(r)) {
00319 if (at_most
00320 ? height[t].min() < 0
00321 : height[t].max() > 0) {
00322 GECODE_PUSH_EVENTS(Event(EVENT_PROF, t, start[t].min(),
00323 at_most ? height[t].min()
00324 : height[t].max(), true));
00325 GECODE_PUSH_EVENTS(Event(EVENT_PROF, t, end[t].max(),
00326 at_most ? -height[t].min()
00327 : -height[t].max()));
00328 }
00329 if (!(machine[t].assigned() &&
00330 height[t].assigned() &&
00331 start[t].assigned() &&
00332 end[t].assigned())) {
00333 GECODE_PUSH_EVENTS(Event(EVENT_PRUN, t, start[t].min()));
00334 }
00335 }
00336 }
00337 #undef GECODE_PUSH_EVENTS
00338
00339
00340 if (events_size == 0) {
00341 continue;
00342 }
00343
00344
00345 Less<Event> less;
00346 Support::insertion(&events[0], events_size, less);
00347
00348
00349 int d = 0;
00350 int ntask = 0;
00351 int sheight = 0;
00352 int ei = 0;
00353
00354 prune_tasks_size = 0;
00355 for (int i = start.size(); i--; ) contribution[i] = 0;
00356
00357 d = events[ei].date;
00358 while (ei < events_size) {
00359 if (events[ei].e != EVENT_PRUN) {
00360 if (d != events[ei].date) {
00361 GECODE_ES_CHECK(prune(home, d, events[ei].date-1, r,
00362 ntask, sheight,
00363 contribution, prune_tasks, prune_tasks_size));
00364 d = events[ei].date;
00365 }
00366 if (events[ei].e == EVENT_CHCK) {
00367 ntask += events[ei].inc;
00368 } else {
00369 sheight += events[ei].inc;
00370 if(events[ei].first_prof)
00371 contribution[events[ei].task] = at_most
00372 ? std::max(contribution[events[ei].task], events[ei].inc)
00373 : std::min(contribution[events[ei].task], events[ei].inc);
00374 }
00375 } else {
00376 assert(prune_tasks_size<start.size());
00377 prune_tasks[prune_tasks_size++] = events[ei].task;
00378 }
00379 ei++;
00380 }
00381
00382 GECODE_ES_CHECK(prune(home, d, d, r,
00383 ntask, sheight,
00384 contribution, prune_tasks, prune_tasks_size));
00385 }
00386 return subsumed ? ES_SUBSUMED(*this,home): ES_NOFIX;
00387 }
00388
00389 }}}
00390
00391
00392