Solving production scheduling problems using advanced model checking tools
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

The full text of this article is only available to individual subscribers or to users at subscribing institutions.

Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.

Pay per view:
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:

    Username:        Password:         

Forgotten your 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