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 条

[41] Bicriteria scheduling of a two-machine flowshop with sequence-dependent setup times [J].

Mansouri, S. Afshin ;

Hendizadeh, S. Hamed ;

Salmasi, Nasser .

INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2009, 40 (11-12) :1216-1226

[42] Hybrid genetic algorithms with dispatching rules for unrelated parallel machine scheduling with setup time and production availability [J].

Joo, Cheol Min ;

Kim, Byung Soo .

COMPUTERS & INDUSTRIAL ENGINEERING, 2015, 85 :102-109

[43] Metaheuristic solutions to the "Job shop scheduling problem with sequence-dependent setup times" [J].

Gonzalez, Miguel A. .

AI COMMUNICATIONS, 2013, 26 (04) :419-421

[44] Heuristics for the Hybrid Flow Shop Scheduling Problem with Sequence-Dependent Setup times [J].

Yong, Liao ;

Zhantao, Li ;

Xiang, Li ;

Chenfeng, Peng .

MATHEMATICAL PROBLEMS IN ENGINEERING, 2022, 2022

[45] Solving the flexible job shop scheduling problem with sequence-dependent setup times [J].

Shen, Liji ;

Dauzere-Peres, Stephane ;

Neufeld, Janis S. .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2018, 265 (02) :503-516

[46] Using genetic algorithms and heuristics for job shop scheduling with sequence-dependent setup times [J].

Cheung, WM ;

Zhou, H .

ANNALS OF OPERATIONS RESEARCH, 2001, 107 (1-4) :65-81

[47] Using Genetic Algorithms and Heuristics for Job Shop Scheduling with Sequence-Dependent Setup Times [J].

Waiman Cheung ;

Hong Zhou .

Annals of Operations Research, 2001, 107 :65-81

[48] Solving a Discrete Lot Sizing and Scheduling Problem with Unrelated Parallel Machines and Sequence Dependent Setup Using a Generic Decision Support Tool [J].

Klement, Nathalie ;

Silva, Cristovao ;

Gibaru, Olivier .

ADVANCES IN PRODUCTION MANAGEMENT SYSTEMS: THE PATH TO INTELLIGENT, COLLABORATIVE AND SUSTAINABLE MANUFACTURING, 2017, 513 :459-466

[49] A hybrid multi-objective evolutionary algorithm approach for handling sequence- and machine-dependent set-up times in unrelated parallel machine scheduling problem [J].

Manupati, V. K. ;

Rajyalakshmi, G. ;

Chan, Felix T. S. ;

Thakkar, J. J. .

SADHANA-ACADEMY PROCEEDINGS IN ENGINEERING SCIENCES, 2017, 42 (03) :391-403

[50] Multiobjective unrelated parallel machines scheduling problem with periodic maintenance activities and dependent processing times [J].

Yaghtin, Mohammad ;

Javid, Youness .

JOURNAL OF MODELLING IN MANAGEMENT, 2025, 20 (02) :477-494

← 1 2 3 4 5 →