This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Hooker, J. N. Search for Related Content

Planning and Scheduling by Logic-Based Benders Decomposition

Tepper School of Business, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
john{at}hooker.tepper.cmu.edu

We combine mixed-integer linear programming (MILP) and constraint programming (CP) to solve an important class of 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 problems in which the objective is to minimize cost, makespan, or total tardiness. We obtain significant computational speedups, of several orders of magnitude for the first two objectives, relative to the state of the art in both MILP and CP. We also obtain better solutions and bounds for problems than cannot be solved to optimality.

Subject classifications: integer programming; Benders decomposition; production/scheduling; planning.
History: Received August 2004; revision received May 2006; accepted May 2006.