A variable neighborhood descent heuristic for the problem of makespan minimisation on unrelated parallel machines with setup times

被引：27

作者：

Fleszar, Krzysztof ^{[1
]}

Charalambous, Christoforos ^{[2
]}

Hindi, Khalil S. ^{[1
]}

机构：

[1] AUB, Olayan Sch Business, Beirut 11072020, Lebanon

[2] Frederick Univ, Dept Comp Sci & Engn, CY-1303 Nicosia, Cyprus

来源：

JOURNAL OF INTELLIGENT MANUFACTURING | 2012年 / 23卷 / 05期

关键词：

Parallel machine scheduling; Hybrid optimization; Neighborhood search; Makespan minimization; Mixed-integer programming; MULTI-EXCHANGE NEIGHBORHOOD; TOTAL WEIGHTED TARDINESS; SCHEDULING PROBLEM; ALGORITHM; SEQUENCE; APPROXIMATION; SEARCH;

D O I：

10.1007/s10845-011-0522-8

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

The NP-hard problem of scheduling jobs on unrelated parallel machines, in the presence of machine-dependent and sequence-dependent setup times, with the objective of minimizing the makespan, is considered. A variable neighborhood descent search algorithm, hybridized with mathematical programming elements, is presented and its performance is evaluated on a large set of benchmark problem instances. The extensive computational experiments show that the proposed algorithm outperforms previously proposed methods in terms of solution quality as well as computation time.

引用

页码：1949 / 1958

页数：10

共 50 条

[31] GRASP algorithm for the unrelated parallel machine scheduling problem with setup times and additional resources
Yepes-Borrero, Juan C.
Villa, Fulgencia
Perea, Federico
Pablo Caballero-Villalobos, Juan
EXPERT SYSTEMS WITH APPLICATIONS, 2020, 141
[32] Including preventive maintenance activities in an unrelated parallel machine environment with dependent setup times
Avalos-Rosales, Oliver
Angel-Bello, Francisco
Alvarez, Ada
Cardona-Valdes, Yajaira
COMPUTERS & INDUSTRIAL ENGINEERING, 2018, 123 : 364 - 377
[33] A Hybrid Large Neighborhood Search Method for Minimizing Makespan on Unrelated Parallel Batch Processing Machines with Incompatible Job Families
Ji, Bin
Xiao, Xin
Yu, Samson S. S.
Wu, Guohua
SUSTAINABILITY, 2023, 15 (05)
[34] An Effective Scheduling Algorithm for Linear Makespan Minimization on Unrelated Parallel Machines
Fan, Liya
Zhang, Fa
Wang, Gongming
Liu, Zhiyong
16TH INTERNATIONAL CONFERENCE ON HIGH PERFORMANCE COMPUTING (HIPC), PROCEEDINGS, 2009, : 40 - 49
[35] A Mixed Integer Programming Model for Unrelated Parallel Machine Scheduling Problem with Sequence Dependent Setup Time to Minimize Makespan and Total Tardiness
Kongsri, Papimol
Buddhakulsomsiri, Jirachai
2020 IEEE 7TH INTERNATIONAL CONFERENCE ON INDUSTRIAL ENGINEERING AND APPLICATIONS (ICIEA 2020), 2020, : 605 - 609
[36] Variable Neighborhood Descent for the Capacitated Clustering Problem
Brimberg, Jack
Mladenovic, Nenad
Todosijevic, Raca
Urosevic, Dragan
DISCRETE OPTIMIZATION AND OPERATIONS RESEARCH, DOOR 2016, 2016, 9869 : 336 - 349
[37] Efficient arc-flow formulations for makespan minimisation on parallel machines with a common server
Druetto, Alessandro
Grosso, Andrea
Jeunet, Jully
Salassa, Fabio
COMPUTERS & OPERATIONS RESEARCH, 2025, 174
[38] Efficient heuristics and metaheuristics for the unrelated parallel machine scheduling problem with release dates and setup times
Athmani, Mohamed Elamine
Arbaoui, Taha
Mimene, Younes
Yalaoui, Farouk
PROCEEDINGS OF THE 2022 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE (GECCO'22), 2022, : 177 - 185
[39] Metaheuristics for optimizing unrelated parallel machines scheduling with unreliable resources to minimize makespan
Kaid, Husam
Al-Ahmari, Abdulrahman
Al-Shayea, Adel
Abouel Nasr, Emad
Kamrani, Ali K.
Mahmoud, Haitham A.
ADVANCES IN MECHANICAL ENGINEERING, 2022, 14 (05)
[40] A fix-and-optimize heuristic for the Unrelated Parallel Machine Scheduling Problem
Fonseca, George H. G.
Figueiroa, Guilherme B.
Toffolo, Tulio A. M.
COMPUTERS & OPERATIONS RESEARCH, 2024, 163

← 1 2 3 4 5 →