An improved approach for marking optimization of timed weighted marked graphs

Timed weighted marked graphs are a mathematical formalism suitable to model automated manufacturing systems in which synchronization and bulk services and arrivals appear, such as assembly lines and kanban systems. In this paper, we aim to develop practically efficient methods for the marking optimization of timed weighted marked graphs, a problem which consists in finding an initial resource assignment to minimize the cost of resources under a given requirement on the cycle time. Starting with a live initial marking, we first compute the critical places of a timed weighted marked graph by exploring an equivalent model called timed marked graph. Then, we develop an analytical method to identify the critical circuit of the system to which tokens will be iteratively added. Application to a real manufacturing system is finally provided, which shows that the developed approach is significantly more efficient than the existing ones.