Simulated-annealing-based hyper-heuristic for flexible job-shop scheduling

The flexible job-shop scheduling problem (FJSP) is common in high-mix industries such as semiconductor manufacturing. An FJSP is initiated when an operation can be executed on a machine assigned from a set of alternative machines. Thus, an FJSP consists of the machine assignment and job sequencing sub-problems, which can be resolved using a pair of problem-dependent machine assignment rules (MARs) and job sequencing rules (JSRs). Selecting an MAR-JSR pair that performs efficiently is a challenge. This study proposes a simulated-annealing-based hyper-heuristic (SA-HH) for assembling an heuristic scheme (HS) consisting of MAR-JSR pairs with a set of problem state features. Two variants of SA-HH, i.e. SA-HH based on HS with problem state features (SA-HHPSF) and without problem state features (SA-HHNO-PSF), are investigated. In terms of the best makespan, SA-HHpsF outperforms or is comparable with over 75% of benchmark algorithms on 8 out of 10 instances in the Brandimarte dataset.

Automated summary

The flexible job-shop scheduling problem (FJSP) is common in high-mix industries. This study proposes a simulated-annealing-based hyper-heuristic algorithm (SA-HH) to solve the problem and investigates two variants. The experimental results show that the method performs well on most instances.