Comparison of Priority Rules, Machine Allocation, and Stage Allocation Strategies for Hybrid Flow Shop Instances Using Combinatorial Logic and a Standard Trace Format

The configuration of heuristics strongly affects the resulting objective function values for given problem instances. Finding the most suitable algorithm components is essential for efficient production scheduling. This paper aims to automatically compare and combine different priority rules, machine allocation, and stage allocation strategies on hybrid flow shop instances with different sets of real-world constraints. To test and tune algorithm configurations and parameters for scheduling problems, an approach with combinatorial logic using the combinatory logic synthesizer is applied. To automatically test scheduling instances, the trace formats in the literature are first reviewed. A trace format is proposed to harmonize the data sets for a large number of beta constraints. In the second step, 32 constructive heuristic configurations are automatically constructed using componentization and recombination with four priority rules, four machine assignment strategies, and two-stage assignment strategies in a general framework of a constructive heuristic. Finally, three sets of test instances with different numbers of jobs by Wittrock (Operations Research 36:445–453, 1988), Naderi et al. (Computers & Operations Research 37:236–246, 2010) and Ruiz et al. (Computers & Operations Research 35: 1151–1175, 2008) are used to evaluate the resulting constructive heuristics.