2006-12-01
Lower bounds for minimizing total completion time in a two-machine flow shop
Publication
Publication
Journal of Scheduling , Volume 9 - Issue 6 p. 559- 568
For the NP -hard problem of scheduling n jobs in a two-machine flow shop so as to minimize the total completion time, we present two equivalent lower bounds that are computable in polynomial time. We formulate the problem by the use of positional completion time variables, which results in two integer linear programming formulations with O(n 2) variables and O(n) constraints. Solving the linear programming relaxation renders a very strong lower bound with an average relative gap of only 0.8% for instances with more than 30 jobs. We further show that relaxing the formulation in terms of positional completion times by applying Lagrangean relaxation yields the same bound, no matter which set of constraints we relax.
Additional Metadata | |
---|---|
doi.org/10.1007/s10951-006-8789-x, hdl.handle.net/1765/76364 | |
Journal of Scheduling | |
Organisation | Erasmus Research Institute of Management |
Hoogeveen, H., van Norden, L., & van de Velde, S. (2006). Lower bounds for minimizing total completion time in a two-machine flow shop. Journal of Scheduling, 9(6), 559–568. doi:10.1007/s10951-006-8789-x |