Parallel-Machine Scheduling Problem: An Experimental Study of Instances Difficulty and Algorithms Performance

Octavio Ramos-Figueroa, Marcela Quiroz-Castellanos, Guadalupe Carmona-Arroyo, Betsabé Vázquez, Rupak Kharel

Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review

2 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationRecent Advances of Hybrid Intelligent Systems Based on Soft Computing
EditorsPatricia Melin, Oscar Castillo, Janusz Kacprzyk
PublisherSpringer, Cham
Number of pages37
ISBN (Electronic)9783030587284
ISBN (Print)978303058727, 9783030587307
Publication statusPublished - 7 Nov 2021
Externally publishedYes

Publication series

NameStudies in Computational Intelligence
VolumeSCI 915
ISSN (Print)1860-949X
ISSN (Electronic)1860-9503

Cite this