Том 21, номер 4, 2014 г., Стр. 89-101

УДК 519.1
Симанчёв Р. Ю., Шерешик Н. Ю.
Целочисленные модели обслуживания требований одним прибором с прерываниями

Аннотация:
Рассматривается задача минимизации общего времени обслуживания различных требований одним прибором с прерываниями. Описаны три модели целочисленного линейного программирования для данной задачи. Проведён сравнительный анализ моделей, и описан вычислительный эксперимент.
Табл. 1, ил. 6, библиогр. 7.

Ключевые слова: теория расписаний, модель целочисленного линейного программирования, многогранник, полиэдр, правильное неравенство.

Симанчёв Руслан Юрьевич ¹
Шерешик Николай Юрьевич ²
1. Комплексный научно-исследовательский отдел региональных проблем ОНЦ СО РАН,
пр. К.Маркса, 15, 644010 Омск, Россия
2. Омский филиал Ин-та математики им. С. Л. Соболева СО РАН,
ул. Певцова, 13, 644043 Омск, Россия
е-mail: osiman@rambler.ru, m-m_pikm@mail.ru

Статья поступила 13 марта 2014 г.
Исправленный вариант — 7 мая 2014 г.

Литература

[1] Баптист Ф., Карлье Ж., Керан М., Кононов А. В., Севастьянов С. В., Свириденко М. Структурные свойства оптимальных расписаний с прерыванием операций // Дискрет. анализ и исслед. операций. - 2009. - T. 16, N1. - С. 3–36.
Baptiste Ph., Carlier J., Kononov A., Queyranne M., Sevastyanov S., Sviridenko M. Structural properties of optimal schedules with preemption // J. Appl. Industr. Math. - 2010. - Vol. 4, N4. - P. 455–474.

[2] Лазарев А. А., Кварацхелия А. Г. Свойства оптимальных расписаний задачи теории расписаний минимизации суммарного взвешенного момента окончания для одного прибора // Автоматика и телемеханика. - 2010. - № 10. - С. 80-89.

[3] Симанчёв Р. Ю., Толстуха Б. А. Некоторые полиэдральные свойства одной задачи теории расписаний // Сб. тр. междунар. конф. .Дискретная оптимизация и исследование операций. (Новосибирск, 24–28 июня 2013 г.). - Новосибирск: Ин-т математики СО РАН, 2013. - C. 153.

[4] Симанчёв Р. Ю., Шерешик Н. Ю. Схема дихотомии для поиска минимального директивного срока в задаче обслуживания различных требований одним прибором // Вестн. Омск. гос. ун-та. - 2013. - №2. - С. 48–50.

[5] Толстуха Б. А., Уразова И. В., Шерешик Н. Ю. Класс опорных неравенств для задачи $1|pmtn;p_i=2;r_i|\sum\omega_i C_i$ // Сб. тр. междунар. конф. .Дискретная оптимизация и исследование операций. (Новосибирск, 24–28 июня 2013 г.). - Новосибирск: Ин-т математики СО РАН, 2013. - C. 154.

[6] Bouma W. H., Goldengorin B. A polytime algorithm based on a primal LP model for scheduling problem $1|pmtn;p_i=2;r_i|\sum\omega_i C_i$ // Recent Adv. Appl. Math. Proc. American Conf. Applied Mathematics (AMERICAN-MATH’10). - Cambridge, MA: Harvard Univ., 2010. - P. 415–420.

[7] Brucker P., Knust S. Complexity results for scheduling problems //
www.mathematik.uni-osnabrueck.de/research/OR/class.