Том 15, номер 4, 2008 г., Стр. 57-73
УДК 519.8
И. А. Рыков
О сравнении задачи упаковки в полосу c одной задачей календарного планирования
Аннотация:
Проводится сравнение частного случая задачи календарного планирования с задачей упаковки в полосу. Улучшена оценка сверху для отношения оптимумов рассматриваемых задач. Построен пример с оптимумами 5 и 4 и шириной полосы 8. Показано, что данный пример является минимальным, т. е. не существует примера с оптимумами 5 и 4 и с меньшей шириной полосы.
Ил. 3, библиогр. 9.
Ключевые слова: комбинаторная оптимизация, календарное планирование, упаковкa в полосу.
Рыков Иван Александрович 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: rykov@ledas.com
Статья поступила 12 сентября 2007 г.
Исправленный вариант — 7 мая 2008 г.
