Decomposition of timed automata for solving scheduling problems
Tatsushi Nishi, Masato Wakatake, Masahiro Inuiguchi · Conference proceedings/Conference proceedings - IEEE International Conference on Systems, Man, and Cybernetics · 2008
In this paper, we propose a decomposition and coordination method for timed automata for modeling and solution of scheduling problems. Parallel composition of timed automata makes it possible to describe concurrent dynamics for several submodels represented by timed automata. To reduce state space explosion for parallel composition of timed automata, a decomposition and coordination method is developed. In the proposed method, a feasible solution is derived by coordinating the solution of each decomposed subproblem. Computational experiments demonstrate the feasibility of the proposed method.