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 条
[31]   Two-agent parallel-machine scheduling with rejection [J].
Li, Dawei ;
Lu, Xiwen .
THEORETICAL COMPUTER SCIENCE, 2017, 703 :66-75
[32]   Improved algorithms for two-agent scheduling on an unbounded serial-batching machine [J].
He, Cheng ;
Lin, Hao .
DISCRETE OPTIMIZATION, 2021, 41
[33]   Parallel-batching scheduling with nonlinear processing times on a single and unrelated parallel machines [J].
Min Kong ;
Xinbao Liu ;
Jun Pei ;
Panos M. Pardalos ;
Nenad Mladenovic .
Journal of Global Optimization, 2020, 78 :693-715
[34]   Parallel-batching scheduling with nonlinear processing times on a single and unrelated parallel machines [J].
Kong, Min ;
Liu, Xinbao ;
Pei, Jun ;
Pardalos, Panos M. ;
Mladenovic, Nenad .
JOURNAL OF GLOBAL OPTIMIZATION, 2020, 78 (04) :693-715
[35]   Two-Agent Slack Due-Date Assignment Scheduling with Resource Allocations and Deteriorating Jobs [J].
Zhang, Li-Han ;
Lv, Dan-Yang ;
Wang, Ji-Bo .
MATHEMATICS, 2023, 11 (12)
[36]   Novel mathematical formulations for parallel-batching processing machine scheduling problems [J].
Zheng, Shaoxiang ;
Xie, Naiming ;
Wu, Qiao ;
Liu, Caijie .
COMPUTERS & OPERATIONS RESEARCH, 2025, 173
[37]   Single-machine scheduling with deteriorating jobs [J].
Kuo, Wen-Hung ;
Yang, Dar-Li .
INTERNATIONAL JOURNAL OF SYSTEMS SCIENCE, 2012, 43 (01) :132-139
[38]   Single machine scheduling problems with deteriorating jobs [J].
Zhao, CL ;
Tang, HY .
APPLIED MATHEMATICS AND COMPUTATION, 2005, 161 (03) :865-874
[39]   Scheduling jobs on a flexible batching machine: Model, complexity and algorithms [J].
Fan, Baoqiang ;
Tang, Guochun .
THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, PROCEEDINGS, 2006, 3959 :118-127
[40]   Parallel-machine scheduling with deteriorating jobs and rejection [J].
Li, Shisheng ;
Yuan, Jinjiang .
THEORETICAL COMPUTER SCIENCE, 2010, 411 (40-42) :3642-3650
12345