Задачи обслуживания бинарного потока объектов в системе с накопительно-расходным компонентом

Рассматривается модель одностадийного обслуживания конечного детерминированного потока объектов процессором с накопительно-расходным компонентом – резервуаром ограниченной емкости. Поток состоит из подпотока объектов, пополняющих резервуар, и подпотока объектов, заполняемых из резервуара. С каждым объектом ассоциируется линейная функция индивидуального штрафа за время пребывания в системе обслуживания. Изучается задача построения расписания, минимизирующего суммарный штраф по всем объектам потока. Конструируемые алгоритмы основываются на принципе динамического программирования, схеме ветвей и границ, а также на их совместной реализации. Приводятся результаты вычислительных экспериментов.

Статья представлена к публикации членом редколлегии: А. А. Лазарев