Online Scheduling Method of Cluster Tools with Residency Time Constraint

doi:10.16182/j.issn1004731x.joss.201702014

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

CLC Number:

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.

References

[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.