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 条

[31] Makespan minimization for scheduling unrelated parallel machines with setup times [J].

Kuo-Ching Ying ;

Zne-Jung Lee ;

Shih-Wei Lin .

Journal of Intelligent Manufacturing, 2012, 23 :1795-1803

[32] Makespan minimization for scheduling unrelated parallel machines with setup times [J].

Ying, Kuo-Ching ;

Lee, Zne-Jung ;

Lin, Shih-Wei .

JOURNAL OF INTELLIGENT MANUFACTURING, 2012, 23 (05) :1795-1803

[33] A Hybrid Metaheuristic for the Unrelated Parallel Machine Scheduling Problem [J].

Lin, Dung-Ying ;

Huang, Tzu-Yun .

MATHEMATICS, 2021, 9 (07)

[34] A Hybrid Algorithm for the Unrelated Parallel Machine Scheduling Problem [J].

Rego, Marcelo Ferreira ;

Freitas Souza, Marcone Jamilson .

ENTERPRISE INFORMATION SYSTEMS (ICEIS 2019), 2020, 378 :37-56

[35] Integrating dominance properties with genetic algorithms for parallel machine scheduling problems with setup times [J].

Chang, Pei-Chann ;

Chen, Shih-Hsin .

APPLIED SOFT COMPUTING, 2011, 11 (01) :1263-1274

[36] Comparing an ACO algorithm with other heuristics for the single machine scheduling problem with sequence-dependent setup times [J].

Gagné, C ;

Price, WL ;

Gravel, M .

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2002, 53 (08) :895-906

[37] Integrated maintenance and production scheduling for unrelated parallel machines with setup times [J].

Geurtsen, Michael ;

Adan, Jelle ;

Akcay, Alp .

FLEXIBLE SERVICES AND MANUFACTURING JOURNAL, 2024, 36 (03) :1046-1079

[38] Iterated Local Search Algorithms for the Sequence-Dependent Setup Times Flow Shop Scheduling Problem Minimizing Makespan [J].

Wang, Yanqi ;

Dong, Xingye ;

Chen, Ping ;

Lin, Youfang .

FOUNDATIONS OF INTELLIGENT SYSTEMS (ISKE 2013), 2014, 277 :329-338

[39] Modeling and solving static m identical parallel machines scheduling problem with a common server and sequence dependent setup times [J].

Hamzadayi, Alper ;

Yildiz, Gokalp .

COMPUTERS & INDUSTRIAL ENGINEERING, 2017, 106 :287-298

[40] Design of a genetic algorithm for bi-objective unrelated parallel machines scheduling with sequence-dependent setup times and precedence constraints [J].

Tavakkoli-Moghaddam, R. ;

Taheri, F. ;

Bazzazi, M. ;

Izadi, M. ;

Sassani, F. .

COMPUTERS & OPERATIONS RESEARCH, 2009, 36 (12) :3224-3230

← 1 2 3 4 5 →