有滞留时间约束的集束型装备在线调度方法

doi:10.16182/j.issn1004731x.joss.201702014

系统仿真学报 ›› 2017, Vol. 29 ›› Issue (2): 337-345.doi: 10.16182/j.issn1004731x.joss.201702014

有滞留时间约束的集束型装备在线调度方法

李林瑛¹, 卢睿², 李绍华¹, 景雨¹, 刁建华¹

1.大连外国语大学软件学院,辽宁大连 116044;
2.辽宁警察学院公安信息系,辽宁大连 116036

收稿日期:2015-11-27 修回日期:2016-03-12 出版日期:2017-02-08 发布日期:2020-06-01
作者简介:李林瑛(1975-),男,辽宁大连,博士,副教授,研究方向为优化理论与优化方法。
基金资助:
国家自然科学基金(61501082); 辽宁省教育厅科学研究一般项目(L2015137, L2014011, L2014455, L2014456)

Online Scheduling Method of Cluster Tools with Residency Time Constraint

Li Linying¹, Lu Rui², Li Shaohua¹, Jing Yu¹, Diao Jianhua¹

1. School of Software, Dalian University of Foreign Languages, Dalian 116044, China;
2. Police Information Department, Liaoning Police College, Dalian 116036, China

Received:2015-11-27 Revised:2016-03-12 Online:2017-02-08 Published:2020-06-01

摘要/Abstract

摘要： 针对半导体制造中有滞留时间约束的集束型装备,研究了客户紧急订单、返工、新产品试制等临时晶圆到达时的在线调度问题,提出了不改变已有晶圆调度的前提下,利用资源空闲时间区间的两层在线调度方法。外层算法通过改进量子进化算法用以优化临时晶圆加工排序;内层算法在给定晶圆排序的基础上,采用后向逐级递推的策略从资源的空闲时间区间获得可行解,利用逆序最大逐级回溯策略在可行解空间获得晶圆的加工开始时间。通过不同规模测试问题上的仿真实验和算法比较,验证了提出方法的有效性。

关键词: 在线调度, 量子进化算法, 集束型装备, 半导体制造, 滞留时间约束

Abstract: For cluster tools with residency time constraints in semiconductor manufactory, online scheduling problem was studied when temporary wafers arrived with emergency order, rework and new product development, et al. Utilizing available resource interval, the two-layer online scheduling method was proposed without changing existing schedule. The outer layer algorithm used an improved quantum evolutionary algorithm to optimize processing order of temporary wafers. Based on the results, the inner layer algorithm gained feasible solutions from available space by backward stepwise recursive strategy, and determined start time of wafer in feasible solution space by means of reverted sequence maximum backtrack strategy. Simulation results and comparisons on benchmarks with different scales demonstrate the effectiveness of the presented method.

Key words: online scheduling, quantum evolutionary algorithm, cluster tools, semiconductor manufactory, residency time constraints

中图分类号:

李林瑛, 卢睿, 李绍华, 景雨, 刁建华. 有滞留时间约束的集束型装备在线调度方法[J]. 系统仿真学报, 2017, 29(2): 337-345.

Li Linying, Lu Rui, Li Shaohua, Jing Yu, Diao Jianhua. Online Scheduling Method of Cluster Tools with Residency Time Constraint[J]. Journal of System Simulation, 2017, 29(2): 337-345.

参考文献

[1] 卢睿, 李林瑛. 有晶圆滞留时间约束的集束型装备调度问题研究[J]. 系统仿真学报, 2014, 26(8): 1775-1780.
(Lu Rui, Li Linying.Research on scheduling problem of cluster tools with residency time constraints[J]. Journal of System Simulation (S1004-731X), 2014, 26(8): 1775-1780.)
[2] 李林瑛, 胡静涛. 有滞留时间约束的集束型装备在线调度问题研究[J]. 控制与决策, 2011, 26(1): 44-48.
(Li Linying, Hu Jingtao.Online scheduling problem of cluster tools with residency time constraints[J]. Control and Decision, 2011, 26(1): 44-48. )
[3] Zhang R, Song S, Wu C.A hybrid artificial bee colony algorithm for the job scheduling problem[J]. International Journal of Production Economics (S0925-5273), 2013, 141(1): 167-178.
[4] 晏鹏宇, 车阿大, 唐小我. 基于加工时间分类视角的自动化生产系统调度综述[J]. 计算机集成制造系统, 2012, 18(2): 332-341.
(Yan Pengyu, Che Ada, Tang Xiaowo.Scheduling problems in automated production systems based on processing times classification[J]. Computer Integrated Manufacturing Systems, 2012, 18(2): 332-341.)
[5] 王艳红, 王文霞, 于洪霞, 等. 一类求解作业车间调度问题的动态平衡自适应蚁群算法[J]. 计算机集成制造系统, 2013(10): 2521-2527.
(Wang Yanhong, Wang Wenxia, Yu Hongxia, et al.Dynamic balance adaptive colony algorithm solving Job-Shop Scheduling[J]. Computer Integrated Manufacturing Systems, 2013(10): 2521-2527.)
[6] Dawande M, Geismar H N, Pindo M, et al.Throughput optimization in dual-gripper interval robotic cells[J]. IIE Transactions (S0740-817X), 2010, 42(1): 1-15.
[7] Li X, Fung R Y K. Optimal K-unit cycle scheduling of two-cluster tools with residency constraints and general robot moving times[J]. Journal of Scheduling (S1094-6136), 2016, 19(2): 165-176.
[8] Rostami S, Hamidzadeh B.An optimal scheduling technique for dual-arm robots in cluster tools with residency constraints[J]. IEEE Transactions on Semiconductor Manufacturing (S0894-6507), 2001, 17(5): 609-618.
[9] Rostami S, Hamidzadeh B.Optimal scheduling techniques for cluster tools with process-module and transport-module residency constraints[J]. IEEE Transactions on Semiconductor Manufacturing (S0894-6507), 2002, 15(3): 341-349.
[10] Kim J H, Lee T E.Scheduling analysis of time-constrained dual-armed cluster tools[J]. IEEE Transactions on Semiconductor Manufacturing (S0894-6507), 2003, 16(3): 521-534.
[11] Jung C, Kim H J, Lee T E.A branch and bound algorithm for cyclic scheduling of timed petri nets[J]. IEEE Transactions on Automation Science & Engineering (S1545-5955), 2015, 12(1): 1-15.
[12] Qiao Y, Wu N Q, Zhou M C.Schedulability and scheduling analysis of dual-arm cluster tools with wafer revisiting and residency Time constraints based on a novel schedule[J]. IEEE Transactions on Systems Man & Cybernetics Systems (S1083-4427), 2015, 45(3): 472-484.
[13] Zhu Q H, Wu N Q, Qiao Y, et al.Scheduling of Single-Arm Multi-cluster Tools With Wafer Residency Time Constraints in Semiconductor Manufacturing[J]. IEEE Transactions on Semiconductor Manufacturing (S0894-6507), 2015, 28(1): 117-125.
[14] Lee J H, Kim H J, Lee T E.Scheduling cluster tools for concurrent processing of two wafer types[J]. IEEE Transactions on Automation Science and Engineering (S1545-5955), 2014, 11(2): 525-536.
[15] 刘明祥, 周炳海. 基于时间约束集的集束型设备群调度方法[J]. 自动化学报, 2012, 32(8): 479-484.
(Liu Mingxiang, Zhou Binghai.Scheduling algorithm of multi-cluster tools based on time constraint sets[J]. Acta Automatic Sinica, 2012, 32(8): 479-484.)
[16] 周炳海, 刘明祥, 周淑美. 带驻留约束的双臂集束型设备群的调度方法[J]. 哈尔滨工业大学学报, 2014, 46(1): 83-89.
(Zhou Binghai, Liu Mingxiang, Zhou Shumei.Scheduling method for dual-blade multi-cluster tools with residency constraints[J]. Journal of Harbin Institute of Technology, 2014, 46(1): 83-89.)
[17] 李林瑛, 胡静涛. 半导体制造两集束型装备调度模型和算法研究[J]. 系统仿真学报, 2010, 22(8): 1942-1946.
(Li Linying, Hu Jingtao.Scheduling model and its algorithm for two-cluster tools with single-blade robot[J]. Journal of System Simulation (S1004-731X), 2010, 22(8): 1942-1946.)
[18] 李林瑛, 胡静涛. 复杂单臂机器人集束型装备调度模型[J]. 信息与控制 [J]. 2009, 38(4): 431-436.
(Li Linying, Hu Jingtao.Scheduling model of complicated cluster tools with single-blade robot[J]. Information and Control, 2009, 38(4): 431-436.)
[19] 钱洁, 郑建国, 张超群, 等. 量子进化算法研究现状综述[J]. 控制与决策, 2011, 26(3): 321-327.
(Qian Jie, Zheng Jianguo, Zhang Chaoqun, et al.Reviews of current studying progress on quantum evolutionary computation[J]. Control and Decision, 2011, 26(3): 321-327.)
[20] 王跃岗, 车阿大. 基于混合量子进化算法的自动化制造单元调度[J]. 计算机集成制造系统, 2012, 19(9): 2193-2201.
(Wang Yuegang, Che Ada.Robotic cells scheduling based on hybrid quantum evolutionary algorithm[J]. Computer Integrated Manufacturing Systems, 2012, 19(9): 2193-2201.)
[21] 宋强磊, 车阿大. 量子进化算法在生产调度中的应用综述[J]. 计算机应用研究, 2012, 29(5): 1601-1605.
(Song Qianglei, Che Ada.Survey on application of quantum evolutionary algorithm in production scheduling[J]. Application Research of Computers, 2012, 29(5): 1601-1605.)
[22] Kumar S.Minimizing cycle time in large robotic cells[J]. IIE Transactions (S0740-817X), 2005, 37(2): 123-136.

有滞留时间约束的集束型装备在线调度方法

Online Scheduling Method of Cluster Tools with Residency Time Constraint

PDF (PC)

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价