Улучшенная аппроксимационная схема для задачи Джонсона с параллельными машинами

Рассматривается обобщение NP-трудной задачи Джонсона на случай идентичных параллельных машин на каждой стадии выполнения работ. В условиях, когда число стадий ограничено константой, а общее число машин является частью входа, предложена новая полиномиальная аппроксимационная схема, имеющая лучшую оценку сложности по сравнению с ранее известной.