Planning and Scheduling to Minimize Tardiness.pdf.pdf' (306.2 kB)
Planning and Scheduling to Minimize Tardiness
journal contribution
posted on 2013-01-01, 00:00 authored by John N. HookerWe combine mixed integer linear programming (MILP) and
constraint programming (CP) to minimize tardiness in planning and
scheduling. Tasks are allocated to facilities using MILP and scheduled
using CP, and the two are linked via logic-based Benders decomposition.
We consider two objectives: minimizing the number of late tasks,
and minimizing total tardiness. Our main theoretical contribution is a
relaxation of the cumulative scheduling subproblem, which is critical to
performance. We obtain substantial computational speedups relative to
the state of the art in both MILP and CP. We also obtain much better
solutions for problems that cannot be solved to optimality.