Том 13, серия 2, номер 1, 2006 г., Стр. 57-76

УДК 519.854.2
А. А. Лазарев, Р. Р. Садыков, С. В. Севастьянов
Схема приближённого решения задачи $1|R_j|L_{\max}$

Аннотация:
Рассматривается NP-трудная в сильном смысле задача теории расписаний о минимизации максимального временного смещения на одном приборе при неодновременном поступлении работ. Представлена схема приближённого решения, основанная на отыскании по заданному примеру другого (наиболее близкого в некоторой метрике) примера, принадлежащего к известному полиномиально разрешимому классу примеров. Для нескольких конкретных вариантов схемы (с использованием различных полиномиально разрешимых классов примеров) найдены аналитические формулы, позволяющие по любому заданному примеру легко вычислить оценку абсолютной погрешности его приближённого решения. 
Библ. 18. 

Лазарев А. А. ²
Садыков Р. Р. ²
Севастьянов С. В. ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Казанский государственный университет, кафедра экономической кибернетики,
ул. Кремлёвская, 18, 420008 Казань, Россия
е-mail: Alexandr.Lazarev@ksu.ru

Статья поступила 10 апреля 2005 г.
Исправленный вариант — 13 ноября 2005 г.