Common due date assignment and single-machine scheduling with release times to minimize the weighted number of tardy jobs

被引：0
作者：
Chuanli Zhao
机构：
[1] Shenyang Normal University Shenyang,School of Mathematics and Systems Science
来源：
Japan Journal of Industrial and Applied Mathematics | 2016年 / 33卷
关键词：
Scheduling; Single-machine; Release time; Due date; 90B35;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
In just-in-time production, meeting due dates is one of the most important goals. Motivated by a scenario of just-in-time production, this paper considers the single-machine scheduling problem with release times and common due date assignment. The objective is to determine the optimal due date and schedule simultaneously to minimize a cost function that includes the weighted number of tardy jobs and the due date assignment cost. We show that the problem is NP-hard in the ordinary sense, and propose a dynamic programming algorithm and a fully polynomial-time approximation scheme.
引用
收藏
页码：239 / 249
页数：10
相关论文
共 54 条
[1]  
Chen ZL(1996)Scheduling and common due date assignment with earliness-tardiness penalties and batch delivery costs Eur. J. Oper. Res. 93 49-60
[2]  
Cheng TCE(1990)Common due date assignment and scheduling for a single processor to minimize the number of tardy jobs Eng. Optim. 16 129-136
[3]  
Gordon V(2002)A survey of the state-of-the-art of common due date assignment and scheduling research Eur. J. Oper. Res. 139 1-25
[4]  
Proth JM(2010)A note on the single machine scheduling to minimize the number of tardy jobs with deadlines Eur. J. Oper. Res. 201 966-970
[5]  
Chu CB(2013)A note on fully polynomial time approximation scheme for the total weighted tardiness minimization with a common due date Discret. Appl. Math. 161 2205-2206
[6]  
He C(2009)Algorithms for common due-date assignment and sequencing on a single machine with sequence-dependent setup times J. Oper. Res. Soc. 60 1264-1272
[7]  
Lin YX(1998)A fully polynomial approximation scheme for minimizing makespan of deteriorating jobs J. Heuristics 3 287-297
[8]  
Yuan JJ(1999)A fully polynomial approximation scheme for the weighted earliness-tardiness problem Oper. Res. 47 757-761
[9]  
Kianfar K(1993)Parallel machine scheduling to minimize costs for earliness and number of tardy jobs Discret. Appl. Math. 47 139-164
[10]  
Moslehi G(1982)Common due-date assignment to minimize total penalty for the one machine scheduling problem Oper. Res. 30 391-399
123456