Computer Engineering and Applications ›› 2019, Vol. 55 ›› Issue (6): 257-264.DOI: 10.3778/j.issn.1002-8331.1712-0145

Previous Articles     Next Articles

Hybrid Grasshopper Optimization Algorithm for Job-Shop Scheduling Problem

YAN Xu, YE Chunming   

  1. Business School, University of Shanghai for Science and Technology, Shanghai 200093, China
  • Online:2019-03-15 Published:2019-03-14


闫  旭,叶春明   

  1. 上海理工大学 管理学院,上海 200093

Abstract: As a new intelligent algorithm, Grasshopper Optimization Algorithm(GOA) solving Job-shop scheduling problem(JSP) is in line with the trend of intelligent manufacturing. However, the insufficient global optimization ability of GOA brings disadvantages of being easily trapped in local optima and poor convergence in solving JSP. To overcome the disadvantages above, this paper improves GOA based on the idea of quantum computation, and a Hybrid Grasshopper Optimization Algorithm(HGOA) is proposed by the quantum rotate gate. In addition, this paper provides the computational complexity analysis, global convergence proof, and simulations of HGOA based on a set of 11 JSP benchmark instances. Comparing HGOA with GOA, Whale Optimization Algorithm(WOA), Cuckoo Search(CS) and Grey Wolf Optimizer(GWO) in simulations, the results show that HGOA has better performance in terms of mean value, minimum value, optimal success rate and number of iterations. Finally, this paper concludes that HGOA has the merits of better exploration, higher convergence accuracy and higher local optima avoidance.

Key words: grasshopper optimization algorithm, quantum rotate gate, job-shop scheduling problem, convergence proof, hybrid algorithm

摘要: 作为新兴的智能算法,蝗虫优化算法在作业车间调度问题中的应用符合智能制造的趋势。但由于全局寻优能力不足,基本蝗虫优化算法(GOA)在解决作业车间调度问题(JSP)时容易陷入局部最优,导致收敛精度较低。为了克服上述缺陷,利用量子旋转门操作对其进行改进,提出了一种基于量子计算思想的混合蝗虫优化算法(HGOA)。此外,对混合蝗虫优化算法进行了计算复杂度分析与全局收敛性证明,并利用11个作业车间标准测试问题进行了仿真实验。通过与基本蝗虫优化算法(GOA)、鲸鱼优化算法(WOA)、布谷鸟搜索算法(CS)、灰狼优化算法(GWO)的比较发现,混合蝗虫优化算法在平均值、最小值、寻优成功率及迭代次数方面存在较优结果。研究表明,混合蝗虫优化算法具有更强的全局搜索能力,更好的收敛精度,能够有效跳出局部最优。

关键词: 蝗虫优化算法, 量子旋转门, 作业车间调度问题, 收敛性证明, 混合算法