Some optimization problems for timed marked graphs

Abstract

Discrete event dynamic systems are frequently encountered in complex man-made systems. Such a system is often described in terms of a timed Petri net. For periodic behaviour of such a system, a timed marked graph provides a convenient and powerful tool of modelling and analysis. In this paper we define three optimization problems for such a system. All of these problems are formulated as mixed integer linear programming (MIP) problems. To improve computational efficiency, we introduce ‘cuts’ to these MIP problems, and the effect of such cuts is examined through computational experiments on some test problems.