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. © 2021, Editorial Department of Control Theory & Applications South China University of Technology. All right reserved.