scientific article; zbMATH DE number 3978803

From MaRDI portal
Publication:3743091





Statement of the problem: There are n jobs; each of the jobs can be fulfilled by anyone of some identical devices working in a parallel way. The time is discrete. An admissible schedule (graph) is a sequence of jobs satisfying the conditions: 1) all the jobs start in the interval (0,t); 2) at any moment, not more than one job is starting. Let N be the number of devices and for the construction of the optimal graph. In a paper by \textit{K. V. Kim, G. A. Krajnov} and \textit{E. V. Surmenev} [Ekon. Mat. Metody 12, 767-772 (1976; Zbl 0339.90045)] the upper estimate for the number N and a relation for obtaining the lower estimate was obtained for the case \(t=n\). In the present work, the general case \(t\geq n\) is considered. The lower and upper estimates of the number N have been obtained. Algorithms for the construction of the optimal graph are proposed.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3743091)