The slack-based heuristics for constraint satisfaction scheduling paper visits a number of points that we have seen through the semester, although it doesn't call them what we know them as. Here are a couple of them:
1. In the introduction, 2 different methods of constraint-based scheduling are mentioned: that of posting start times, and the method which the authors use, of posting sufficient additional sequencing constraints between pairs of operations contending for the same resource. It should be really clear that (in planning lingo) this is in essence totally-ordered plans vs. partially-ordered plans: as the authors point out, the solutions generated by the latter method "... typically represent a *set* of feasible schedules" (emphasis added). These are but partially-ordered plans; any topological sort of them will yield a total-order that is executable.
2. This second point probably has a lot to do with the fact that the method proposed deals with constraints as a CSP would: the initial configuration of variable and value ordering heuristics as defined by the authors is something we have already seen in CSP.
Min-Slack: This is similar to the Most-Constrained Variable (MCV) selection in CSP.
Max-Slack: This is similar to the Least-Constraining Value selection in CSP.
kartik
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment