A hybrid method for planning and scheduling. (English) Zbl 1152.90445
Wallace, Mark (ed.), Principles and practice of constraint programming – CP 2004. 10th international conference, CP 2004, Toronto, Canada, September 27–October 1, 2004. Proceedings. Berlin: Springer (ISBN 978-3-540-23241-4/pbk). Lecture Notes in Computer Science 3258, 305-316 (2004).
Summary: We combine mixed integer linear programming (MILP) and constraint programming (CP) to solve planning and scheduling problems. Tasks are allocated to facilities using MILP and scheduled using CP, and the two are linked via logic-based Benders decomposition. Tasks assigned to a facility may run in parallel subject to resource constraints (cumulative scheduling). We solve minimum cost problems, as well as minimum makespan problems in which all tasks have the same release date and deadline. We obtain computational speedups of several orders of magnitude relative to the state of the art in both MILP and CP.
For the entire collection see [Zbl 1139.68008].
For the entire collection see [Zbl 1139.68008].
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
| 90C11 | Mixed integer programming |
