Planning and Scheduling by Logic-Based Benders Decomposition

J. N. Hooker ()
Additional contact information
J. N. Hooker: Tepper School of Business, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213

Operations Research, 2007, vol. 55, issue 3, 588-602

Abstract: 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.

Keywords: integer programming; Benders decomposition; production/scheduling; planning (search for similar items in EconPapers)
Date: 2007
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (62)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1060.0371 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:55:y:2007:i:3:p:588-602

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().