The complexity of the problem of minimizing makespan for identical jobs Conference attendances
| Language | Английский | ||
|---|---|---|---|
| Participant type | Секционный | ||
| Conference |
22nd International conference "Mathematical Optimization Theory and Operations Research" 02-08 Jul 2023 , Екатеринбург |
||
| Authors |
|
||
| Affiliations |
|
Abstract:
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.
Cite:
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
The complexity of the problem of minimizing makespan for identical jobs
22nd International conference "Mathematical Optimization Theory and Operations Research" 02-08 Jul 2023