scientific article; zbMATH DE number 3978803
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.
- scientific article; zbMATH DE number 3941253
- scientific article; zbMATH DE number 4029243
- A problem in scheduling theory
- The schedule-sequencing problem
- Les problèmes d'ordonnancement
- Scheduling problems
- scientific article; zbMATH DE number 1560337
- On approximating a scheduling problem
- On one scheduling problem
- One problem of scheduling theory
- The problem of schedule construction in the joint design of hardware and software
- Optimization of schedules with precedence logical conditions
- Optimal schedules for problems with various routes
- Minimization of the number of devices under working in systems of identical parallel devices
- Polynomial algorithms of solution for some problems of construction of the timetables of a device for demands with waiting
- scientific article; zbMATH DE number 3843474 (Why is no real title available?)
- scientific article; zbMATH DE number 4201583 (Why is no real title available?)
- Complex Scheduling
- Solving job shop problems in the context of hypergraphs
- scientific article; zbMATH DE number 3896981 (Why is no real title available?)
- scientific article; zbMATH DE number 3941253 (Why is no real title available?)
- Scheduling to Minimize Maximum Workload
- scientific article; zbMATH DE number 3970495 (Why is no real title available?)
- scientific article; zbMATH DE number 4023002 (Why is no real title available?)
- scientific article; zbMATH DE number 3570347 (Why is no real title available?)
- scientific article; zbMATH DE number 4123510 (Why is no real title available?)
- scientific article; zbMATH DE number 569960 (Why is no real title available?)
- An existence theorem for packing problems with implications for the computation of optimal machine schedules
- Graph models for scheduling systems with machine saturation property
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)