FMS Scheduling Based on Timed Petri Net Model
Youngwoo Kim, Akio Inaba, Tatsuya Suzuki, Shigeru Okuma · 2001
Scheduling of manufacturing process is one of the significant problems in FMSs. Requirements for the FMSs' scheduling are as follows : (1) It is easy to formulate a problem. (2) Semi-optimal solution can be found within short time. However, no scheduling method which meets these requirements, has been proposed yet. This paper presents a new scheduling method for manufacturing system based on a Petri net model and a reactive fast serach algorithm. The following two typical problems are addressed an this paper. (1) Minimize the maximum completion time. (2) Minimize the .total deadline over-time. As for problem (l), a search algorithm which combines RTA* and rule-based supervisor is proposed. Since both RTA* and rule-based supervisor can be executed in a reactive manner, machines and AG Vs allocations can be scheduled reactively, and simultaneously. As for problem (2), original petri net model is converted to its reverse model and the algorithm developed an problem (1) is applied with regarding the due time as a starting time in the reverse.mode1. And then some minor refinements is considered to get feaseble solution. The usefulness of the proposed algorithm is also shown through some numerical experiments.