A faster branch-and-bound algorithm for the earliness-tardiness scheduling problem

Francis Sourd (1) , Safia Kedad-Sidhoum (1)

1 RO - Recherche Opérationnelle

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.

Domaines: Informatique [cs]

Francis Sourd, Safia Kedad-Sidhoum. A faster branch-and-bound algorithm for the earliness-tardiness scheduling problem. Journal of Scheduling, 2008, 11 (1), pp.49-58. ⟨10.1007/s10951-007-0048-2⟩. ⟨hal-01185214⟩