The highly concurrent time discrete event systems modeled by Time Petri Net (TPN) suffer from the problem of the state space explosion owing to a large number of accessible markings. To handle this problem, this paper proposes a new solution based on modelling in discrete time the reachable markings of TPN using a new structure so-called Time Reduced Ordered Binary Decision Diagrams (TROBDDs). In this work a new efficient methodology is presented to generate and store a big state space to deal with the time execution and memory space constraints. This new approach is used to resolve the Flight Rescheduling Problem (FRP) subject to capacity constraints due to adverse weather conditions. An optimization algorithm is proposed to minimize the cost function and determine the optimal flight plan according to the new capacity constraints. A number of instances on the FRP is presented in order to illustrate such approach, which allows us to save the memory space and CPU requirements.
Discrete event system, Time Petri Net, binary decision diagram, rescheduling problem.
Mohamed Ali KAMMOUN, Nidhal REZG, Zied ACHOUR, Sadok REZIG, "State Space Search for Safe Time Petri Nets Based on Binary Decision Diagrams Tools: Application to Air Traffic Flow Management Problem", Studies in Informatics and Control, ISSN 1220-1766, vol. 25(1), pp. 39-50, 2016. https://doi.org/10.24846/v25i1y201605
All articles published by Studies in Informatics and Control (SIC) are published in accordance with the terms and conditions of the Creative Commons Attribution License (CC BY-NC-SA 4.0).