A note on a single machine scheduling problem with generalized total tardiness objective function

作者：Gafarov Evgeny R; Lazarev Alexander A; Werner Frank^*

来源：Information Processing Letters, 2012, 112(3): 72-76.

DOI：10.1016/j.ipl.2011.10.013

• Scheduling
• Single machine
• Total tardiness
• Number of tardy jobs
• Total late work
• Pseudo-polynomial algorithm
• Graphical algorithm

In this note, we consider a single machine scheduling problem with generalized total tardiness objective function. A pseudo-polynomial time solution algorithm is proposed for a special case of this problem. Moreover, we present a new graphical algorithm for another special case, which corresponds to the classical problem of minimizing the weighted number of tardy jobs on a single machine. The latter algorithm improves the complexity of an existing pseudo-polynomial algorithm by Lawler. Computational results are presented for both special cases considered.

• 出版日期2012-1-31