An iterative linear relaxation and tabu search approach to minimum initial marking problems of timed marked graphs

The minimum cost initial distributed state problem, Minimum Initial Marking (MIM) problem in Petri nets, is very important for the design of many discrete event dynamic systems (DEDSs). This paper considers MIM for Timed strongly connected Marked Graphs (MG). Unfortunately, even for the untimed MG subclass the problem is NP-hard. A suboptimal two phases approach for timed MGs (TMG) is developed. The first one tries to provide "a reasonable" initial solution. Technically it is based on a greedy algorithm consisting on an iterative scheme where linear programming problems (LPP) are solved. A post-optimization is done through a tabu search (TS) technique.