Article ID: | iaor20133930 |
Volume: | 207 |
Issue: | 1 |
Start Page Number: | 121 |
End Page Number: | 136 |
Publication Date: | Aug 2013 |
Journal: | Annals of Operations Research |
Authors: | Werner Frank, Gafarov Evgeny, Lazarev Alexander |
Keywords: | job shop, order review and release, tardiness |
In this paper, we consider some scheduling problems on a single machine, where weighted or unweighted total tardiness has to be maximized in contrast to usual minimization problems. These problems are theoretically important and have also practical interpretations. For the total weighted tardiness maximization problem, we present an NP‐hardness proof and a pseudo‐polynomial solution algorithm. For the unweighted total tardiness maximization problem with release dates, NP‐hardness is proven. Complexity results for some other classical objective functions (e.g., the number of tardy jobs, total completion time) and various additional constraints (e.g., deadlines, weights and/or release dates of jobs may be given) are presented as well.