00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #include "minimodel.hh"
00023
00024 #include <algorithm>
00025
00026 namespace Gecode {
00027
00028 using namespace Int;
00029
00030 void
00031 producer_consumer(Space *home,
00032 const IntVarArgs& produce_date, const IntArgs& produce_amount,
00033 const IntVarArgs& consume_date, const IntArgs& consume_amount,
00034 int initial, IntConLevel cl)
00035 {
00036 if(produce_date.size() != produce_amount.size() ||
00037 consume_date.size() != consume_amount.size())
00038 throw new ArgumentSizeMismatch("Minimodel::producer_consumer");
00039
00040 int ntasks = produce_date.size() + consume_date.size();
00041
00042 IntArgs machine(ntasks), height(ntasks), limit(1);
00043 IntVarArgs start(ntasks), duration(ntasks), end(ntasks);
00044
00045 int i = 0;
00046 int sum_height = initial;
00047 if(initial < Limits::Int::int_min ||
00048 initial > Limits::Int::int_max)
00049 throw new NumericalOverflow("MiniModel::producer_consumer");
00050
00051 int maxval = 0;
00052 for (int j = produce_date.size(); j--; )
00053 maxval = std::max(produce_date[i].max(), maxval);
00054 for (int j = consume_date.size(); j--; )
00055 maxval = std::max(consume_date[j].max(), maxval);
00056 ++maxval;
00057
00058 IntVar minvar = IntVar(home, 0, 0);
00059 IntVar maxvar = IntVar(home, maxval, maxval);
00060
00061
00062
00063 for (int k = produce_date.size(); k--; ++i) {
00064 sum_height += produce_amount[k];
00065 machine[i] = 0;
00066
00067 start[i] = minvar;
00068 end[i] = produce_date[k];
00069 duration[i] = IntVar(home, end[i].min(), end[i].max());
00070 height[i] = produce_amount[k];
00071 if(height[i] < Limits::Int::int_min ||
00072 height[i] > Limits::Int::int_max)
00073 throw new NumericalOverflow("MiniModel::producer_consumer");
00074 }
00075
00076
00077 for (int k = consume_date.size(); k--; ++i) {
00078 machine[i] = 0;
00079
00080 start[i] = consume_date[k];
00081 end[i] = maxvar;
00082 duration[i] = IntVar(home, maxval - start[i].max(),
00083 maxval - start[i].min());
00084 height[i] = consume_amount[k];
00085 if(height[i] < Limits::Int::int_min ||
00086 height[i] > Limits::Int::int_max)
00087 throw new NumericalOverflow("MiniModel::producer_consumer");
00088 }
00089
00090 limit[0] = sum_height;
00091
00092 cumulatives(home, machine, start, duration, end, height, limit, true, cl);
00093 }
00094
00095
00096
00097
00098
00099
00100
00101
00102
00103
00104
00105
00106
00107
00108
00109
00110 namespace {
00111 class ConstVar {
00112 Space *home_;
00113 int val_;
00114 public:
00115 ConstVar(Space *home, int val) : home_(home), val_(val) {}
00116
00117 operator int() { return val_; }
00118 operator IntVar() { return IntVar(home_, val_, val_); }
00119 };
00120
00121 IntVar make_intvar(Space *home, int val)
00122 {
00123 return IntVar(home, val, val);
00124 }
00125
00126 IntVar make_intvar(Space *home, IntVar iv)
00127 {
00128 return iv;
00129 }
00130
00131 template<class Duration, class Height>
00132 void
00133 post_cumulative(Space *home, const IntVarArgs& start, const Duration& duration,
00134 const Height& height, int limit, bool at_most, IntConLevel cl)
00135 {
00136 if(start.size() != duration.size() ||
00137 duration.size() != height.size())
00138 throw new ArgumentSizeMismatch("MiniModel::cumulative");
00139
00140 if(limit < Limits::Int::int_min ||
00141 limit > Limits::Int::int_max)
00142 throw new NumericalOverflow("MiniModel::cumulative");
00143
00144 int n = start.size() + !at_most;
00145 IntArgs m(n), l(1, limit);
00146 IntVarArgs s(n), d(n), e(n);
00147 Height h(n);
00148
00149 if(!at_most) {
00150 int smin, smax, emin, emax;
00151 IntVarArgs end(n-1);
00152 for (int i = start.size(); i--; ) {
00153 m[i] = 0;
00154 s[i] = start[i];
00155 smin = std::min(s[i].min(), smin);
00156 smax = std::max(s[i].max(), smax);
00157 d[i] = make_intvar(home, duration[i]);
00158 e[i] = IntVar(home, Limits::Int::int_min, Limits::Int::int_max);
00159
00160 end[i] = e[i];
00161 emin = std::min(e[i].min(), emin);
00162 emax = std::max(e[i].max(), emax);
00163 h[i] = height[i];
00164 }
00165 m[n-1] = 0;
00166 s[n-1] = IntVar(home, smin, smax);
00167 d[n-1] = IntVar(home, 0, emax - smin);
00168 e[n-1] = IntVar(home, emin, emax);
00169 h[n-1] = ConstVar(home, 0);
00170
00171 min(home, start, s[n-1]);
00172 max(home, end, e[n-1]);
00173 } else {
00174 for (int i = start.size(); i--; ) {
00175 m[i] = 0;
00176 s[i] = start[i];
00177 d[i] = make_intvar(home, duration[i]);
00178 e[i] = IntVar(home, s[i].min()+d[i].min(), s[i].max()+d[i].max());
00179 h[i] = height[i];
00180 }
00181 }
00182
00183 cumulatives(home, m, s, d, e, h, l, at_most, cl);
00184 }
00185
00186 }
00187
00188 void
00189 cumulative(Space *home, const IntVarArgs& start, const IntVarArgs& duration,
00190 const IntVarArgs& height, int limit, bool at_most, IntConLevel cl)
00191 {
00192 post_cumulative(home, start, duration, height, limit, at_most, cl);
00193 }
00194
00195 void
00196 cumulative(Space *home, const IntVarArgs& start, const IntArgs& duration,
00197 const IntVarArgs& height, int limit, bool at_most, IntConLevel cl)
00198 {
00199 post_cumulative(home, start, duration, height, limit, at_most, cl);
00200 }
00201
00202 void
00203 cumulative(Space *home, const IntVarArgs& start, const IntVarArgs& duration,
00204 const IntArgs& height, int limit, bool at_most, IntConLevel cl)
00205 {
00206 post_cumulative(home, start, duration, height, limit, at_most, cl);
00207 }
00208
00209 void
00210 cumulative(Space *home, const IntVarArgs& start, const IntArgs& duration,
00211 const IntArgs& height, int limit, bool at_most, IntConLevel cl)
00212 {
00213 post_cumulative(home, start, duration, height, limit, at_most, cl);
00214 }
00215
00216
00217 namespace {
00218 template <class Duration>
00219 void
00220 post_serialized(Space *home, const IntVarArgs& start, const Duration& duration,
00221 IntConLevel cl)
00222 {
00223 if(start.size() != duration.size())
00224 throw new ArgumentSizeMismatch("MiniModel::serialized");
00225
00226 IntArgs height(start.size());
00227 for (int i = start.size(); i--; ) height[i] = 1;
00228
00229 post_cumulative(home, start, duration, height, 1, true, cl);
00230 }
00231 }
00232
00233 void
00234 serialized(Space *home, const IntVarArgs& start, const IntVarArgs& duration,
00235 IntConLevel cl)
00236 {
00237 post_serialized(home, start, duration, cl);
00238 }
00239
00240
00241 void
00242 serialized(Space *home, const IntVarArgs& start, const IntArgs& duration,
00243 IntConLevel cl)
00244 {
00245 post_serialized(home, start, duration, cl);
00246 }
00247
00248 }
00249
00250