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 条
  • [1] Two-agent scheduling with deteriorating jobs on a single parallel-batching machine: refining computational complexity
    Kovalyov, Mikhail Y.
    Sesok, Dmitrij
    JOURNAL OF SCHEDULING, 2019, 22 (05) : 603 - 606
  • [2] Competitive two-agent scheduling with deteriorating jobs on a single parallel-batching machine
    Tang, Lixin
    Zhao, Xiaoli
    Liu, Jiyin
    Leung, Joseph Y. -T.
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2017, 263 (02) : 401 - 411
  • [3] Single Machine Two-Agent Scheduling with Deteriorating Jobs
    Wang, Zhenyou
    Wei, Cai-Min
    Wu, Yu-Bin
    ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH, 2016, 33 (05)
  • [4] Two-agent group scheduling with deteriorating jobs on a single machine
    Peng Liu
    Lixin Tang
    Xiaoye Zhou
    The International Journal of Advanced Manufacturing Technology, 2010, 47 : 657 - 664
  • [5] Two-agent single-machine scheduling with deteriorating jobs
    Yin, Yunqiang
    Cheng, T. C. E.
    Wan, Long
    Wu, Chin-Chia
    Liu, Jun
    COMPUTERS & INDUSTRIAL ENGINEERING, 2015, 81 : 177 - 185
  • [6] Two-agent group scheduling with deteriorating jobs on a single machine
    Liu, Peng
    Tang, Lixin
    Zhou, Xiaoye
    INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2010, 47 (5-8): : 657 - 664
  • [7] A single-machine scheduling problem with two-agent and deteriorating jobs
    Lee, Wen-Chiung
    Wang, Wei-Jhe
    Shiau, Yau-Ren
    Wu, Chin-Chia
    APPLIED MATHEMATICAL MODELLING, 2010, 34 (10) : 3098 - 3107
  • [8] A Note on Two-agent Single-machine Scheduling Problem with Deteriorating Jobs
    Liu, Peng
    Feng, Daguang
    Zhou, Xiaoye
    Tang, Qi
    2010 CHINESE CONTROL AND DECISION CONFERENCE, VOLS 1-5, 2010, : 3832 - +
  • [9] Two-agent scheduling on a single parallel-batching machine with equal processing time and non-identical job sizes
    Wang, Jun-Qiang
    Fan, Guo-Qiang
    Zhang, Yingqian
    Zhang, Cheng-Wu
    Leung, Joseph Y. T.
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2017, 258 (02) : 478 - 490
  • [10] Single-Machine and Parallel-Machine Parallel-Batching Scheduling Considering Deteriorating Jobs, Various Group, and Time-Dependent Setup Time
    Liao, Baoyu
    Pei, Jun
    Yang, Shanlin
    Pardalos, Panos M.
    Lu, Shaojun
    INFORMATICA, 2018, 29 (02) : 281 - 301
12345