SOLVING PRODUCTION SCHEDULING PROBLEMS USING ADVANCED MODEL CHECKING TOOLS
Dimitrios Panopoulos, Kostas S. Metaxiotis, Dimitrios Ptochos, C. LIGOURAS, M. SKLAVENITI · Journal of Advanced Manufacturing Systems · 2006
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 in order to model complex production scheduling problems like the job-shop and the open-shop scheduling problems. By modeling scheduling problems using timed automata, feasible schedules correspond then 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 to find 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.