Planning and scheduling by logic-based Benders decomposition

Planning and scheduling by logic-based Benders decomposition

0.00 Avg rating0 Votes
Article ID: iaor20082442
Country: United States
Volume: 55
Issue: 3
Start Page Number: 588
End Page Number: 602
Publication Date: May 2007
Journal: Operations Research
Authors:
Keywords: programming: integer
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.

Reviews

Required fields are marked *. Your email address will not be published.