Sequence Planning for Labeled Petri Nets With Time and Resource Constraints Using Basis Markings
This paper addresses the scheduling problem for discrete event systems modeled by labeled Petri nets with time and resource constraints where deadlocks are inevitable. For better resource utilization and shorter processing time, a heuristic algorithm is presented for designing a suitable transition...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2023-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10272588/ |
| _version_ | 1797660839084294144 |
|---|---|
| author | Yejia Liu Xunbo Li Ahmed M. El-Sherbeeny |
| author_facet | Yejia Liu Xunbo Li Ahmed M. El-Sherbeeny |
| author_sort | Yejia Liu |
| collection | DOAJ |
| description | This paper addresses the scheduling problem for discrete event systems modeled by labeled Petri nets with time and resource constraints where deadlocks are inevitable. For better resource utilization and shorter processing time, a heuristic algorithm is presented for designing a suitable transition sequence that starts from the initial marking to a set of target markings using basis markings. Specially, two reasons exist for deadlocks in the given system. One is resource exhaustion and the other is unreasonable resource allocation. We only focus on the former. First, the set of target markings, i.e., deadlocks caused by resource exhaustion, is identified using the notion of basis markings and resource-exhausted markings. The basis reachability graph instead of the conventional reachability graph is constructed to avoid state space explosion. An integer linear programming problem based on the notion of deadlocks is carried out to distinguish basis markings, where deadlocks can be reached by firing unobservable transitions only. Then, the A-star algorithm is applied to the basis marking space to schedule the transition firing sequences and the optimal results may be obtained. Unpromising searching areas are reduced and only a part of the markings is probed. Finally, a numerical case is studied to verify the effectiveness of the proposed algorithm. The main advantages of the proposed approach include that the exhaustive enumeration of the reachability space can be avoided and the calculation can be completed off-line. |
| first_indexed | 2024-03-11T18:35:39Z |
| format | Article |
| id | doaj.art-359a5cdfd626466e9a8a88ad9701b354 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-03-11T18:35:39Z |
| publishDate | 2023-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-359a5cdfd626466e9a8a88ad9701b3542023-10-12T23:00:33ZengIEEEIEEE Access2169-35362023-01-011110950010951210.1109/ACCESS.2023.332214110272588Sequence Planning for Labeled Petri Nets With Time and Resource Constraints Using Basis MarkingsYejia Liu0https://orcid.org/0009-0007-5494-5092Xunbo Li1https://orcid.org/0009-0002-3727-4630Ahmed M. El-Sherbeeny2https://orcid.org/0000-0003-3559-6249School of Mechanical and Electrical Engineering, University of Electronic Science and Technology of China, Chengdu, ChinaSchool of Mechanical and Electrical Engineering, University of Electronic Science and Technology of China, Chengdu, ChinaIndustrial Engineering Department, College of Engineering, King Saud University, Riyadh, Saudi ArabiaThis paper addresses the scheduling problem for discrete event systems modeled by labeled Petri nets with time and resource constraints where deadlocks are inevitable. For better resource utilization and shorter processing time, a heuristic algorithm is presented for designing a suitable transition sequence that starts from the initial marking to a set of target markings using basis markings. Specially, two reasons exist for deadlocks in the given system. One is resource exhaustion and the other is unreasonable resource allocation. We only focus on the former. First, the set of target markings, i.e., deadlocks caused by resource exhaustion, is identified using the notion of basis markings and resource-exhausted markings. The basis reachability graph instead of the conventional reachability graph is constructed to avoid state space explosion. An integer linear programming problem based on the notion of deadlocks is carried out to distinguish basis markings, where deadlocks can be reached by firing unobservable transitions only. Then, the A-star algorithm is applied to the basis marking space to schedule the transition firing sequences and the optimal results may be obtained. Unpromising searching areas are reduced and only a part of the markings is probed. Finally, a numerical case is studied to verify the effectiveness of the proposed algorithm. The main advantages of the proposed approach include that the exhaustive enumeration of the reachability space can be avoided and the calculation can be completed off-line.https://ieeexplore.ieee.org/document/10272588/Basis markingdiscrete event systemlabeled Petri netresource consumptionsequence planning |
| spellingShingle | Yejia Liu Xunbo Li Ahmed M. El-Sherbeeny Sequence Planning for Labeled Petri Nets With Time and Resource Constraints Using Basis Markings IEEE Access Basis marking discrete event system labeled Petri net resource consumption sequence planning |
| title | Sequence Planning for Labeled Petri Nets With Time and Resource Constraints Using Basis Markings |
| title_full | Sequence Planning for Labeled Petri Nets With Time and Resource Constraints Using Basis Markings |
| title_fullStr | Sequence Planning for Labeled Petri Nets With Time and Resource Constraints Using Basis Markings |
| title_full_unstemmed | Sequence Planning for Labeled Petri Nets With Time and Resource Constraints Using Basis Markings |
| title_short | Sequence Planning for Labeled Petri Nets With Time and Resource Constraints Using Basis Markings |
| title_sort | sequence planning for labeled petri nets with time and resource constraints using basis markings |
| topic | Basis marking discrete event system labeled Petri net resource consumption sequence planning |
| url | https://ieeexplore.ieee.org/document/10272588/ |
| work_keys_str_mv | AT yejialiu sequenceplanningforlabeledpetrinetswithtimeandresourceconstraintsusingbasismarkings AT xunboli sequenceplanningforlabeledpetrinetswithtimeandresourceconstraintsusingbasismarkings AT ahmedmelsherbeeny sequenceplanningforlabeledpetrinetswithtimeandresourceconstraintsusingbasismarkings |