Two-agent scheduling with deteriorating jobs on a single parallel-batching machine: refining computational complexity

被引：0
作者：
Mikhail Y. Kovalyov
Dmitrij Šešok
机构：
[1] National Academy of Sciences of Belarus,United Institute of Informatics Problems
[2] Vilnius Gediminas Technical University,undefined
来源：
Journal of Scheduling | 2019年 / 22卷
关键词：
Scheduling; Batching; Agent scheduling; Computational complexity; Deterioration;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
Tang et al. (Eur J Oper Res 263:401–411, 2017) have recently introduced a parallel-batching machine scheduling problem with linearly deteriorating jobs of two agents and presented a computational complexity classification of various special cases of this problem, including a number of NP-hardness proofs. We refine these results by demonstrating strong NP-hardness of several special cases, which are proved NP-hard in the ordinary sense in Tang et al. (Eur J Oper Res 263:401–411, 2017). Our reduction employs the problem studied in the first issue of Journal of Scheduling.
引用
收藏
页码：603 / 606
页数：3
相关论文
共 50 条
[41]   Parallel-machine scheduling with deteriorating jobs and rejection [J].
Li, Shisheng ;
Yuan, Jinjiang .
THEORETICAL COMPUTER SCIENCE, 2010, 411 (40-42) :3642-3650
[42]   Parallel machine scheduling problems with proportionally deteriorating jobs [J].
Cheng, Mingbao ;
Wang, Guoqing ;
He, Longmin .
INTERNATIONAL JOURNAL OF SYSTEMS SCIENCE, 2009, 40 (01) :53-57
[43]   Single-machine scheduling of proportionally deteriorating jobs by two agents [J].
Gawiejnowicz, S. ;
Lee, W-C ;
Lin, C-L ;
Wu, C-C .
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2011, 62 (11) :1983-1991
[44]   Two-agent single-machine scheduling with cumulative deterioration [J].
Ren-Xia Chen ;
Shi-Sheng Li .
4OR, 2019, 17 :201-219
[45]   Two-agent single-machine scheduling with cumulative deterioration [J].
Chen, Ren-Xia ;
Li, Shi-Sheng .
4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2019, 17 (02) :201-219
[46]   Two-agent scheduling of time-dependent jobs [J].
He, Cheng ;
Leung, Joseph Y-T .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2017, 34 (02) :362-377
[47]   Two-agent scheduling of time-dependent jobs [J].
Cheng He ;
Joseph Y.-T. Leung .
Journal of Combinatorial Optimization, 2017, 34 :362-377
[48]   Scheduling a single parallel-batching machine with non-identical job sizes and incompatible job families [J].
Yang, Fan ;
Davari, Morteza ;
Wei, Wenchao ;
Hermans, Ben ;
Leus, Roel .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2022, 303 (02) :602-615
[49]   Scheduling a variable maintenance and linear deteriorating jobs on a single machine [J].
Luo, Wenchang ;
Ji, Min .
INFORMATION PROCESSING LETTERS, 2015, 115 (01) :33-39
[50]   Scheduling linear deteriorating jobs with an availability constraint on a single machine [J].
Ji, Min ;
He, Yong ;
Cheng, T. C. E. .
THEORETICAL COMPUTER SCIENCE, 2006, 362 (1-3) :115-126
12345