Abstract: To solve the conflict and deadlock problems of transportation equipment in united layout of 300mm semiconductor fabrication, an event-driven dispatching scheduling algorithm was proposed. A mathematical model was set up with optimization objective of minimizing total completion time by considering the interrelationship of each Overhead Hoist Transport (OHT) in handling system. Combined K-shortest routing algorithm with time constraint sets, the conflicted time intervals were detected. A conflict free path was planned successively by using back tracking scheduling algorithm, thus the shortest path was determined to dispatch OHT. The simulation experiments were designed to evaluate the proposed algorithm, and the results indicated that the algorithm could avoid deadlocks effectively and improve the efficiency of the system.

Key words: overhead hoist transport, material handling systems, dispatching, routing scheduling, back tracking search

摘要： 为有效解决300mm晶圆工厂整合式布局环境下搬运设备所出现的碰撞、拥堵、死锁等问题，提出一种基于事件驱动的派工调度算法。充分考虑搬运系统中各搬运设备之间的相互影响，以搬运完工时间最小为优化目标建立数学模型；将第K短路径算法和时间约束集概念相结合，侦测冲突时间区间，采用回溯搜索的方法依次进行无冲突路径的规划，从而确定最短路径进行高架提升传输小车派工。通过对算法进行仿真分析表明，该算法能有效避免死锁和碰撞，提高系统的效率。

关键词: 高架提升传输小车, 物料搬运系统, 派工, 路径调度, 回溯搜索