Аннотация:
Для $r$-стадийной задачи open shop с идентичными параллельными процессорами на каждой стадии и критерием “минимум длины расписания” строится аппроксимационная схема временной сложности $O(nrm+C(m,\varepsilon))$, где $n$ – число работ, $m$ – общее число процессоров, а $C(m,\varepsilon)$ – функция, не зависящая от $n$. Библиогр. 6.