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 条
[21]   Two-agent scheduling with agent specific batches on an unbounded serial batching machine [J].
Mikhail Y. Kovalyov ;
Ammar Oulamara ;
Ameur Soukhal .
Journal of Scheduling, 2015, 18 :423-434
[22]   Two-agent scheduling with agent specific batches on an unbounded serial batching machine [J].
Kovalyov, Mikhail Y. ;
Oulamara, Ammar ;
Soukhal, Ameur .
JOURNAL OF SCHEDULING, 2015, 18 (04) :423-434
[23]   Two-agent scheduling with position-based deteriorating jobs and learning effects [J].
Cheng, T. C. E. ;
Wu, Wen-Hsiang ;
Cheng, Shuenn-Ren ;
Wu, Chin-Chia .
APPLIED MATHEMATICS AND COMPUTATION, 2011, 217 (21) :8804-8824
[24]   Bounded parallel-batching scheduling with two competing agents [J].
B. Q. Fan ;
T. C. E. Cheng ;
S. S. Li ;
Q. Feng .
Journal of Scheduling, 2013, 16 :261-271
[25]   Unbounded parallel-batching scheduling with two competitive agents [J].
Li, Shisheng ;
Yuan, Jinjiang .
JOURNAL OF SCHEDULING, 2012, 15 (05) :629-640
[26]   Bounded parallel-batching scheduling with two competing agents [J].
Fan, B. Q. ;
Cheng, T. C. E. ;
Li, S. S. ;
Feng, Q. .
JOURNAL OF SCHEDULING, 2013, 16 (03) :261-271
[27]   A further study on two-agent parallel-batch scheduling with release dates and deteriorating jobs to minimize the makespan [J].
Gao, Yuan ;
Yuan, Jinjiang ;
Ng, C. T. ;
Cheng, T. C. E. .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2019, 273 (01) :74-81
[28]   Single machine parallel-batch scheduling with deteriorating jobs [J].
Qi, Xianglai ;
Zhou, Shiguo ;
Yuan, Jinjiang .
THEORETICAL COMPUTER SCIENCE, 2009, 410 (8-10) :830-836
[29]   Two-agent scheduling with rejection on a single machine [J].
Feng, Qi ;
Fan, Baoqiang ;
Li, Shisheng ;
Shang, Weiping .
APPLIED MATHEMATICAL MODELLING, 2015, 39 (3-4) :1183-1193
[30]   Two-agent single-machine scheduling problem with just-in-time jobs [J].
Choi, Byung-Cheon ;
Chung, Jibok .
THEORETICAL COMPUTER SCIENCE, 2014, 543 :37-45
12345