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 Scheduling { namespace Cumulative {
00041
00043 class Event {
00044 public:
00046 enum Type {
00047 LRT = 0,
00048 LCT = 1,
00049 EST = 2,
00050 ZRO = 3,
00051 ERT = 4,
00052 END = 5
00053 };
00054 Type e;
00055 int t;
00056 int i;
00057
00058 void init(Type e, int t, int i);
00060 bool operator <(const Event& e) const;
00061 };
00062
00064 template<class Task>
00065 class TaskByDecCap {
00066 public:
00068 bool operator ()(const Task& t1, const Task& t2) const;
00069 };
00070
00071 forceinline void
00072 Event::init(Event::Type e0, int t0, int i0) {
00073 e=e0; t=t0; i=i0;
00074 }
00075
00076 forceinline bool
00077 Event::operator <(const Event& e) const {
00078 if (this->t == e.t)
00079 return this->e < e.e;
00080 return this->t < e.t;
00081 }
00082
00083 template<class Task>
00084 forceinline bool
00085 TaskByDecCap<Task>::operator ()(const Task& t1, const Task& t2) const {
00086 return t1.c() > t2.c();
00087 }
00088
00089
00090
00091 template<class Task>
00092 ExecStatus
00093 basic(Space& home, Propagator& p, int c, TaskArray<Task>& t) {
00094
00095 TaskByDecCap<Task> tbdc;
00096 Support::quicksort(&t[0], t.size(), tbdc);
00097
00098 Region r(home);
00099
00100 Event* e = r.alloc<Event>(4*t.size()+1);
00101
00102
00103 bool assigned=true;
00104 {
00105 bool required=false;
00106 int n=0;
00107 for (int i=t.size(); i--; )
00108 if (t[i].assigned()) {
00109
00110 if (t[i].pmin() > 0) {
00111 required = true;
00112 e[n++].init(Event::ERT,t[i].lst(),i);
00113 e[n++].init(Event::LRT,t[i].ect(),i);
00114 } else if (t[i].pmax() == 0) {
00115 required = true;
00116 e[n++].init(Event::ZRO,t[i].lst(),i);
00117 }
00118 } else {
00119 assigned = false;
00120 e[n++].init(Event::EST,t[i].est(),i);
00121 e[n++].init(Event::LCT,t[i].lct(),i);
00122
00123 if (t[i].lst() < t[i].ect()) {
00124 required = true;
00125 e[n++].init(Event::ERT,t[i].lst(),i);
00126 e[n++].init(Event::LRT,t[i].ect(),i);
00127 }
00128 }
00129
00130
00131 if (!required)
00132 return assigned ? home.ES_SUBSUMED(p) : ES_FIX;
00133
00134
00135 e[n++].init(Event::END,Int::Limits::infinity,-1);
00136
00137
00138 Support::quicksort(e, n);
00139 }
00140
00141
00142 Support::BitSet<Region> tasks(r,static_cast<unsigned int>(t.size()));
00143
00144
00145 while (e->e != Event::END) {
00146
00147 int time = e->t;
00148
00149
00150 for ( ; (e->t == time) && (e->e == Event::LRT); e++)
00151 if (t[e->i].mandatory()) {
00152 tasks.set(static_cast<unsigned int>(e->i)); c += t[e->i].c();
00153 }
00154
00155 for ( ; (e->t == time) && (e->e == Event::LCT); e++)
00156 tasks.clear(static_cast<unsigned int>(e->i));
00157
00158 for ( ; (e->t == time) && (e->e == Event::EST); e++)
00159 tasks.set(static_cast<unsigned int>(e->i));
00160
00161 for ( ; (e->t == time) && (e->e == Event::ZRO); e++)
00162 if (c < t[e->i].c())
00163 return ES_FAILED;
00164
00165
00166 int zltime = time;
00167
00168 for ( ; (e->t == time) && (e->e == Event::ERT); e++)
00169 if (t[e->i].mandatory()) {
00170 tasks.clear(static_cast<unsigned int>(e->i));
00171 c -= t[e->i].c(); zltime = time+1;
00172 if (c < 0)
00173 return ES_FAILED;
00174 } else if (t[e->i].optional() && (t[e->i].c() > c)) {
00175 GECODE_ME_CHECK(t[e->i].excluded(home));
00176 }
00177
00178
00179 for (Iter::Values::BitSet<Support::BitSet<Region> > j(tasks);
00180 j() && (t[j.val()].c() > c); ++j)
00181
00182 if (t[j.val()].mandatory()) {
00183 if (t[j.val()].pmin() > 0) {
00184 GECODE_ME_CHECK(t[j.val()].norun(home, time, e->t - 1));
00185 } else {
00186 GECODE_ME_CHECK(t[j.val()].norun(home, zltime, e->t - 1));
00187 }
00188 }
00189 }
00190
00191 return assigned ? home.ES_SUBSUMED(p) : ES_NOFIX;
00192 }
00193
00194 }}}
00195
00196