Computer Engineering and Applications ›› 2017, Vol. 53 ›› Issue (17): 249-253.DOI: 10.3778/j.issn.1002-8331.1612-0100

Previous Articles     Next Articles

Modified cuckoo search algorithm for job-shop scheduling problem based on simulated annealing

SHI Wenzhang1, HAN Wei1, DAI Ruiwen2   

  1. 1.College of Information Engineering, Nanjing University of Finance & Economics, Nanjing 210046, China
    2. College of Computer Science and Technology, Nanjing University of Technology, Nanjing 210046, China
  • Online:2017-09-01 Published:2017-09-12

模拟退火下布谷鸟算法求解车间作业调度问题

施文章1,韩  伟1,戴睿闻2   

  1. 1.南京财经大学 信息工程学院,南京 210046
    2.南京工业大学 计算机科学与技术学院,南京 210046

Abstract: This paper proposes a Modified Cuckoo Search algorithm based on Simulated Annealing(SA-MCS) for the job-shop scheduling problem. Adding the self-adaptive method in the Levy flight makes the step-length changing in the process of algorithm to improve the ability of global and local search. Introducing 2 values crossover operator keeps the population diversity and makes the algorithm avoiding premature convergence. What is more, the ability of jumping out of local optimum has increased under the framework of simulated annealing. Finally it uses the modified one in job-shop scheduling problem with standard test cases. The results prove the validity and efficiency of proposed algorithm.

Key words: job-shop scheduling, cuckoo algorithm, self-adaptive, 2 values crossover, simulation annealing

摘要: 针对车间作业调度问题(JSP),在标准布谷鸟算法的莱维飞行中加入自适应机制,寻优过程中引入二值交叉算子保持改进算法的种群多样性,最后在模拟退火框架下增强改进算法跳出局部最优的能力。通过标准算例对所提的改进算法进行实验仿真,结果证明了改进算法的正确性和有效性。

关键词: 车间作业调度, 布谷鸟算法, 自适应, 二值交叉算子, 模拟退火