|
|||||
|
|
A faster branch-and-bound algorithm for the earliness-tardiness scheduling problem |
|
| Authors: | Francis Sourd Safia Kedad-Sidhoum |
| Affiliation: | (1) LIP6, CNRS, 4 place Jussieu, 75252 Paris, Cedex 05, France;(2) LIP6, Université Pierre et Marie Curie, 4 place Jussieu, 75252 Paris, Cedex 05, France |
| Abstract: | This paper addresses the one-machine scheduling problem with earliness-tardiness penalties. We propose a new branch-and-bound algorithm that can solve instances with up to 50 jobs and that can solve problems with even more general non-convex cost functions. The algorithm is based on the combination of a Lagrangean relaxation of resource constraints and new dominance rules. |
| Keywords: | One-machine scheduling Earliness-tardiness Lagrangean relaxation Branch-and-bound |
| 本文献已被 SpringerLink 等数据库收录！ | |