Solving production scheduling problems using advanced model checking tools Online publication date: Fri, 16-Jun-2006
by Dimitrios Panopoulos, Kostas Metaxiotis
International Journal of Computer Applications in Technology (IJCAT), Vol. 26, No. 1/2, 2006
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.
Online publication date: Fri, 16-Jun-2006
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Computer Applications in Technology (IJCAT):
Login with your Inderscience username and password:
Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.
If you still need assistance, please email email@example.com