Том 2, номер 1, 1995 г., Стр. 57-67
УДК 519.8
П. И. Шарыгин
Оценки приближенного решения одной задачи календарного планирования
Аннотация:
Исследуется частный случай труднорешаемой задачи календарного планирования, который с критерием минимума длины расписания является оценочной снизу задачей для задачи упаковки в полосу. На примере показывается, что существуют списки работ, для которых отношение оптимальных значений целевых функций обеих задач может достигать величины 5/4. Для критерия максимума суммарного получаемого дохода на примерах показывается «плохое» поведение в общем случае списочных алгоритмов, использующих общеизвестные типы сортировки. Предлагаются точные нижние оценки при некоторых ограничениях на параметры работ.
Ил. 3, библиогр. 3.
Шарыгин П. И. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
Статья поступила 5 октября 1994 г.
