Performance evaluation of job-shop systems using timed event-graphs. (English) Zbl 0656.90054

Timed event-graphs, a special class of timed Petri nets, are used for modeling and analyzing job-shop systems. The modeling allows for evaluating the steady-state performance of the system under a deterministic and cyclic production process. Given any fixed processing times, the productivity (i.e., production rate) of the system can be determined from the initial state. It is shown in particular that, given any desired product mix, it is possible to start the system with enough jobs in-process so that some machines will be fully utilized in steady- state. These machines are called bottleneck machines, since they limit the throughput of the system. In that case, the system works at maximal rate and the productivity is optimum. The minimal number of jobs in- process allowing an optimum functioning of the system is further specified as an integer linear programming problem. An efficient heuristic algorithm is finally developed to obtain a near-optimal solution.


90B35 Deterministic scheduling theory in operations research
90C10 Integer programming
90C35 Programming involving graphs or networks
90B30 Production models
90C05 Linear programming
Full Text: DOI