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 tok ens 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 "gree dy" 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. T he other two procedures involve the solution of a mixed integer linear prog ramming problem. The first one needs the knowledge of the elementary circui ts, thus it is convenient only for those classes of CTEG whose number of el ementary circuits is roughly equal to the number of places, such as some ka nban-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. (C) 2001 Elsevier Science Ltd. All rights reserved.