Journal of Computer Applications ›› 2020, Vol. 40 ›› Issue (3): 689-697.DOI: 10.11772/j.issn.1001-9081.2019071203

• Artificial intelligence • Previous Articles     Next Articles

Parallel machine scheduling optimization based on improved discrete artificial bee colony algorithm

ZHANG Jiapeng1,2, NI Zhiwei1,2, NI Liping1,2, ZHU Xuhui1,2, WU Zhangjun1,2   

  1. 1. School of Management, Hefei University of Technology, Hefei Anhui 230009, China;
    2. Key Laboratory of Process Optimization and Intelligent Decision-making of Ministry of Education(Hefei University of Technology), Hefei Anhui 230009, China
  • Received:2019-07-10 Revised:2019-09-03 Online:2020-03-10 Published:2020-03-23
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (91546108, 71490725, 71521001, 71301041),the Natural Science Foundation of Anhui Province (1708085MG169).

基于改进离散人工蜂群算法的同类机调度优化

张架鹏1,2, 倪志伟1,2, 倪丽萍1,2, 朱旭辉1,2, 伍章俊1,2   

  1. 1. 合肥工业大学 管理学院, 合肥 230009;
    2. 过程优化与智能决策教育部重点实验室(合肥工业大学), 合肥 230009
  • 通讯作者: 倪志伟
  • 作者简介:张架鹏(1994-),男,安徽亳州人,硕士研究生,主要研究方向:机器学习、数据挖掘;倪志伟(1963-),男,安徽合肥人,教授,博士,主要研究方向:人工智能、机器学习、云计算;倪丽萍(1981-),女,安徽合肥人,副教授,博士,主要研究方向:数据挖掘、金融数据分析、商务智能与智能决策;朱旭辉(1991-),男,安徽阜阳人,讲师,博士,主要研究方向:智能计算、机器学习;伍章俊(1972-),男,安徽合肥人,副教授,博士,主要研究方向:机器学习、数据挖掘。
  • 基金资助:
    国家自然科学基金资助项目(91546108, 71490725, 71521001, 71301041);安徽省自然科学基金资助项目(1708085MG169)。

Abstract: For the parallel machine scheduling problem of minimizing the maximum completion time, an Improved Discrete Artificial Bee Colony algorithm (IDABC) was proposed by considering the processing efficiency of the machine and the delivery time of the product as well as introducing the mathematical model of the problem. Firstly, a uniformly distributed population and a generation strategy of the parameters to be optimized were achieved by adopting the population initialization strategy, resulting in the improvement of the convergence speed of population. Secondly, the mutation operator in the differential evolution algorithm and the idea of simulated annealing algorithm were used to improve the local search strategy for the employed bee and the following bee, and the scout bee was improved by using the high-quality information of the optimal solution, resulting in the increasement of the population diversity and the avoidance of trapping into the local optimum. Finally, the proposed algorithm was applied in the parallel machine scheduling problem to analyze the performance and parameters of the algorithm. The experimental results on 15 examples show that compared with the Hybrid Discrete Artificial Bee Colony algorithm (HDABC), IDABC has the accuracy and stability improved by 4.1% and 26.9% respectively, and has better convergence, which indicates that IDABC can effectively solve the parallel machine scheduling problem in the actual scene.

Key words: parallel machine scheduling, minimization of maximum completion time, mutation operator, Artificial Bee Colony algorithm (ABC), optimization

摘要: 针对一类最小化最大完工时间的同类机调度问题,考虑到机器的加工效率和产品的交付时间,引入同类机调度问题的数学模型,提出一种改进的离散型人工蜂群算法(IDABC)求解该问题。首先,引入种群初始化策略,得到均匀分布的种群,并获得待优参数的生成策略,加快种群的收敛;其次,借鉴差分进化算法的变异算子和模拟退火算法的思想,改进雇佣蜂和跟随蜂的局部搜索策略,并利用最优解的优质信息改进侦察蜂,增加种群多样性、防止算法陷入局部最优;最后,分析算法的性能和参数,并将改进的算法应用于同类机调度问题,在15个算例上的实验结果表明,与混合离散人工蜂群(HDABC)算法相比,IDABC的求解精度和稳定性分别平均提高了4.1%和26.9%,且具有更好的收敛性,表明在实际场景中IDABC可以有效求解同类机调度问题。

关键词: 同类机调度, 最小化最大完工时间, 变异算子, 人工蜂群算法, 优化

CLC Number: