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