Оценки приближенного решения одной задачи календарного планирования

Исследуется частный случай труднорешаемой задачи календарного планирования, который с критерием минимума длины расписания является оценочной снизу задачей для задачи упаковки в полосу. На примере показывается, что существуют списки работ, для которых отношение оптимальных значений целевых функций обеих задач может достигать величины 5/4. Для критерия максимума суммарного получаемого дохода на примерах показывается “плохое” поведение в общем случае списочных алгоритмов, использующих общеизвестные типы сортировки. Предлагаются точные нижние оценки при некоторых ограничениях на параметры работ.
Ил. 3, библиогр. 3