sheaf / unary-scheduling

Constraint propagation algorithms for unary resource scheduling
0 stars 0 forks source link

Shaving #9

Open sheaf opened 4 years ago

sheaf commented 4 years ago

Shaving is a useful propagator / search procedure, where we try to schedule a task at an extremity of one of its availability intervals. If that leads to a conclusion (either through constraint propagation or through a search procedure), we can eliminate that option, thus shaving that end off the interval.

If proper care is taken to keep track of the reason why a task scheduled at an interval extremity causes a problem (as in #10), one should be able to shave intervals over continuous domains, at least in the case where one only uses certain unary scheduling propagators and not a general search to arrive at a contradiction. In the discrete case we can at the very least eliminate that singular possibility (task scheduled at the extreme of an interval), although keeping track of the justification might have enabled a slightly stronger shaving.