On the complexity of proportionate open shop and job shop problems

被引：0
作者：
Azerine, Abdennour [1 ,2 ]
Boudhar, Mourad [1 ]
Rebaine, Djamal [3 ]
机构：
[1] Univ Sci & Technol Houari Boumedienne, Fac Math, Lab RECITS, Algiers, Algeria
[2] CERIST, Res Ctr Sci & Tech Informat, Algiers, Algeria
[3] Univ Quebec Chicoutimi, Dept Informat & Math, Quebec City, PQ, Canada
来源：
OPTIMIZATION LETTERS | 2024年 / 18卷 / 01期
关键词：
Proportionate shop; Complexity; Scheduling; Makespan; Maximum lateness; Mean finish time; Just-in-time;
D O I：
10.1007/s11590-023-02000-0
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
In this paper, we present NP-hardness proofs and exhibit linear-time algorithms for proportionate two-machine open shop and job shop problems with respect to the maximum lateness, the makespan with release dates, the total weighted completion times and the number of just-in-time jobs.
引用
收藏
页码：365 / 375
页数：11
相关论文
共 21 条
[1]   A two-machine no-wait flow shop problem with two competing agents [J].
Azerine, Abdennour ;
Boudhar, Mourad ;
Rebaine, Djamal .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2022, 43 (01) :168-199
[2]  
Garey M. R., 1979, Computers and intractability. A guide to the theory of NP-completeness
[3]  
Jackson J.R., 1956, Naval Research Logistics Quarterly, V3, P201, DOI DOI 10.1002/NAV.3800030307
[4]   The proportionate two-machine no-wait job shop scheduling problem [J].
Koulamas, Christos ;
Panwalkar, S. S. .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2016, 252 (01) :131-135
[5]   The three-machine proportionate open shop and mixed shop minimum makespan problems [J].
Koulamas, Christos ;
Kyparisis, George J. .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2015, 243 (01) :70-74
[6]  
LAWLER EL, 1981, MATH OPER RES, V6, P153, DOI 10.1287/moor.6.1.153
[7]   Scheduling two-machine preemptive open shops to minimize total completion time [J].
Liaw, CF .
COMPUTERS & OPERATIONS RESEARCH, 2004, 31 (08) :1349-1363
[8]  
Liu L., 2018, CoRR abs/1809.02165
[9]   Approximation algorithms for the three-machine proportionate mixed shop scheduling [J].
Liu, Longcheng ;
Chen, Yong ;
Dong, Jianming ;
Goebel, Randy ;
Lin, Guohui ;
Luo, Yue ;
Ni, Guanqun ;
Su, Bing ;
Xu, Yao ;
Zhang, An .
THEORETICAL COMPUTER SCIENCE, 2020, 803 :57-70
[10]   Polynomial time algorithms for two special classes of the proportionate multiprocessor open shop [J].
Matta, Marie E. ;
Elmaghraby, Salah E. .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2010, 201 (03) :720-728
123