Том 6, серия 1, номер 2, 1999 г., Стр. 3-22
УДК 519.854
Г. Д. Воегингер, С. В. Севастьянов
Линейная аппроксимационная схема для многопроцессорной задачи open shop
Аннотация:
Для$r$ -стадийной задачи open shop с идентичными параллельными процессорами на каждой стадии и критерием “минимум длины расписания” строится аппроксимационная схема временной сложности$O(nrm+C(m,\varepsilon))$ , где$n$ – число работ,$m$ – общее число процессоров, а$C(m,\varepsilon)$ – функция, не зависящая от$n$ .
Библиогр. 6.
Воегингер Г. Д. 2
Севастьянов С. В. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Institute fur Mathematik,
TU Graz, Steyrergasse, 30, A-8010 Graz, Austria
е-mail: gwoegi@opt.math.tu-graz.ac.at, seva@math.nsc.ru
Статья поступила 5 ноября 1998 г.
