Автоматика и телемеханика, № 7, 2014
© 2014 г. Ю.Н. СОТСКОВ, д-р физ.-мат. наук (sotskov@newman.bas-net.by), Н.Г. ЕГОРОВА, канд. техн. наук (NataMog@yandex.ru) (Объединенный институт проблем информатики Национальной академии наук Беларуси, Минск)
МНОГОГРАННИКИ УСТОЙЧИВОСТИ ОПТИМАЛЬНОЙ ПЕРЕСТАНОВКИ ОБСЛУЖИВАНИЯ ТРЕБОВАНИЙ
Рассматривается задача минимизации суммы взвешенных моментов завершения обслуживания п требований одним прибором при условии, что длительность обслуживания требования может принимать любое вещественное значение из заданного числового отрезка. Разработан алгоритм сложности О(п) для построения многогранника (параллелепипеда) оптимальности перестановки обслуживания п требований, который содержится в области устойчивости той же перестановки и содержит в себе многогранник ее устойчивости. Для случайно сгенерированных задач проведено экспериментальное сравнение размерностей и относительных объемов многогранников оптимальности и устойчивости оптимальной перестановки обслуживания п требований при случайно сгенерированных сценариях.
1. Введение
Для многих задач оперативно-календарного планирования (ОКП), возникающих в промышленности, на транспорте, при планировании сервиса, не удается заранее определить точные значения длительностей операций, которые требуется выполнить в обслуживающей системе, однако имеется возможность оценивать снизу и сверху длительности обслуживания заданных требований. Для решения таких задач ОКП требуются алгоритмы построения расписаний в условиях неопределенных (интервальных) числовых исходных данных [1, 2].
В данной статье рассматривается задача построения оптимального расписания обслуживания требований множества ^ = {<7\,..., ,1п}, где п ^ 2, одним прибором с критерием ^ WiCi минимизации суммы взвешенных моментов С завершения обслуживания требований Ji € J при условии, что на момент построения расписания известны только нижняя граница р^ > 0 и верхняя граница ри ^ р^ возможных длительностей pi обслуживания требований Ji € ^. Для рассматриваемой задачи вводится понятие многогранника (параллелепипеда) оптимальности перестановки обслуживания п требований, который заведомо содержит многогранник устойчивости перестановки обслуживания п требований, исследованный ранее в [3-5]. Разработан алгоритм сложности О(п) для построения многогранника (параллелепипеда) оптимальности перестановки обслуживания п требований.
2. Постановка задачи
Заданное множество требований ^ = ..., }, п ^ 2, необходимо обслужить одним прибором. Каждому требованию .!г € ^ приписан вес —г > 0, характеризующий важность более раннего завершения обслуживания требования Jг.
Фактическая длительность рг обслуживания требования .]г € ^ может оказаться равной любому вещественному числу, заключенному между нижней границей р^ > 0 и верхней границей ^ которые известны до начала составления расписания. При реализации построенного расписания длительность рг обслуживания требования .]г может оставаться неизвестной вплоть до момента завершения операции по обслуживанию требования J.¿. Такая неопределенность длительностей операций характерна для многих задач ОКП.
Пусть Т обозначает множество п-мерных вещественных векторов р = = (р1,... ,Рг,... ,рп) всех возможных длительностей обслуживания требований Ji € ^. Множество Т - это замкнутый прямоугольный многогранник (параллелепипед) в пространстве К+ неотрицательных п-мерных вещественных векторов. Множество Т можно представить в виде декартова произведения п отрезков [р^,ри], г € {1,...,п}:
(1) Т = {р | р € Е+, ргь < рг < ри, г € {1,...,п}} = хп=1 [р^,рГ] .
Фиксированный вектор р € Т длительностей обслуживания требований будем называть сценарием. Пусть Б = {п1,..., пп|} - множество всех перестановок Пк = (Jfc1,..., Jfcn), определяющих порядок обслуживания требований из множества ^. Если перестановки Пк требований множества ^ и сценарий р € Т зафиксированы, то Сг = Сг(пк,р) будет обозначать момент завершения обслуживания требования J¿ € ^ в активном расписании, определяемом перестановкой Пк. Расписание принято называть активным, если ни одно требование Ji € ^ нельзя начать обслуживать раньше без задержки обслуживания другого требования или без изменения порядка обслуживания некоторых требований из множества ^ [1, 6]. В качестве критерия оптимальности будем рассматривать минимизацию суммарного взвешенного времени ^ —гСг обслуживания всех требований ^:
В критерии (2) перестановка Пt = (^, ■ ■ ■ ) € Б - это искомая оптимальная перестановка для критерия ^ —гСг. Используя трехпозиционную форму обозначения а|в|7, введенную в [6], сформулированную задачу будем обозначать в виде 1|ргь ^ рг ^ ри | ^ —гСг.
Поскольку сценарий р € Т может оставаться неизвестным вплоть до окончания выполнения всех требований ^, то момент Сг завершения обслуживания требований .]г € ^, вообще говоря, нельзя определить при построении
расписания. Поэтому задача 1|р^ ^ pi ^ ри wiCi математически некорректна в том смысле, что значения целевой функции 7 = ^^wiCi(пk,р) для различных перестановок П] € 5 обслуживания требований не могут быть вычислены до завершения обслуживания всех требований множества ^. Однако прежде чем реализовать расписание, его надо так или иначе определить.
Если имеют место равенства р^ = ри = р^ то заданный отрезок [р^, ри] вырождается в точку pi = [р^р^ для каждого требования Ji, г € {1,..., п}, а задача 1|р^ ^ pi ^ ри | ^ wiCi превращается в классическую задачу 1|| ^ wiCi с детерминированными длительностями обслуживания требований. Полученная таким образом задача 1|| ^ WiCi математически корректна и может быть решена с помощью алгоритма сложности О(п ^ п), как было установлено Смитом [7].
Задачу а|р^ ^ pi ^ ри|7 с целевой функцией 7 = /..., Cn) будем называть задачей с неопределенными данными, а задачу а||7 - детерминированной. Детерминированная задача а||7 является частным случаем задачи с неопределенными данными а|р^ ^ pi ^ ри|7 (когда выполняются равенства р^ = ри для всех требований Ji, г € {1,..., п}). Если для детерминированной задачи 1||^ WiCi эффективный алгоритм построения оптимального расписания обслуживания требований был опубликован в 1956 г. [7], то задача с неопределенными данными 1 |р"Р ^ Pi ^ ри | ^ WiCi и поныне привлекает внимание исследователей, продолжающих развивать различные методы коррекции задачи 1|р^ ^ pi ^ ри | ^ wiCi и разрабатывать алгоритмы ее "решения" в том или ином смысле (см. [8-10]).
3. Обзор известных результатов
В [7] было установлено, что для решения детерминированной задачи 1|IS w^Ci требуется O(n log n) элементарных операций, если использовать следующее необходимое и достаточное условие оптимальности перестановки
nfc = (Jfcx, • • • , Jfcn) €
wfci ^ ^ wfcn
(3) ^ ^ ^ ^
Pkl Pfc2 Pfcn
В нестрогих неравенствах (3) и для каждого требования Jki € ^ должно выполняться строгое неравенство р^ > 0. Для рассматриваемой задачи 1|р^ ^ ^ Pi ^ р^^ wiCi предполагается включение р] € [р^. ,ри ], р^ > 0.
Для задачи с неопределенными данными 1|р^ ^ pi ^ ри |7, как правило, не существует перестановки обслуживания требований множества ^, которая оставалась бы оптимальной при всех сценариях из множества Т. Поэтому при "решении" этой задачи, как правило, вводят дополнительный критерий оптимальности перестановки обслуживания требований с неопределенными длительностями. Например, в [8] было введено понятие робастного расписания, которое должно минимизировать максимальное для возможных сценариев отклонение от оптимума.
3.1. Метод, основанный на устойчивости оптимального 'расписания
В данной статье для решения задачи 1|р^ ^ рг ^ шгСг применя-
ется метод, основанный на устойчивости оптимального расписания [1, 9-12] к вариациям сценариев из множества Т, определенного в (1). Этот метод объединяет анализ устойчивости оптимальных расписаний [1, 2, 13-16], многостадийное принятие решений (а именно: стадию планирования в режиме оф-лайн и стадии последовательного уточнения реализуемого расписания в режиме он-лайн) [1, 17, 18] и концепцию "решения" задачи с неопределенными данными в виде минимального доминирующего множества активных расписаний [1, 9-12, 19, 20] (т.е. в виде минимального доминирующего множества перестановок для задачи 1|р^ ^ рг ^ | ^ шгСг). При решении задачи 1|р^ ^ рг ^ | шгСг дополнительный критерий оптимальности расписания не вводится, а в качестве "решения" этой задачи используется следующее минимальное доминирующее множество перестановок (или активных расписаний).
Определение 1. Множество перестановок (активных расписаний) Б(Т)СБ называется минимальным доминирующим множеством для задачи а|р^ ^ рг ^ |7, если (а) для любого фиксированного сценария р € Т множество Б(Т) содержит хотя бы одну перестановку обслуживания требований, которая является оптимальной для детерминированной задачи а||7 со сценарием р, (Ъ) причем свойством (а) не обладает ни одно собственное подмножество множества Б(Т).
Минимальное доминирующее множество Б(Т) может быть построено для задачи 1|р^ ^ рг ^ | ^ шгСг на основе следующего отношения доминирования, которое можно эффективно (т.е. полиномиально) задать на множестве требований ^.
Определение 2. Требование ,1и € ^ доминирует над требованием € € ^ относительно Т (обозначение: ,1и ^ ), если существует минимальное доминирующее множество Б(Т) для задачи 1|р^ ^ рг ^ | ^ шгСг такое, что требование Ли предшествует требованию Jv в каждой перестановке из множества Б(Т).
Из определений 1 и 2 следует, что минимальное доминирующее множество, построенное для детерминированной задачи 1||^ —гСг со сценарием р € Т, является одноэлементным доминирующим множеством Б(Т) = {Пк}, где Т = {р}. Иными словами, для детерминированной задачи 1|| ^ —гСг имеет место совершенный строгий порядок Jk1 ^ Jk2 ^ ... ^ ^ -Ткп. Таким образом, для детерминированной задачи 1|| ^ —гСг минимальное доминирующее множество Б(Т) - это оптимальная перестановка Пк обслуживания требований множества ^.
Следующее утверждение было доказано в [9].
Теорема 1 [9]. Для задачи 1|р^ ^ рг ^ | ^шгСг требование .1и доминирует над требованием Jv относительно Т тогда и только тог
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.