An Exact Method to Minimize the Number of Tardy Jobs in Single Machine Scheduling |
| |
Authors: | Stéphane Dauzère-Pérès Marc Sevaux |
| |
Affiliation: | (1) Ecole des Mines de Saint-Etienne, CMP Georges Charpak, Avenue des Anémones, Quartier Saint-Pierre, F-13541, Gardanne, France;(2) University of Valenciennes, Dept. Production Systems, UMR CNRS 8530, LAMIH-SP, cMont-Houy, F-59313, Valenciennes Cedex, France |
| |
Abstract: | This paper considers the problem of scheduling n jobs on a single machine to minimize the number of tardy (or late) jobs. Each job has a release date, a processing time and a due date. The general case with non-equal release dates and different due dates is considered. Using new and efficient lower bounds and several dominance rules, a branch and bound scheme is proposed based on the definition of a master sequence, i.e. a sequence containing at least one optimal sequence. With this procedure, 95% of 140-job instances are optimally solved in a maximum of one-hour CPU time. |
| |
Keywords: | one-machine scheduling late jobs branch and bound |
本文献已被 SpringerLink 等数据库收录! |
|