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

Abstract

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-HH${}_{\mathrm{PSF}}$) and without problem state features (SA-HH${}_{\mathrm{NO}-\mathrm{PSF}}$), are investigated. In terms of the best makespan, SA-HH${}_{\mathrm{PSF}}$ outperforms or is comparable with over 75% of benchmark algorithms on 8 out of 10 instances in the Brandimarte dataset.

Keywords:

• Manufacturing
• production scheduling
• machine scheduling
• heuristic selection
• heuristic scheme

Disclosure statement

No potential conflict of interest was reported by the author(s).

Data availability statement

The data that support the findings of this study are available from the corresponding author, L.-P. Wong, upon reasonable request.

Additional information

Funding

The work was supported by a Research University Grant awarded by Universiti Sains Malaysia [Grant No. 1001/PMEKANIK/8014069].