СОСТАВЛЕНИЕ ДОПУСТИМОГО РАСПИСАНИЯ ОПТИМАЛЬНОГО ПО КРИТЕРИЮ МИНИМИЗАЦИИ СУММАРНОГО ОПЕРЕЖЕНИЯ РАБОТ



Павлов А.А., Халус Е.А. Розглянута задача складання допустимого розкладу виконання незалежних робіт з різними тривалостями та директивними термінами одним приладом, при якому мінімізується сумарне випередження директивних термінів. Запропановано ПДС – алгоритм знаходження оптимального розкладу за критерієм мінімізації сумарного випередження.

We considered a problem of creation of feasible schedule of performing an independent operations with different durations and due dates of a single device, in which the minimum of the total earliness of due dates is achieved. We consider PDS – an algorithm for finding an optimal schedule on criteria of minimizing the total earliness.

УДК 519.854.2

Введение

В теории расписаний особое место занимают задачи с одним прибором. Результаты,получаемые при исследовании таких задач, могут быть использованы для построения алгоритмов решения сложных задач со многими приборами и многостадийных задач,возникающих на практике. Классические задачи теории расписаний с одним прибором являются схематичными теоретическими моделями многих задач, встречающихся на практике.

Постановка задачи

Задано множество независимых работ $J=\{1,\,2,\,...,\,n\}$, каждая из которых состоит из одной операции. Для работы $j\in J$ известны длительность выполнения ${{p}_{j}}$ и директивный срок выполнения ${{d}_{j}}$. Прерывания работ не допускаются.Работы поступают в систему одновременно. Процесс выполнения работ является непрерывным: после выполнения первой по порядку работы сразу же начинает выполняться вторая и т.д. Необходимо найти допустимое расписание, в котором суммарное опережение моментов окончания выполнения работ относительно директивных сроков принимает минимальное значения.

Эта задача является близкой к двухкритериальной задаче, рассмотренной в [1,2], в которой требуется найти допустимое расписание, в котором момент запуска работ является максимально поздним (критерий 1), а суммарное опережение выполнения работ относительно директивных сроков принимает минимальное значения (критерий 2). В рамках решения двухкритериальной задачи предполагалось, что первичным критерием являлся критерий 1. В некоторых практических задачах основным критерием оценки расписания является критерий 2 – минимизация суммарного опережения, именно этот критерий и рассматривается в данной работе.

Для решения рассматриваемой задачи были использованы результаты, полученные при исследовании двухкритериальной задачи [1,2]. Так, в работе [1] был разработан алгоритм А определения самого позднего момента запуска выполнения работ в системе $n/1/r\to \max $, при котором расписание остается допустимым..

Отметим, что при ухудшении расписания по критерию 1 (при смещении его влево) можно получить расписание, которое по критерию 2 лучше предыдущего.

Одним из подходов к эффективному решению как труднорешаемых (NP-полных) задач комбинаторной оптимизации, так и в некоторых случаях P – разрешимых задач комбинаторной оптимизации является разработка ПДС – алгоритмов [1]. Данная задача решается ПДС – алгоритмом второго типа: кроме Р – составляющей он содержит полиномиальную аппроксимацию точного алгоритма (приближенное решение, полученное в случае не выполнения достаточных условий оптимальности).

В работе [3] определены два признака оптимальности допустимого расписания.

Принципиальная схема ПДС-алгоритма

Вначале для ${{r}_{\max }}$ строится оптимальное по критерию 2 расписание. Если для него выполняется признак 1) признака оптимальности, то полученное расписание оптимально. Если не выполняется, то применяется полиномиальный алгоритм, который изменяя моменты запуска выполнения заданий от ${{r}_{\max }}$ до 0 и применяя рекуррентно процедуру из теоремы 5 [2] позволяет получить ряд расписаний, оптимальных для моментов запуска

\[{{r}_{\max}},\,\,\,{{r}_{1}},\,{{\,}_{\,}}{{r}_{2}},\,\,...\,,\,\,{{r}_{k}},\,\]

где: $\,{{r}_{1}}={{r}_{max}}-{{\Delta}_{1}},\,\,{{r}_{2}}={{r}_{1}}-{{\Delta}_{2}},\,...,\,{{r}_{k}}={{r}_{k-1}}-{{\Delta }_{k}}$.

$\,{{r}_{1}},\,{{\,}_{\,}}{{r}_{2}},\,\,...\,,\,\,{{r}_{k}}$ – дискретные моменты изменения структуры оптимального по критерию 2 расписания, когда меняется позиция хотя бы одного задания ($k$ - заданное число).

Если на каком-то этапе выполняется признак оптимальности 2), то точное решение находится в отрезке $[{{r}_{l}},\,{{r}_{\max}}]$, это одно из значений $\,\,{{r}_{l}},\,{{\,}_{\,}}{{r}_{l-1}},\,\,...\,,\,\,{{r}_{\max}}\,$, если $\,l\le k$. Если же на $k$ структурах изменения расписаний признак оптимальности 2) не выполняется, то находим минимальное значение суммарного опережения на всех дискретных моментах изменения структур. И таким образом, получим приближенное решение, но точное $\forall{r}\in [{{r}_{l}},\,{{r}_{\max }}]$.

Проиллюстрируем процесс решения задачи с помощью алгоритма нахождения оптимального расписания по критерию минимизации суммарного опережения графически (рисунок 1) [3].

Заданы шесть работ с различными директивными сроками и соответствующими длительностями.

Рис. 1 Пошаговый процесс нахождения оптимального расписания по критерию минимизации суммарного опережения

Выводы

Рассмотрена задача теории расписаний выполнения множества работ с различными директивными сроками одним прибором, в которых все работы должны быть выполнены без нарушения их директивных сроков и минимизировано суммарное опережение моментов окончания работ от их директивных сроков. Продемонстрирован процесс решения задачи ПДС - алгоритмом нахождения оптимального расписания.

Список литературы

  1. Павлов А.А. Исследование свойств задачи календарного планирования для одного прибора по критерию минимизации суммарного опережения заданий при условии допустимости расписании /А. А. Павлов, Е.Б. Мисюра, О.А. Халус // Вісник НТУУ “КПІ”. Серія «Інформатика, управління та обчислювальна техніка». – К.: “ВЕК+”, 2012. – №56.– С. 98–102.

  2. Згуровский М.З. Задача построения допустимого расписания с максимально поздним моментом запуска и минимальным суммарным опереженем / М.З.Згуровский, А. А. Павлов, О.А. Халус // // Системні дослідження та інформаційні технології. — 2015. — № 2. — 12 с.

  3. ПавловА.А. Составление допустимого расписания выполнения работ на одном приборе с целью минимизации суммарного опережения работ [Текст] / А.А. Павлов, Е.А. Халус // ВісникНТУУ “КПІ”. Серія «Інформатика, управління та обчислювальна техніка». – К.:“ВЕК+”, 2014. – №61. – 27-35 с.
Jun 14, 2016