A Simulated Annealing-Based Hyper-Heuristic For The Flexible Job Shop Scheduling Problem
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 strai...
| Main Author: | |
|---|---|
| Format: | Thesis |
| Language: | English |
| Published: |
2023
|
| Subjects: | |
| Online Access: | http://eprints.usm.my/61274/1/24%20Pages%20from%20KELVIN%20LIM%20CHING%20WEI.pdf |
| _version_ | 1825908443307835392 |
|---|---|
| author | Kelvin, Lim Ching Wei |
| author_facet | Kelvin, Lim Ching Wei |
| author_sort | Kelvin, Lim Ching Wei |
| collection | USM |
| description | 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). |
| first_indexed | 2024-12-09T02:32:35Z |
| format | Thesis |
| id | usm.eprints-61274 |
| institution | Universiti Sains Malaysia |
| language | English |
| last_indexed | 2024-12-09T02:32:35Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | usm.eprints-612742024-10-14T01:16:51Z http://eprints.usm.my/61274/ A Simulated Annealing-Based Hyper-Heuristic For The Flexible Job Shop Scheduling Problem Kelvin, Lim Ching Wei QA75.5-76.95 Electronic computers. Computer science 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). 2023-03 Thesis NonPeerReviewed application/pdf en http://eprints.usm.my/61274/1/24%20Pages%20from%20KELVIN%20LIM%20CHING%20WEI.pdf Kelvin, Lim Ching Wei (2023) A Simulated Annealing-Based Hyper-Heuristic For The Flexible Job Shop Scheduling Problem. Masters thesis, Perpustakaan Hamzah Sendut. |
| spellingShingle | QA75.5-76.95 Electronic computers. Computer science Kelvin, Lim Ching Wei A Simulated Annealing-Based Hyper-Heuristic For The Flexible Job Shop Scheduling Problem |
| title | A Simulated Annealing-Based Hyper-Heuristic For The Flexible Job Shop Scheduling Problem |
| title_full | A Simulated Annealing-Based Hyper-Heuristic For The Flexible Job Shop Scheduling Problem |
| title_fullStr | A Simulated Annealing-Based Hyper-Heuristic For The Flexible Job Shop Scheduling Problem |
| title_full_unstemmed | A Simulated Annealing-Based Hyper-Heuristic For The Flexible Job Shop Scheduling Problem |
| title_short | A Simulated Annealing-Based Hyper-Heuristic For The Flexible Job Shop Scheduling Problem |
| title_sort | simulated annealing based hyper heuristic for the flexible job shop scheduling problem |
| topic | QA75.5-76.95 Electronic computers. Computer science |
| url | http://eprints.usm.my/61274/1/24%20Pages%20from%20KELVIN%20LIM%20CHING%20WEI.pdf |
| work_keys_str_mv | AT kelvinlimchingwei asimulatedannealingbasedhyperheuristicfortheflexiblejobshopschedulingproblem AT kelvinlimchingwei simulatedannealingbasedhyperheuristicfortheflexiblejobshopschedulingproblem |