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

Hillion, Hervé P.; Proth, Jean-Marie

IEEE Trans. Autom. Control 34, No. 1, 3-9 (1989).

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.

MSC:

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

Keywords:

Timed event-graphs; timed Petri nets; job-shop systems; steady-state performance; cyclic production process; bottleneck machines; integer linear programming; heuristic; near-optimal solution