电子学报 ›› 2021, Vol. 49 ›› Issue (9): 1708-1715.DOI: 10.12263/DZXB.20210039

• 学术论文 • 上一篇    下一篇

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

吕阳1,2, 钱斌1,2, 胡蓉1,2, 张梓琪1   

  1. 1.昆明理工大学信息工程与自动化学院,云南 昆明 650500
    2.昆明理工大学云南省人工智能重点实验室,云南 昆明 650500
  • 收稿日期:2020-12-29 修回日期:2021-02-10 出版日期:2021-09-25 发布日期:2021-09-25
  • 作者简介:吕 阳 男,1996年生于曲靖.现为昆明理工大学大学信息工程与自动化学院硕士研究生.主要研究方向为智能算法与优化调度.E‑mail: 726564418@qq.com
    钱 斌(通讯作者) 男,1976年出生,教授,博士研究生导师.主要研究方向为优化调度理论与方法.E‑mail:bin.qian@vip.163.com
    胡 蓉 女,1973年出生,副教授,硕士研究生导师.主要研究方向为优化方法和决策支持系统.E‑mail:ronghu@vip.163.com
    张梓琪 男,1989年生于云南曲靖.现为昆明理工大学大学信息工程与自动化学院博士研究生.主要研究方向为智能算法与优化调度.E‑mail: 768894018@qq.com
  • 基金资助:
    国家自然科学基金(51665025)

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

Yang LÜ1,2, Bin QIAN1,2, Rong HU1,2, Zi-qi ZHANG1   

  1. 1.Faculty of Information Engineering and Automation,Kunming University of Science and Technology,Kunming,Yunnan 650500,China
    2.Yunnan Key Laboratory of Artificial Intelligence,Kunming University of Science and Technology,Kunming,Yunnan 650500,China
  • Received:2020-12-29 Revised:2021-02-10 Online:2021-09-25 Published:2021-09-25

摘要:

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

关键词: 半导体最终测试, 人工蜂群算法, 启发式规则, 贝叶斯网络, 多策略融合, 概率模型, 排序模型

Abstract:

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 Multiagent Evolutionary Algorithm) and CCIWO(Cooperative Co-evolutionary Invasive Weed Optimization) demonstrated the effectiveness and robustness of the proposed algorithm.

Key words: semiconductor final test, artificial bee colony algorithm, heuristic rules, Bayesian network, multistrategy integration, probability model, permutation-based model

中图分类号: