| 52 | // Basic propagation (timetabling) |
| 53 | template<class Task, class Cap> |
| 54 | forceinline ExecStatus |
| 55 | timetabling(Space& home, Propagator& p, Cap c, TaskArray<Task>& t) { |
| 56 | int ccur = c.max(); |
| 57 | int cmax = ccur; |
| 58 | int cmin = ccur; |
| 59 | |
| 60 | // Sort tasks by decreasing capacity |
| 61 | TaskByDecCap<Task> tbdc; |
| 62 | Support::quicksort(&t[0], t.size(), tbdc); |
| 63 | |
| 64 | Region r; |
| 65 | |
| 66 | bool assigned; |
| 67 | if (Event* e = Event::events(r,t,assigned)) { |
| 68 | // Set of current but not required tasks |
| 69 | Support::BitSet<Region> tasks(r,static_cast<unsigned int>(t.size())); |
| 70 | |
| 71 | // Process events, use ccur as the capacity that is still free |
| 72 | do { |
| 73 | // Current time |
| 74 | int time = e->time(); |
| 75 | |
| 76 | // Process events for completion of required part |
| 77 | for ( ; (e->type() == Event::LRT) && (e->time() == time); e++) |
| 78 | if (t[e->idx()].mandatory()) { |
| 79 | tasks.set(static_cast<unsigned int>(e->idx())); |
| 80 | ccur += t[e->idx()].c(); |
| 81 | } |
| 82 | // Process events for completion of task |
| 83 | for ( ; (e->type() == Event::LCT) && (e->time() == time); e++) |
| 84 | tasks.clear(static_cast<unsigned int>(e->idx())); |
| 85 | // Process events for start of task |
| 86 | for ( ; (e->type() == Event::EST) && (e->time() == time); e++) |
| 87 | tasks.set(static_cast<unsigned int>(e->idx())); |
| 88 | // Process events for zero-length task |
| 89 | for ( ; (e->type() == Event::ZRO) && (e->time() == time); e++) { |
| 90 | ccur -= t[e->idx()].c(); |
| 91 | if (ccur < cmin) cmin=ccur; |
| 92 | if (ccur < 0) |
| 93 | return ES_FAILED; |
| 94 | ccur += t[e->idx()].c(); |
| 95 | } |
| 96 | |
| 97 | // norun start time |
| 98 | int nrstime = time; |
| 99 | // Process events for start of required part |
| 100 | for ( ; (e->type() == Event::ERT) && (e->time() == time); e++) |
| 101 | if (t[e->idx()].mandatory()) { |
| 102 | tasks.clear(static_cast<unsigned int>(e->idx())); |
| 103 | ccur -= t[e->idx()].c(); |
| 104 | if (ccur < cmin) cmin=ccur; |
| 105 | nrstime = time+1; |
| 106 | if (ccur < 0) |
| 107 | return ES_FAILED; |
| 108 | } else if (t[e->idx()].optional() && (t[e->idx()].c() > ccur)) { |
| 109 | GECODE_ME_CHECK(t[e->idx()].excluded(home)); |
| 110 | } |
| 111 | |