Disjunctive Graph-based Modeling and Scheduling for Cluster Tools

Abstract

Abstract:

To solve the scheduling problem in single-arm cluster tools with chamber buffers and processing multiple part-type wafers, a branching search scheduling method was proposed based on the disjunctive graph model. First, a scheduling problem of cluster tools was transformed to a single machine scheduling problem. Next, a mathematical model of the problems was constructed based on disjunctive graphs. Then, a feasible solution space was obtained by using the branching method. After that, a branching searching algorithm was proposed for scheduling cluster tools with chamber buffers to obtain optimal robot action sequences to meet the system minimum makespan. Finally, experiments were designed to evaluate the proposed algorithm. The results indicate that the proposed algorithm is feasible and valid, and that the throughput of cluster tools with chamber buffers can be improved.

Key words: cluster tools, buffers, scheduling, disjunctive graph, branching search

CLC Number:

TP 391
F 27

GAO Zhongshun，ZHOU Binghai. Disjunctive Graph-based Modeling and Scheduling for Cluster Tools[J]. Journal of Shanghai Jiaotong University, 2013, 47(08): 1227-1233.

References

［1］Geismar N, Dawande M, Sriskandarajah C. Productivity improvement from using machine buffers in dualgripper cluster tools ［J］. IEEE Transactions on Automation Science and Engineering, 2011, 8(1): 2941.

［2］Rostami S, Hamidzadeh B. An optimal residencyaware scheduling technique for cluster tools with buffer module ［J］. IEEE Transactions on Semiconductor Manufacturing, 2004, 17(1): 6873.

［3］Perkinson T L, McLarty P K, Gyurcsik S R, et al. Singlewafer cluster tool performance: An analysis of throughput ［J］. IEEE Ttansactions on Semiconductor Manufacture, 1994, 7(3): 369373.

［4］Venkatesh S, Davenport R, Foxhoven P, et al. A steadystate throughput analysis of cluster tools: dualblade versus singleblade robots ［J］. IEEE Transactions on Semiconductor Manufacturing, 1997, 10(4): 418424.

［5］Herrmann J W, Chandrasekaran N, Conaghan B F, et al. Evaluating the impact of process changes on cluster tool performance ［J］. IEEE Transactions on Semiconductor Manufacturing, 2000, 13(2): 181192.

［6］Kim J H, Lee T E, Lee H Y, et al. Scheduling analysis of timeconstrained dualarmed cluster tools ［J］. IEEE Transactions on Semiconductor Manufacturing, 2003, 16(3): 512534.

［7］Rostami S, Hamidzadeh B. Optimal scheduling techniques for cluster tools with processmodule and transportmodule residency constraints ［J］. IEEE Transactions on Semiconductor Manufacturing, 2002, 15(3): 341349.

［8］Shadi R, Babak H, Dan C. An optimal periodic scheduler for dualarm robots in cluster tools with residency constraints ［J］. IEEE Transactions on Robotics and Automation, 2001, 17(5): 609618.

［9］李鑫, 周炳海, 陆志强. 基于事件驱动的集束型晶圆制造设备调度算法［J］. 上海交通大学学报,2009,43(6): 898901.

LI Xin, ZHOU Binghai, LU Zhiqiang. Scheduling algorithm for cluster tools of wafer fabrications based on eventsdriven ［J］. Journal of Shanghai Jiaotong University, 2009, 43(6): 898901.

［10］Lee T E. A review of scheduling theory and methods for semiconductor manufacturing cluster tools ［C］∥Proceedings of the 2008 Winter Simulation Conference. Austin, TX: IEEE, 2008: 21272135.

［11］Ding S, Yi J, Zhang M T. Multicluster tools scheduling: an integrated event graph and network model approach ［J］. IEEE Transactions on Semiconductor Manufacturing, 2006, 19(3): 339351.

［12］刘明祥, 周炳海. 基于时间约束集的集束型设备群调度方法［J］. 自动化学报, 2012, 38(3): 479485.

LIU Mingxiang, ZHOU Binghai. Scheduling algorithm of multicluster tools based on time constraint sets ［J］. Acta Automatica Sinica, 2012, 38(3): 479485.

［13］Carlier J, Haouari M, Kharbeche M, et al. An optimizationbased heuristic for the robotic cell problem ［J］. European Journal of Operation Research, 2010, 202: 636645.

［14］Drobouchevitch I G, Sethi S P, Sriskandarajah C. Scheduling dual gripper robotic cell: Oneunit cycles ［J］. European Journal of Operational Research, 2006, 171: 598631.

［15］Sriskandarajah C, Sethi S P, Drobouchevitch I G. Throughput optimization in robotic cells with input and output machine buffers: A comparative study of two key models ［J］. European Journal of Operational Research, 2010, 206: 623633.

[1]	LIU Yahui, SHEN Xingwang, GU Xinghai, PENG Tao, BAO Jinsong, ZHANG Dan. A Dual-System Reinforcement Learning Method for Flexible Job Shop Dynamic Scheduling [J]. Journal of Shanghai Jiao Tong University, 2022, 56(9): 1262-1275.
[2]	LI Dechang, YANG Hualong, DUAN Jingru. A Joint Optimization of Vessel Scheduling and Refueling Strategy for Container Liner Shipping with Cooperative Agreements [J]. Journal of Shanghai Jiao Tong University, 2022, 56(7): 953-964.
[3]	LI Linyan, HAN Shuang, QIAO Yanhui, LI Li, LIU Yongqian, YAN Jie, LIU Haidong. A Wind-Solar-Electric Vehicles Coordination Scheduling Method for High Proportion New Energy Grid-Connected Scenarios [J]. Journal of Shanghai Jiao Tong University, 2022, 56(5): 554-563.
[4]	TANG Hongtao, WANG Dannan, SHAO Yiping, ZHAO Wenbin, JIANG Weiguang, CHEN Qingfeng. A Modified Migrating Birds Optimization for Multi-Objective Lot Streaming Hybrid Flowshop Scheduling [J]. Journal of Shanghai Jiao Tong University, 2022, 56(2): 201-213.
[5]	WANG Zixiang, WU Zerui, LIU Ran. Weekly Physician Scheduling for Emergency Departments with Time-Varying Demands of Patients with Revisits [J]. Journal of Shanghai Jiao Tong University, 2022, 56(2): 242-252.
[6]	LU Qiuyu, YU Zhen, YANG Yinguo, LI Li. Two-Stage Optimal Schedule of Offshore Wind-Power-Integrated Multi-Microgrid Considering Uncertain Power of Sources and Loads [J]. Journal of Shanghai Jiao Tong University, 2022, 56(10): 1308-1316.
[7]	WANG Jinfeng, CHEN Lu, YANG Wenhui. A Single Machine Scheduling Problem Considering Machine Availability Constraints [J]. Journal of Shanghai Jiao Tong University, 2021, 55(1): 103-110.
[8]	JIANG Xiaokang, ZHANG Peng, LÜ Youlong, ZHAO Xinming, ZHANG Jie. Hybrid Ant Colony Algorithm for Batch Scheduling in Semiconductor Furnace Operation [J]. Journal of Shanghai Jiaotong University, 2020, 54(8): 792-804.
[9]	ZHU Hongwei, LU Zhiqiang. Modeling and Optimization of Resource Constrained Project Scheduling Problem Considering Employee-Timetabling [J]. Journal of Shanghai Jiaotong University, 2020, 54(6): 624-635.
[10]	MENG Lingtong, JIANG Zuhua, TAO Ningrong, LIU Jianfeng, ZHENG Hong. Multi-Stockyard Scheduling Considering Technological Process and Combined Assembly Block [J]. Journal of Shanghai Jiao Tong University, 2020, 54(4): 331-343.
[11]	MA Changpu，ZHOU Binghai. Scheduling of Multi-Load Rail Guided Vehicles in AS/RS with Collision Avoidance Constrains [J]. Journal of Shanghai Jiaotong University, 2020, 54(2): 126-134.
[12]	FANG Jia, LU Zhiqiang. Modeling and Optimization of Robust Scheduling Template Considering Equipment Failure [J]. Journal of Shanghai Jiao Tong University, 2020, 54(12): 1278-1290.
[13]	ZHAO Rui, GU Xingsheng. A Discrete Sine Optimization Algorithm for No-Idle Flow-Shop Scheduling Problem [J]. Journal of Shanghai Jiao Tong University, 2020, 54(12): 1291-1299.
[14]	CUI Weiwei (崔维伟). Approximate Approach to Deal with the Uncertainty in Integrated Production Scheduling and Maintenance Planning [J]. Journal of Shanghai Jiao Tong University (Science), 2020, 25(1): 106-117.
[15]	MENG Lingtong,JIANG Zuhua,TAO Ningrong,LIU Jianfeng,LI Baihe. Combined Assembly Block Scheduling in Storage Yard of Shipbuilding [J]. Journal of Shanghai Jiaotong University, 2019, 53(7): 780-788.