Title: Solving production scheduling problems using advanced model checking tools

Authors: Dimitrios Panopoulos, Kostas Metaxiotis

Addresses: School of Electrical and Computer Engineering, National Technical University of Athens, Athens, Greece. ' School of Electrical and Computer Engineering, National Technical University of Athens, Athens, Greece

Abstract: The main scope of this paper is the implementation of a method for production scheduling, using advanced model checking tools. This method makes use of timed automata to model complex production scheduling problems such as the job-shop and the open-shop scheduling problems. By modelling scheduling problems using timed automata, feasible schedules correspond to paths in the automata, while finding the optimum schedule corresponds to finding the shortest path in an automaton. Several algorithms and heuristics have been proposed for finding the shortest paths in timed automata, which are mainly based on the implementation of graph algorithms that search the transition graph. In our work, an advanced model design and checking tool, called UPPAAL, has been used to implement and test the above method on a number of different models and to show the effectiveness of such an approach in terms of finding optimal or near to optimal, schedules in polynomial time, even for large-scale problems.

Keywords: production scheduling; model checking; timed automata; job-shops; distributed manufacturing.

DOI: 10.1504/IJCAT.2006.010079

International Journal of Computer Applications in Technology, 2006 Vol.26 No.1/2, pp.37 - 48

Published online: 16 Jun 2006 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article