| Article ID: | iaor2009268 |
| Country: | United Kingdom |
| Volume: | 11 |
| Issue: | 1 |
| Start Page Number: | 49 |
| End Page Number: | 58 |
| Publication Date: | Feb 2008 |
| Journal: | Journal of Scheduling |
| Authors: | Sourd Francis, Kedad-Sidhoum Safia |
| Keywords: | lagrange multipliers, programming: multiple criteria |
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.