应用离散事件系统控制理论求解生产调度的新方法

众所周知, 生产调度问题属组合优化问题, 一般来说不存在求得精确最优解的多项式算法. 因此, 对于大规 模调度问题, 人们应用启发式算法和元启发式算法以企求得满意解. 在实际的应用中, 许多工业过程需要满足严格 的工艺约束. 对于这类过程的调度问题, 很难应用启发式算法和元启发式算法, 因为这些方法难于保证所求得调度 的可行性. 为了解决这一问题, 本文以半导体芯片制造中组合设备的调度问题作为例子, 介绍了一种基于离散事件 系统控制理论的生产调度新方法. 利用Petri网建模, 任何违反约束的状态均被描述为非法状态, 而使非法状态出现 的调度则是不可行调度. 通过可行调度的存在性分析, 该方法获得可行解空间并将调度问题转化为连续优化问题, 从而可以有效求解. 并且指出, 该方法可以应用于其他应用领域.

A novel production scheduling methodology by using discrete event system control theories

It is well known that the production scheduling problem is essentially combinatorial, and generally there is no polynomial algorithm to find an exact optimal solution. Thus, for large-size scheduling problems people use heuristics and mate-heuristics to find a satisfactory solution. In practical applications, many industrial processes are subject to strict process constraints. For the scheduling problem of such processes, it is very difficult to apply heuristics and mate-heuristics, since they cannot ensure the solution feasibility. To overcome this challenge, with the scheduling problem of cluster tools in wafer fabrication as a case problem, this paper introduces a novel production scheduling methodology based on discrete event control theories. With a Petri net model, a state that violates any constraint is described as an illegal one and a schedule that reaches such a state is infeasible. It shows that, by analyzing the schedulability, the space of feasible solutions is obtained and the problem can be converted to a continuous optimization problem and can be efficiently solved. It also points out that it is applicable to other application problems.