Heuristic search based on Petri net structures for FMS scheduling

A heuristic search method using Petri net structures for flexible manufacturing system (FMS) scheduling is presented. To minimize makespan, an FMS scheduling problem is formulated as finding a firing sequence from the initial state to the final state of a timed Petri net model, such that the sequenc...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on industry applications 1999-01, Vol.35 (1), p.196-202
Main Authors: Jeng, Mu Der, Chen, Shih Chang
Format: Article
Language:English
Subjects:
Automation
Concurrent computing
Costs
Equations
Firing
Flexible manufacturing systems
Heuristic
Industrial control
Job shop scheduling
Marketing
Mathematical analysis
Mathematical models
Optimal scheduling
Petri nets
Scheduling
Searching
State-space methods
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A heuristic search method using Petri net structures for flexible manufacturing system (FMS) scheduling is presented. To minimize makespan, an FMS scheduling problem is formulated as finding a firing sequence from the initial state to the final state of a timed Petri net model, such that the sequence reveals the minimal cost. The reachability graph is partially generated and searched. The search process is guided by a heuristic function based on firing count vectors of the state equation, predicting the total cost. Since this heuristic search exploits the linear characteristics of the state equation, which contains sufficient global information, it can efficiently generate a near-optimal or optimal solution. To deal with large systems, the proposed algorithm exploits the concurrency information to reduce the searched state space.
ISSN:0093-9994
1939-9367
DOI:10.1109/28.740865