基于析取图的集束型设备建模与调度方法

摘要/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

中图分类号:

TP 391
F 27

高忠顺，周炳海. 基于析取图的集束型设备建模与调度方法[J]. 上海交通大学学报（自然版）, 2013, 47(08): 1227-1233.

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.

参考文献

［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]	刘亚辉, 申兴旺, 顾星海, 彭涛, 鲍劲松, 张丹. 面向柔性作业车间动态调度的双系统强化学习方法[J]. 上海交通大学学报, 2022, 56(9): 1262-1275.
[2]	李林晏, 韩爽, 乔延辉, 李莉, 刘永前, 阎洁, 刘海东. 面向高比例新能源并网场景的风光-电动车协同调度方法[J]. 上海交通大学学报, 2022, 56(5): 554-563.
[3]	汤洪涛, 王丹南, 邵益平, 赵文彬, 江伟光, 陈青丰. 基于改进候鸟迁徙优化的多目标批量流混合流水车间调度[J]. 上海交通大学学报, 2022, 56(2): 201-213.
[4]	陆秋瑜, 于珍, 杨银国, 李力. 考虑源荷功率不确定性的海上风力发电多微网两阶段优化调度[J]. 上海交通大学学报, 2022, 56(10): 1308-1316.
[5]	王兴志, 翟海保, 严亚勤, 吴庆曦. 基于数字孪生和深度学习的新一代调控系统预调度方法[J]. 上海交通大学学报, 2021, 55(S2): 37-41.
[6]	许凌, 王兴志, 肖林朋. 基于语义特征抓取电网调度事件的检测技术[J]. 上海交通大学学报, 2021, 55(S2): 86-91.
[7]	范厚明, 于佳琪, 马梦知, 蒋晓丹, 慈吉利, 翟志伟. 模糊时间窗下多船型不定期船调度与航速联合优化[J]. 上海交通大学学报, 2021, 55(3): 297-310.
[8]	吕祥梅, 刘天琪, 刘绚, 何川, 南璐, 曾红. 考虑高比例新能源消纳的多能源园区日前低碳经济调度[J]. 上海交通大学学报, 2021, 55(12): 1586-1597.
[9]	王金凤, 陈璐, 杨雯慧. 考虑设备可用性约束的单机调度问题[J]. 上海交通大学学报, 2021, 55(1): 103-110.
[10]	蒋小康, 张朋, 吕佑龙, 赵新明, 张洁. 基于混合蚁群算法的半导体生产线炉管区调度方法[J]. 上海交通大学学报, 2020, 54(8): 792-804.
[11]	李柏鹤, 蒋祖华, 陶宁蓉, 孟令通, 郑虹. 考虑平板车合作运输的船舶分段堆场间调度[J]. 上海交通大学学报, 2020, 54(7): 718-727.
[12]	朱宏伟, 陆志强. 考虑人力资源排班的资源受限项目调度问题建模与优化[J]. 上海交通大学学报, 2020, 54(6): 624-635.
[13]	孟令通, 蒋祖华, 陶宁蓉, 刘建峰, 郑虹. 考虑工艺顺序和组合分段的多堆场调度方法[J]. 上海交通大学学报, 2020, 54(4): 331-343.
[14]	周建, 甘淇匀, 钱未, 曹云. 阴极区添加腐植酸缓冲液对电渗排水效果影响的试验研究[J]. 上海交通大学学报, 2020, 54(3): 239-246.
[15]	许显杨，陈璐. 考虑设备可靠性与能耗的平行机调度[J]. 上海交通大学学报, 2020, 54(3): 247-255.