Search

We present a reachability graph-based search optimization tool for scheduling.Motivated by the lack of tool support for optimization of TCPNs.Implements an event-driven timed state space with AI heuristic search algorithms.Aimed at supporting flexible decision making process with algorithm portfolio.Comparative study of nine search algorithms on real system demonstrates tool efficiency. 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 several HS algorithms, XML-based model integration, the event-driven exploration of the timed state space including its condensed variant, localized enabling of transitions, the introduction of static place, and the 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 application of the tool for scheduling purposes.

To achieve a significant improvement in the overall performance of a flexible manufacturing system, the scheduling process must consider the interdependencies that exist between the machining and transport systems. However, most works have addressed the scheduling problem as two independent decision making problems, assuming sufficient capacity in the transport system. In this paper, we study the simultaneous scheduling (SS) problem of machines and automated guided vehicles using a timed coloured Petri net (TCPN) approach under two performance objectives; makespan and exit time of the last job. The modelling approach allows the evaluation of all the feasible vehicle assignments as opposed to the traditional dispatching rules and demonstrates the benefits of vehicle-controlled assignments over machine-controlled for certain production scenarios. In contrast with the hierarchical decomposition technique of existing approaches, TCPN is capable of describing the dynamics and evaluating the performance of the ...

The multiple lot size scheduling problem plays a crucial role in minimizing production and setup costs in order to respond to constant fluctuations in customer demands. However, the computational cost to optimize a scheduling problem increases as the lot size of jobs increases, leading to a scalability problem for most scheduling algorithms. This paper presents an efficient search approach based on colored Petri net (CPN) formalism that addresses the state explosion problem of reachability graphs used for finding the optimal solutions to scheduling problems. To reduce the memory requirements, the proposed approach exploits the structural equivalence found in the reachability graphs of flexible manufacturing systems’ (FMS) CPNs to discard states once they are no longer needed to explore the state space. The hypothetical structural equivalence is attributed to the repetitive patterns identified in the execution of manufacturing processes when the lot sizes of jobs are scaled for FMS whose underlying layout configuration is fixed. We present the concept of structural equivalence based on duplicate state detection for FMS of different lot sizes and give sufficient conditions under which the structural equivalence obtained from a few lot size (smaller) instances holds for the same FMS of a larger size. The approach is validated experimentally on different FMS examples which confirm that the behavior of an FMS of any large lot size can be inferred from the FMS of a smaller size. Experimental results indicate that this work performs better than prior search methods and obtains optimal schedules of FMS with large lot sizes. Also, we show that the approach is applicable to FMS problems of similar configurations where the problem size differ by the number of jobs, resources and operations.

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.

Given the fluctuations in demand, diversity in products, production flexibility requirements, and tight customer due dates, obtaining optimal production schedules is considered a complex research problem. This can drastically affect the survival of some manufacturing companies in today’s fiercely competitive global market. In a very demanding decision-making environment, scheduling problems are dealt with in a short-term horizon, in which computation time is a critical factor. Producing optimal solutions is practically impossible given the time limitations and the nondeterministic polynomial (NP)-hard nature of scheduling problems. This paper presents an anytime-heuristic search approach based on a simulation-optimization framework that combines evaluation methods (simulation) and search methods (optimization) through the reachability analysis (or state space) of timed colored Petri net models to schedule flexible manufacturing systems (FMS). The anytime search algorithm is capable of finding a first suboptimal solution very quickly and continuously improves the solution quality over time. If given enough computation time, the algorithm eventually converges to an optimal solution. The proposed approach is aimed at obtaining optimal or near-optimal solutions to FMS scheduling problems in relatively short computation times with the objective of minimizing the makespan. Its effectiveness is highlighted with excellent results that outperform previous methods on benchmark examples with flexible material handling systems, machine, and routing configurations. The approach can also serve as a decision support tool to assist production schedulers that require rapid and almost real-time responses to time-critical production scheduling on the shop floor.

Organizations increasingly find that they must rely on effective supply chains to successfully compete in the global market and networked economy. Over the years, simulation models have proved to be a useful decision support tool for examining the performance of different system configurations and/or alternative operating procedures for complex systems to improve operational and organizational efficiency. This paper presents a new approach that transforms an optimization problem to a search problem by evaluating the interrelationship of decision making when either one or more actors in the supply chain take aggressive or conservative positions. This is aimed at improving and optimizing performance, both individually and for the entire chain in order to reduce costs, lower inventories, and increase manufacturing throughput.