A HEURISTIC-SEARCH APPROACH USING APPROXIMATE SOLUTIONS TO PETRI-NET STATE-EQUATIONS FOR SCHEDULING FLEXIBLE MANUFACTURING SYSTEMS

This paper proposes a new heuristic search approach based on an analyt ic theory of the Petri net state equations for scheduling flexible man ufacturing systems (FMSs) with the goal of minimizing makespan. The pr oposed method models an FMS using a timed Petri net and exploits appro ximate solutions of the net's state equation to predict the total cost (makespan) from the initial state through the current state to the go al. That is, the heuristic function considers global information provi ded by the state equation. This makes the method possible to obtain so lutions better than those obtained using prior works nee and DiCesare, 1994a, 1994b) that consider only the current status or limited global information. In addition, to reduce memory requirement and thus to in crease the efficiency of handling larger systems, the proposed schedul ing algorithm contains a procedure to reduce the searched state space.