Том 22, номер 6, 2015 г., Стр. 78–90

УДК 519.1
Шерешик Н. Ю.
Релаксации многогранника оптимальных расписаний обслуживания требований одним прибором c прерываниями

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

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

DOI: 10.17377/daio.2015.22.486

Статья поступила 11 апреля 2015 г.
Исправленный вариант — 16 августа 2015 г.

Литература

[1] Баптист Ф., Карлье Ж., Керан М., Кононов А. В., Севастьянов С. В., Свириденко М. И. Структурные свойства оптимальных расписаний с прерыванием операций // Дискрет. анализ и исслед. операций. 2009. T. 16, № 1. С. 3–36.

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

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

[4] Симанчёв Р. Ю., Шерешик Н. Ю. Целочисленные модели задачи обслуживания требований одним прибором с прерываниями // Дискрет. анализ и исслед. операций. 2014. T. 21, № 4. С. 89–101.

[5] Bouma W. H., Goldengorin B. A polytime algorithm based on a primal LP model for scheduling problem 1|pmtn; p_i = 2; r_i| Σ ω_iC_i // Recent Advances in Applied Mathematics. Proc. Amer. Conf. Appl. Math.
(AMERICAN-MATH’10). (Cambridge, MA, Jan. 27–29, 2010). Athens: WSEAS Press, 2010. P. 415–420.

[6] Brucker P., Knust S. Complexity results for scheduling problems //
http://www.informatik.uni-osnabrueck.de/knust/class/. Accessed Oct. 13, 2015.