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

LÜ Yang; QIAN Bin; HU Rong; ZHANG Zi-qi

doi:10.12263/DZXB.20210039

您当前的位置：

首页 >

文章列表页 >

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

PAPERS | 更新时间：2025-12-08

- Enhanced Artificial Bee Colony Algorithm to Solve Semiconductor Final Test Scheduling Problem
- ACTA ELECTRONICA SINICA Vol. 49, Issue 9, Pages: 1708-1715(2021)
- 作者机构：
  
  1.昆明理工大学信息工程与自动化学院，云南昆明 650500
  2.昆明理工大学云南省人工智能重点实验室，云南昆明 650500
- 作者简介：
- 基金信息：
- DOI：10.12263/DZXB.20210039
  CLC： TP391.9;TN406
- Received：29 December 2020，
  
  Revised：2021-02-10，
  
  Published：25 September 2021
- 稿件说明：
移动端阅览
吕阳,钱斌,胡蓉等.增强人工蜂群算法求解半导体最终测试调度问题[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 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Optimal BN Structure Learning Algorithm Based on Double Constraints

Artificial Bee Colony Algorithm Based on Multiple Information Guidance

Bayesian Program Analysis

Related Author

XU Wen

ZHANG Huan

ZHANG Xin-lan

WANG Peng

DI Ruo-hai

CHEN Yi-wei

ZHOU Xin-yu

LIU Ying

Related Institution

School of Electronics and Information Engineering, Xi'an Technological University, , Shannxi

Aerospace Research Institute of Materials & Processing Technology

School of Computer Science， Central China Normal University

School of Computer and Communication Engineering， Changsha University of Science and Technology

School of Computer and Information Engineering， Jiangxi Normal University

⁰