In: Proc. IEEE Int. Conf. on Systems, Man, and Cybernetics (SMC'2000), 8-11 October 2000, Nashville, TN, Vol. 4, pages 3004-3008. 2000.
Abstract: This paper addresses the minimum initial marking (MIM) problem in timed marked graphs (TMGs). In this problem, both the net and the cycle time are fixed, so the problem consists of finding a minimum initial marking M such that the cycle time of the TMG be less or equal to the required one. The main result of this work is the heuristic algorithm MIM-Solver. It computes a subset of p-semiflows and adds tokens to places in two steps. First it adds the minimum number of tokens needed to reduce the difference between the required cycle time and the cycle time of each p-semiflow in the computed subset. In this step, a heuristic based on the places belonging to the maximum number of p-semiflows is used. Afterwards, the algorithm adds the largest number of tokens in p-semiflows to satisfy the cycle time constraints. In this step, a heuristic based on the places belonging to the smallest number of p-semiflows is used.
Keywords: MIM-Solver, minimum initial marking, p-semiflows, timed marked graphs.