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]	YANG Yinguo, FENG Yinying, WEI Wei, XIE Pingping, CHEN Yue. Coordinated Day-Ahead Scheduling and Real-Time Dispatch of a Wind-Thermal-Storage Energy Base Considering Flexibility Interval [J]. Journal of Shanghai Jiao Tong University, 2025, 59(9): 1270-1280.
[2]	ZHONG Ming, WU Ying, WU Chunli, WANG Fang. Tugboat Scheduling Problem Considering Time Windows and Flexible Returning Way to Base [J]. J Shanghai Jiaotong Univ Sci, 2025, 30(6): 1276-1288.
[3]	CHEN Shi, YANG Linsen, LIU Yihong, LUO Huan, ZANG Tianlei, ZHOU Buxiang. Optimal Scheduling Strategy of Newly-Built Microgrid in Small Sample Data-Driven Mode [J]. Journal of Shanghai Jiao Tong University, 2025, 59(6): 732-745.
[4]	ZHANG Li, WANG Bao, JIA Jianxiong, SONG Zhumeng, YE Yutong, YU Yue, LIN Jiaqing, XU Xiaoyuan. End-to-End Collaborative Optimization Method for Microgrid Power Prediction and Optimal Scheduling [J]. Journal of Shanghai Jiao Tong University, 2025, 59(6): 720-731.
[5]	QIU Zizhang, WANG Dawang, LU Zhifeng, WU Guohua. An Illuminator Resource Scheduling Methods Based on Tabu Search [J]. Air & Space Defense, 2025, 8(3): 132-140.
[6]	ZHAO Yingying, QIU Yue, ZHU Tianchen, LI Fan, SU Yun, TAI Zhenying, SUN Qingyun, FAN Hang. Online Steady-State Scheduling of New Power Systems Based on Hierarchical Reinforcement Learning [J]. Journal of Shanghai Jiao Tong University, 2025, 59(3): 400-412.
[7]	HU Kaiqiang, CAI Zexiang, CAI Yu, QU Jing, LIU Yuanyuan. Micro-Service Scheduling Model and Optimization for Protection and Control of Distribution Network Considering Virtualization Delay [J]. Journal of Shanghai Jiao Tong University, 2025, 59(11): 1684-1693.
[8]	ZHANG Jianhua, YAO Yi, ZHAO Si, WANG Yongyue. A Coordinated Control Scheme for Fast Frequency Regulation of Thermal Power Units Based on Flexibility Transformation [J]. Journal of Shanghai Jiao Tong University, 2025, 59(11): 1694-1706.
[9]	WANG Xuan, WANG Bao, CHEN Yanping, LIU Hong, MA Xiaohui. Joint Economic Optimization of AGV Logistics Scheduling and Orderly Charging in a Low-Carbon Automated Terminal [J]. Journal of Shanghai Jiao Tong University, 2024, 58(9): 1370-1380.
[10]	ZHOU Siyi, YANG Huanhong, HUANG Wentao, ZHOU Ze, JIAO Wei, YANG Zhenyu. Two-Stage Day-Ahead and Intra-Day Rolling Optimization Scheduling of Container Integrated Port Energy System [J]. Journal of Shanghai Jiao Tong University, 2024, 58(9): 1357-1369.
[11]	JIANG Zuhua^1∗(蒋祖华), ZHOU Hongming²(周宏明), TAO Ningrong³(陶宁蓉), LI Baihe¹(李柏鹤). Knowledge-Based Curved Block Construction Scheduling and Application in Shipbuilding [J]. J Shanghai Jiaotong Univ Sci, 2024, 29(5): 759-765.
[12]	CHEN Yini(陈旖旎), JIANG Zuhua^* (蒋祖华). Multi-AGVs Scheduling with Vehicle Conflict Consideration in Ship Outfitting Items Warehouse [J]. J Shanghai Jiaotong Univ Sci, 2024, 29(3): 492-508.
[13]	GU Huijie, ZHOU Huafeng, PENG Chaoyi, HU Yaping, ZHAO Xinyi, XIE Jun, SHI Xionghua. A Multi-Time Scale Scheduling Model for Power Generation Systems with a High Proportion of New Energy Including Pumped Storage Power Stations [J]. Journal of Shanghai Jiao Tong University, 2024, 58(12): 1957-1967.
[14]	YE Zhiliang, LI Canbing, ZHANG Yongjun, LI Licheng, XIAO Yinjing, WU Yuhang, TAI Nengling. Optimization of Day-Ahead Dispatch Time Resolution in Power System with a High Proportion of Climate-Sensitive Renewable Energy Sources [J]. Journal of Shanghai Jiao Tong University, 2023, 57(7): 781-790.
[15]	LI Junshuang, HU Yan, TAI Nengling. Collaborative Optimization Scheduling of 5G Base Station Energy Storage and Distribution Network Considering Communication Load and Power Supply Reliability [J]. Journal of Shanghai Jiao Tong University, 2023, 57(7): 791-802.