Planning and scheduling by logic-based benders decomposition
成果类型：
Article
署名作者：
Hooker, J. N.
署名单位：
Carnegie Mellon University
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.1060.0371
发表日期：
2007
页码：
588-602
关键词：
摘要：
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 CR We also obtain better solutions and bounds for problems than cannot be solved to optimality.