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

摘要/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]. 上海交通大学学报, 2026, 60(2): 224-234.
[2]	刘东林, 周霞, 戴剑丰, 解相朋, 汤奕, 李隽诗. 考虑虚拟储能的建筑综合能源系统双层优化调度策略[J]. 上海交通大学学报, 2026, 60(1): 61-73.
[3]	杨银国, 冯胤颖, 魏韡, 谢平平, 陈玥. 基于可消纳区间的风-火-储大基地日前-实时协同调度[J]. 上海交通大学学报, 2025, 59(9): 1270-1280.
[4]	彭楚轩, 边晓燕, 金海翔, 林顺富, 徐波, 赵健. 基于多能灵活性约束的含富氧燃烧机组综合能源系统两阶段优化调度[J]. 上海交通大学学报, 2025, 59(9): 1281-1291.
[5]	. 考虑时间窗和灵活返回基地的拖船调度研究[J]. J Shanghai Jiaotong Univ Sci, 2025, 30(6): 1276-1288.
[6]	张理, 王宝, 贾健雄, 宋竹萌, 叶钰童, 余跃, 林嘉庆, 徐潇源. 微电网功率预测与调度端到端协同优化方法[J]. 上海交通大学学报, 2025, 59(6): 720-731.
[7]	陈实, 杨林森, 刘艺洪, 罗欢, 臧天磊, 周步祥. 小样本数据驱动模式下的新建微电网优化调度策略[J]. 上海交通大学学报, 2025, 59(6): 732-745.
[8]	张澳圆, 胡小锋, 张亚辉. 多场景多目标动态变化下船舶小组立装焊重调度[J]. 上海交通大学学报, 2025, 59(4): 476-488.
[9]	秦立成, 梁学先, 房煦凯, 等. 浮托安装系统分析技术现状及未来[J]. 海洋工程装备与技术, 2025, 12(4): 83-95.
[10]	吴静, 刘轩宇, 李响, 齐笑言, 李成俊, 张忠. 碳市场价格不确定性对电网调度影响机理分析[J]. 上海交通大学学报, 2025, 59(3): 354-364.
[11]	赵莹莹, 仇越, 朱天晨, 李凡, 苏运, 邰振赢, 孙庆赟, 凡航. 基于分层强化学习的新型电力系统在线稳态调度[J]. 上海交通大学学报, 2025, 59(3): 400-412.
[12]	娄为, 胡蓉, 于谨铭, 张希鹏, 樊飞龙, 刘嵩源. 内嵌市场博弈模型的电网-抽水蓄能多主体协调调度[J]. 上海交通大学学报, 2025, 59(3): 365-375.
[13]	邱子彰, 汪达旺, 陆志沣, 伍国华. 基于禁忌搜索的照射器资源调度方法[J]. 空天防御, 2025, 8(3): 132-140.
[14]	陈子杰, 宋柄兵, 李语桐, 王利峰, 滕晓毕, 严正, 陈思捷. 面向现货市场的省间联络线功率考核机制与模型[J]. 上海交通大学学报, 2025, 59(12): 1773-1783.
[15]	张嘉敏, 蔡晔, 唐夏菲, 谭玉东, 曹一家, 李俊雄. 考虑源荷不确定性的信息间隙决策理论-谱聚类典型场景生成方法[J]. 上海交通大学学报, 2025, 59(11): 1625-1636.