time-tabling.hpp
Go to the documentation of this file.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
00039
00040 namespace Gecode { namespace Int { namespace Cumulative {
00041
00043 template<class Task>
00044 class TaskByDecCap {
00045 public:
00047 bool operator ()(const Task& t1, const Task& t2) const;
00048 };
00049
00050 template<class Task>
00051 forceinline bool
00052 TaskByDecCap<Task>::operator ()(const Task& t1, const Task& t2) const {
00053 return t1.c() > t2.c();
00054 }
00055
00056
00057 template<class Task, class Cap>
00058 forceinline ExecStatus
00059 timetabling(Space& home, Propagator& p, Cap c, TaskArray<Task>& t) {
00060 int ccur = c.max();
00061 int cmax = ccur;
00062 int cmin = ccur;
00063
00064
00065 TaskByDecCap<Task> tbdc;
00066 Support::quicksort(&t[0], t.size(), tbdc);
00067
00068 Region r(home);
00069
00070 bool assigned;
00071 if (Event* e = Event::events(r,t,assigned)) {
00072
00073 Support::BitSet<Region> tasks(r,static_cast<unsigned int>(t.size()));
00074
00075
00076 do {
00077
00078 int time = e->time();
00079
00080
00081 for ( ; (e->type() == Event::LRT) && (e->time() == time); e++)
00082 if (t[e->idx()].mandatory()) {
00083 tasks.set(static_cast<unsigned int>(e->idx()));
00084 ccur += t[e->idx()].c();
00085 }
00086
00087 for ( ; (e->type() == Event::LCT) && (e->time() == time); e++)
00088 tasks.clear(static_cast<unsigned int>(e->idx()));
00089
00090 for ( ; (e->type() == Event::EST) && (e->time() == time); e++)
00091 tasks.set(static_cast<unsigned int>(e->idx()));
00092
00093 for ( ; (e->type() == Event::ZRO) && (e->time() == time); e++) {
00094 ccur -= t[e->idx()].c();
00095 if (ccur < cmin) cmin=ccur;
00096 if (ccur < 0)
00097 return ES_FAILED;
00098 ccur += t[e->idx()].c();
00099 }
00100
00101
00102 int nrstime = time;
00103
00104 for ( ; (e->type() == Event::ERT) && (e->time() == time); e++)
00105 if (t[e->idx()].mandatory()) {
00106 tasks.clear(static_cast<unsigned int>(e->idx()));
00107 ccur -= t[e->idx()].c();
00108 if (ccur < cmin) cmin=ccur;
00109 nrstime = time+1;
00110 if (ccur < 0)
00111 return ES_FAILED;
00112 } else if (t[e->idx()].optional() && (t[e->idx()].c() > ccur)) {
00113 GECODE_ME_CHECK(t[e->idx()].excluded(home));
00114 }
00115
00116
00117 for (Iter::Values::BitSet<Support::BitSet<Region> > j(tasks);
00118 j() && (t[j.val()].c() > ccur); ++j)
00119
00120 if (t[j.val()].mandatory())
00121 GECODE_ME_CHECK(t[j.val()].norun(home, nrstime, e->time() - 1));
00122 } while (e->type() != Event::END);
00123
00124 GECODE_ME_CHECK(c.gq(home,cmax-cmin));
00125 }
00126
00127 if (assigned)
00128 return home.ES_SUBSUMED(p);
00129 return ES_NOFIX;
00130 }
00131
00132 }}}
00133
00134