Asymptotic optimal state of a generalized time event graph: application to an assembly problem. (Régime asymptotique optimal d’un graphe d’événements temporisé généralisé: application à un problème d’assemblage.) (French) Zbl 0801.90056

Munier, Alix

RAIRO, Autom. Prod. Inf. Ind. 27, No. 5, 487-513 (1993).

Summary: The aim of this paper is to study the optimal behavior of a generalized timed event graph and to apply these results to an assembly system. As there are no conflicts between the firings of the transitions for a generalized timed event graph, their frequencies are maximum for the earliest operational mode. We prove that the resulting schedule is \(K\)- periodic and we propose an algorithm to compute these frequencies. This algorithm is based on a particular decomposition of the set of transitions and on the expansion of its components. We construct a valued graph by contracting these components and we show that the longest paths of that graph provide the maximum values of the frequencies.

MSC:

90B30	Production models
90B35	Deterministic scheduling theory in operations research

Keywords:

earliest schedule; performance; generalized timed event graph; assembly system