A. Tarek (USA)
Dynamic Programming, Linear Programming, Opti mal Operational Sequence.
Petri nets (PNs) are a graphical and mathemati cal modelling tool for the formal analysis of discrete event dynamic systems. Reachability is fundamen tal to the analysis of PN models, since many prob lems in PNs can be reduced to the PN reachability problem. Currently, there are not enough computa tional tools, and techniques that employ linear alge braic approaches for analyzing manufacturing systems. A reachability tree method for analyzing PN models has already been discussed in [6]. But the method dis cussed in [6] uses an exponential complexity algorithm, and encounters state-space explosion for larger prob lems. Therefore, this method is not suitable for veri fying the properties of the PN-based models of manu facturing systems. To improve computation time, and to avoid the state-space explosion problem associated with some of the previously proposed methods, this paper introduces an improved Dynamic Programming (DP)-based Linear Programming (LP) method. The method in this paper combines a forward-recursive dy namic programming with LP (FDP+LP method with FDP standing for forward-recursive dynamic program ming) for computing an optimal operational sequence (OOS) of machines. The method uses f LP steps, and also alleviates the combinatorial explosion problem of a pure DP-based approach. Particularly, the method is useful in analyzing Flexible Manufacturing Systems (FMSs).
Important Links:
Go Back
