Minsum scheduling with acceptable lead-times and optional job rejection

被引:0
作者
Baruch Mor
Dana Shapira
机构
[1] Ariel University,Department of Economics and Business Administration
[2] Ariel University,Department of Computer Science
来源
Optimization Letters | 2022年 / 16卷
关键词
Single-machine scheduling; Due-date assignment; Minsum; Job-rejection; Dynamic programming;
D O I
暂无
中图分类号
学科分类号
摘要
In our current fast-paced era, customers are often willing to pay extra premium for shorter lead times, which motivates further research on the scheduling problem with due-date assignment and customer-specified lead times. As part of this effort, we extend the classic minsum ‘DIF’ scheduling model to allow optional job-rejection, thus adding an important component of real-life applications, namely, the possibility that the scheduler decides to process only a subset of the jobs and outsource the disjoint set. The scheduler is penalised for rejecting certain jobs by setting job-dependent rejection costs, and he is limited by a given upper bound on the total rejection cost. The most general version of the minsum DIF problem includes job-dependent cost parameters and lead-times, and it is strongly NP-hard. Therefore, we study six variants of the problem, where either only the cost parameters or the lead-times are job dependent. All alternatives are extended by optional job-rejection that possibly bounds the constraints or the underlying cost functions. We establish that all studied problems are NP-hard in the ordinary sense and present pseudo-polynomial dynamic programming algorithms and extensive numerical studies for most solutions.
引用
收藏
页码:1073 / 1091
页数:18
相关论文
共 54 条
[1]  
Cao ZG(2006)On several scheduling problems with rejection or discretely compressible processing times Lect. Notes Comput. Sci. 3959 90-98
[2]  
Wang Z(1990)Minimizing total tardiness on one machine is NP-hard Math. Oper. Res. 15 483-495
[3]  
Zhang YZ(2017)Minmax scheduling with acceptable lead-times: extensions to position-dependent processing times, due-window and job rejection Comput. Oper. Res. 83 150-156
[4]  
Liu SP(2017)Single machine scheduling problems with generalised due-dates and job-rejection Int. J. Prod. Res. 55 3164-3172
[5]  
Du J(2013)Minmax due-date assignment with a time window for acceptable lead-times Ann. Oper. Res. 211 167-177
[6]  
Leung JYT(2015)Scheduling with a due-window for acceptable lead-times J. Oper. Res. Soc. 66 1578-1588
[7]  
Gerstl E(2010)Fully polynomial time approximation scheme for the total weighted tardiness minimization with a common due date Discret. Appl. Math. 158 1035-1040
[8]  
Mor B(2006)A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date Theoret. Comput. Sci. 369 230-238
[9]  
Mosheiov G(2013)A note on “Fully polynomial time approximation scheme for the total weighted tardiness minimization with a common due date” Discrete Appl. Math. 161 2205-2206
[10]  
Gerstl E(1977)A 'pseudopolynomial' algorithm for sequencing jobs to minimize total tardiness Ann. Discrete Math. 1 331-342