引用本文:伍乃骐,乔岩.应用离散事件系统控制理论求解生产调度的新方法[J].控制理论与应用,2021,38(11):1809~1818.[点击复制]
WU Nai-qi,QIAO Yan.A novel production scheduling methodology by using discrete event system control theories[J].Control Theory and Technology,2021,38(11):1809~1818.[点击复制]
应用离散事件系统控制理论求解生产调度的新方法
A novel production scheduling methodology by using discrete event system control theories
摘要点击 1813  全文点击 589  投稿时间：2021-08-15  修订日期：2021-11-22
查看全文  查看/发表评论  下载PDF阅读器
DOI编号  10.7641/CTA.2021.10748
  2021,38(11):1809-1818
中文关键词  生产调度  离散事件系统  Petri网
英文关键词  production scheduling  discrete event systems  Petri nets
基金项目  国家自然科学基金项目(61803397), 澳门科技发展基金项目(0017/2019/A1)资助.
作者单位E-mail
伍乃骐* 澳门科技大学 nqwu@must.edu.mo 
乔岩 澳门科技大学  
中文摘要
      众所周知, 生产调度问题属组合优化问题, 一般来说不存在求得精确最优解的多项式算法. 因此, 对于大规 模调度问题, 人们应用启发式算法和元启发式算法以企求得满意解. 在实际的应用中, 许多工业过程需要满足严格 的工艺约束. 对于这类过程的调度问题, 很难应用启发式算法和元启发式算法, 因为这些方法难于保证所求得调度 的可行性. 为了解决这一问题, 本文以半导体芯片制造中组合设备的调度问题作为例子, 介绍了一种基于离散事件 系统控制理论的生产调度新方法. 利用Petri网建模, 任何违反约束的状态均被描述为非法状态, 而使非法状态出现 的调度则是不可行调度. 通过可行调度的存在性分析, 该方法获得可行解空间并将调度问题转化为连续优化问题, 从而可以有效求解. 并且指出, 该方法可以应用于其他应用领域.
英文摘要
      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.