Scheduling calculations for a multiprocessor system in real time

Введение. Главной отличительной чертой вычислительных систем реального времени является то, что каждый прикладной модуль должен выполняться в строго заданном временном директивном интервале и завершиться не позднее установленного заранее срока. Такие системы находят широкое применение в различных областях деятельности человека. Например, при проектировании, испытаниях и эксплуатации сложных технических объектов (самолеты, ракеты, электростанции), при проведении опытно-конструкторских работ, в гражданском и военном строительстве, при оценке запасов полезных ископаемых в месторождениях, при обработке больших массивов информации, при проектировании и функционировании транспортных и конвейерных систем, во многих других областях. При этом одна из основных задач заключается в распределении ресурсов вычислительной системы между программными модулями и построении оптимального расписания их выполнения. Алгоритмам решения таких задач посвящено большое количество публикаций. Здесь можно отметить такие фундаментальные работы, как [1—3], в которых авторы изучают различные постановки (составление расписаний с прерываниями и переключениями с одного процессора на другой и без прерываний, задачи на быстродействие и на соблюдение директивных сроков, построение однопроцессорных и многопроцессорных расписаний). В [3] исследуются NP-трудные задачи быстродействия и минимизации максимального временного смещения для одного и нескольких приборов. Предлагается новый подход к поиску приближенных решений. В [4, 5] рассматривается методика построения оптимальных расписаний в задачах с нефиксированными параметрами (длительности, потребляемые ресурсы). Методика основана на использовании метода “ветвей и границ” и построении многогранников устойчивости решений. В [6—8] разработана методика проверки выполнения ограничений реального времени, заключающихся в том, что каждая работа должна выполняться в заданном директивном интервале. Проведенные исследования выполнены для многоядерной вычислительной системы реального времени и базируются на построении имитационной модели с применением обобщенных конечных автоматов с остановкой таймера. С помощью этой модели строится временная диаграмма работы системы, позволяющая осуществить непосредственную проверку выполнения ограничений реального времени. В [8] предложен псевдополиномиальный алгоритм решения задачи построения оптимального по быстродействию расписания исполнения заданий с логическими условиями предшествования. В этой задаче для каждого задания дан список его непосредственных предшественников, а также число завершенных непосредственных предшественников, необходимое для начала его выполнения. Задача сведена к циклической игре. В [9, 10] некоторые задачи планирования работ сведены к минимаксным задачам.

Указанные выше публикации посвящены распределению возобновляемых ресурсов (процессоров, машин, исполнительных механизмов, приборов, рабочих), т.е. ресурсов, которые могут использоваться многократно. В ряде публикаций исследуются вопросы распределения невозобновляемых ресурсов (финансы, топливо, электроэнергия, различные материалы, оперативная память ЭВМ, закрепленная за определенными программными модулями). В отличие от возобновляемых ресурсов, невозобновляемые повторно применяться не могут. В этой связи отметим работы [11, 12], в которых предполагается, что длительности заданий линейно зависят от величины выделенного им ресурса. В [13] исследована задача со смешанными типами ресурсов — возобновляемыми и невозобновляемыми. Рассматривается задача составления допустимого расписания с прерываниями в многопроцессорной системе в случае, когда заданы директивные интервалы, процессоры могут иметь произвольные производительности, имеется несколько типов невозобновляемых ресурсов, а длительности выполнения работ линейно зависят от выделенного им количества этих ресурсов. Построены полиномиальные алгоритмы, основанные на сведéнии исходной задачи к потоковой в сети специального вида.

Отметим несколько интересных статей по планированию в промышленном производстве. Так, в [14] авторы исследовали методику совместного планирования развития производственных мощностей и составления расписания с учетом рыночных возможностей, а также детализировали интегрированную модель планирования мощности производства с несколькими дискретными и непрерывными вариантами изменения краткосрочной и среднесрочной мощности и разработали эвристический алгоритм, основанный на сведении исходной задачи к нелинейной смешанной целочисленной задаче. В [15] представлены некоторые вопросы в области планирования и контроля производства, разработана иерархическая архитектура планирования и управления производством. В [16] приведена двухуровневая система хранения одного продукта, с помощью которой региональный центр пополняет заказы нескольких независимых местных распределительных центров в течение установленного периода времени. Разработанная модель определяет значения цены продукта, обязательного времени пополнения и обязательного времени доставки, которые максимизируют ожидаемую общесистемную прибыль за заданный период с учетом затрат на хранение продукта и фиксированных затрат на оборудование.

В [17] исследована задача, в которой планирование осуществляется в два этапа: сначала определяется последовательность действий, затем в график вставляется время простоя, чтобы минимизировать сумму ранних и поздних затрат. Последовательность работ определяется с помощью эвристического метода, а задача вставки времени простоя решается с помощью линейного программирования для задания времени начала и окончания действий. В [18] приведена задача планирования сроков выполнения заказов, а также указаны компромиссы, которые следует учитывать при установлении этих сроков. Предложена модель, показывающая, как запланированное время выполнения операции зависит от стохастической изменчивости требований к ресурсам для этой операции, а также от использования ресурсов, связанных с этой операцией. В [19] описана задача планирования работы и маршрутизации двух роботов, которые доставляют продукты в определенные места. Решена задача минимизации времени выполнения всех операций и возврата роботов в исходное положение. Доказана NP-трудность задачи. Решение основано на использовании целочисленного линейного программирования и генетического алгоритма, а также динамического программирования для оценки качества решений.

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

1. Постановка задачи. В моменты времени ${\tau }_k$ поступают запросы на выполнение K комплексов работ (заданий): $W_k=\left\{w_k^1, w_k^2, \dots , w_k^{r_k}\right\}$, $k=\overline{\mathrm{1,} K}$, ${\tau }_1<{\tau }_2<\dots < {\tau }_K$. Для этого в каждом интервале $\left[{\tau }_k, {\tau }_{k+1}\right]$ имеется $m_k$ процессоров ( ${\tau }_{K+1}$ — момент времени, после которого эти процессоры использоваться не могут). Все процессоры идентичные. Каждое задание $w_k^i$ имеет следующие характеристики: $[b_k^i, c_k^i]$ — директивный интервал (работа $w_k^i$ может исполняться только в этом интервале), $b_k^i\ge$ ${\tau }_k$, $t_k^i$ — его длительность, $t_k^i\le c_k^i-b_k^i$, i $=\overline{\mathrm{1,} r_k}$. При выполнении заданий допускаются их прерывания и переключения с одного процессора на другой, которые по предположению не требуют временных затрат. Кроме того, не допускается параллельное исполнение одного задания несколькими процессорами и одновременное выполнение нескольких работ одним процессором.

Рассматриваются две постановки задачи. В каждой из них моменты ${\tau }_k$ известны заранее. Однако в первой постановке состав всех комплексов $W_k$ и характеристики входящих в них работ также известны заранее. Поэтому в данном случае планировать работу всех заданий можно до момента времени ${\tau }_1$. Во второй постановке состав комплекса заданий $W_k$ и их характеристики становятся известными только в момент ${\tau }_k$. Тогда планировать выполнение работ $W_k$ возможно только после поступления соответствующего запроса, который поступает в момент ${\tau }_k$, т.е. в режиме реального времени.

В обеих постановках требуется определить, существует ли допустимое расписание для всего комплекса работ:

$W={\displaystyle \underset{k=1}{\overset{K}{\cup }}{W}_k}$

(т.е. расписание, при котором каждое задание выполняется в своем директивном интервале) и построить его в случае положительного ответа. Предполагается, что временем работы самого алгоритма построения расписания в обоих случаях можно пренебречь.

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

2. Краткое описание полиномиального алгоритма поиска максимального потока в сети. Дана сеть $G=\left(V, A\right)$, V — множество вершин, u — источник, v — сток, $u, v \in V$, A — множество ориентированных дуг, $U\left(a, b\right)$ — пропускная способность дуги $\left(a, b\right)\in A$. В [20] предложен следующий полиномиальный алгоритм поиска максимального потока в сети G.

Шаг 1. Выбрать в качестве начального нулевой поток f, т.е. положить $f\left(a, b\right)=0$ для всех $\left(a, b\right)\in A.$

Шаг 2. Построить остаточную сеть $G\left(f\right)=\left(V, A\left(f\right)\right)$:

если $f\left(a, b\right)<U\left(a, b\right)$, то включить в $A\left(f\right)$ дугу $\left(a, b\right)$ с пропускной способностью $U\left(a, b\right)-f\left(a, b\right)$; если $f\left(a, b\right)>0$, то включить в $A\left(f\right)$ дугу $\left(b, a\right)$ с пропускной способностью $f\left(a, b\right)$.

Шаг 3. Если в сети $G\left(f\right)$ не существует прямого пути из u в v, то f — максимальный поток; алгоритм завершен. В противном случае перейти на шаг 4.

Шаг 4. Построить слоистую сеть $G^{*}\left(f\right)=\left(V^{*}\left(f\right), A^{*}\left(f\right)\right)$. Она содержит все кратчайшие ориентированные пути из u в v.

Шаг 5. Найти тупиковый поток g в сети $G^{*}\left(f\right)$. (Тупиковый поток — это поток, относительно которого нет прямого увеличивающего пути.)

Шаг 5.1. Определить узел $a_0\in V^{*}\left(f\right)$ с минимальной пропускной способностью. (Пропускная способность узла — это минимум из максимальной величины потока, который может войти в этот узел, и максимальной величины потока, который может выйти из него.)

Шаг 5.2. “Протолкнуть” из узла $a_0$ влево вплоть до источника u и вправо вплоть до стока v максимально возможный поток. Полученные при этом потоки по дугам определяют поток g.

Шаг 5.3. Удалить из сети $G^{*}\left(f\right)$ узел $a_0$ и все другие узлы с нулевой остаточной пропускной способностью, инцидентные этим узлам дуги, все полностью насыщенные дуги, образовавшиеся “висячие” узлы (если таковые имеются) и все инцидентные им дуги.

Шаг 5.4. Если существует путь из u и v в оставшейся части сети $G^{*}\left(f\right)$, то перейти на шаг 5.1. В противном случае тупиковый поток g в сети $G^{*}\left(f\right)$ построен.

Шаг 6. Произвести коррекцию потока f в сети G:

если дуге $\left(a, b\right)\in A$ соответствует дуга $\left(a, b\right)\in A^{*}\left(f\right)$, то положить $f\left(a, b\right)=f\left(a, b\right)+ g\left(a, b\right)$; если дуге $\left(a, b\right)\in A$ соответствует дуга $\left(b, a\right)\in A^{*}\left(f\right)$, то положить $f\left(a, b\right)=f\left(a, b\right)- g\left(b, a\right)$. Перейти на шаг 2.

Вычислительная сложность описанного алгоритма составляет $O\left({\left|V\right|}^3\right)$.

3. Краткое описание алгоритма В.С. Танаева построения допустимого расписания. Дальнейшее исследование поставленной задачи основано на использовании алгоритма В.С. Танаева построения допустимого многопроцессорного расписания с прерываниями и переключениями [1]. Приведем краткое описание этого алгоритма для сформулированной в разд. 1 задачи при $K=1$. Будем предполагать, что в этом случае множество работ $W=\left\{w_1, w_2, \dots , w_n\right\}$, их длительности $t_i$ и директивные интервалы $\left[b_i, c_i\right]$, m — число идентичных процессоров.

Пусть $y_0<y_1<\dots <y_p$ — все различные величины $b_i, c_i$, $i=\overline{\mathrm{1,} n}$, $I_j=\left[y_{j-1}, y_j\right],$ ${\delta }_j=y_j-y_{j-1},$ $j=\overline{\mathrm{1,} p}$. Строится потоковая сеть $G=\left(V, A\right)$ (см. рисунок), где $V=\left\{u, I_j, w_i, v\right\}$ —множество вершин, u — источник, v — сток, $A=\{\left(u, I_j\right), \left(I_j, w_i\right),$ ( $w_i, v)\}$ — множество ориентированных дуг. Дуга $\left(I_j, w_i\right)$ вводится в сеть, если $I_j\in \left[b_i, c_i\right]$. Отметим, что при всех j и i либо $I_j\in \left[b_i, c_i\right]$, либо $I_j\cap \left[b_i, c_i\right]=\varnothing$. Пропускные способности U Î дуг определяются следующим образом: $U\left(u, I_j\right)=m{\delta }_j$, $U\left(I_j, w_i\right)= {\delta }_j$, $U$ ( $w_i, v)=t_i$.

Рисунок. Потоковая сеть G для поиска допустимого расписания

В [1] доказано, что допустимое расписание существует в том и только том случае, когда максимальный поток f в сети G насыщает все выходные дуги ( $w_i, v)$, т.е. когда $f\left(w_i, v\right)=t_i$ при всех $i=\overline{\mathrm{1,} n}$. Величина $f\left(I_j, w_i\right)$ равна процессорному времени, выделяемому работе $w_i$ в интервале $I_j$. Для построения допустимого расписания следует в каждом интервале $I_j$ применить алгоритм упаковки [1], вычислительная сложность которого составляет $O\left(n\right)$. Для поиска максимального потока в сети G можно использовать полиномиальный алгоритм, описанный в разд. 2. Поскольку $p\le 2n$, то вычислительная сложность алгоритма В.С. Танаева в этом случае составляет $O\left(n^3\right)$.

4. Построение расписания для случая, когда информация о множествах ${\mathit{W}}_{\mathbf{k}}$, $\mathit{k}\mathbf{=}\overline{\mathbf{1}\mathbf{,}\mathbf{ }\mathbf{K}}$, поступает до момента τ₁. Рассмотрим случай, когда заранее (т.е. до момента времени ${\tau }_1$ ) известны состав всех множеств $W_k$ и характеристики входящих в них работ. В этом случае еще до поступления запросов на выполнение работ $W_k$ в моменты времени ${\tau }_k$ (т.е. до момента времени ${\tau }_1$ ) можно составить расписание для всего комплекса заданий W.

Пусть $y_k^j$ — это все различные величины ${\tau }_k$, $b_k^i$ и $c_k^i$, $k=\overline{\mathrm{1,} K},$ $i=\overline{\mathrm{1,} r_k}$. Далее, так же как в разд. 3, определяются интервалы $I_k^j$ и потоковая сеть $G_k=\left(V_k, A_k\right)$, где $V_k=\left\{u, v, I_k^j, w_k^i, j=\overline{\mathrm{1,} p_k}\right\}$ — множество узлов, u — источник, v — сток, $A_k=\left\{\left(u, I_k^j\right), \left(I_k^j, w_k^i\right), \left(w_k^i, v\right)\right\}$ — множество ориентированных дуг. Дуга $\left(I_k^j, w_k^i\right)$ вводится в сеть $G_k$, если $I_k^j[b_k^i$ Î $I_k^j[b_k^i$, $c_k^i]$.

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

$O\left({\left({\displaystyle \sum }_{k=1}^K{r}_k\right)}^3\right).$

5. Построение расписания для случая, когда информация о множестве ${\mathit{W}}_{\mathbf{k}}$ поступает в момент τ_k, $\mathit{k}\mathbf{=}\overline{\mathbf{1}\mathbf{,}\mathbf{ }\mathbf{K}}$. Рассматривается случай, когда моменты ${\tau }_k$ поступления запросов на выполнение работ $W_k$ известны заранее, а состав каждого множества $W_k$ и характеристики входящих в него заданий становятся известными только в момент ${\tau }_k$. Сначала рассмотрим задачу построения расписания для $W_1$.

5.1. Построение сетевой модели и допустимого расписания для $W_1$. Пусть $y_1^0<y_1^1<\dots <y_1^{p_1}$ — все различные величины среди ${\tau }_1,$ ${\tau }_2$, $b_1^i$, $c_1^i$, $i=\overline{\mathrm{1,} r_1}$, принадлежащие интервалу $\left[{\tau }_1, {\tau }_2\right]$. Определим интервалы $I_1^j=\left[y_1^{j-1}, y_1^j\right]$, $j=\overline{\mathrm{1,} p_1}$, и сеть $G_1=\left(V_1, A_1\right)$, где $V_1=\left\{u, v, I_1^j, w_1^i\right\},$ а множество ориентированных дуг $A_1$ и их пропускные способности $U_1\left(i, j\right)$ определяются по аналогии с тем, как это сделано в разд. 3 при $m=m_1$, $n=r_1$.

При нахождении максимального потока $f_1$ в сети $G_1$ используется следующая модификация алгоритма, описанного в разд. 2. При проталкивании потока из вершины $I_1^j$ вправо (шаг 5.2 разд. 2) в первую очередь следует использовать дуги $(I_1^j, w_1^i)$ для работ $w_1^i$, у которых $c_1^i\le {\tau }_2$. Это объясняется тем, что такие задания могут выполняться только в интервале $\left[{\tau }_1, {\tau }_2\right]$, а работам с директивным сроком, большим ${\tau }_2$, процессорное время может выделяться и после момента ${\tau }_2$.

Величина потока $f_1(I_1^j, w_1^i)$ равна объему процессорного времени, выделенному работе $w_1^i$ в интервале $I_1^j$. Расписание в интервале $I_1^j$ строится с помощью алгоритма упаковки.

Если хотя бы для одной работы $w_1^i$ с директивным сроком $c_1^i\le {\tau }_2$ оказалось, что $f_1\left(w_1^i, v\right)<t_1^i$ (т.е. дуга $\left(w_1^i, v\right)$ насыщена не полностью), то допустимого расписания для $W_1$, и, следовательно, для всего комплекса заданий W не существует. В случае когда $f_1\left(w_1^i, v\right)=t_1^i$ для всех работ $w_1^i$ с директивным сроком $c_1^i\le {\tau }_2$, построение допустимого расписания продолжится в момент ${\tau }_2$ для незавершенных работ из $W_1$ (если таковые имеются) и вновь поступивших работ из $W_2$.

5.2. Построение сетевой модели и допустимого расписания для $W_1\cup \dots \cup W_k, k=\overline{\mathrm{2,} K}$. Предположим, что построена потоковая сеть $G_{k-1}, k=\overline{\mathrm{2,} K}$, и в ней найден максимальный поток $f_{k-1}$. Если хотя бы для одной работы $w_r^i, r=\overline{\mathrm{2,} k-1}$, для которой $c_r^i\le {\tau }_k$, после нахождения максимального потока $f_{k-1}$ в сети $G_{k-1}$ оказалось, что $f_{k-1}\left(w_r^i, v\right)<t_r^i$, т.е. дуга $\left(w_r^i, v\right)$ насыщена не полностью, то допустимого расписания для $W_1\cup \dots \cup W_{k-1}$, и, следовательно, для всего комплекса W не существует. Если же $f_{k-1}\left(w_r^i, v\right)=t_r^i$ для всех дуг $\left(w_r^i, v\right)$, $r=\overline{\mathrm{1,} k-1}$, для которых $c_r^i\le {\tau }_{k-1}$, то построение допустимого расписания для W продолжается в момент ${\tau }_k$ для незавершенных работ из множества $W_1\cup \dots \cup W_{k-1}$ (если таковые имеются) и вновь поступивших заданий из $W_k$.

Пусть $y_k^0<y_k^1<\dots <y_k^{p_k}$ — все различные величины ${\tau }_k,$ ${\tau }_{k+1}$, $b_k^i$, $c_k^i$, $i=\overline{\mathrm{1,} r_k}$. Определим интервалы $I_k^j=\left[y_k^{j-1}, y_k^j\right]$ и пусть ${\delta }_k^j=y_k^j- y_k^{j-1}$. Из сети $G_{k-1}$ удалим следующие элементы: узлы $I_{k-1}^j$, $j=\overline{\mathrm{1,} p_{k-1}}$, и все инцидентные им дуги $\left(u, I_{k-1}^j\right)$, $\left(I_{k-1}^j, w_{k-1}^i\right)$, $j=\overline{\mathrm{1,} p_k}$ , $i=\overline{\mathrm{1,} r_{k-1}}$; узлы $w_z^i$, для которых

 $f_{k-1}\left(w_z^i, v\right)=t_z^i$, (5.1)

и соответствующие дуги $\left(w_z^i, v\right)$, $z=\overline{\mathrm{1,} k-1}$, $i=\overline{\mathrm{1,} r_z}$ (поскольку выполнение условия (5.1) означает завершение работы $w_z^i$ ).

Далее, длительности каждой оставшейся работы $w_z^i$ уменьшаются на величину потока $f_{k-1}\left(w_z^i, v\right)$ по дуге $\left(w_z^i, v\right)$. Сеть $G_k$ строится из оставшейся не удаленной части сети $G_{k-1}$ путем добавления к ней узлов $I_k^j$, $w_k^i$ и дуг $\left(I_k^j, w_z^i\right)$, $j=\overline{\mathrm{1,} p_k}$, $i=\overline{\mathrm{1,} r_z}$, $z=\overline{\mathrm{1,} k}$, $\left(w_k^i, v\right)$, $i=\overline{\mathrm{1,} r_k}$, по аналогии с тем, как это описано в разд. 3 при $m=m_k$, n = n_k + (число оставшихся вершин в G_k–1). В сети $G_k$ находится максимальный поток $f_k$. По аналогии с разд. 5.1 при проталкивании потока из вершины $I_k^j$ вправо (шаг 5.2 разд. 2) в первую очередь следует использовать дуги $\left(I_k^j, w_k^i\right)$ для работ $w_k^i$, у которых $c_k^j\le {\tau }_{k+1}$. Величина потока $f_k\left(I_k^j, w_k^i\right)$ равна объему процессорного времени, выделяемому работе $w_k^i$ в интервале $I_k^j$. Расписание выполнения работ в интервале $I_k^j$ находится с помощью алгоритма упаковки [1].

Вычислительная сложность предложенного алгоритма составляет

$O\left(K{\left({\displaystyle \sum }_{k=1}^K{r}_k\right)}^3\right).$

6. Распределение неоднородного комплекса ресурсов. Предполагается, что при выполнении работ помимо процессоров используется невозобновляемый ресурс, количество которого в интервале $\left[{\tau }_k, {\tau }_{k+1}\right]$ составляет $S_k$, $k=\overline{\mathrm{1,} K}$. Работе $w_k^i$ невозобновляемый ресурс может быть выделен только в момент времени ${\tau }_k$. Если его объем составляет $s_k^i$, то длительность выполнения задания $w_k^i$ равна

 $t_k^i={\phi }_k^i\left(s_k^i\right)$, (6.1)

где

 $s_k^iϵ\left[\mathrm{0,} {\overline{s}}_k^i\right]$, (6.2)

 ${\displaystyle \sum }_{i=1}^{r_k}{s}_k^i \le S_k.$ (6.3)

Здесь ${\phi }_k^i$ — строго убывающая на интервале $\left[\mathrm{0,} {\overline{s}}_k^i\right]$ функция, принимающая положительные значения, ${\overline{s}}_k^i$ — заданные величины, $i=\overline{\mathrm{1,} r_k}$.

В этих предположениях для решения задачи, поставленной в разд. 1, нам понадобится обобщение алгоритма В.С. Танаева.

6.1. Обобщение алгоритма В.С. Танаева на случай наличия невозобновляемого ресурса. Будем использовать обозначения, введенные в разд. 3. Кроме того, символы $t_k^i$, $s_k^i$, ${\overline{s}}_k^i$, $S_k$, ${\phi }_k^i$, $W_k$, $w_k^i$ заменим на $t_i$, $s_i$, $\overline{s_i}$, $S$, ${\phi }_i$, $W$, $w_i$ соответственно. В этом случае ограничения (6.1)—(6.3) записываются следующим образом:

 $t_i={\phi }_i\left(s_i\right)$, (6.4)

 $s_iϵ\left[\mathrm{0,} \overline{s_i}\right]$, (6.5)

 ${\displaystyle \sum }_{i=1}^n{s}_i\le S.$ (6.6)

Докажем следующие утверждения.

Лемма 1. Допустимое расписание выполнения множества работ W в задаче без невозобновляемого ресурса (без ограничений (6.4)—(6.6)), при котором заданию $w_i$ предоставляется процессорное время в объеме $f_i$, существует в том и только том случае, когда в сети G существует поток $f\left(a, b\right), \left(a,b\right)ϵA$, такой, что выполнены равенства

 $f\left(w_i, v\right)=f_i$ (6.7)

при всех $i=\overline{\mathrm{1,} n}$.

Доказательство следует из [1]. Пусть ${\phi }_i^{-1}\left(s_i\right)$ — функция, обратная по отношению к ${\phi }_i\left(s_i\right)$.

Лемма 2. Допустимое расписание выполнения множества работ W в задаче с невозобновляемым ресурсом (с учетом ограничений (6.4)—(6.6)), при котором заданию $w_i$ предоставляется процессорное время в объеме $f_i$, существует в том и только том случае, когда в сети G существует поток $f\left(a, b\right), \left(a,b\right)ϵA$, такой, что справедливы равенства (6.7) и неравенства

 ${\displaystyle \sum }_{i=1}^n{\phi }_i^{-1}(f_i)\le S,$ (6.8)

 ${\phi }_i^{-1}\left(f_i\right)\le \overline{s_i}$, $i=\overline{\mathrm{1,} n}$. (6.9)

Доказательство. 1. Пусть в сети G существует поток f, для которого справедливы соотношения (6.7)—(6.9). В этом случае из (6.8) следует, что каждой работе $w_i$ может быть выделен невозобновляемый ресурс в объеме $s_i= {\phi }_i^{-1}\left(f_i\right)$. При этом будет справедливо неравенство (6.6), а в силу (6.4) длительность выполнения работы $w_i$ (т.е. требуемое процессорное время) составит ${\phi }_i\left({\phi }_i^{-1}\left(f_i\right)\right)=f_i$. Поскольку ${\phi }_i^{-1}\left(f_i\right)=s_i$, то из (6.9) вытекает (6.5). Тогда из леммы 1 следует существование допустимого расписания для W с учетом ограничений (6.4)—(6.6).

2. Пусть теперь существует допустимое расписание выполнения работ W в задаче с невозобновляемом ресурсом (с учетом ограничений (6.4)—(6.6)), при котором заданию $w_i$ выделяется процессорное время в объеме $f_i$. Пусть при этом работе $w_i$ выделен невозобновляемый ресурс в объеме $s_i$. Тогда в силу (6.4) $f_i={\phi }_i\left(s_i\right)$ или $s_i={\phi }_i^{-1}\left(f_i\right)$. В этом случае из (6.6) и (6.5) следуют неравенства (6.8) и (6.9) соответственно. Теперь доказательство вытекает из леммы 1. Лемма доказана.

Из (6.7), (6.9) следует, что при построении допустимого расписания в задаче с невозобновляемым ресурсом нужно искать поток f в сети G, для которого $f\left(w_i, v\right)=f_i\le \phi \left(\overline{s_i}\right)$ при всех $i=\overline{\mathrm{1,} n}$. С учетом того, что функции ${\phi }_i^{-1}\left(f_i\right)$ строго убывают, величины $f_i$ необходимо максимизировать. Поэтому для решения этой задачи предлагается следующий алгоритм.

В сети G сначала определяется вершина $w_{i_1}$, для которой величина максимального потока g из u в $w_i$ является наибольшей среди всех вершин $w_i$, $i=\overline{\mathrm{1,} n}$. Далее, номер $i_1$ включается в множество N и пропускные способности всех дуг $\left(a, b\right)ϵA$ сети G уменьшаются на величину $g\left(a, b\right)$. После чего данная процедура повторяется для вершин $w_i$, $i=\overline{\mathrm{1,} n}$, $iN$. Далее, выполняется проверка условия (6.8).

Алгоритм 1.

Шаг 1. В сети G положить $U\left(w_i,v\right)={\phi }_i\left(\overline{s_i}\right)$, $N=\varnothing$.

Шаг 2. Для $i_0=\overline{\mathrm{1,}n},i_0\in N$, выполнять шаги 3—5.

Шаг 3. Удалить из сети G все дуги $\left(w_i, v\right)$, $i=\overline{\mathrm{1,} n}$, $i\ne i_0$.

Шаг 4. Найти максимальный поток g в сети G и пусть $g_{i_0}$ — его величина.

Шаг 5. Включить в сеть G дуги, удаленные на шаге 3.

Шаг 6. Пусть $\underset{i_{\mathit{0}}=\overline{1\mathit{,}n}\mathit{,}\mathit{ }{i}_{\mathit{0}\mathit{\in }N}}{\min }{\mathrm{\phi }}_{i_{\mathit{0}}}^{-1}\left({\mathrm{g}}_{i_0}\right)={\mathrm{g}}_{i1}$. Включить $i_1$ в N. Положить $f_{i_1}=g\left(w_{i_1}, v\right)=g_i{}_1$. Пропускные способности $U\left(a, b\right)$ всех дуг $\left(a, b\right)ϵA$ сети G уменьшить на величину $g\left(a, b\right)$.

Шаг 7. Если $\left|N\right|<n$, то перейти на шаг 2. Если $\left|N\right|=n$, то перейти на шаг 8.

Шаг 8. Если выполнено неравенство (6.8), то допустимое расписание существует. При этом работе $w_i$ выделяется невозобновляемый ресурс в объеме ${\phi }_i^{-1}\left(f_i\right)$, $i=\overline{\mathrm{1,} n}$. Длительность выполнения работы $w_i$ составляет $f_i$. Расписание строится так, как описано в разд. 3. Если неравенство (6.8) не выполнено, то допустимого расписания не существует. Алгоритм завершен.

Вычислительная сложность алгоритма 1 составляет $O\left(n^5\right)$.

6.2. Обобщение исходной задачи на случай наличия нево-зобновляемого ресурса. Перейдем теперь к задаче, сформулированной в разд. 1, с дополнительными ограничениями (6.1)—(6.3), связанными с распределением невозобновляемого ресурса. Вновь вернемся к обозначениям $t_k^i$, $s_k^i$, ${\overline{s}}_k^i$, $S_k$, ${\phi }_k^i$, $W_k$, $w_k^i$, которые ранее были заменены на $t_i$, $s_i$, $\overline{s_i}$, $S$, ${\phi }_i$, $W$, $w_i$ соответственно.

С учетом исследований, проведенных в разд. 5.1, 5.2 и 6.1, предлагается следующий алгоритм решения исходной задачи, сформулированной в разд. 1, для случая наличия невозобновляемого ресурса.

Алгоритм 2.

Шаг 1. Положить $k=1$.

Шаг 2. Построить сеть $G_k$ (см. разд. 5.1, 5.2).

Шаг 3. Из сети $G_k$ удалить узлы $w_m^i$, соответствующие работам с директивным сроком $c_m^i>{\tau }_{k+1}$, и инцидентные им дуги.

Шаг 4. К полученной сети применить алгоритм 1. Если на шаге 8 алгоритма 1 выяснилось, что допустимого расписания не существует, то алгоритм 2 завершен, решения не существует. В противном случае перейти на шаг 5.

Шаг 5. Включить в сеть $G_k$ удаленные на шаге 3 узлы и дуги. Положить $k=k+1$. Если $k\le K$, то перейти на шаг 1. Если $k>K$, то решение построено. Алгоритм завершен.

Вычислительная сложность алгоритма 2 составляет

$O\left(K{\left({\displaystyle \sum }_{k=1}^K{r}_k\right)}^5\right).$

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