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

吕阳; 钱斌; 胡蓉; 张梓琪

doi:10.12263/DZXB.20210039

您当前的位置：

首页 >

文章列表页 >

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

学术论文 | 更新时间：2025-12-08

- 增强人工蜂群算法求解半导体最终测试调度问题
- Enhanced Artificial Bee Colony Algorithm to Solve Semiconductor Final Test Scheduling Problem
- 电子学报 2021年49卷第9期页码：1708-1715
- 作者机构：
  
  1.昆明理工大学信息工程与自动化学院，云南昆明 650500
  2.昆明理工大学云南省人工智能重点实验室，云南昆明 650500
- 作者简介：
  
  [ "吕　阳　男，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;61963022)
- DOI：10.12263/DZXB.20210039
  中图分类号： TP391.9;TN406
- 收稿：2020-12-29，
  
  修回：2021-02-10，
  
  纸质出版：2021-09-25
- 稿件说明：
移动端阅览
吕阳,钱斌,胡蓉等.增强人工蜂群算法求解半导体最终测试调度问题[J].电子学报,2021,49(09):1708-1715.

LÜ Yang,QIAN Bin,HU Rong,et al.Enhanced Artificial Bee Colony Algorithm to Solve Semiconductor Final Test Scheduling Problem[J].ACTA ELECTRONICA SINICA,2021,49(09):1708-1715.
吕阳,钱斌,胡蓉等.增强人工蜂群算法求解半导体最终测试调度问题[J].电子学报,2021,49(09):1708-1715. DOI： 10.12263/DZXB.20210039.

LÜ Yang,QIAN Bin,HU Rong,et al.Enhanced Artificial Bee Colony Algorithm to Solve Semiconductor Final Test Scheduling Problem[J].ACTA ELECTRONICA SINICA,2021,49(09):1708-1715. DOI： 10.12263/DZXB.20210039.

摘要

本文提出一种增强人工蜂群算法（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的有效性和鲁棒性.

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

关键词

Keywords

references

朱泓达 . 中国半导体硅的现状与发展趋势［J］. 数字通信世界， 2020 ， 19 （ 6 ）： 268 - 278 .

ZHU H D . The status quo and development trend of semiconductor silicon in China ［J］. Digital Communication Circle ， 2020 ， 19 （ 6 ）： 268 - 278 . （in Chinese）

UZSOY R ， LEE C Y ， MARTIN‑VEGA L A . Scheduling semiconductor test operations： Minimizing maximum lateness and number of tardy jobs on a single machine ［J］. Naval Research Logs ， 1992 ， 39 （ 3 ）： 369 - 388 .

UZSOY R ， CHURCH L K ， OVACIK I M ， et al . Performance evaluation of dispatching rules for semiconductor testing operations ［J］. Journal of Electronics Manufacturing ， 2012 ， 3 （ 2 ）： 95 - 105 .

WU J Z ， CHIEN C F . Modeling semiconductor testing job scheduling and dynamic testing machine configuration ［J］. Expert Systems with Applications ， 2008 ， 35 （ 1‑2 ）： 485 - 496 .

WU J Z ， HAO X C ， CHIEN C F ， et al . A novel bi‑vector encoding genetic algorithm for the simultaneous multiple resources scheduling problem ［J］. Journal of Intelligent Manufacturing ， 2012 ， 23 （ 6 ）： 2255 - 2270 .

HAO X C ， et al . The cooperative estimation of distribution algorithm： a novel approach for semiconductor final test scheduling problems ［J］. Journal of Intelligent Manufacturing ， 2014 ， 25 （ 5 ）： 867 - 879 .

ZHENG X L ， WANG L ， WANG S Y . A novel fruit fly optimization algorithm for the semiconductor final testing scheduling problem ［J］. Knowledge‑Based Systems ， 2014 ， 57 （ 2 ）： 95 - 103 .

SANG H Y ， DUAN P Y ， LI J Q . An effective invasive weed optimization algorithm for scheduling semiconductor final testing problem ［J］. Swarm and Evolutionary Computation ， 2018 ， 38 （ 1 ）： 1 - 12 .

LU S J ， LIU X B ， PEI J ， et al . A hybrid ABC‑TS algorithm for the unrelated parallel‑batching machines scheduling problem with deteriorating jobs and maintenance activity ［J］. Applied Soft Computing ， 2018 ， 66 （ 1 ）： 168 - 182 .

LI J Q ， SONG M X ， WANG L ， et al . Hybrid artificial bee colony algorithm for a parallel batching distributed flow‑shop problem with deteriorating jobs ［J］. IEEE Transactions on Cybernetics ， 2020 ， 50 （ 6 ）： 1 - 15 .

GAO K Z ， SUGANTHAN P N ， CHUA T J ， et al . A two‑stage artificial bee colony algorithm scheduling flexible job‑shop scheduling problem with new job insertion ［J］. Expert Systems with Applications ， 2015 ， 42 （ 21 ）： 7652 - 7663 .

GONG G L ， CHIONG R ， DENG Q W ， et al . A hybrid artificial bee colony algorithm for flexible job shop scheduling with worker flexibility ［J］. International Journal of Production Research ， 2020 ， 58 （ 14 ）： 1 - 15 .

LI Y ， HUANG W ， WU R ， et al . An improved artificial bee colony algorithm for solving multi‑objective low‑carbon flexible job shop scheduling problem ［J］. Applied Soft Computing ， 2020 ， 95 （ 5 ）： 1 - 14 .

BANHARNSAKUN A ， ACHALAKUL T ， SIRINAOVAKUL B . The best‑so‑far selection in artificial bee colony algorithm ［J］. Applied Soft Computing Journal ， 2010 ， 11 （ 2 ）： 2888 - 2901 .

LI H ， LI X ， GAO L . A discrete artificial bee colony algorithm for the distributed heterogeneous no‑wait flowshop scheduling problem ［J］. Applied Soft Computing ， 2021 ， 100 （ 1 ）： 1 - 19 .

赵博选，高建，付颖斌，等 . 求解柔性作业车间调度问题的多策略融合Pareto人工蜂群算法［J］. 系统工程理论与实践， 2019 ， 39 （ 5 ）： 1225 - 1235 .

ZHAO BOXUAN ， GAO JIAN ， FU YINGBIN ， et al . Multi‑strategy fusion Pareto artificial bee colony algorithm for solving flexible job shop scheduling problems ［J］. Systems Engineering Theory and Practice ， 2019 ， 39 （ 5 ）： 1225 - 1235 . （in Chinese）

WANG S ， WANG L . A knowledge‑based multi‑agent evolutionary algorithm for semiconductor final testing scheduling problem ［J］. Knowledge‑Based Systems ， 2015 ， 84 （ 8 ）： 1 - 9 .

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

基于双重约束的最优BN结构学习算法

基于多元信息引导的人工蜂群算法

贝叶斯程序分析