J. Christopher Beck, ILOG, S.A. and Mark S. Fox, University of Toronto
In realistic scheduling problems, there may be choices among resources or among process plans. We formulate a constraint-based representation of alternative activities to model problems containing such choices. We extend existing constraint-directed scheduling heuristic commitment techniques and propagators to reason directly about the fact that an activity does not necessarily have to exist in a final schedule. Experimental results show that an algorithm using a novel texture-based heuristic commitment technique together with extended edge-finding propagators achieves the best overall performance of the techniques tested.