The majority of large-size job shop scheduling problems are non-polynomial-hard (NP-hard). In the past decades, Genetic algorithms have demonstrated considerable success in providing efficient solutions to many NP-hard optimization problems. But there is no literature considering the optimal parameters when designing genetic algorithms. Unsuitable parameters may cause terrible solution for a specific scheduling problem. In this paper, we proposed a two-stage genetic algorithm, which attempts to firstly find the fittest control parameters, namely, number of population, probability of crossover, probability of mutation, for a given job shop problem with a fraction of time; and then the fittest parameters are used in the genetic algorithm for further more search operation to find optimal solution. For large-size problem, the two-stage genetic algorithm can get optimal solution effectively and efficiently. The method is validated based on some hard benchmark problems of job shop scheduling.
Genetic algorithm Large-size job shop scheduling problem Control parameters Optimal computing budget allocation
Yongming Wang Nanfeng Xiao Chenggui Zhao Hongli Yin Enliang Hu Yanrong Jiang
School of Computer Science and Engineering South China University of Technology Guangzhou, Guangdong Computer Science Department Yunnan University of finance and economics Kunming, Yunnan Province, Chi School of Computer Science and Information Technology Yunnan Normal University Kunming, Yunnan Provi School of mathematics Yunnan Normal University Kunming, Yunnan Province, China School of Computer Guangdong University of Technology Guangzhou, Guangdong Province, China