Том 18, номер 1, 2011 г., Стр. 85-97
УДК 519.6
Симанчев Р. Ю., Уразова И. В.
Многогранник расписаний обслуживания идентичных требований параллельными приборами
Аннотация:
В статье изучается многогранник расписаний обслуживания частично упорядоченного множества требований, имеющих одинаковые длительности обслуживания, параллельными идентичными приборами. Построена полиэдральная релаксация этого многогранника, описан класс правильных неравенств. Показано, что полученные неравенства могут служить отсечениями в соответствующих алгоритмах. Обсуждается задача идентификации этих неравенств для данной нецелочисленной точки.
Ил. 1, табл. 1, библиогр. 5.
Ключевые слова: расписание, ациклический орграф, ЦЛП, многогранник, опорное неравенство.
Симанчев Руслан Юрьевич 1
Уразова Инна Владимировна 1
1. Омский гос. университет,
пр. Мира, 55а, 644077 Омск, Россия
е-mail: osiman@rambler.ru, urazovainn@mail.ru
Статья поступила 3 ноября 2009 г.
Исправленный вариант — 6 декабря 2010 г.
Литература
[1] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М.: Мир, 1982. — 416 с.
[2] Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978. — 431 с.
[3] Танаев В. С., Гордон В. С., Шафранский Я. М. Теория расписаний. Одностадийные системы. — М.: Наука, 1984. — 382 с.
[4] Lawler E. L. Combinatorial optimization: networks and matroids. — New York: Holt, Rinehart, and Winston, 1976. — 374 p.
[5] http://www.mathematik.uni-osnabrueck.de/research/OR/class
