New hard benchmark for the 2-stage multi-machine assembly scheduling problem: Design and computational evaluation

Abstract

The assembly scheduling problem is a common layout with many applications in real manufacturing scenarios. Despite the high number of studies dealing with this problem, no benchmark has been proposed up-to-now in the literature generating neither hard nor balanced instances. In this paper we present two extensive sets of instances for two variants of the 2-stage assembly scheduling problem. The first set is composed of 240 instances for the variant with one assembly machine in the second stage, while in the second set 960 instances are proposed for the variant with several assembly machines. An exhaustive experimental procedure, generating several preliminary testbeds with different processing times and number of jobs and machines, is carried out in order to identify the most representative instances of the problem under study. A total of 120,000 instances are generated and, among them, 1,200 are selected ensuring that the new benchmarks satisfy the desired characteristics of any benchmark: adequacy, empirical hardness, exhaustiveness, and amenity for statistical analysis. Finally, two computational evaluations are performed comparing and evaluating the existing heuristics in the literature, thus establishing the set of efficient heuristics for this assembly problem.