Unary NP-hardness of minimizing total weighted tardiness with generalized due dates

作者：Gao, Yuan; Yuan, Jinjiang^*

来源：Operations Research Letters, 2016, 44(1): 92-95.

DOI：10.1016/j.orl.2015.12.006

• Single machine scheduling
• Total weighted tardiness
• Generalized due dates
• Unary NP-hard

In the scheduling with generalized due dates, the due dates are sequenced in the EDD order and assigned to the jobs by the increasing order of their completion times such that the ith completed job receives the ith due date. The exact complexity of the. single machine scheduling of minimizing total weighted tardiness with generalized due dates is a long standing open problem. We show in this paper that this problem is unary NP-hard.

• 出版日期2016-1
• 单位郑州大学