Firing rate optimization of cyclic timed event graphs by token allocations

In this paper, we deal with the problem of allocating a given number of tokens in a cyclic timed event graph (CTEG) so as to maximize the firing rate of the net. We propose three different approaches. The first one is a "greedy" incremental procedure that is computationally very efficient. The only drawback is that the convergence to the optimum is guaranteed only when the set of places where tokens can be allocated satisfies given constraints. The other two procedures involve the solution of a mixed integer linear programming problem. The first one needs the knowledge of the elementary circuits, thus it is convenient only for those classes of CTEG whose number of elementary circuits is roughly equal to the number of places, such as some kanban-systems. On the contrary, the second one enables one to overcome this difficulty, thus providing an efficient tool for the solution of allocation problems in complex manufacturing systems like job-shop systems.