A faster algorithm for a due date assignment problem with tardy jobs

作者：Koulamas Christos^*

来源：Operations Research Letters, 2010, 38(2): 127-128.

DOI：10.1016/j.orl.2009.10.013

• Single-machine sequencing
• Weighted number of tardy jobs
• Due date assignment

The single-machine due date assignment problem with the weighted number of tardy jobs objective, (the TWNTD problem), and its generalization with resource allocation decisions and controllable job processing times have been solved in O(n(4)) time by formulating and solving a series of assignment problems. In this note, a faster O(n(2)) dynamic programming algorithm is proposed for the TWNTD problem and for its controllable processing times generalization in the case of a convex resource consumption function.

• 出版日期2010-3