Том 14, серия 1, номер 4, 2007 г., Стр. 3-15

УДК 519.854
А. А. Агеев
Алгоритм с оценками для пропорционального случая двухпроцессорной задачи теории расписаний типа flow shop c минимальными задержками

Аннотация:
Рассматривается двухпроцессорная задача типа flow shop с минимальными задержками. Известно, что эта задача NP-трудна в сильном смысле даже в случае единичных длительностей операций и может быть решена за полиномиальное время с точностью 2 в общем случае. В ряде работ ставился вопрос о существовании полиномиального алгоритма с лучшей оценкой точности, но он до сих пор остаётся открытым. В этой статье предлагается полиномиальный алгоритм с оценкой точности $\frac32$ для частного случая задачи, в котором обе операции каждой работы имеют равные длительности (этот случай задач типа flow shop в литературе обычно принято называть пропорциональным). Анализ алгоритма основан на нетривиальном обобщении нижней границы, установленной в работе В. Ю для случая единичных длительностей операций.
Библ. 13.

Агеев А. А. ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: ageev@math.nsc.ru

Статья поступила 24 июля 2007 г.