TY - CHAP

T1 - Parallel-Machine Scheduling Problem

T2 - An Experimental Study of Instances Difficulty and Algorithms Performance

AU - Ramos-Figueroa, Octavio

AU - Quiroz-Castellanos, Marcela

AU - Carmona-Arroyo, Guadalupe

AU - Vázquez, Betsabé

AU - Kharel, Rupak

N1 - Publisher Copyright:
© 2021, The Editor(s) (if applicable) and The Author(s), under exclusive license to Springer Nature Switzerland AG.

PY - 2021/11/7

Y1 - 2021/11/7

N2 - Parallel-machine scheduling problems are well-known NP-hard combinatorial optimization problems with many real-world applications. Given the increasing appearance of these problems, over the last few years, several algorithms have been developed to solve them, and different instances of these problems have been designed to be used as the benchmark for testing the algorithms. However, there is limited knowledge about why the algorithms show some performance and the difficulty degree of the instances. This chapter provides a starting point for the characterization of Parallel-machine scheduling problems with an emphasis on the case of unrelated machines, jobs with non-preemptions, and the reduction of the maximum completion time (R| | Cmax). For this purpose, we calculate seventeen measures for characterizing the structure of the instances, and we apply data analysis techniques to study how the features of the instances affect the performances of eleven constructive heuristics. The algorithmic behavior explanations obtained by the study suggest that the difficulty of the R| | Cmax instances is related to: (1) the number of jobs and machines; (2) the dispersion of the processing times of the jobs; (3) characteristics generated by considering only the minimum times in which each job can be processed; and (4) the difference between the processing times of the two fastest machines.

AB - Parallel-machine scheduling problems are well-known NP-hard combinatorial optimization problems with many real-world applications. Given the increasing appearance of these problems, over the last few years, several algorithms have been developed to solve them, and different instances of these problems have been designed to be used as the benchmark for testing the algorithms. However, there is limited knowledge about why the algorithms show some performance and the difficulty degree of the instances. This chapter provides a starting point for the characterization of Parallel-machine scheduling problems with an emphasis on the case of unrelated machines, jobs with non-preemptions, and the reduction of the maximum completion time (R| | Cmax). For this purpose, we calculate seventeen measures for characterizing the structure of the instances, and we apply data analysis techniques to study how the features of the instances affect the performances of eleven constructive heuristics. The algorithmic behavior explanations obtained by the study suggest that the difficulty of the R| | Cmax instances is related to: (1) the number of jobs and machines; (2) the dispersion of the processing times of the jobs; (3) characteristics generated by considering only the minimum times in which each job can be processed; and (4) the difference between the processing times of the two fastest machines.

KW - Algorithm behavior analysis

KW - Characterization

KW - Unrelated parallel machine scheduling

UR - http://www.scopus.com/inward/record.url?scp=85095829566&partnerID=8YFLogxK

UR - https://doi.org/10.1007/978-3-030-58728-4

U2 - 10.1007/978-3-030-58728-4_2

DO - 10.1007/978-3-030-58728-4_2

M3 - Chapter

AN - SCOPUS:85095829566

SN - 978303058727

SN - 9783030587307

T3 - Studies in Computational Intelligence

SP - 13

EP - 49

BT - Recent Advances of Hybrid Intelligent Systems Based on Soft Computing

A2 - Melin, Patricia

A2 - Castillo, Oscar

A2 - Kacprzyk, Janusz

PB - Springer, Cham

ER -