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 #include <algorithm>
00041
00042 namespace Gecode { namespace Scheduling { namespace Cumulative {
00043
00045 template<class TaskView, bool inc>
00046 class StoCap {
00047 public:
00049 bool operator ()(const TaskView& t1, const TaskView& t2) const {
00050 return inc ? (t1.c() < t2.c()) : (t2.c() < t1.c());
00051 }
00052 };
00053
00055 class PrecOrder {
00056 public:
00057 int* prec;
00059 PrecOrder(int* prec0) : prec(prec0) {}
00061 bool operator ()(int i, int j) const {
00062 return prec[i] > prec[j];
00063 }
00064 };
00065
00066 template<class TaskView>
00067 forceinline ExecStatus
00068 edgefinding(Space& home, int c, TaskViewArray<TaskView>& t) {
00069 sort<TaskView,STO_LCT,false>(t);
00070
00071 Region r(home);
00072
00074
00075
00076 int* prec = r.alloc<int>(t.size());
00077 for (int i=t.size(); i--; )
00078 prec[i] = t[i].ect();
00079
00080 OmegaLambdaTree<TaskView> ol(r,c,t);
00081
00082 for (int j=0; j<t.size(); j++) {
00083 while (!ol.lempty() &&
00084 (ol.lenv() > static_cast<double>(c)*t[j].lct())) {
00085 int i = ol.responsible();
00086 prec[i] = std::max(prec[i], t[j].lct());
00087 ol.lremove(i);
00088 }
00089 ol.shift(j);
00090 }
00091
00093
00094
00095
00096
00097
00098
00099 int* cap = r.alloc<int>(t.size());
00100 for (int i=t.size(); i--;)
00101 cap[i] = i;
00102 SortMap<TaskView,StoCap,true> o(t);
00103 Support::quicksort(cap, t.size(), o);
00104
00105 int* capacities = r.alloc<int>(t.size());
00106 int* capInv = r.alloc<int>(t.size());
00107 for (int i=t.size(); i--;) {
00108 capacities[cap[i]] = t[i].c();
00109 capInv[cap[i]] = i;
00110 }
00111
00112 int n_c = 0;
00113 for (int i=0, cur_c=INT_MIN; i<t.size(); i++) {
00114 if (capacities[i] != cur_c)
00115 capacities[n_c++] = cur_c = capacities[i];
00116 cap[capInv[i]] = n_c-1;
00117 }
00118 r.free<int>(capInv, t.size());
00119
00120
00121
00122 int* update = r.alloc<int>(t.size()*n_c);
00123 for (int i=t.size()*n_c; i--;)
00124 update[i] = -Int::Limits::infinity;
00125
00126 ExtOmegaTree<TaskView> eo(r,c,ol);
00127 for (int i=0; i<n_c; i++) {
00128 eo.init(capacities[i]);
00129 int u = -Int::Limits::infinity;
00130 for (int j=t.size(); j--;) {
00131 double lctj = static_cast<double>(c-capacities[i])*t[j].lct();
00132 double diff_d = ceil(div(plus(eo.env(j), -lctj),capacities[i]));
00133 int diff = (diff_d == -Int::Limits::double_infinity) ?
00134 -Int::Limits::infinity : static_cast<int>(diff_d);
00135 u = std::max(u,diff);
00136 update[i*t.size()+j] = u;
00137 }
00138 }
00139
00140
00141
00142
00143 int* precMap = r.alloc<int>(t.size());
00144 for (int i=t.size(); i--;)
00145 precMap[i] = i;
00146 PrecOrder po(prec);
00147 Support::quicksort(precMap, t.size(), po);
00148
00149 int curJ = 0;
00150 for (int i=0; i<t.size(); i++) {
00151 while (curJ < t.size() && t[curJ].lct() > prec[precMap[i]])
00152 curJ++;
00153 while (curJ < t.size() && t[curJ].lct() == prec[precMap[i]]) {
00154 if (t[curJ].lct() != t[precMap[i]].lct()) {
00155 GECODE_ME_CHECK(
00156 t[precMap[i]].est(home,update[cap[precMap[i]]*t.size()+curJ]));
00157 }
00158 curJ++;
00159 }
00160 }
00161
00162 return ES_OK;
00163 }
00164
00165 template<class Task>
00166 ExecStatus
00167 edgefinding(Space& home, int c, TaskArray<Task>& t) {
00168 TaskViewArray<typename TaskTraits<Task>::TaskViewFwd> f(t);
00169 GECODE_ES_CHECK(edgefinding(home,c,f));
00170 TaskViewArray<typename TaskTraits<Task>::TaskViewBwd> b(t);
00171 GECODE_ES_CHECK(edgefinding(home,c,b));
00172 return ES_OK;
00173 }
00174
00175 }}}
00176
00177