增强人工蜂群算法求解半导体最终测试调度问题

Enhanced Artificial Bee Colony Algorithm to Solve Semiconductor Final Test Scheduling Problem

本文提出一种增强人工蜂群算法(Enhanced Artificial Bee Colony,EABC),用于最小化半导体最终测试调度问题(Semiconductor Final Testing Scheduling Problem,SFTSP)的最大完工时间.该算法采用混合启发式方法初始化种群,并利用前插式解码策略来提高初始解的质量.在算法搜索阶段设计多种基于问题性质的探索策略和基于贝叶斯网络的概率模型对问题解空间进行深度与宽度的协同搜索.此外,提出基于重启策略的种群更新机制以加强算法跳出局部最优的能力.实验部分构造多种对比算法来验证EABC中各关键环节的有效性.通过基于实例的数值仿真以及与NFOA(Novel Fruit fly Optimization Algorithm)、KMEA(Knowledge-based Multi-agent Evolutionary Algorithm)和CCIWO(Cooperative Co-evolutionary Invasive Weed Optimization)的算法比较验证了EABC的有效性和鲁棒性.

This paper proposed an enhanced artificial bee colony algorithm(EABC)to minimize the maximum completion time of the semiconductor final test scheduling problem(SFTSP).EABC used hybrid heuristic methods to initialize the population,and used forward interpolation decoding strategies to improve the quality of the initial solution.A variety of exploration strategies based on the problem features and a Bayesian network-based probability model were designed to conduct a depth and width search of the problem solution space.In addition,a population update mechanism based on the restart strategy was proposed to strengthen the algorithm’s ability to jump out of the local optimum.In the experimental part,multiple comparison algorithms were constructed to verify the effectiveness of the EABC’s key components.Simulation results based on some instances and comparisons with NFOA(Novel Fruit fly Optimization Algorithm)、KMEA(Knowledge-based Multi-agent Evolutionary Algorithm)and CCIWO(Cooperative Co-evolutionary Invasive Weed Optimization)demonstrated the effectiveness and robustness of the proposed algorithm.