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

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||C_{max}\)). 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||C_{max}\) 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.