This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Kanet, J. J. Search for Related Content

New Precedence Theorems for One-Machine Weighted Tardiness

Department of Management Information Systems, Operations Management, and Decision Sciences, University of Dayton, 300 College Park, Dayton, Ohio 45469
kanet{at}udayton.edu

In an earlier paper by Emmons [Emmons, H. 1969. One-machine sequencing to minimize certain functions of job tardiness. Oper. Res. 17 701–715], the problem of sequencing jobs on a single machine in order to minimize total tardiness was analyzed. Emmons provided three theorems for specifying precedence relations for pairs of jobs. His theorems apply when the tardiness penalty for each job grows at the same rate. Rinnooy Kan et al. [Rinnooy Kan, A. H. G., B. J. Lageweg, J. K. Lenstra. 1975. Minimizing total costs in one-machine scheduling. Oper. Res. 23 908–927] later extended Emmons’s theorems to the case when job tardiness penalties can grow at different rates for different jobs. Provided here is a set of theorems, stronger than those of Rinnooy Kan et al., that more fully exploits the special properties of the weighted tardiness function, allowing for greater reduction of the solution space.

Key Words: single-machine scheduling; weighted tardiness; precedence
History: Received: December 6, 2003; revision received: March 7, 2006;