Skip to main content
Article
A Hybrid Method for Planning and Scheduling
M. Wallace, ed., Principles and Practice of Constraint Programming
  • John N. Hooker, Carnegie Mellon University
Date of Original Version
4-1-2004
Type
Book Chapter
Abstract or Description

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.

DOI
10.1007/b100482
Citation Information
John N. Hooker. "A Hybrid Method for Planning and Scheduling" M. Wallace, ed., Principles and Practice of Constraint Programming Vol. LNCS 3528 (2004) p. 305 - 316
Available at: http://works.bepress.com/jnhooker/79/