Автоматика и телемеханика, № 7, 2014
© 2014 г. Д.И. КОГАН, д-р техн. наук (kdi_41@mail.ru) (Московский государственный университет приборостроения и информатики), А.С. КУИМОВА, канд. техн. наук (anastasia.kuimova@gmail.com), Ю.С. ФЕДОСЕНКО, д-р техн. наук (fds@vgavt-nn.ru) (Волжская государственная академия водного транспорта, Нижний Новгород)
ЗАДАЧИ ОБСЛУЖИВАНИЯ БИНАРНОГО ПОТОКА ОБЪЕКТОВ В СИСТЕМЕ С НАКОПИТЕЛЬНО-РАСХОДНЫМ КОМПОНЕНТОМ1
Рассматривается модель одностадийного обслуживания конечного детерминированного потока объектов процессором с накопительно-расходным компонентом — резервуаром ограниченной емкости. Поток состоит из подпотока объектов, пополняющих резервуар, и подпотока объектов, заполняемых из резервуара. С каждым объектом ассоциируется линейная функция индивидуального штрафа за время пребывания в системе обслуживания. Изучается задача построения расписания, минимизирующего суммарный штраф по всем объектам потока. Конструируемые алгоритмы основываются на принципе динамического программирования, схеме ветвей и границ, а также на их совместной реализации. Приводятся результаты вычислительных экспериментов.
1. Введение
Рассматриваемая модель возникла при изучении процессов грузовой обработки танкерного флота в условиях Северного завоза [1] через речной порт г. Салехарда.
В течение непродолжительного навигационного периода крупнотоннажным танкерным флотом по реке Обь с нефтеперегонных заводов Западной Сибири в Салехардский порт доставляется дизельное топливо. Прибывающие суда в определенной очередности подаются к специализированному терминалу, техническими средствами которого нефтепродукт перекачивается в резервуар ограниченной емкости. Многочисленные пункты потребления дизельного топлива, являющегося основным энергетическим ресурсом в Заполярье, располагаются в основном по берегам Обской губы и малых рек прилегающего региона полуострова Ямал. Доставка топлива в эти пункты осуществляется водным путем из Салехардского порта малотоннажными танкерами ледового класса, загрузка которых осуществляется на упомянутом специализированном терминале. По техническим условиям на терминале не может одновременно обслуживаться более одного танкера.
В описанной схеме Северного завоза задействованы танкеры, характеризующиеся различными технико-экономическими параметрами. Задача диспетчеризации заключается в выработке стратегии управления очередностью
1 Работа выполнена при финансовой поддержке Фонда научно-исследовательской деятельности Волжской государственной академии водного транспорта (грант №02-2013).
их грузовой обработки — расписания обслуживания, которое в пределах горизонта оперативного планирования обеспечивает сокращение суммарных эксплуатационных расходов, обусловленных непроизводительными простоями флота.
Специфика задач диспетчеризации заключается в том, что между моментом, когда полностью определились исходные данные конкретной задачи, и моментом, когда следует начать работу по построенному расписанию, проходит относительно небольшой промежуток времени. В течение этого промежутка задача должна быть решена. Поэтому при математическом исследовании каждой типовой задачи диспетчеризации важно получить оценку ее вычислительной сложности. Вячеслав Сергеевич Танаев был одним из первых математиков, активно исследовавших вопросы вычислительной сложности задач теории расписаний; в написанных им совместно с коллегами и получивших мировое признание монографиях [2, 3] вопросы разделения задач на полиномиально разрешимые и КР-трудные [4] играют ключевую роль.
Статья состоит из шести разделов и Приложения. В разделе 2 дано описание модели обслуживания, приведена математическая постановка задачи синтеза оптимального расписания обслуживания и сформулированы связанные с этой задачей результаты о труднорешаемости. Раздел 3 посвящен описанию процедуры решения поставленной задачи на основе рекуррентных соотношений динамического программирования; технология решения этой задачи с использованием схемы ветвей и границ приводится в разделе 4. В разделе 5 рассмотрены некоторые пути сокращения счета при синтезе расписаний обслуживания, в том числе благодаря комбинированному применению концепции динамического программирования и схемы ветвей и границ. В этом же разделе вводится конкретизация рассматриваемой задачи, предполагающая ограниченность числа типов подлежащих обслуживанию объектов; получаемая при таком ограничении частная задача оказывается полиномиально разрешимой. Доказательства приведенных в разделе 2 теорем о труднорешаемости вынесены в Приложение.
2. Математическая модель обслуживания, постановка оптимизационной задачи и исследование вычислительной сложности
Изучается модель М, в которой конечный поток объектов Оп = (оь 02,..., оп} подлежит однофазному обслуживанию стационарным процессором с накопительно-расходным компонентом - резервуаром емкости V*. Для каждого объекта о^, г = 1 ,п, определены целочисленные параметры: ti -момент поступления в очередь на обслуживание; т - норма длительности обслуживания; а% - штраф за единицу времени пребывания в системе обслуживания; Уг - объемная характеристика (вместимость объекта), V* ^ Уг. Поток Оп состоит из подпотоков О+ и О-. Объекты подпотока О+ предназначены для пополнения резервуара, объекты подпотока О- - для заполнения из резервуара. Принадлежность объекта о^, г = 1 ,п, тому или иному подпотоку определяется значением параметра wi (тг = +1, если ог € О+; wi = —1, если 0г € О-). Объекты пронумерованы в порядке их поступления: 0 = ¿1 ^ ¿2 ^
^ ... < ¿п.
Считается, что процессор не может обслуживать более одного объекта одновременно; обслуживание каждого объекта осуществляется без прерываний. Заполнение резервуара в момент времени Ь будем характеризовать переменной V (Ь) с известным начальным значением V (0). Обслуживание объекта ог из подпотока 0+ может быть начато при наличии в резервуаре достаточного свободного объема; в результате реализации обслуживания объекта ог заполнение резервуара увеличивается на величину Уг. Обслуживание объекта ог из подпотока О- может быть начато при наличии достаточного заполнения резервуара; в результате реализации его обслуживания заполнение резервуара уменьшается на величину Уг.
Расписание обслуживания потока 0п определяем как перестановку р = {г(1),г(2),..., г(п)} совокупности индексов N = {1, 2 ,...,п}; при его реализации объект с индексом г(к) обслуживается к-м по очереди (к = = 1 ,п). Расписание р именуем допустимым, если в процессе его выполнения удовлетворяются отмеченные выше объемные ограничения, т.е. 0 ^ V(0) +
= 1 Уг(р)™г(р) ^ V % Я = 1) 2,Совокупность допустимых в модели М расписаний обслуживания обозначим через О.
Как очевидно, заполнение резервуара после завершения обслуживания всех объектов потока 0п оказывается равным V(0) + ^п=1 У^г. Выполнение двойного неравенства
п
(1) 0 < V(0)+£ ВД < V*
г=1
является необходимым, но недостаточным условием непустоты множества О. Приведем иллюстрирующий пример: положим V(0) = V* = 5; подпоток 0+ составляет единственный объект с объемной характеристикой, равной пяти; в подпоток 0- входит пять объектов, объемная характеристика каждого из них равна двум. Здесь условие (1) выполнено, но допустимого расписания обслуживания не имеется.
Выделим и назовем моделью Мо частый случай модели М, в котором все подлежащие обслуживанию объекты изначально присутствуют в системе: Ьи = 0, к = 1, 2,...,п.
Теорема 1. Проблема определения по исходным данным модели М0 (условие (1) выполнено), является ли множество допустимых в ней расписаний обслуживания непустым, МР-полна в сильном смысле.
Доказательство теоремы 1 приведено в Приложении.
Легко видеть, что при соблюдении условия (1) выполнение неравенства
(2) 2 тах^ ^ V*
1=1,п
достаточно для обеспечения непустоты совокупности О.
В рассматриваемом классе воднотранспортных приложений неравенства (1) и (2) всегда имеют место. Далее будем считать их выполненными.
Заметим также, что условия
^ Уг < V(0П & { У < V* - V(0)
необходимы и достаточны, чтобы любое расписание обслуживания было допустимо.
Считаем, что процессор готов к обслуживанию объектов начиная с момента времени £ = 0. Каждое допустимое расписание р = (¿(1), ¿(2),... , ¿(п)} однозначно определяет для произвольного объекта о^д.) моменты начала и завершения его обслуживания, которые далее будут обозначаться ¿ъед(¿(Л), р) и ¿*(г(к),р) соответственно. Указанные моменты последовательно в порядке возрастания значений параметра к вычисляются по формулам:
При реализации расписания р суммарный штраф К(р) по всем объектам потока Оп оказывается равным ^П=1 &г[£*(г,р) — ¿г].
Задача 1. Найти допустимое расписание обслуживания, минимизирующее величину суммарного штрафа, т.е.
Задачей 1о назовем задачу 1, сформулированную в рамках частной модели Мо, т.е. для случая, когда все подлежащие обслуживанию объекты изначально присутствуют в системе: ¿д = 0, к = 1, 2,..., п.
Теорема 2. Задача 10 МР-трудна в сильном смысле.
Доказательство теоремы 2 приведено в Приложении.
3. Решение задачи 1 методом динамического программирования
Определение искомой последовательности обслуживания объектов трактуем как синтез оптимальной траектории в соответствующим образом построенной дискретной системе с конечным числом состояний и конечным числом возможных в каждом состоянии управлений; пошаговые штрафы зависят от выбираемых управлений. Требуется найти минимизирующую суммарный штраф последовательность управлений, переводящую систему из начального состояния в одно из финальных ее состояний. Задача решается методом динамического программирования [5].
Оптимальное значение критерия задачи 1 обозначим К^. Пусть -определяемое исходными данными этой задачи подмножество индексов объектов потока Оп, которые поступают в систему обслуживания в момент дискретного времени ¿; при этом Л(0) - подмножество индексов объектов, ожидающих обслуживания по состоянию на момент времени t = 0. Совокупность
¿Ъед (¿(1),р) = ¿г(1);
¿■Ьед(¿(к), р) = шах[Г(г(к — 1), р),], к = 2,3,... ,п;
¿*(г(к),р) = ¿Ъед (¿(к), р) + тг(д), к = 1,2,..
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.