Журнал вычислительной математики и математической физики, 2021, T. 61, № 7, стр. 1179-1191

1. ВВЕДЕНИЕ

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

Существуют два типа методов решения таких задач: точные и приближенные (см. [1]). К первой группе относятся целочисленное линейное программирование (см. [2]), динамическое программирование (см. [3]), метод ветвей и границ (см. [4]), локальный элиминационный алгоритм (см. [5]) и т.д. В этом случае оптимальное значение целевой функции вычисляется без каких-либо ошибок, но вычисления требуют больших затрат времени и памяти. Приближенные методы, такие как генетические алгоритмы (см. [6]), алгоритмы муравьиной колонии (см. [7]), алгоритмы пчелиного роя (см. [8]), табу-поиск (см. [9]) и многие другие, гораздо быстрее получают приближенное решение, но, как правило, не имеют оценок отклонения значения целевой функции от оптимального (см. [10]).

В настоящей работе мы описываем общий приближенный подход, который называется метрический (см. [11]). Данный подход позволяет находить приближенное решение с гарантированной погрешностью целевой функции, не превышающей значения функции метрики.

Идея метрического подхода заключается в следующем. Пример задачи $A$ характеризуется точкой, координаты которой соответствуют входным данным задачи. Для этой задачи рассмотрим все известные полиномиальные и псевдополиномиальные алгоритмы. Затем вводим некоторую метрику, значение которой фактически ограничивает сверху оценку абсолютной погрешности целевой функции. С помощью этой метрики находим полиномиально или псевдополиномиально разрешимый пример задачи $B$ с наименьшим расстоянием от данного примера $A$ во введенной метрике. Для этого мы формулируем и решаем задачу линейного программирования. Другими словами, строим проекцию начальной точки $A$ на подпространство задач.

На данный момент для этого подхода получены следующие результаты. В [12] проводится сравнение допустимых областей и дается понятие полиномиальной меры неразрешимости для задачи теории расписаний с одним прибором $1\,|\,{{r}_{j}}\,|\,{{L}_{{{\text{max}}}}}$. Возможно, его можно уменьшить еще больше, найдя новые подпространства полиномиально разрешимых примеров. В [13], [14] получены соответствующие метрики для задач теории расписаний с функцией суммарного запаздывания.

2. ПОСТАНОВКА ЗАДАЧИ СУММАРНОГО ЗАПАЗДЫВАНИЯ ДЛЯ ОДНОГО ПРИБОРА

Необходимо обслужить $n$ требований на одном приборе. Прерывания обслуживания требований, искусственные простои прибора при обслуживании и обслуживание более одного требования в любой момент времени запрещены. Требования пронумерованы числами $1,2, \ldots ,n$. Множество $N = \{ 1,2, \ldots ,n\} $ назовем множеством требований.

Для требования $j \in N$ заданы следующие параметры: продолжительность обслуживания ${{p}_{j}} > 0$ и директивный срок окончания обслуживания ${{d}_{j}}$. Задан момент начала обслуживания ${{t}_{0}}$, с которого прибор готов начать обслуживание требований. Все требования поступают на обслуживание одновременно в момент времени ${{t}_{0}}$.

Расписание обслуживания требований множества $N$ задается кусочно-постоянной непрерывной слева функцией $s:\mathbb{R} \to \{ 0,1, \ldots ,n\} $. Если $s(t) = 0$, то в момент времени $t$ прибор простаивает; если $s(t) = j$, $j \in N$, то в момент времени $t$ прибор обслуживает требование $j$. Поскольку в рассматриваемой задаче требования поступают на обслуживание одновременно, обслуживаются на приборе без прерываний и искусственных простоев прибора, то расписание однозначно задается перестановкой $\pi $ элементов множества $N$. Далее в работе понятие расписания и перестановки множества требований будем отождествлять и называть расписанием перестановку $\pi $.

Индивидуальный пример исследуемой задачи (далее пример) c заданными множеством требований $N$, продолжительностями обслуживания ${{p}_{j}}$, директивными сроками ${{d}_{j}}$ и моментом начала обслуживания ${{t}_{0}}$ будем обозначать через $I = \left\langle {{{{\{ {{p}_{j}},{{d}_{j}}\} }}_{{j \in N}}},{{t}_{0}}} \right\rangle $. В случае, если параметры требований фиксированы (однозначно определены), для обозначения примера $I$ будем использовать запись $\{ N,{{t}_{0}}\} $. Множество всех $n!$ расписаний для примера $I$ будем обозначать через $\Pi (I)$.

Через ${{C}_{j}}(\pi )$ будем обозначать момент окончания обслуживания требования $j$ при расписании $\pi $. Моменты окончания обслуживания требований при расписании $\pi = ({{j}_{1}}, \ldots ,{{j}_{n}})$ вычисляются следующим образом:

Если обслуживание требования $i$ предшествует обслуживанию требования $j$ при расписании $\pi $ (т.е. выполняется ${{C}_{i}}(\pi ) < {{C}_{j}}(\pi )$), то будем использовать запись ${{(i \to j)}_{\pi }}$. Используя это обозначение, момент окончания обслуживания требования $j \in N$ при расписании $\pi $ можно записать как ${{C}_{j}}(\pi ) = {{t}_{0}} + \sum\nolimits_{i \in N:{{{(i \to j)}}_{\pi }}} {{{p}_{i}} + {{p}_{j}}} $. Обслуживание всех требований примера $I$ завершается в момент времени ${{t}_{0}} + \sum\nolimits_{j \in N} {{{p}_{j}}} $ при любом расписании $\pi \in \Pi (I)$.

Под запаздыванием требования $j \in N$ при расписании $\pi $ будем понимать величину

Суммарное запаздывание требований при расписании $\pi $ определяется как

Задача минимизации суммарного запаздывания заключается в построении оптимального расписания $\pi {\kern 1pt} * \in \Pi (I)$, при котором выполняется неравенство $F(\pi {\kern 1pt} *) \leqslant F(\pi )$ для всех расписаний $\pi \in \Pi (I)$. Отметим, что данная задача является $NP$-трудной (см. [15]). Известен псевдополиномиальный алгоритм ее решения (см. [16]) трудоемкости $O\left( {{{n}^{4}}\sum\nolimits_{j \in N} {{{p}_{j}}} } \right)$ операций, в случае когда $p_{j}^{{}} \in {{\mathbb{Z}}^{ + }}$ $\forall j \in N$, основанный на методе динамического программирования.

Через $\Pi {\kern 1pt} *{\kern 1pt} (I)$ будем обозначать множество всех оптимальных расписаний для примера $I$. Для обозначения величины оптимального суммарного запаздывания примера $I$ будем использовать запись $F{\kern 1pt} *{\kern 1pt} (I)$.

Покажем, что без ограничения общности рассуждений можно предполагать, что рассматриваются только те примеры $I$, для которых выполняется

В случае, если для примера $I$ условия (2.1) не выполняются, построим пример $I{\kern 1pt} ' = \left\langle {{{{\{ {{p}_{j}},d_{j}^{'}\} }}_{{j \in N}}},{{t}_{0}}} \right\rangle $ такой, что Если для некоторого требования $j \in N$ выполняется ${{d}_{j}} > {{t}_{0}} + \sum\nolimits_{i \in N} {{{p}_{i}}} $, то имеем $d_{j}^{'} = {{t}_{0}} + \sum\nolimits_{i \in N} {{{p}_{i}}} $. Это означает, что требование $j$ не запаздывает при любом расписании $\pi $ для обоих примеров $I$ и $I{\kern 1pt} '$. Таким образом, можно исключить такое требование $j$ из рассмотрения и после построения оптимального расписания для редуцированного примера добавить требование $j$ на последнюю позицию в построенное расписание.

Если для некоторого требования $j \in N$ выполняется ${{d}_{j}} < {{t}_{0}}$, то имеем $d_{j}^{'} = {{t}_{0}}$, и требование $j$ запаздывает при любом расписании $\pi $. Лоулером в [16] была доказана следующая

Теорема 1 (см. [16]). Пусть $\pi {\kern 1pt} *$ – оптимальное расписание примера ${{I}_{1}} = \left\langle {{{{\{ {{p}_{j}},{{d}_{j}}\} }}_{{j \in N}}},{{t}_{0}}} \right\rangle $. Выберем величины $d_{j}^{'}$ так, что

Тогда любое оптимальное расписание примера ${{I}_{2}} = \left\langle {{{{\{ {{p}_{j}},d_{j}^{'}\} }}_{{j \in N}}},{{t}_{0}}} \right\rangle $ будет оптимальным и для примера ${{I}_{1}}$.

В нашем случае условия (2.2) для примеров $I$ и $I{\kern 1pt} '$ выполняются, поскольку при любом расписании $\pi $ справедливо неравенство ${{t}_{0}} < {{C}_{j}}(\pi ) \leqslant {{t}_{0}} + \sum\nolimits_{i \in N} {{{p}_{i}}} $, $j \in N$. Следовательно, любое оптимальное расписание для примера $I{\kern 1pt} '$ будет оптимальным и для примера $I$. Таким образом, параметры требований примера $I{\kern 1pt} '$ удовлетворяют условиям (2.1) и выполняется $\Pi {\kern 1pt} *{\kern 1pt} (I{\kern 1pt} ') \subseteq \Pi {\kern 1pt} *{\kern 1pt} (I)$.

Необходимо заметить, что не любое оптимальное расписание примера $I$ будет оптимальным и для примера $I{\kern 1pt} '$.

Как следствие теоремы 1, может быть сформулирована

Лемма 1. Для любого оптимального расписания $\pi $ и любого незапаздывающего требования $j$ верно: все требования, которые обслуживаются в интервале $[{{C}_{j}}(\pi ),{{d}_{j}}]$ не запаздывают.

Данная лемма легко доказывается от противного.

Два примера $I = \left\langle {{{{\{ {{p}_{j}},{{d}_{j}}\} }}_{{j \in N}}},{{t}_{0}}} \right\rangle $ и $I{\kern 1pt} ' = \left\langle {{{{\{ p_{j}^{'},d_{j}^{'}\} }}_{{j \in N}}},t_{0}^{'}} \right\rangle $ будем называть равными, если множества оптимальных расписаний для обоих примеров совпадают, т.е. $\Pi {\kern 1pt} *{\kern 1pt} (I) = \Pi {\kern 1pt} *{\kern 1pt} (I{\kern 1pt} ')$. Через $T_{j}^{'}(\pi )$ будем обозначать значение запаздывания требования $j$ при некотором расписании $\pi $, вычисленное для примера $I{\kern 1pt} '$. В рамках данного исследования будут полезны следующие случаи равенства примеров.

(1) Примеры $I$ и $I{\kern 1pt} '$ равны, если $p_{j}^{'} = {{p}_{j}}$, $d_{j}^{'} = {{d}_{j}} + C$, $j \in N$, и $t_{0}^{'} = {{t}_{0}} + C$, где $C$ – произвольная константа. Действительно, в этом случае для любого расписания $\pi $ и любого требования $j \in N$, обслуживаемого при расписании $\pi $, выполняется

Следовательно, $F{\kern 1pt} *{\kern 1pt} (I) = F{\kern 1pt} *{\kern 1pt} (I{\kern 1pt} ')$ и $\Pi {\kern 1pt} *{\kern 1pt} (I) = \Pi {\kern 1pt} *{\kern 1pt} (I{\kern 1pt} ')$. В этом смысле без потери общности момент начала обслуживания требований можно считать равным нулю: ${{t}_{0}} = 0$. Если требуется выполнение некоторых условий относительно директивных сроков, например ${{d}_{j}} \in {{\mathbb{Z}}^{ + }}$, то это обычно достигается путем изменения момента начала обслуживания ${{t}_{0}}$. Поэтому в работе мы будем предполагать, что ${{t}_{0}}$ – произвольная величина.

(2) Примеры $I$ и $I{\kern 1pt} '$ равны, если $p_{j}^{'} = \alpha {{p}_{j}}$, $d_{j}^{'} = \alpha {{d}_{j}}$, $j \in N$, и $t_{0}^{'} = \alpha {{t}_{0}}$, где $\alpha > 0$ – произвольная положительная константа. Действительно, в этом случае для любого расписания $\pi $ и любого требования $j \in N$, обслуживаемого при расписании $\pi $, выполняется

Следовательно, $F{\kern 1pt} *{\kern 1pt} (I) = \alpha F{\kern 1pt} *{\kern 1pt} (I{\kern 1pt} ')$ и $\Pi {\kern 1pt} *{\kern 1pt} (I) = \Pi {\kern 1pt} *{\kern 1pt} (I{\kern 1pt} ')$. Рассмотрим любой пример $I$ как точку в $(2n + 1)$-мерном евклидовом пространстве с координатами $({{t}_{0}},{{p}_{1}}, \ldots ,{{p}_{n}},{{d}_{1}}, \ldots ,{{d}_{n}})$. Тогда все примеры (точки), расположенные на луче, исходящем из нуля пространства, равны между собой (фиг. 1). Поэтому можно предполагать, что рассматриваются только те примеры (точки), которые лежат на поверхности единичной сферы в рассматриваемом пространстве. Однако в общем случае данный подход неприемлем при построении оптимального расписания некоторым алгоритмом, для работы которого необходимо, чтобы продолжительности обслуживания требований были целочисленными величинами. Поэтому ограничимся выбором константы $\alpha = 1{\text{/НОД}}({{p}_{1}}, \ldots ,{{p}_{n}})$, где НОД – наибольший общий делитель.

Необходимо также отметить, что для любых двух равных примеров $I$ и $I{\kern 1pt} '$ выполняется свойство: если требование при оптимальном расписании $\pi $ примера $I$ запаздывает (не запаздывает), то и в примере $I{\kern 1pt} '$ при расписании $\pi $ требование запаздывает (не запаздывает). Доказательство этого можно провести от противного.

Введем некоторые дополнительные обозначения и понятия.

Расписание $\pi $ будем называть $SPT$-расписанием (Shortest Processing Time) и обозначать через ${{\pi }_{{spt}}}$, если требования упорядочены при данном расписании в порядке неубывания продолжительностей обслуживания, т.е. для любых двух требований $i$ и $j$ таких, что ${{p}_{i}} < {{p}_{j}}$, выполняется ${{(i \to j)}_{{{{\pi }_{{spt}}}}}}$.

Расписание $\pi $ будем называть $EDD$-расписанием (Earliest Due Date) и обозначать через ${{\pi }_{{edd}}}$, если требования упорядочены при данном расписании в порядке неубывания директивных сроков, т.е. для любых двух требований $i$ и $j$ таких, что ${{d}_{i}} < {{d}_{j}}$, выполняется ${{(i \to j)}_{{{{\pi }_{{edd}}}}}}$.

Через $\{ \pi \} $ будем обозначать множество требований, упорядоченных при расписании $\pi $. В случае $\{ \pi \} \ne N$ ($\{ \pi \} \subset N$) расписание $\pi $ будем называть частичным расписанием.

Запись ${{(i \to j)}_{\pi }}$ при необходимости будет расширена до ${{(i \to j \to k)}_{\pi }}$ для обозначения порядка обслуживания более, чем двух требований при некотором расписании $\pi $. Также будем использовать записи ${{(j \to N{\kern 1pt} ')}_{\pi }}$ или ${{(N{\kern 1pt} ' \to N{\kern 1pt} '{\kern 1pt} ')}_{\pi }}$ для обозначения порядка обслуживания между некоторыми подмножествами требований.

Для обозначения структуры расписания $\pi $ будем использовать запись $\pi = ({{\pi }_{1}}, \ldots ,{{\pi }_{m}})$, где расписание ${{\pi }_{i}}$, $i = 1,2, \ldots ,m$, является частичным расписанием (подрасписанием расписания $\pi $). При этом для частичных расписаний ${{\pi }_{i}}$ выполняется $\{ \pi \} = \bigcup\nolimits_{i = 1}^m {\{ {{\pi }_{i}}\} } $, $\{ {{\pi }_{i}}\} \cap \{ {{\pi }_{j}}\} = \not {0}$ для $i \ne j$, ${{(\{ {{\pi }_{1}}\} \to \ldots \to \{ {{\pi }_{m}}\} )}_{\pi }}$, и требования каждого частичного расписания ${{\pi }_{i}}$, $i = 1,2, \ldots ,m$, упорядочены в том же порядке, что и при расписании $\pi $. Для обозначения структуры расписания $\pi $ относительно некоторого требования $j \in \{ \pi \} $ будем использовать запись $\pi = ({{\pi }_{1}},j,{{\pi }_{2}})$.

Пользуясь нотацией, предложенной в [17], для обозначения исследуемой задачи будем использовать запись $1\,{\text{|}}{\kern 1pt} {\text{|}}\,\sum {{{T}_{j}}} $. Рассматриваемая задача $1\,{\text{|}}{\kern 1pt} {\text{|}}\,\sum {{{T}_{j}}} $ является $NP$-трудной в обычном смысле (см. [15]).

В заключение данного раздела приведем пример связи рассматриваемой задачи для одного прибора $1\,{\text{|}}{\kern 1pt} {\text{|}}\,\sum {{{T}_{j}}} $ с некоторой задачей оптимального упорядочения набора требований, возникающей на практике. Рассмотрим некоторый обслуживающий центр (ОЦ), процесс работы которого разбит на циклы, состоящие из двух этапов. На первом этапе центр набирает заявки и на втором этапе осуществляет их исполнение. В ОЦ имеется $m$ однородных исполнителей, каждая заявка может быть исполнена любым из них. Исполнители обладают в общем случае различной производительностью и выполняют в любой момент времени не более одной заявки. Выполнение заявки не может быть прервано, т.е., если исполнитель начинает выполнение некоторой заявки, то он выполняет ее до конца. При приеме заявки ОЦ и клиент договариваются о сумме, которую ОЦ получит за выполнение заявки, а также о моменте времени, к которому заявка должна быть исполнена. При выполнении некоторой заявки позднее обговоренного момента времени ОЦ выплачивает клиенту фиксированный для любой заявки штраф за каждую единицу времени, прошедшую после этого момента. Целью составления расписания работы ОЦ является минимизация суммы штрафных выплат по всем принятым к исполнению заявкам.

Данная задача может быть сформулирована в терминах теории расписаний следующим образом. Задано множество требований $N = \{ 1,2, \ldots ,n\} $ и множество параллельных приборов $M = \{ 1,2, \ldots ,m\} $. Каждое требование $j \in N$ имеет директивный срок ${{d}_{j}}$, к которому желательно завершить обслуживание данного требования, и продолжительность ${{p}_{{ji}}}$ обслуживания требования $j$ на приборе $i \in M$. Требования обслуживаются на приборах без прерываний, в любой момент времени любой прибор обслуживает не более одного требования. Расписание обслуживания требований $\pi $ строится с момента времени ${{t}_{0}} = 0$ и для данной задачи может быть задано в виде набора из $m$ перестановок ${{\pi }_{1}}, \ldots ,{{\pi }_{m}}$, где ${{\pi }_{i}}$, $i \in M$, задает порядок обслуживания требований множества $\{ {{\pi }_{i}}\} $ на приборе $i$. При этом $\{ {{\pi }_{1}}\} , \ldots ,\{ {{\pi }_{m}}\} $ задает разбиение множества требований $N$ (т.е. $\bigcup\nolimits_{i \in M} {\{ {{\pi }_{i}}\} } = N$ и $\{ {{\pi }_{i}}\} \cap \{ {{\pi }_{j}}\} = \not {0}$ для $i,j \in M$, $i \ne j$). Момент окончания ${{C}_{j}}(\pi )$ требования $j \in N$ при расписании $\pi $ вычисляется описанным выше образом. Необходимо построить такое расписание обслуживания требований множества $N$ на приборах из множества $M$, при котором минимизируется суммарное запаздывание требований, т.е. $\sum\nolimits_{j \in N} {max\{ 0,{{C}_{j}}(\pi ) - {{d}_{j}}\} } \to min$.

Имея некоторый алгоритм, основанный, например, на идее метода ветвей и границ, для задачи суммарного запаздывания для параллельных приборов было бы желательно иметь некоторый способ вычисления нижних оценок оптимального значения целевой функции. Это может быть сделано с помощью использования методов решения и построения оценок для примеров задачи $1\,{\text{|}}{\kern 1pt} {\text{|}}\,\sum {{{T}_{j}}} $. Однако алгоритм решения задачи суммарного запаздывания для параллельных приборов может быть организован так, что сначала строится разбиение множества требований $N$ на $m$ подмножеств, которые будут обслуживаться на соответствующих приборах, а затем решается $m$ независимых примеров задачи $1\,{\text{|}}{\kern 1pt} {\text{|}}\,\sum {{{T}_{j}}} $. В этом случае исходная задача для многих приборов допускает разбиение на несколько независимых подзадач для одного прибора.

3. МЕТРИКА ДЛЯ ЗАДАЧИ $1\left| {{{r}_{j}}} \right|\sum {{{T}_{j}}} $