Реферат: The problem of minimizing the total processing time of identical jobs with a complex technological route, when it is possible to reentrant receive jobs on some machines, is considered. The paper investigates the computational complexity of this problem. Its NP-hardness in the usual sense is proved. Algorithms for constructing an approximate solution based on the use of cyclic schedules are proposed.

Библиографическая ссылка: Servakh
The complexity of the problem of minimizing makespan for identical jobs
22nd International conference "Mathematical Optimization Theory and Operations Research" 02-08 Jul 2023