Algorithms for the Unrelated Parallel Machine Scheduling Problem with Sequence Dependent Setup Times

被引：0
作者：
Silva, Luciano Geraldo [1 ]
Rego, Marcelo Ferreira [2 ]
de Assis, Luciana Pereira [3 ]
Andrade, Alessandro Vivas [3 ]
机构：
[1] Fed Univ Jequitinhonha & Mucuri Valleys, Open & Distance Educ Directorate, Diamantina, Brazil
[2] Univ Fed Ouro Preto, Dept Comp, Ouro Preto, Brazil
[3] Fed Univ Jequitinhonha & Mucuri Valleys, Dept Comp, Diamantina, Brazil
来源：
2018 37TH INTERNATIONAL CONFERENCE OF THE CHILEAN COMPUTER SCIENCE SOCIETY (SCCC) | 2018年
关键词：
unrelated parallel machines scheduling; UPMSPST; metaheuristic; mathematical heuristics; neighborhood structures; VNS; genetic algorithm; fix-and-optimize; relax-and-fix; gurobi; FIX;
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
This work addresses the Unrelated Parallel Machines Scheduling Problem with Sequence-Dependent Setup Times - UPMSPST. The objective considered here is to minimize the scheduling maximum completion time, also known as makespan. This is important in the practical sense as the UPMSPST is widely found in industries. As well, in a theoretical sense, it belongs to the NP-Hard class. Five algorithms have been implemented to find solutions for the UPMSPST. The results obtained by the execution of these algorithms were compared. Among all the algorithms studied here, the VNS and F&O heuristic with the VNS metaheuristic generating the initial solution presented the best results. In some cases, it even presented better results than in [1].
引用
收藏
页数：8
相关论文
共 50 条
[21]   A Statistical Comparison of Metaheuristics for Unrelated Parallel Machine Scheduling Problems with Setup Times [J].
Antunes, Ana Rita ;
Matos, Marina A. ;
Rocha, Ana Maria A. C. ;
Costa, Lino A. ;
Varela, Leonilde R. .
MATHEMATICS, 2022, 10 (14)
[22]   The single machine scheduling problem with sequence-dependent setup times and a learning effect on processing times [J].
Mustu, Settar ;
Eren, Tamer .
APPLIED SOFT COMPUTING, 2018, 71 :291-306
[23]   Fuzzy bi-objective formulation for a parallel machine scheduling problem with machine eligibility restrictions and sequence-dependent setup times [J].
Naderi-Beni, Mahdi ;
Ghobadian, Ehsan ;
Ebrahimnejad, Sadoullah ;
Tavakkoli-Moghaddam, Reza .
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2014, 52 (19) :5799-5822
[24]   A HYBRIT APPROACH ON SINGLE SERVER PARALLEL MACHINES SCHEDULING PROBLEM WITH SEQUENCE DEPENDENT SETUP TIMES [J].
Tuerker, A. Kuersad ;
Sel, Cagri .
JOURNAL OF THE FACULTY OF ENGINEERING AND ARCHITECTURE OF GAZI UNIVERSITY, 2011, 26 (04) :731-740
[25]   Bi-criteria formulation for green scheduling with unrelated parallel machines with sequence-dependent setup times [J].
Cota, Luciano P. ;
Coelho, Vitor N. ;
Guimaraes, Frederico G. ;
Souza, Marcone J. F. .
INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 2021, 28 (02) :996-1017
[26]   A hybrid genetic algorithm for the single machine scheduling problem with sequence-dependent setup times [J].
Sioud, A. ;
Gravel, M. ;
Gagne, C. .
COMPUTERS & OPERATIONS RESEARCH, 2012, 39 (10) :2415-2424
[27]   The distributionally robust machine scheduling problem with job selection and sequence-dependent setup times [J].
Bruni, M. E. ;
Khodaparasti, S. ;
Demeulemeester, E. .
COMPUTERS & OPERATIONS RESEARCH, 2020, 123
[28]   Parallel Machines Scheduling with Sequence-Dependent Setup Times Constraints [J].
Hu, Dayong ;
Yao, Zhenqiang .
ADVANCED SCIENCE LETTERS, 2011, 4 (6-7) :2528-2531
[29]   Unrelated parallel machine energy-efficient scheduling considering sequence-dependent setup times and time-of-use electricity tariffs [J].
Sanati, Hemen ;
Moslehi, Ghasem ;
Reisi-Nafchi, Mohammad .
EURO JOURNAL ON COMPUTATIONAL OPTIMIZATION, 2023, 11
[30]   Application of graph search and genetic algorithms for the single machine scheduling problem with sequence-dependent setup times and quadratic penalty function of completion times [J].
Kodaganallur, Viswanathan ;
Sen, Anup K. ;
Mitra, Subrata .
COMPUTERS & INDUSTRIAL ENGINEERING, 2014, 67 :10-19
12345