This paper addresses the deadlock (DL)-free scheduling problem of flexible manufacturing systems (FMS) characterized by resource sharing, limited buffer capacity, routing flexibility, and the availability of material handling systems. The FMS scheduling problem is formulated using timed colored Petri net (TCPN) modeling where each operation has a certain number of preconditions, an estimated duration, and a set of postconditions. Based on the reachability analysis of TCPN modeling, we propose a new anytime heuristic search algorithm which finds optimal or near-optimal DL-free schedules with respect to makespan as the performance criterion. The methodology tackles the time-constrained problem of very demanding systems (high diversity production and make-to-order) in which computational time is a critical factor to produce optimal schedules that are DL-free. In such a rapidly changing environment and under tight customer due-dates, producing optimal schedules becomes intractable given the time limitations and the NP-hard nature of scheduling problems. The proposed anytime search algorithm combines breadth-first iterative deepening A* with suboptimal breadth-first heuristic search and backtracking. It guarantees that the search produces the best solution obtained so far within the allotted computation time and provides better solutions when given more time. The effectiveness of the approach is evaluated on a comprehensive benchmark set of DL-prone FMS examples and the computational results show the superiority of the proposed approach over the previous works.

The traffic alert and collision avoidance system (TCAS) currently mandated worldwide on all commercial transport aircraft is intended to provide last-minute collision avoidance (CA) guidance directly to the flight crew and has been shown to significantly reduce the risk of near-midair collisions. The TCAS logic uses a deterministic model to predict the future trajectories of the aircraft and does not explicitly represent variability in pilot response time which can have a great impact on the execution of the CA logic. Prior work has designed an encounter model to identify all the induced potential collision scenarios that are representative of possible hazardous situations that may occur with a fixed configuration of aircraft in the surrounding airspace. This paper extends the encounter model using an agent-based modeling approach developed via the colored Petri net (CPN) formalism to include the agent pilot response time that captures the variability delay in pilot behavior in order to analyze its influence on TCAS-induced collisions. Quantitative simulation results are conducted to validate the proposed causal model, dealing with challenging results about the extra airside capacity that could be obtained by offering a specific training on TCAS to the pilots or by use of automatisms, which is the case of remotely piloted aircraft systems.

The combination of Petri net (PN) modeling with AI-based heuristic search (HS) algorithms (PNHS) has been successfully applied as an integrated approach to deal with scheduling problems that can be transformed into a search problem in the reachability graph. While several efficient HS algorithms have been proposed albeit using timed PN, the practical application of these algorithms requires an appropriate tool to facilitate its development and analysis. However, there is a lack of tool support for the optimization of timed colored PN (TCPN) models based on the PNHS approach for schedule generation. Because of its complex data structure, TCPN-based scheduling has often been limited to simulation-based performance analysis only. Also, it is quite difficult to evaluate the strength and tractability of algorithms for different scheduling scenarios due to the different computing platforms, programming languages and data structures employed. In this light, this paper presents a new tool called TIMSPAT developed to overcome the shortcomings of existing tools. Some features that distinguish this tool are the collection of different HS algorithms, the event-driven exploration of the timed state space including its condensed variant, localized enabling of transitions, the introduction of a static place, and its easy-to-use syntax statements. The tool is easily extensible and can be integrated as a component into existing PN simulators and software environments. A comparative study is performed on a real-world eyeglass production system to demonstrate the usage of the tool for scheduling purposes.