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 -