Однопроцессорные задачи синтеза расписаний обслуживания конечных детерминированных потоков заявок

Каноническая задача однопроцессорного обслуживания потока заявок.

Однопроцессорная система должна обслужить поток R = {1, 2,..., n } поступающих в дискретном времени заявок. Каждая заявка i характеризуется тремя целочисленными параметрами: t (i) – момент поступления в систему обслуживания (считается, что 0 = t (1) ≤ t (2) ≤... ≤ t (n)); τ (i) – требуемая продолжительность (число тактов дискретного времени) обслуживания процессором; а (i) – штраф за единицу времени (такт) пребывания заявки в системе обслуживания, здесь i =1,..., n. Если обслуживание произвольной заявки i завершается в момент времени t* (i), то величина индивидуального штрафа по этой за-явке считается равной а (i)⋅ [ t* (i) – t (i)]; таким образом, функция, определяющая величину индивидуального штрафа, линейна относительно времени пребывания заявки в системе обслуживания. Полагаем, что процессор П готов к обслуживанию заявок потока начиная от момента времени t = 0. Обслуживание каждой заявки можно выполнять с любого момента, начиная от момента ее поступления в систему. Обслуживание каждой заявки реализуется без прерываний, одновременное обслуживание процессором нескольких (более одной) заявок невозможно.

Расписание обслуживания отождествляем с перестановкой ρ = (i ₁, i ₂,..., i_n) элементов множества {1, 2,..., n }; заявка i_k в расписании ρ обслуживается k -й по очереди, k = 1,..., n. Обозначим через t _нач(ρ, i_k) и t* (ρ, i_k) моменты начала и завершения обслуживания заявки i_k при реализации расписания ρ, k = 1,..., n. Считаем, что реализация расписания компактна, т.е. имеют место соотношения:

t _нач(ρ, i ₁) = t(i ₁); (12)

t _нач(ρ, i_k) = max [ t* (ρ, i_{k − 1)}, t (i_k)], k = 2, 3,..., n; (13)

t* (ρ, i_k) = t _нач(ρ, i_k) + τ (i_k), k = 1, 2,..., n. (14)

Суммарный штраф по всем заявкам потока R, обслуживаемым согласно расписанию ρ, есть

Проблема заключается в минимизации суммарного штрафа, т.е. в нахождении

(15)

Задачу (15) именуем канонической задачей однопроцессорного обслуживания. Применим метод динамического программирования для ее решения.

Обозначим через V (t) определяемую исходными данными задачи совокупность заявок, поступающих на обслуживание в момент времени t. При этом V (0) – совокупность заявок, которые по состоянию на момент времени t = 0 присутствуют в системе и ожидают обслуживания.

Очевидно, что при обслуживании входного потока заявок управленческие решения принимаются для тех моментов дискретного времени, когда процессор свободен; каждое такое решение состоит в определении, какая заявка будет обслуживаться следующей. При этом текущая ситуация вполне характеризуется парой (t, S), где t – момент, для которого принимается решение (сокращенно МПР, в этот момент процессор свободен), а S – множество заявок, которые по состоянию на момент времени t прибыли и ожидают обслуживания. Пары (t, S), где t – МПР, а S – совокупность заявок, которые по состоянию на момент t прибыли и находятся в ожидании обслуживания, будем называть состояниями системы обслуживания.

Пусть Σ (t, S) обозначает минимальную величину суммарного штрафа по заявкам множества S и всем заявкам, поступающим в систему обслуживания позднее момента времени t для определяемой состоянием (t, S) ситуации. Как очевидно, Σ (0, V (0)) – оптимальное значение критерия в решаемой задаче (15).

Через D (t, μ) обозначим совокупность заявок, прибывающих в систему обслуживания на временном отрезке [ t + 1, t + μ ]. Ясно, что

Для любого состояния системы обслуживания (t, S) множество S считаем непустым, что обеспечивается обязательным включением в него фиктивной заявки 0 с параметрами а (0) = 0, t (0) = t и τ (0) = min {θ ⎢ D (t, t + θ) ≠ ∅ }. Взятие на обслуживание фиктивной заявки фактически означает простой процессора от момента t до ближайшего момента, когда в систему прибудет какая-либо новая заявка потока R. Если поступившая в момент t фиктивная заявка не принимается на немедленное обслуживание, она выпадает из дальнейшего рассмотрения.

Если в момент времени t на немедленное обслуживание процессором отправить заявку i, то:

1) величина штрафа по этой заявке окажется равной а (i)× [ t + τ (i) – t (i)];

2) следующим за t моментом принятия решения будет t + τ (i);

3) совокупность заявок, ожидающих обслуживания по состоянию на момент времени t + τ (i) запишется как (S \ i) ∪ D (t, τ (i)).

В принятых обозначениях рекуррентное соотношение динамического программирования записывается в виде

(16)

Если минимум реализуется при i = i*, то в МПР, характеризуемый парой (t, S), на процессор следует направить заявку i* из совокупности ожидающих обслуживания. Направление на обслуживание фиктивной (нулевой) заявки означает простой процессора по меньшей мере до следующего момента пополнения множества S вновь прибывающими заявками. Простой нередко оказывается целесообразным и в ситуациях наличия в S нефиктивных заявок непосредственно перед поступлением заявки с относительно большим значением характеристики a (i). Если в совокупности S имеется нефиктивная заявка, которая может быть завершена обслуживанием до следующего момента пополнения множества S вновь прибывшими заявками, то начало обслуживания в момент времени t фиктивной заявки нецелесообразно.

Реализации рекуррентной процедуры (16) должно предшествовать вычисление величин Σ (t (n), S) для всех возможных значений аргумента S, S ⊆ {1, 2,..., n }.

Задача построения оптимального от момента t (n) расписания – это задача мастера, рассмотренная в данной главе выше. Построение оптимального от момента t (n) расписания выполняется упорядочением не обслуженных по состоянию на этот момент заявок по убыванию значений показателя μ (i) = а (i)/τ (i). При известном расписании каждое значение Σ (t (n), S) вычисляется арифметически.

Далее отметим справедливость равенства

(17)

для любых θ > 0 и S ⊆ {1, 2, …, n }. Равенство (17) при известных значениях Σ (t (n), S) дает возможность элементарным образом вычислять нужные для счета по рекуррентному соотношению (16) величины Σ (t (n) + θ, S) для различных множеств S при θ > 0.

В реализации процедуры, определяемой формулой (16), последовательно, для всех возможных подмножеств заявок S, вычисляются значения Σ (t (n) – 1, S), Σ (t (n) – 2, S) и т.д. Процесс счета (16) заканчивается отысканием Σ (0, V (0)), т.е. оптимального значения критерия в решаемой задаче.

Дадим верхнюю оценку числа элементарных операций, выполняемых при вычислениях по соотношению (16) в процессе решения задачи. Эта оценка зависит от количества состояний (t, S), на которых подсчитываются значения функции Σ (t, S), и сложности вычисления каждого отдельного значения этой функции. При подсчетах по формуле (16) в рассматриваемых парах (t, S) первый аргумент принимает t (n) различных значений, число возможных значений второго аргумента оцениваем сверху как 2 ⁿ (полагаем, что S – произвольное подмножество заявок). Получаем, что верхней оценкой для числа подсчитываемых значений функции Σ (t, S) является t (n)× 2 ^n. Число элементарных операций, выполняемых при подсчете каждого очередного значения функции Σ (t, S), по верхней оценке зависит от n линейно. Таким образом, верхней оценкой числа реализуемых алгоритмом элементарных операций является С n t (n) 2 ⁿ, где С – не зависящая от n константа.

Приведенная оценка временной вычислительной сложности изложенного алгоритма экспоненциальна. Как будет показано в следующем примере, общий объем вычислений можно существенно сократить за счет достаточно просто выполняемой процедуры определения действительно необходимых наборов (t, S), на которых следует отыскивать значения функции Σ. Вместе с тем, построить алгоритм решения задачи (15) с полиномиально зависящей от n оценкой числа выполняемых им элементарных операций в принципе невозможно (рассматриваемая задача относится к числу NP-трудных, см. главу 3 данного пособия).

Пример 2.4.

Каноническая задача однопроцессорного обслуживания потока из пяти заявок характеризуется следующими данными: t (1) = 0, τ (1) = 2, а (1) = 3; t (2) = 0, τ (2) = 3, а (2) = 5; t (3) = 1, τ (3) = 1, а (3) = 7; t (4) = 3, τ (4) = 1, а (4) = 5; t (5) = 3, τ (5) = = 3, а (5) = 3. Требуется найти оптимальное расписание обслуживания.

Оптимальное значение критерия суммарного штрафа в решаемой задаче равно Σ (0, {1, 2}). Из (16) определяем, что для подсчета Σ (0, {1, 2}) необходимо (с учетом возможности принятия на обслуживание в момент времени 0 фиктивной заявки) предварительно найти значения Σ (1, {1, 2, 3}), Σ (2, {2, 3}), Σ (3, {1, 3, 4, 5}). Для отыскания величины Σ (1, {1, 2, 3}) необходимо предварительно определить только значение Σ (2, {1, 2}); действительно, принятие на обслуживание от момента времени 0 фиктивной заявки могло оказаться целесообразным только в случае, когда далее, от момента времени 1, будет проходить обслуживание заявки 3. Для отыскания величины Σ (2, {2, 3}) необходимо предварительно определить Σ (5, {3, 4, 5}) и Σ (3, {2, 4, 5});

фиктивную заявку в состоянии системы (2, {2, 3}) принимать на обслуживание заведомо нецелесообразно, лучше выбрать из очереди заявку 3 с единичной продолжительностью обслуживания. Для отыскания величины Σ (2, {1, 2}) необходимо предварительно определить Σ (3, {1, 2, 4, 5}), Σ (4, {2, 4, 5}) и Σ (5, {1, 4, 5}).

Вычислительную процедуру далее проводим следующим образом. Сначала, применяя алгоритм решения задачи мастера и пользуясь формулой (17), находим, что Σ (3, {1, 3, 4, 5}) = 73; Σ (5, {3, 4, 5}) = 76; Σ (3, {2, 4, 5}) = 61; Σ (3, {1, 2, 4, 5}) = 94; Σ (4, {2, 4, 5}) =74; Σ (3, {2, 4, 5}) = 61; Σ (5, {1, 4, 5}) = 63. Затем определяем нужные значения функции Σ (t, S) для значений t последовательно равных 2, 1 и 0. Начинаем с вычисления Σ (2, {1, 2}) и Σ (2, {2, 3}). При этом, согласно (16), Σ (2, { 1, 2}) = min(0 + 94, 12+74, 25 + 63) = 86 (минимум берется по трем суммам, причем первая сумма соответствует выбору фиктивной заявки, вторая сумма – выбору из числа ожидающих заявки 1, третья – выбору из числа ожидающих заявки 2; здесь и ниже в каждой сумме первое слагаемое – штраф по выбранной и принимаемой к немедленному исполнению заявке, второе слагаемое – значение Σ для следующего состояния системы; после определения минимума правой части соответствующую заявку в записи левой части подчеркиваем). Так как минимум реализуется на второй сумме, в состоянии (2, {1, 2}), на обслуживание следует направить заявку 1, в записи Σ (2, {1, 2}) подчеркиваем эту заявку. Затем имеем: Σ (2, {2, 3 }) = min(25 + 76, 14 + 61) = 75 (минимум берется по двум суммам, первая сумма соответствует выбору из числа ожидающих обслуживания заявки 2, вторая сумма - выбору заявки 3, фиктивная заявка здесь не может быть выбрана по выше описанной причине). Далее определяем Σ (1, {1, 2, 3 }) = = 7 + 86 = 93 (для МПР, характеризуемого парой (1, {1, 2, 3}) фактически имеется только один вариант действий – на обслуживание следует направить заявку 3). В итоге получаем: Σ (0, { 1, 2}) = = min (93, 6 + 75, 15 + 73) = 81. Нами определено оптимальное значение критерия в решаемом примере, оно равно 81.

Так как при подсчете значения Σ (0, {1, 2}) минимум реализуется на второй сумме, которая соответствует выбору заявки 1, в начальный МПР на обслуживание направляется заявка 1. Следующим состоянием системы будет (2, {2, 3}). При подсчете Σ (2, {2, 3}) мы отметили, что минимум реализуется на сумме, соответствующей выбору заявки 3. Поэтому в оптимальном расписании вслед за заявкой 1 на обслуживание процессором направляется заявка 3. Следующий МПР характеризуется парой (3, {2, 4, 5}). Так как по состоянию на момент времени 3 все подлежащие обслуживанию заявки уже прибыли, заявки совокупности {2, 4, 5} должны обслуживаться в порядке убывания значений показателя μ (i) = а (i)/τ (i). В итоге получаем оптимальное расписание обслуживания заявок: (1, 3, 4, 2, 5). Данное расписание обеспечивает минимальную, равную 81, величину суммарного штрафа.

Выполненное решение состоит из трех частей. В первой части сделана так называемая разметка, т.е. определены достижимые состояния (состояния, в которых система обслуживания может действительно оказаться). Во второй части с использованием алгоритма решения задачи мастера, формулы (17) и рекуррентного соотношения динамического программирования реализован процесс вычисления значений функции Σ (t, S) для достижимых состояний. Процедура разметки, как правило, существенно сокращает объем выполняемых вычислений. В третьей части определено оптимальное расписание.

Изложенный алгоритм решения канонической задачи одно-процессорного обслуживания потока заявок использует процедуру обратного счета – значения функции Σ (t, S) вычисляются в порядке убывания параметра t. Перейдем к изложению основанного на принципе динамического программирования алгоритма, решающего эту задачу методом прямого счета. Преимуществом алгоритма прямого счета является ненужность предварительного выполнения разметки. Запись соотношений динамического программирования для выполнения прямого счета в явном виде ниже делаться не будет, ибо весьма громоздкими являются описания множеств состояний, которые непосредственно предшествуют рассматриваемым.

Пусть Σ *(t, S) – минимально возможный суммарный штраф по всем обслуженным до момента времени t включительно заявкам, здесь t – произвольный МПР (в момент времени t процессор свободен), а S – совокупность заявок, которые по состоянию на момент t прибыли, но пока не прошли обслуживания. Отметим, что в частности Σ *(0, V (0)) = 0. Стандартными называем записи структуры < t, S, Σ *(t, S)>; первые две компоненты стандартной записи – аргументы функции Σ *, характеризующие со-стояние системы (момент принятия решения и совокупность прибывших и ожидающих обслуживания заявок), а третья компонента – значение функции Σ * на данном наборе аргументов. Стандартную запись < t, S, Σ *(t, S)> считаем терминальной, если t ≥ t (n), соответствующее состояние (t, S) называем Т - состоянием.

Введем операцию раскрытия стандартной записи ξ = = < t, S, Σ *(t, S)>. Выполняя раскрытие записи ξ, мы для каждой заявки i из S строим расширенную запись, состоящую из следующих шести компонент:

1. t + τ (i);

2. (S \ i) ∪ D (t, τ (i)));

3. Σ *(t, S)+ а (i) (t + τ (i) – t (i));

4. t;

5. S;

6. i.

Операцию раскрытия далее будем выполнять только для нетерминальных стандартных записей. Первая и вторая компоненты расширенной записи показывают, в какое очередное состояние перейдет система обслуживания из состояния (t, S) в случае, когда в S для первоочередного обслуживания выбрана заявка i. Третья компонента – суммарный штраф по всем обслуженным к моменту времени t + τ (i) заявкам в такой ситуации (начальная (t, S)-траектория системы оптимальна, следующий шаг заключается в обслуживании заявки i). Назначение последних трех компонент – указать предыдущее состояние системы и выбранное в нем управление. Общее число расширенных записей, получаемых раскрытием стандартной записи ξ равно числу элементов в множестве S (как всегда, фиктивная заявка считается присутствующей). Расширенную запись именуем терминальной, если ее первая координата имеет значение не меньшее, чем t (n). Ясно, что если в некоторое состояние система может прийти двумя способами, причем первый способ более дешевый, то второй способ надо изъять из рассмотрения. Формализуя и уточняя данное высказывание, введем над списком расширенных записей операцию усечения. При выполнении этой операции над списком М мы в случаях, когда в М имеются записи с одинаковым значением второй компоненты η ₁ = < t ₁ *, S*, С ₁, t ₁, S ₁, i ₁> и η ₂ = < t ₂ *, S*, С ₂, t ₂, S ₂, i ₂> такие, что t ₁ * ≤ t ₂ * и С ₁ ≤ С₂ (причем по меньшей мере одно из неравенств – строгое), запись η ₂ изымаем; если в записях η ₁ и η ₂ первые три компоненты соответственно совпадают, изымается любая из этих записей.

Пусть η = < t*, S*, С, t, S, i > – произвольная расширенная запись. Результатом свертки этой записи называем запись < t*, S*, С >.

Алгоритм прямого счета включает три последовательные процедуры, работающие над списками.

Процедура 1 выполняет следующее:

1. Список записей А полагается состоящим из единственной стандартной записи < 0, V (0), 0>; списки В, С и D считаются пустыми.

2. Все содержащиеся в списке А стандартные записи из это-го списка изымаются и раскрываются, результаты раскрытия пополняют список В.

3. Над списком В выполняется операция усечения.

4. Записи списка В упорядочиваются по возрастанию первой компоненты. Минимальное из значений первых компонент за-писей списка В фиксируется как k (в процессе работы алгоритма, в результате каждой следующей реализации п. 4 значение k возрастает);

5. Если k < t (n), реализуется переход к п. 6; в противном случае – к п. 8.

6. Все записи списка В с минимальным значением первой компоненты из этого списка изымаются и переносятся в список С; одновременно с переносом каждой изъятой из списка В записи в список С, эта запись в свернутом виде переносится в список А.

7. Переход к выполнению п. 1.

8. Процедура работу заканчивает.

В результате работы процедуры 1 мы получаем итоговый список В, содержащий ряд расширенных терминальных записей. Каждая такая запись первыми двумя компонентами задает некоторое первичное Т-состояние, т.е. Т -состояние, для которого не-посредственно предшествующее состояние системы, оно указа-но компонентами 4-5 той же записи, Т -состоянием не является. В совокупности полученные расширенные терминальные записи итогового списка В своими первыми двумя компонентами перечисляют все первичные Т -состояния Х системы за исключением заведомо нецелесообразных. Каждое состояние Х содержится только в одной записи итогового списка В, назовем эту запись η _х. Существенно, что третья компонента записи η _х равна минимально возможному суммарному штрафу по заявкам, обслуженным в процессе перехода системы из начального состояния в состояние Х.

Процедура 2 выполняет для каждой расширенной терминальной записи итогового списка В операцию дополнения. В применении к произвольной записи η = < t, S, С, t ₁, S ₁, i > итогового списка эта операция предусматривает следующие действия. Заявки множества S (другие заявки в систему уже не прибудут, ибо t ≥ t (n)) в соответствии с алгоритмом решения задачи мастера упорядочиваются по убыванию показателя μ (i) = а (i) / τ (i). Получаемую последовательность обозначим ρ (S). Считается, что расписание ρ (S) обслуживания процессором заявок множества S реализуется начиная от момента времени t. Для каждой заявки множества S определяется момент завершения ее обслуживания и соответствующая величина индивидуального штрафа. Сумму индивидуальных штрафов по всем заявкам множества S обозначим U (t, S). Результатом применения операции дополнения к записи η = < t, S, С, t ₁, S ₁, i > является состоящая из семи компонент запись η ' = < t, S, ρ (S), С + U (t, S), t ₁, S ₁, i >. Далее каждая дополненная указанным образом запись из списка В переносится в список D. В списке D отыскивается запись с минимальным значением четвертой координаты. Найденная запись, пусть это (η ') * = < t*, S*, ρ (S*), Σ ₁₁₁ * >, – итог работы процедуры 2. Четвертая координата найденной записи – оптимальное значение критерия в задаче (15).

Процедура 3 заключается в построении расписания ρ _opt, обеспечивающего полученное оптимальное значение критерия Σ *. Указанное расписание состоит из начальной части ρ ₁ и заключительной части ρ ₂. При этом ρ ₂. = ρ (S*), т.е. это третья компонента записи (η ') *, найденной в итоге работы процедуры 2. В расписании ρ ₁ на последнем месте должна стоять заявка i ₁ *. Согласно записи (η ')*, эта заявка начинается обслуживанием, когда система находится в состоянии (t ₁ *, S ₁ *). Отыскиваем в списке С запись с первой компонентой t ₁ *, и второй компонентой S ₁ *; указанному требованию удовлетворяет ровно одна запись списка С. Пусть эта запись своими четвертой, пятой и шестой компонентами имеет соответственно. t ₂ *, S ₂ *, i ₂ *. Тогда в расписании ρ ₁ на предпоследнем месте должна стоять заявка i ₂ *. Далее отыскиваем в списке С запись с первой компонентой t ₂ * и второй компонентой S ₂ *; указанному требованию удовлетворяет ровно одна запись списка С. Пусть эта запись своими четвертой, пятой и шестой компонентами имеет соответственно. t ₃ *, S ₃ *, i ₃ *. Тогда в расписании ρ ₁ заявке i ₂ * должна непосредственно предшествовать заявка i ₃ *. Действуя идентичным образом дальше, реализуем полное построение искомого расписания. Отметим, что последняя найденная в списке С запись своими четвертой и пятой компонентами должна иметь 0 и V (0)), что соответствует начальному состоянию системы.

Задача однопроцессорного обслуживания потока заявок с учетом времен переналадок. Данная задача отличается от канонической тем, что при переходе процессора, завершившего обслуживание заявки i, к обслуживанию заявки j необходимо выполнение соответствующей переналадки продолжительностью р (i, j). Считается, что в момент времени 0 процессор находится в нейтральном (нулевом) состоянии и продолжительность его наладки для обслуживания заявки i равна р (0, i). Все числа р (i, j), где i = 1, …, n и j = 1, …, n, предполагаются заданными в виде целочисленной матрицы времен переналадок Р = { р_ij } соответствующей размерности. Условно будем говорить, что процессор, завершивший обслуживание заявки i, находится в конфигурации i.

Расписание обслуживания отождествляем с перестановкой ρ = (i ₁, i ₂, …, i_n) элементов множества {1, 2,..., n }; заявка i_k в расписании ρ обслуживается k -й по очереди. Обозначим через t _нач(ρ, i_k) и t* (ρ, i_k) моменты начала и завершения обслуживания заявки i _k при реализации расписания ρ, k = 1,..., n. Считаем, что реализация расписания компактна, т.е. имеют место соотношения:

t _нач(ρ, i ₁) = max { t (i ₁), р (0, i ₁)};

t _нач(ρ, i_k) = max { t* (ρ, i_{k − 1}) + р (i_{k − 1}, i_k), t (i_k)}, k = 2, 3,..., n;

t* (ρ, i_k) = t _нач(ρ, i _k) + τ (i _k), k =1, 2,..., n.

Суммарный штраф по всем заявкам потока R, обслуживаемым по расписанию ρ, есть

(18)

Проблема заключается в минимизации суммарного штрафа, т.е. в нахождении

(19)

Состояние системы обслуживания определяем как тройку (t, i, S), где t – момент принятия очередного решения по загрузке процессора; в момент t процессор считается свободным и находящимся в конфигурации i; S – множество заявок, которые по состоянию на момент времени t прибыли и ожидают обслуживания.

Пусть Σ (t, i, S) обозначает минимальную величину суммарного штрафа по заявкам множества S и заявкам, поступающим в систему обслуживания позднее момента времени t, для системы, находящейся в состоянии (t, i, S). Как очевидно, Σ (0, 0, V (0)) – оптимальное значение критерия в решаемой задаче (19).

Как и ранее, через D (t, μ) обозначаем совокупность заявок, прибывающих в систему обслуживания на временном отрезке [ t + 1, t + μ ].

Существенно, что в состоянии (t, i, S) в качестве очередной обслуживаемой может быть выбрана заявка не обязательно из числа имеющихся в совокупности S (как это было ранее); она может быть взята из совокупности поступающих во время реализации соответствующей переналадки (при этом для времени переналадки берется верхняя оценка . Для учета но-вой возможности введем в рассмотрение множество S ′, состоящее из заявок, поступающих во временном промежутке ]. Выбор очередной обслуживаемой заявки в ситуации, описываемой тройкой (t, i, S), будем осуществлять в совокупности S* = S ∪ S ′.

Кроме того, во множество S* включаем нулевую (фиктивную) заявку. При этом считаем, что принятие на обслуживание фиктивной заявки не предусматривает предварительной переналадки процессора и означает его простой в течение одного такта.

Если в момент принятия решения t в совокупности S* выбрана заявка j, то ее обслуживание начнется в момент max { t + р(i, j), t (j)} и завершится в момент Т (t, i, j) = max{ t + р (i, j), t (j)} + τ (j).

В принятых обозначениях основное рекуррентное соотношение динамического программирования для рассматриваемой задачи записывается в виде

(20)

Задача однопроцессорного обслуживания потока заявок с нелинейными функциями индивидуальных штрафов.

Минимизируемым в данной задаче критерием считаем суммарный штраф по всем заявкам. Вместо показателя а (i), как это имело место в канонической модели, здесь каждой заявке i приписывается, вообще говоря, нелинейная функция индивидуального штрафа ϕ _i (t). Если обслуживание заявки i завершается в момент времени t*, то величина выплачиваемого по данной заявке штрафа равна ϕ _i (t*), i = 1,..., n. Все функции ϕ _i (t) считаются монотонно возрастающими в нестрогом смысле. Как и ранее, состояния системы обслуживания – пары (t, S), где t – МПР, а S – множество заявок, которые по состоянию на момент времени t прибыли и ожидают обслуживания; фиктивная заявка в совокупности S присутствует. Пусть Σ _нл(t, S) обозначает минимальную величину суммарного штрафа по заявкам множества S и заявкам, поступающим в систему позднее момента t, для системы, находящейся в состоянии (t, S). Тогда общее рекуррентное соотношение динамического программирования для решения рассматриваемой задачи записывается в виде

(21)

Задача однопроцессорного обслуживания потока заявок с нелинейными функциями индивидуальных штрафов и директивными сроками.

Здесь в дополнение к исходным данным предшествующей задачи для каждой заявки i считается указанным обозначаемый через d (i) директивный срок завершения обслуживания, i = 1,..., n. Расписание ρ именуем допустимым, если для всех i = 1,..., n имеет место t* (ρ, i) ≤ d (i). Проблема заключается в отыскании допустимого расписания, минимизирующего величину суммарного штрафа.

Пусть . Таким образом, L – оценка сверху величины минимизируемого критерия (возможными считаются только допустимые расписания). Рассматриваемую задачу модифицируем следующим образом: исключим необходимость соблюдения директивных сроков, но введем новые функции индивидуального штрафа: величину штрафа ϕ ′ _i(t) по заявке i определим следующим образом: ϕ ′ _i (t) = ϕ _i (t), если t ≤ d (i), и ϕ ′ _i (t) = ϕ _i (t) + L в противном случае.

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

Если минимальное значение суммарного штрафа в полученной задаче оказывается меньшим L, то обеспечивающее его расписание является одновременно оптимальным решением исходной задачи (с учетом директивных сроков).

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