New Precedence Theorems for One-Machine Weighted Tardiness
Document Type
Article
Publication Date
8-2007
Publication Source
Mathematics of Operations Research
Abstract
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.
Inclusive pages
579-588
ISBN/ISSN
0364-765X
Copyright
Copyright © 2007, INFORMS
Publisher
INFORMS
Volume
32
Issue
3
Peer Reviewed
yes
eCommons Citation
Kanet, John J., "New Precedence Theorems for One-Machine Weighted Tardiness" (2007). MIS/OM/DS Faculty Publications. 18.
https://ecommons.udayton.edu/mis_fac_pub/18
COinS
Comments
Permission documentation is on file.\
INFORMS is the Institute for Operations Research and the Management Sciences.