The actual problem
| 190 | public: |
| 191 | /// The actual problem |
| 192 | OpenShop(const SizeOptions& opt) |
| 193 | : IntMinimizeScript(opt), |
| 194 | spec(examples[opt.size()]), |
| 195 | b(*this, (spec.n+spec.m-2)*spec.n*spec.m/2, 0,1), |
| 196 | makespan(*this, 0, Int::Limits::max), |
| 197 | _start(*this, spec.m*spec.n, 0, Int::Limits::max) { |
| 198 | |
| 199 | Matrix<IntVarArray> start(_start, spec.m, spec.n); |
| 200 | IntArgs _dur(spec.m*spec.n, spec.p); |
| 201 | Matrix<IntArgs> dur(_dur, spec.m, spec.n); |
| 202 | |
| 203 | int minmakespan; |
| 204 | int maxmakespan; |
| 205 | crosh(dur, minmakespan, maxmakespan); |
| 206 | rel(*this, makespan <= maxmakespan); |
| 207 | rel(*this, makespan >= minmakespan); |
| 208 | |
| 209 | int k=0; |
| 210 | for (int m=0; m<spec.m; m++) |
| 211 | for (int j0=0; j0<spec.n-1; j0++) |
| 212 | for (int j1=j0+1; j1<spec.n; j1++) { |
| 213 | // The tasks on machine m of jobs j0 and j1 must be disjoint |
| 214 | rel(*this, |
| 215 | b[k] == (start(m,j0) + dur(m,j0) <= start(m,j1))); |
| 216 | rel(*this, |
| 217 | b[k++] == (start(m,j1) + dur(m,j1) > start(m,j0))); |
| 218 | } |
| 219 | |
| 220 | for (int j=0; j<spec.n; j++) |
| 221 | for (int m0=0; m0<spec.m-1; m0++) |
| 222 | for (int m1=m0+1; m1<spec.m; m1++) { |
| 223 | // The tasks in job j on machine m0 and m1 must be disjoint |
| 224 | rel(*this, |
| 225 | b[k] == (start(m0,j) + dur(m0,j) <= start(m1,j))); |
| 226 | rel(*this, |
| 227 | b[k++] == (start(m1,j) + dur(m1,j) > start(m0,j))); |
| 228 | } |
| 229 | |
| 230 | // The makespan is greater than the end time of the latest job |
| 231 | for (int m=0; m<spec.m; m++) { |
| 232 | for (int j=0; j<spec.n; j++) { |
| 233 | rel(*this, start(m,j) + dur(m,j) <= makespan); |
| 234 | } |
| 235 | } |
| 236 | |
| 237 | // First branch over the precedences |
| 238 | branch(*this, b, BOOL_VAR_AFC_MAX(opt.decay()), BOOL_VAL_MAX()); |
| 239 | // When the precedences are fixed, simply assign the start times |
| 240 | assign(*this, _start, INT_ASSIGN_MIN()); |
| 241 | // When the start times are fixed, use the tightest makespan |
| 242 | assign(*this, makespan, INT_ASSIGN_MIN()); |
| 243 | } |
| 244 | |
| 245 | /// Constructor for cloning \a s |
| 246 | OpenShop(OpenShop& s) : IntMinimizeScript(s), spec(s.spec) { |
nothing calls this directly
no test coverage detected