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.

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.

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.