A two-stage genetic algorithm for large size job shop scheduling problems |
| |
Authors: | Yong Ming Wang Nan Feng Xiao Hong Li Yin En Liang Hu Cheng Gui Zhao Yan Rong Jiang |
| |
Affiliation: | 1. School of Computer Science and Engineering, South China University of Technology, Guangzhou, 510641, China 2. School of Computer Science and Information Technology, Yunnan Normal University, Kunming, 650092, China 3. School of Mathematics, Yunnan Normal University, Kunming, 650092, China 4. Computer Science Department, Yunnan University of Finance and Economics, Kunming, 650221, China 5. School of Computer, Guangdong University of Technology, Guangzhou, 510641, China
|
| |
Abstract: | The majority of large size job shop scheduling problems are non-polynomial-hard (NP-hard). In the past few decades, genetic algorithms (GAs) have demonstrated considerable success in providing efficient solutions to many NP-hard optimization problems. But there is no literature available considering the optimal parameters when designing GAs. Unsuitable parameters may generate an inadequate solution for a specific scheduling problem. In this paper, we proposed a two-stage GA which attempts to firstly find the fittest control parameters, namely, number of population, probability of crossover, and probability of mutation, for a given job shop problem with a fraction of time using the optimal computing budget allocation method, and then the fittest parameters are used in the GA for a further searching operation to find the optimal solution. For large size problems, the two-stage GA can obtain optimal solutions effectively and efficiently. The method was validated based on some hard benchmark problems of job shop scheduling. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|