以改良式珊瑚礁優化法解決零工式排程問題
Modified Coral Reef Optimization methods for Job Shop
Scheduling Problems
姓名：阮庭強
In the field of operational research, the job shop scheduling problem is considered
as one of the common problems and has many practical applications. Due to the nature
of the NP-hard (nondeterministic polynomial time) problem, approximation approaches
are often applied to solve this type of problem. In the thesis framework, a novel
biologically inspired metaheuristic method called coral reef optimization is proposed in
combination with two local search techniques (simulated annealing and variable
neighborhood search) with different search strategies. The performance of the two hybrid
algorithms is evaluated based on solving different sizes of the job shop scheduling
problem. The results are compared with the original algorithm, showing the positive
impact of local search techniques on the search efficiency of the two hybrid algorithms.
Furthermore, the results of the comparison with two other metaheuristic algorithms
indicates that the search ability of the two proposed hybrid algorithms is quite competitive
with other metaheuristic methods.
Keywords: coral reef optimization method, hybrid approach, local search, job
shop scheduling.