On the complexity of proportionate open shop and job shop problems

被引：0
作者：
Abdennour Azerine
Mourad Boudhar
Djamal Rebaine
机构：
[1] Université des Sciences et de la Technologie Houari Boumedienne,Laboratoire RECITS, Faculté de Mathématiques
[2] CERIST,Research Center on Scientific and Technical Information
[3] Université du Québec à Chicoutimi,Département d’Informatique et de Mathématique
来源：
Optimization Letters | 2024年 / 18卷
关键词：
Proportionate shop; Complexity; Scheduling; Makespan; Maximum lateness; Mean finish time; Just-in-time;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
In this paper, we present NP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{N}\mathcal{P}$$\end{document}-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
页数：10
相关论文
共 38 条
[1]  
Azerine A(2022)A two-machine no-wait flow shop problem with two competing agents J. Comb. Optim. 43 168-199
[2]  
Boudhar M(1956)An extension of Johnson’s results on job IDT scheduling Naval Res. Logist. Q. 3 201-203
[3]  
Rebaine D(2015)The three-machine proportionate open shop and mixed shop minimum makespan problems Eur. J. Oper. Res. 243 70-74
[4]  
Jackson JR(2016)The proportionate two-machine no-wait job shop scheduling problem Eur. J. Oper. Res. 252 131-135
[5]  
Koulamas C(1981)Minimizing maximum lateness in a two-machine open shop Math. Oper. Res. 6 153-158
[6]  
Kyparisis GJ(2004)Scheduling two-machine preemptive open shops to minimize total completion time Comput. Oper. Res. 31 1349-1363
[7]  
Koulamas C(2020)Approximation algorithms for the three-machine proportionate mixed shop scheduling Theor. Comput. Sci. 803 57-70
[8]  
Panwalkar S(2010)Polynomial time algorithms for two special classes of the proportionate multiprocessor open shop Eur. J. Oper. Res. 201 720-728
[9]  
Lawler EL(2015)A note: minimizing maximum earliness on a proportionate flowshop Inf. Process. Lett. 115 253-255
[10]  
Lenstra JK(2014)Polynomial time approximation algorithms for proportionate open-shop scheduling Int. Trans. Oper. Res. 21 1031-1044
1234