Name
Title | ||
|---|---|---|
Hybrid heuristic search approach for deadlock-free scheduling of flexible manufacturing systems using Petri nets. |
Abstract | ||
|---|---|---|
Display OmittedBased on the Petri net models of flexible manufacturing systems, this paper focuses on deadlock-free scheduling problem with the objective of minimizing the makespan. To avoid deadlocks, the deadlock control policy is embedded into heuristic search strategies, and two hybrid heuristic search algorithms for deadlock-free scheduling of FMSs are proposed. Deadlock control and scheduling for flexible manufacturing system is integrated.Deadlock control policy is embedded into the heuristic search algorithm.Two hybrid deadlock-free scheduling algorithms for flexible manufacturing system are proposed. Based on the Petri net models of flexible manufacturing systems (FMSs), this paper focuses on deadlock-free scheduling problem with the objective of minimizing the makespan. Two hybrid heuristic search algorithms for solving such scheduling problems of FMSs are proposed. To avoid deadlocks, the deadlock control policy is embedded into heuristic search strategies. The proposed algorithms combine the heuristic best-first strategy with the controlled backtracking strategy based on the execution of the Petri nets. The scheduling problem is transformed into a heuristic search problem in the reachability graph of the Petri net, and a schedule is a transition sequence from the initial marking to the final marking in the reachability graph. By using the one-step look-ahead method in the deadlock control policy, the safety of a state in the reachability graph is checked, and hence, deadlock is avoided. Experimental results are provided and indicate the effectiveness of the proposed hybrid heuristic search algorithms in solving deadlock-free scheduling problems of FMSs. Especially, the comparison against previous work shows that both new algorithms are promising in terms of solution quality and computing times. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.asoc.2017.01.045 | Appl. Soft Comput. |
Keywords | Field | DocType |
Flexible manufacturing systems,Scheduling,Petri net,Deadlock control policy,Hybrid heuristic search | Heuristic,Incremental heuristic search,Mathematical optimization,Petri net,Job shop scheduling,Fair-share scheduling,Computer science,Deadlock,Flexible manufacturing system,Rate-monotonic scheduling,Distributed computing | Journal |
Volume | Issue | ISSN |
55 | C | 1568-4946 |
Citations | PageRank | References |
2 | 0.36 | 19 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hang Lei | 1 | 6 | 2.50 |
| Keyi Xing | 2 | 522 | 34.59 |
| LiBin Han | 3 | 126 | 5.63 |
| Zhenxin Gao | 4 | 6 | 1.10 |