Задачи обслуживания множеств заявок

Задача мастера.

Имеется множество заявок {1, 2, …, n } и процессор Р, на котором должна пройти обслуживание каждая заявка; процессор не может обслуживать несколько (т.е. более одной) заявок одновременно. Обслуживание каждой заявки (от начала до конца) реализуется без прерываний; переход от обслуживания одной заявки к обслуживанию следующей за ней заявки затрат времени не требует. Обслуживание заявок начинается от момента времени t = 0. Для каждой заявки i известны две характеристики: τ (i) – продолжительность обслуживания на процессоре; а (i) – штраф за единицу времени пребывания в системе обслуживания. Считаем, что τ (i) > 0, а (i) ≥ 0, i = 1, …, n.

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

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

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

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

При реализации расписания ρ величина штрафа W_i (ρ) по произвольной заявке i оказывается равной а (i) t* (ρ, i). Суммарный штраф по всем заявкам, обслуживаемым согласно расписанию ρ, есть

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

(4)

В стандартной для задачи мастера интерпретации считается, что заявки – это сломавшиеся станки, процессор – мастер по их ремонту, а (i) – величина потерь, связанных с каждой единицей времени простоя i- го станка; τ (i) – время, которое мастер должен затратить на ремонт i -го станка, i = 1, …, n.

Предположим, что расписание ρ ⁰ = (1, 2,..., n) в задаче (4) является оптимальным. Через ρ ^q обозначим расписание, получаемое из ρ ⁰ переменой местами двух соседних заявок, q и q + 1. Очевидно, что для каждого значения i, отличного от q и от q + 1, имеет место t* (ρ ^q, i) = t* (ρ ⁰, i). Поэтому в суммах

и

отличаются между собой только q -е и (q + 1)-е слагаемые. Легко определяется, что

Так как расписание ρ ⁰ – оптимально, записанная разность неположительна. Получаем

а (q + 1)τ (q) – а (q)τ (q + 1) ≤ 0,

т.е.

а (q)τ (q + 1) ≥ а (q + 1)τ (q).

Разделив обе части полученного неравенства на положительное произведение τ (q)τ (q + 1), получаем

{ а (q)/τ (q)} ≥ { а (q + 1)/τ (q + 1)} (5)

Неравенство (5) – следствие сделанного предположения об оптимальности расписания ρ ⁰. Из этого неравенства вытекает простейший алгоритм синтеза оптимального расписания в задаче мастера: для каждой заявки i нужно определить показатель μ (i) = а (i)/τ (i), i = 1, …, n, и упорядочить заявки по убыванию значений μ (i). Полученная перестановка является оптимальным расписанием обслуживания имеющегося множества заявок.

Изложенный способ отыскания правила оптимального упорядочения заявок называется перестановочным приемом. Найденный для задачи мастера способ синтеза оптимального расписания именуем μ -правилом. Содержательный смысл его очевиден: чем меньше продолжительность обслуживания заявки и чем больше по этой заявке штраф за единицу времени пребывания в системе, тем раньше она должна обслуживаться.

Двухпроцессорная задача мастера.

Отличие рассматриваемой задачи от предыдущей состоит в наличии двух идентичных процессоров, Р ₁ и Р ₂. Каждая заявка множества {1, 2, …, n } должна быть обслужена либо первым, либо вторым процессором. Оба процессора считаются готовыми к обслуживанию заявок начиная с момента времени t = 0. Обслуживание одной заявки двумя процессорами считается невозможным. Расписание определяем как пару ρ = (ρ ₁, ρ ₂), где ρ ₁ = (i ₁, i ₂, i ₃, …, i_p)-перестановка, определяющая последовательность обслуживания заявок первым процессором, а ρ ₂ = (j ₁, j ₂, j ₃, …, j_q)-перестановка, определяющая последовательность обслуживания заявок вторым процессором. Каждая заявка входит либо в первую, либо во вторую перестановку, поэтому р + q = n. Требуется найти расписание, минимизирующее суммарный по всем заявкам штраф.

По аналогии с результатами, полученными для однопроцессорной задачи мастера, можно предположить, что оптимальным является расписание, синтезируемое в соответствии с интерпретируемым следующим образом μ -правилом: упорядочиваем совокупность всех заявок по убыванию показателя μ (i), в этом порядке выполняем их перенумерацию и в этом же порядке направляем на обслуживание освобождающимися процессорами. В синтезируемом расписании процессоры Р ₁ и Р ₂ сначала должны обслужить заявки 1 и 2 соответственно (все номера заявок – новые), заявка 3 направляется следующей на процессор, который раньше освободится. Точно так же заявка 4 направляется следующей на процессор, который раньше обслужит поступившие ему заявки из совокупности {1, 2, 3}, и т.д.

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

Таблица 2.1 Характеристики заявок

Применением μ -правила в рассматриваемом примере строится расписание ρ ⁰ = (ρ ₁, ρ ₂), где ρ ₁ = (1, 3) и ρ ₂ = (2). В случае реализации этого расписания суммарный штраф по трем заявкам равен 10111. В то же время при реализации расписания ρ ¹ = ((1, 2), (3)) будем иметь суммарный штраф, равный 10015. Таким образом, в двухпроцессорной задаче мастера расписание, синтезируемое в соответствии с μ -правилом, оптимальным вообще говоря, не является.

Для синтеза оптимального в двухпроцессорной задаче мастера расписания применим метод динамического программирования. Будем считать, что все заявки пронумерованы в порядке убывания значений показателя μ. Тогда если ρ = (ρ ₁, ρ ₂) – оптимальное расписание, то заявки в каждой из последовательностей ρ ₁= (i ₁, i ₂, i ₃, …, i_p) и ρ ₂ = (j ₁, j ₂, j ₃, …, j_q) записаны в порядке возрастания номеров.

При синтезе оптимального расписания для каждой следующей (в порядке возрастания номеров, т.е. по убыванию показателя μ) заявки i + 1 мы должны определить, на какой из двух процессоров ее направить в качестве подлежащей обслуживанию в следующую очередь. При этом все заявки множества {1, 2, …, i } по процессорам уже распределены, известны величины промежутков времени, которое будет потрачено на обслуживание этих заявок первым и вторым процессорами; время работы процессора Р ₁ над предписанными ему заявками из совокупности {1, 2, …, i } обозначим Δ. В таком случае время работы процессора Р ₂ над заявками из той же совокупности равно .

Через W* (i, Δ) обозначим минимально возможную величину суммарного штрафа по заявкам множества {1, 2, …, i }, если на обслуживание направленных на процессор Р ₁ заявок из этого множества затрачивается время Δ. Как очевидно,

W*(1, τ (1)) = W*(1, 0) = a(1)τ (1) (6)

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

W* (1, Δ)= + ∞, если Δ ∉ {0, τ (1)}; (7)

далее для любых нереализуемых ситуаций (i, Δ) из определяемого ниже соотношения (8) будем получать W* (i, Δ) = +∞.

Предположим, что все значения функции W* (i, Δ) для некоторого конкретного значения i уже найдены. Рассмотрим ситуацию в процессе обслуживания, определяемую парой (i + 1, Δ). В случае Δ ≥ τ (i + 1) непосредственно предшествующими для этой ситуации являются две: (i, Δ) и (i, Δ – τ (i + 1)); в случае Δ < < τ (i + 1) непосредственно предшествующей является только ситуация (i, Δ); значение W* (i, Δ – τ (i + 1)), где второй аргумент функции отрицательный, считается равным +∞. Переход от ситуации (i, Δ) к ситуации (i + 1, Δ) предполагает, что обслуживание заявки i + 1 выполняется процессором Р ₂; обслуживание этой заявки начинается в момент времени

и завершается в момент

.

Переход от ситуации (i, Δ – τ (i + 1)) к ситуации (i + 1, Δ) предполагает, что обслуживание заявки i + 1 выполняется процессором Р ₁; обслуживание начинается в момент времени Δ – τ (i + 1)) и завершается в момент Δ.

Отсюда получаем:

(8)

Процедуру вычисления значений функции W* (i, Δ) удобно представлять как процесс заполнения таблицы, строки которой соответствуют значениям параметра i, а столбцы – значениям параметра Δ; в клетку, являющуюся пересечением строки i и столбца Δ, вносится значение W* (i, Δ). Общее число строк таблицы значений функции W* (i, Δ) равно n. Величины W* (i, Δ) требуется определять для значений второго аргумента из множества

{0, 1, …, },

поэтому общее число столбцов таблицы равно

.

Строки таблицы заполняются сверху вниз, в порядке роста значений параметра i. Первая строка заполняется по формулам (6)–(7), остальные – по формуле (8). Отметим, что в силу идентичности процессоров в клетки (i + 1, Δ) и (i + 1, ).вносятся одинаковые числа; если при вычислении значения W* (i + 1, Δ) минимум правой части (8) реализуется на первой (второй) компоненте, то при отыскании величины W* (i + 1, ) минимум правой части (8) реализуется на второй (соответственно первой) компоненте. Оптимальным значением критерия в решаемой задаче является минимальный элемент, внесенный в нижнюю строку таблицы значений функции W* (i, Δ). Если данный элемент находится в столбце Δ ', то общее время работы одного процессора в реализации оптимального расписания равно Δ ', время работы другого процессора равно

Для обеспечения возможности синтеза оптимального расписания в каждую клетку (i + 1, Δ) таблицы кроме значения W* (i + 1, Δ), требуется записывать условный символ, указывающий, на какой компоненте правой части соотношения (8) при вычислении W* (i + 1, Δ) реализуется минимум.

Равенства (6) – (8) – рекуррентные соотношения динамического программирования для решения двухпроцессорной задачи мастера.

Общая задача однопроцессорного обслуживания множества заявок с критерием суммарного штрафа.

Данная задача – обобщение однопроцессорной задачи мастера. Ее отличие от задачи мастера в том, что для каждой заявки i вместо числовой характеристики а (i) задается монотонно возрастающая (в нестрогом смысле) функция индивидуального штрафа ϕ _i (t). Значение этой функции – величина штрафа по заявке i, если обслуживание этой заявки завершается в момент времени t. При реализации расписания ρ величина штрафа W_i (ρ) по произвольной заявке i оказывается равной ϕ _i (t* (ρ, i)), где t* (ρ, i) – момент завершения обслуживания заявки i при реализации расписания ρ. Требуется найти расписание, минимизирующее величину суммарного по всем заявкам штрафа.

Сначала выделим частные случаи, в которых правила оптимального упорядочения заявок получаются применением перестановочного приема.

Рассмотрим ситуацию, когда все функции индивидуального штрафа экспоненциальны:

ϕ _i (t) = а_i ехр (α t) + b_i, i = 1, …, n;

константа α считается положительной. Реализуя перестановочный прием, легко получаем алгоритм синтеза оптимального расписания: для каждой заявки i, i = 1, …, n, нужно вычислить показатель

ν (i) = (1 – ехр (α τ (i))/ а_i;

далее заявки следует упорядочить по убыванию значений ν (i). Полученная перестановка является оптимальным расписанием обслуживания имеющегося множества заявок. Выделим случай, когда все функции индивидуального штрафа одинаковы: ϕ _i (t) = Ф(t), i = 1, …, n; здесь Ф(t) – произвольная монотонно возрастающая (в нестрогом смысле) функция. Перестановочный прием дает следующий алгоритм синтеза оптимального расписания: заявки следует упорядочить по возрастанию показателя τ (i) – требуемой продолжительности обслуживания; полученная перестановка является оптимальным расписанием.

Перестановочный прием срабатывает, когда знак разности между величинами суммарного штрафа для расписания ρ ⁰ = (1, 2,..., n) и для расписания ρ ^q, получаемого из ρ ⁰ переменой местами заявок q и q + 1, зависит только от параметров переставляемых заявок. Теорема Кладова–Лившица [23] устанавливает, что перестановочный прием дает способ определения показателя, сортировка по которому приводит к оптимальному расписанию, только для трех случаев:

1) все функции индививидуального штрафа линейны:

ϕ _i (t) = а_i t + b_i, i = 1, …, n;

2) все функции индививидуального штрафа экспоненциальны:

ϕ _i (t) = а_i ехр(α t) + b_i, i = 1, …, n.

3) функции индивидуального одинаковы для всех заявок: ϕ _i (t) = Ф(t), i = 1, …, n; здесь Ф(t) – произвольная монотонно возрастающая (в нестрогом смысле) функция.

Теорема Кладова–Лившица доказана в предположении, что функции индивидуального штрафа являются достаточно глад-кими (существуют третьи производные).

Отметим, что в трех перечисленных случаях вычислительная сложность алгоритма построения оптимального расписания (число выполняемых алгоритмом элементарных операций) имеет порядок n lg n, это соответствует сложности процедуры сортировки. Если исходные данные определяют задачу, не подпадающую под какой-либо из перечисленных в теореме Кладова–Лившица случаев, то целесообразным способом ее решения является метод динамического программирования.

Рассмотрим обозначаемую символом Z задачу обслуживания множества заявок N = {1, 2, …, n } в однопроцессорной системе; единственное ограничение, налагаемое на функции индивидуального штрафа – их монотонное возрастание. Считаем, что для каждой заявки i, i = 1, …, n, известны: τ (i) – продолжительность обслуживания на процессоре и ϕ _i (t) – монотонно возрастающая в нестрогом смысле функция индивидуального штрафа; требуется построить расписание обслуживания, обеспечивающее минимальное значение суммарного по всем заявкам штрафа. Пусть S – произвольное подмножество заявок, S ⊆ {1, 2, …, n }. Через Z (S) обозначим частную задачу, получаемую из Z в предположении, что обслуживанию подлежит только совокупность заявок S, а через К (S) – минимально возможный суммарный штраф в частной задаче Z (S). Для одноэлементного множества заявок, как очевидно, имеем:

К ({ i }) = ϕ _i (τ (i)), i ∈ N. (9)

Сейчас предположим, что все значения функции К (S) для р -элементных множеств S уже найдены, здесь р ∈ {1, 2, …, n –1}. Пусть S* – произвольное (р + 1)-элементное множество заявок. Если считать, что в совокупности S* последней обслуживается заявка j, то величина индивидуального штрафа по этой заявке равна

,

минимально возможный суммарный по всем заявкам данной совокупности штраф в имеющейся ситуации равен

Получаем:

(10)

здесь S* – произвольное подмножество заявок, состоящее не менее, чем из двух элементов. Если минимум правой части (10) достигается при j = q, то последней в подмножестве S* следует обслужить заявку q. Равенства (9)–(10) – рекуррентные соотношения динамического программирования, позволяющие решить задачу Z. Подсчитывая на их основании значения функции К (S*), вычисления выполняются в порядке роста числа элементов в множествах S*, мы в итоге находим величину К (N), т.е. оптимальное значение критерия в решаемой задаче (минимальную величину суммарного штрафа).

Пример 2.2.

Имеется процессор, обслуживанию которым подлежат заявки множества N = {1, 2, 3}. Известно, что τ (1) = 3; τ (2) = 2; τ (3) = 4; ϕ ₁(t) = 2 t ²; ϕ ₂(t) = 3 t; ϕ ₃(t) = t ²+ t. Требуется построить расписание, минимизирующее величину суммарного штрафа.

По формуле (9) вычисляем:

К ({1}) =ϕ ₁(3) = 18; К({2}) = ϕ ₂(2) = 6; К({3}) = ϕ ₃(4) = 20.

Далее, пользуясь формулой (10), находим последователь-но:

К ({1, 2 }) = min{ К ({2}) + ϕ ₁(5),

К ({1}) + ϕ ₂(5)} = min{6 + 50, 18 + 15} = 33;

К ({1, 3 }) = min{К({3}) + ϕ ₁(7),

К ({1}) + ϕ ₃(7)} = min{20 + 98, 18 + 56} = 74;

К ({ 2, 3}) = min{ К ({3}) + ϕ ₂(6),

К ({2}) + ϕ ₃(6)} = min{20 + 18, 6 + 42} = 38;

К ({1, 2, 3}) = min{ К ({2, 3}) + ϕ ₁(9), К ({1, 3})+ ϕ ₂(9),

К ({1, 2}) + ϕ ₃(9)} = min{38 + 162, 74 + 27, 33 + 90} = 101;

в левых частях записанных конкретизаций равенства (10) подчеркнуты значения параметра j, обеспечивающие минимальные значения их правых частей. Оптимальное значение критерия в рассматриваемом примере равно 101.

Благодаря сделанным в процессе вычислений подчеркиваниям, легко определяем оптимальную последовательность обслуживания заявок. Действительно, в совокупности {1, 2, 3} последней надо обслужить заявку 2 (именно этот номер был под-черкнут при определении К ({1, 2, 3})). Заявке 2, таким образом, предшествует пара заявок {1, 3}. В совокупности {1, 3} послед-ней надо обслужить заявку 3 (номер 3 был подчеркнут при определении К ({1, 3})). И, наконец, заявка 1 должна быть обслужена первой. Легко подсчитывается, что при реализации построенного расписания величина суммарного штрафа действительно равна 101.

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

Имеется множество заявок N = = {1, 2, …, n } и процессор П, на котором должна быть обслужена каждая заявка этого множества; процессор не может обслуживать несколько (более одной) заявок одновременно; переход от обслуживания одной заявки к обслуживанию следующей за ней заявки затрат времени не требует. Обслуживание заявок начинается с момента времени t = 0. Для каждой заявки i известны: τ (i) – продолжительность обслуживания на процессоре; монотонно возрастающая (в нестрогом смысле) функция индивидуального штрафа ϕ _i (t). Если обслуживание заявки i завершает-ся в момент времени t, то ϕ _i (t) – величина штрафа по этой заявке. При реализации расписания ρ моменты завершения обслуживания заявок вычисляются по формулам (1)–(3), величина штрафа W_i (ρ) по произвольной заявке i оказывается равной ϕ _i (t* (ρ, i)), i = 1, …, n. Вводим критерий

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

(11)

Очевидно, что обслуживание процессором заявок множества N завершается в момент времени Т = τ (1) + τ (2) + … + τ (n). Под-считаем все значения ϕ _i (Т), i= 1,..., n; пусть ϕ _k (Т) – минимальная из найденных величин. Покажем, что в таком случае имеется оптимальное для задачи (11) расписание, в котором заявка k обслуживается последней. Предположим, что в некотором рас-писании ρ заявка k обслуживается j -й по очереди (j ∈ {1, 2, …, n – 1}), а последней обслуживается заявка р, причем ϕ _k (Т) < ϕ _р (Т). Очевидно, что К (ρ) ≥ ϕ _р (Т) > ϕ _k (Т). Последовательными перестановками заявки k и каждой непосредственно следующей за ней по обслуживанию заявки от расписания ρ переходим к расписанию ρ ', в котором заявка k обслуживается предпоследней. По расписанию ρ ' каждая из заявок множества N \ { k, p } завершается обслуживанием раньше, чем по расписанию ρ; за-явка р завершается обслуживанием в тот же момент времени Т. Заявка k по расписанию ρ ' завершается обслуживанием в момент Т – τ (р), но ϕ _k (Т – τ (р)) ≤ ϕ _k (Т) < ϕ _р (Т). Из изложенного вытекает, что К (ρ ') ≤ К (ρ). От расписания ρ ' перестановкой местами заявок k и р перейдем к расписанию ρ *, в котором заявка k обслуживается последней. По расписанию ρ * каждая из заявок множества N \ { k, p } завершается обслуживанием в тот же момент, что и по расписанию ρ '; заявка р завершается обслуживанием раньше, чем по расписанию ρ '. Заявка k по расписанию ρ * завершается обслуживанием в момент Т, но ϕ _k (Т) < ϕ _р (Т). Из изложенного вытекает, что К (ρ *) ≤ К (ρ '). Мы показали, что в рассматриваемой задаче однопроцессорного обслуживания всегда имеется оптимальное расписание, в котором заявка с минимальным значением индивидуального штрафа в момент времени Т обслуживается последней. Отсюда вытекает следующий алгоритм синтеза оптимального расписания ρ ** = (i ₁, i ₂,..., i_n):

1. Полагаем N = {1, 2, …, n }; Т = τ (1) + τ (2) + … +τ (n); r = n.

2. Для каждой заявки i из N находим значение ϕ _i (Т); пусть ϕ _k (Т) – минимальное из найденных значений (если ϕ _i (Т) минимально при нескольких значениях индекса i, в качестве k берем любое из них).

3. Полагаем i_r = k.

4. Изымаем из множества N заявку k; значение Т уменьшаем на τ (k); значение параметра r уменьшаем на единицу.

5. Если r =0, искомое расписание построено; в противном случае переходим к п. 2. алгоритма.

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

Считается заданным множество заявок {1, 2, …, n } и процессор П, на котором должна быть обслужена каждая заявка; процессор не может обслуживать несколько (т.е. более одной) заявок одновременно; переход от обслуживания одной заявки к обслуживанию следующей за ней заявки затрат времени не требует. Обслуживание заявок начинается от момента времени t = 0. Для каждой заявки i известны две характеристики: τ (i) – продолжительность ее обслуживания на процессоре; d (i) – директивный срок, не позднее которого обслуживание заявки должно завершиться; здесь τ (i) > 0, d (i) > 0, i =1,..., n. Расписание обслуживания отождествляем с перестановкой ρ = (i ₁, i ₂,..., i_n) элементов множества {1, 2,..., n }; заявка i_k в расписании ρ обслуживается k- й по очереди. Расписание ρ для каждой заявки i однозначно определяет момент завершения ее обслуживания t* (ρ, i). Считаем, что заявка i в расписании ρ обслуживается с соблюдением директивного срока, если t* (ρ, i) ≤ d (i). Проблема заключается в построении расписания, в котором для наибольшего числа заявок директивные сроки соблюдаются.

Сначала рассмотрим частный случай, в котором директивный срок одинаков для всех заявок: d (1) = d (2) = … = d (n) = D. Решаемая задача в данном частном случае путем дополнительного введения одной и той же для всех заявок функции индивидуального штрафа Ф(t) сводится к рассмотренной выше задаче однопроцессорного обслуживания множества заявок с критерием суммарного штрафа. Функция Ф(t) вводится следующим образом:

Благодаря способу задания функции Ф(t), при реализации произвольного расписания ρ суммарный по всем заявкам штраф оказывается равным числу заявок, которые по этому расписанию обслуживаются с нарушением директивного срока D. Решая задачу минимизации суммарного штрафа, мы фактически строим расписание, в котором для наибольшего числа заявок директивный срок соблюдается. Так как функция индивидуального штрафа для всех заявок одна и та же, оптимальное расписание строится просто: заявки следует обслуживать в порядке возрастания характеристики τ (i).

Сейчас задачу обслуживания множества заявок при наличии директивных сроков рассмотрим в изложенной выше общей постановке. Систему директивных сроков { d (1), d (2), …, d (n)} именуем реальной, если существует расписание обслуживания ρ такое, что для каждого i = 1,..., n выполняется неравенство t* (ρ, i) ≤ d (i). Пусть (i ₁, i ₂,..., i_n) – перестановка, перечисляющая заявки в порядке возрастания директивных сроков. Очевидно, что указанная система { d (1), d (2), …, d (n)} реальна тогда и только тогда, когда расписание ρ = (i ₁, i ₂,..., i_n) обеспечивает соблюдение каждого из указанных для заявок сроков.

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

Строим перестановку (i ₁, i ₂,..., i_n), перечисляющую заявки в порядке возрастания директивных сроков. Если при реализации расписания ρ * = (i ₁, i ₂,..., i_n) каждая заявка обслуживается с соблюдением директивных сроков, то расписание ρ * оптимально. В случае, когда при реализации расписания ρ * оказывается нарушенным только один из директивных сроков, это расписание также оптимально.

В остальных случаях действуем по следующему алгоритму:

1) полагаем ρ = ρ *; множество W считаем пустым (далее во множество W будут вноситься заявки, которые по конструируемому расписанию обслуживаются с нарушением директивных сроков);

2) последовательность ρ трактуем как расписание обслуживания входящих в нее заявок;

3) если все входящие в ρ заявки обслуживаются с соблюдением директивных сроков или если последовательность ρ оказалась пустой, то переходим к п. 8; в противном случае – к п. 4.

4) в последовательности ρ находим минимальное q такое, что заявка i_q по расписанию ρ обслуживается с нарушением директивного срока;

5) в совокупности заявок { i ₁, i ₂,..., i_q } находим заявку i_х, продолжительность обслуживания которой максимальна;

6) новую последовательность ρ получаем из предшествующей изъятием из нее заявки i_х (все остальные заявки перечисляются в прежнем порядке); Заявку i_х включаем в множество W.

7) переходим к п. 2;

8) искомое оптимальное расписание ρ ** определяем как последовательность, состоящую из двух частей: последовательность ρ (начальная часть расписания ρ **); перечень элементов множества W в любом порядке (заключительная часть расписания ρ **).

Обоснование изложенного алгоритма выполняется рассуждениями от противного.

Легко определяется, что оценка временной вычислительной сложности алгоритма Сn ², где С – некоторая не зависящая от n константа.

Задача Джонсона для n станков (ЗД-n).

Имеется комплект К, состоящий из деталей D ₁, D ₂, …, D_m; все детали должны быть обработаны на станках S ₁, S ₂, …, S_n. Каждая деталь в процессе обработки должна пройти все станки последовательно, в порядке роста их номеров (индексов). Для каждой детали D_i задано требуемое время τ _ij ее обработки на станке S_j; считаем, что все τ _ij – целые положительные числа, i = 1, …, m, j = 1, …, n. В любой момент времени каждый станок может обрабатывать только одну деталь. Работа каждого станка над любой деталью выполняется без прерываний. Работа над комплектом начинается от момента t = 0, по состоянию на этот момент все станки считаются свободными. Расписание в ЗД- n определяем как кортеж ρ = {ρ ₁, ρ ₂, …, ρ _n }, где ρ _j – номеров деталей, определяющая последовательность их обработки на станке S_j, j = 1, …, n. Требуется найти расписание, при реализации которого момент готовности комплекта (т.е. момент завершения работы станка S_n) оказывается минимальным. Джонсон доказал, что в любой задаче описанного типа всегда имеется оптимальное расписание ρ, в котором одновременно ρ ₁ = ρ ₂ и ρ _{n –1} = ρ _n , т.е. последовательности обработки деталей на первом и втором станках совпадают и последовательности обработки деталей на предпоследнем и последнем станках также совпадают. Отсюда вытекает, что в задачах Джонсона для двух и трех станков всегда имеются оптимальные расписания, в которых последовательности обработки деталей на всех станках одинаковы. Легко строится пример задачи Джонсона для четырех станков, в которой имеется единственное оптимальное расписание и оно предусматривает, что первые два станка проходятся деталями в одной последовательности, а два следующих станка – в последовательности, отличающейся от предыдущей.

Для задач Джонсона с двумя или тремя станками оптимальное расписание конструируется как перестановка ρ элементов множества {1, 2, …, m }, определяющая единую последовательность обработки деталей на всех станках. Синтез оптимального расписания может быть выполнен на основе соответствующим образом построенных соотношений динамического программирования. При этом запись и анализ уравнения динамического программирования для задачи Джонсона с двумя станками дает возможность простого и быстрого определения оптимального расписания.

Задача Джонсона для двух станков (ЗД-2).

Для каждой детали D_i считаем, что а_i – требуемое время ее обработки на станке S₁, а b_i – требуемое время ее обработки на станке S₂, i = m, 1. Момент принятия решения (МПР) – это любой момент, когда станок S ₁ свободен и требуется определить следующую деталь, которая начиная от данного МПР на нем будет обрабатываться. Каждый МПР характеризуется следующими факторами: М – совокупность деталей, обработка которых пока не начиналась; Т ₂ – продолжительность отрезка времени, на котором позднее рассматриваемого МПР станок S ₂ еще будет загружен обработкой деталей, уже прошедших станок S ₁. Через F (М, Т ₂) обозначим минимально возможную продолжительность отрезка времени от рассматриваемого МПР до момента завершения изготовления комплекта деталей К. Как очевидно,

F ({ D ₁, D ₂, …, D_m }, 0)

– минимальное время, за которое комплект может быть изготовлен. Предположим, что в МПР, характеризуемый парой (М, Т ₂), на обработку станком следует направить деталь D_х, а в следующий МПР – деталь D_у (D_х ∈ M, D_у ∈ M). В таком случае сначала имеем:

F (М, Т ₂) = а_х + F (М \ { D_х }, b_х + max [(Т ₂ – а_х), 0]).

Учитывая сделанное предположение о направлении на обработку вслед за деталью D_х детали D_у, получаем:

F (М \ { D_х}, b_х + max [(Т ₂ – а_х), 0]) = а_у + F (M \ { D_х, D_у },

b_у + max[(b_х + max [(Т ₂ – а_х), 0] – а_у), 0]).

Далее имеем:

F (М, Т ₂) = а_х + а_у + F (M \ { D_х, D_у }, К_ху),

где

К_ху = b_у + max[(b_х + max [(Т ₂ – а_х), 0] – а_у), 0]) = b_у + b_х – а_у +

+ max {max[(Т ₂ – а_х), 0], а_у – b_х } = b_у + b_х – а_у +

+ max{ Т ₂ – а_х, 0, а_у – b_х } = b_у + b_х – а_у – а_x +

+ max{ Т ₂, а_х, а_х + а_у – b_х } = b_у + b_х - а_у – а_x +

+ max{ Т ₂, max(а_х, а_х + а_у – b_х)}.

Оказывается очевидным, что если

max (а_х, а_х + а_у – b_х) > max (а_у, а_х + а_у – b_у),

то детали D_х и D_у имеет смысл поменять местами. Полученное правило можно переписать в виде

а_х + а_у + max (– а_у, – b_х) > а_х + а_у + max (– а_х, – b_у)

или, что еще проще, как

max (– а_у, – b_х) > max (– а_х, – b_у).

Последнее неравенство эквивалентно следующему:

min(b_х, а_у) > min(b_y, а_x).

Так получаем следующий алгоритм определения оптимального в ЗД-2 расписания (последовательности обработки деталей). Считаем, что исходная информация по задаче записана в виде матрицы А размера m × 2, в первом столбце которой последовательно, сверху вниз, перечислены времена обработки деталей на первом станке а ₁, а ₂, …, а_m; а во втором столбце также последовательно, сверху вниз, перечислены времена обработки деталей на втором станке b ₁, b ₂, …, b_m. Для записи оптимального расписания выделяем набор W из m изначально пустых, идущих слева направо позиций. Далее руководствуемся инструкцией:

1. Выделить наименьший непомеченный элемент матрицы А (изначально все элементы матрицы А считаются непомеченными).

2. Если выделен некоторый элемент а_i левого столбца, вписать D_i в крайне левую пустую позицию набора W; Если выделен некоторый элемент b_i правого столбца, вписать D_i в крайне правую пустую позицию набора W.

3. Если в наборе W пустых позиций нет, перейти к п. 5; в противном случае – к п. 4.

4. В матрице пометить оба элемента i -й строки; перейти к п. 1.

5. В позициях W зафиксировано оптимальное расписание. Запуск деталей в обработку должен осуществляться в порядке их перечисления (слева направо) в позициях набора W.

Отметим, что выполнение приведенной инструкции не всегда является однозначно определенной процедурой, но любая реализация инструкции строит оптимальное расписание (оптимальное для ЗД-2 расписание, вообще говоря, не единственно).

Пример 2.3.

Задача Джонсона для двух станков определена матрицей

Требуется найти оптимальную последовательность обработки деталей.

В синтезируемом по приведенной инструкции оптимальном расписании последней (минимальным элементом матрицы является единица, стоящая в третьей строке правого столбца) должна обрабатываться деталь D ₃, она записывается в крайне правую позицию набора W. Далее в крайне левую и крайне правую свободные позиции (минимальными непомеченными элементами матрицы оказываются две двойки, в левом и правом столбцах) вписываются детали D ₁ и D ₆ соответственно. Затем в крайнюю левую и крайнюю правую свободные позиции (минимальными непомеченными элементами матрицы оказываются две тройки, в левом и правом столбцах) вписываются детали D ₅ и D ₇ соответственно. Далее минимальным непомеченным элементом матрицы оказывается четверка в правом столбце, соответствующая деталь D ₄ вписывается в крайне правую свободную позицию набора W. Последней на оставшееся свободным место вносится деталь D ₂. Таким образом устанавливается, что оптимальной является следующая последовательность обработки деталей: D ₁, D ₅, D ₂, D ₄, D ₇, D ₆, D ₃.