Publication: A Simulated Annealing-Based Hyper-Heuristic For The Flexible Job Shop Scheduling Problem
Date
2023-03
Authors
Kelvin, Lim Ching Wei
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Flexible job shop scheduling problem (FJSP) is a common optimisation problem in the industry. The use of parallel machines allows an operation to be executed on a machine assigned from a set of alternative machines, raising a combination of machine assignment and job sequencing sub-problems. A straightforward technique to solve the FJSP is to apply a pair of machine assignment rule (MAR) and job sequencing rule (JSR), i.e. a MAR-JSR pair. However, the performance of each MAR-JSR pair is problem-dependent. In addition, within an algorithm execution, the MAR-JSR pair performs differently at different problem states. Given a wide range of MAR-JSR permutations, selecting a suitable MAR-JSR pair for a FJSP becomes a challenge. Positive outcomes on the application of simulated annealing-based hyper-heuristic (SA-HH) in addressing similar scheduling problem has been reported in the literature. Hence, this research proposes the SA-HH to produce a heuristic scheme (HS) made up of MAR-JSR pairs to solve the FJSP. The proposed SA-HH also incorporates a set of problem state features to facilitate the application of MAR-JSR pairs in the HS according to the state of the FJSP. This research investigates two variants of SA-HH, i.e. SA-HH based on the HS with problem state features (SA-HHPSF) and without problem state features (SA-HHNO-PSF).
Description
Keywords
Flexible Job Shop Scheduling Problem