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

Рассматриваются две близкие по описанию модели обслуживания одним или двумя мобильными процессорами стационарно расположенных объектов. В рамках этих моделей формулируются и решаются задачи синтеза оптимальных расписаний (последовательностей обслуживания).

Модель I следующая. Имеется n -элементное множество М = = { о ₁, о ₂, …, о_n } стационарных объектов, расположенных в рабочей зоне Ξ мобильного (перемещаемого) процессора P. Зона Ξ представляет собой направленный отрезок L, в фиксированных точках которого расположены объекты о ₁, о ₂, …, о_n. Начальная точка отрезка L является базовой для процессора; от этой точки он сначала перемещается к конечной точке отрезка (прямой рейс, примем для него обозначение λ ₊), а затем, достигнув ее, возвращается к базовой точке (обратный рейс, примем для него обозначение λ _–). При реализации цикла λ ₊ λ _– процессор должен выполнить обслуживание каждого объекта множества М; обслуживание части объектов реализуется в прямом рейсе, обслуживание всех остальных объектов − в обратном рейсе. Осуществляемое процессором обслуживание каждого объекта однократное, без прерываний. Остановки процессора при выполнении цикла λ ₊ λ _– связаны только с обслуживанием объектов множества М. Затраты времени на перемещения процессора и на обслуживание каждого объекта, а также штрафы за задержки в обслуживании характеризуются известными параметрами и функциональными зависимостями.

Отличие модели II от модели I заключается в том, что обслуживание объектов множества М осуществляется не одним, а двумя идентичными процессорами Р ₁ и Р ₂ при реализации движений только в прямом направлении; движение процессора Р ₂ от базовой точки начинается позже, чем движение процессора Р ₁. Удобно считать, что обслуживание объектов процессором Р ₁ реализуется в рейсе, именуемом λ ₊, а обслуживание объектов процессором Р ₂ реализуется в рейсе, именуемом λ _-.

Примем следующие обозначения: α ₁ и α _n – начальная и конечная точки отрезка L соответственно; l ₁, l ₂, …, l_n (α ₁ < l ₁ < l ₂ <, < …, l_{n –1} < l_n = α _n) – точки отрезка L, в которых расположены объекты о ₁, о ₂, …, о_n; γ _{i –1, i} и γ _{i, i –1} – затраты времени на перемещение процессора между точками расположения соседних объектов о_{i –1}, о_i в рейсах λ ₊ и λ _– соответственно, i = 1,..., n; при этом γ _{0, 1} и γ _{1, 0} – затраты времени на перемещения процессора между базовой точкой α ₁ и точкой l ₁ в рейсах λ ₊ и λ _– соответственно; τ _i – продолжительность обслуживания процессором объекта о_i (i = 1,..., n).

Все величины γ _{i − 1, i,} γ _{i, i − 1,} τ _i – целые положительные числа, i = 1,..., n. Для каждого объекта о_j (j = 1,..., n) считается заданной монотонно возрастающая в нестрогом смысле функция индивидуального штрафа ϕ _j (t); если обслуживание объекта о_j завершается в момент времени t, то ϕ _j (t) – соответствующая величина потерь (штрафа) по данному объекту.

Для модели I cчитаем, что t = 0 – момент времени, в который процессор начинает рейс λ ₊. Для модели II cчитаем, что процессор Р ₁ начинает начинает рейс λ ₊ в момент времени t = 0, а процессор Р ₂ начинает рейс λ _– в момент времени t = Т.

Стратегиями обслуживания множества объектов М = { о ₁, о ₂, …, о_n } будем называть подмножества элементов V из совокупности N = {1, 2, …, n }. В рамках модели I объекты о_j, где j ∈ V, в реализации стратегии V обслуживаются процессором P в рейсе λ ₊, все остальные объекты обслуживаются этим процессором в рейсе λ _– (для определенности полагаем, что объект о_n обслуживается при завершении процессором рейса λ ₊, т.е. n ∈ V). В рамках модели II объекты о_j, j ∈ V, в реализации стратегии V обслуживаются процессором P ₁, все остальные объекты – процессором P ₂.

Очевидно, что каждая стратегия однозначно определяет расписание обслуживания объектов. Спецификой рассматриваемых моделей является то, что общее число возможных стратегий обслуживания имеет порядок 2 ⁿ, в то время как обычно для задач однопроцессорного обслуживания число возможных стратегий имеет порядок n!

Для объекта о_j (j = 1, n) через t * _j (V) обозначим момент завершения его обслуживания при реализации стратегии V; при этом ϕ _j (t * _j (V)) – соответствующая величина индивидуального штрафа.

В рамках модели I формулируем две задачи.

Задача I-1:

Задача I-2:

В рамках модели II формулируются идентично записываемые задачи II-1 и II-2 (В задаче II-1 требование n ∈ V не налагается).

Задача I-1, алгоритмы решения. Обозначим через V (j) совокупность не превосходящих j элементов из V (здесь V – произвольная стратегия в рассматриваемой задаче). Для выражения

введем обозначение δ _j. Через М (j) обозначим сумму следующих трех слагаемых:

– затраты времени на перемещение процессора от точки l_j к точке α _n;

– затраты времени на перемещение процессора от точки α _n к точке l_j;

– суммарная продолжительность обслуживания объектов o_j, o_{j +1}, …, o_n.

Как очевидно,

Существенно, что величины М (j), j = 1,..., n, не зависят от выбираемой стратегии обслуживания, т.е. от того, какие объекты совокупности o_{j +1}, o_{j +2}, …, o_{n − 1} обслуживаются в прямом, а какие – в обратном рейсе процессора.

Для решения задачи I-1 применим метод динамического программирования. Пусть В* (i, D) – минимально возможная величина суммарного штрафа по объектам совокупности { о ₁, о ₂, …, о_i } при условии, что в рейсе λ ₊ общее время, затрачиваемое на обслуживание объектов из этой совокупности, равно D (таким образом, в частном случае D = 0 все объекты совокупности { о ₁, о ₂, …, о_i } обслуживаются в рейсе λ _–; в частном случае i = n и D = A₁ⁿ все объекты множества М обслуживаются в рейсе λ ₊). Отметим, что возможные значения параметра D целочисленны и лежат в диапазоне [0, A₁ⁿ]; при D > величины В* (i, D) заведомо не имеют смысла.

Как очевидно, В* (1, 0) – величина индивидуального штрафа по первому объекту в случае, когда его обслуживание реализуется в рейсе λ _-, т.е. завершается в момент времени γ _{0, 1} + М (1). В то же время В* (1, τ ₁) – величина индивидуального штрафа по первому объекту, если его обслуживание выполняется в рейсе λ ₊, т.е. завершается в момент γ _{0, 1} + τ ₁. Поэтому

В* (1, 0) = ϕ ₁(γ _{0, 1} + М (1)), (32)

В* (1, τ ₁) = ϕ ₁(γ _{0, 1} + τ ₁). (33)

При D ∉ {0, τ ₁} величины В* (1, D) смысла не имеют. Дополнительно удобно положить

В*(1, D) = + ∞ при D ∉ {0, τ ₁}. (34)

Предположим, что все значения В* (i, D) для некоторого i ∈ ∈ {1, 2, …, n − 2} уже найдены. При определении значений В* (i + 1, D) надо учитывать две возможности:

1. Объект o_{i +1} обслуживается в рейсе λ _+. Тогда рассматриваемой паре (i + 1, D) непосредственно предшествует ситуация (i, D - τ _{i +1}).

2. Объект o_{i +1} обслуживается в рейсе λ _–. Тогда рассматриваемой паре непосредственно предшествует ситуация (i, D).

С учетом этих возможностей получаем:

В* (i + 1, D) = min { В* (i, D – τ _{i +1}) + ϕ _{i +1}(γ _{0, 1} + γ _{1, 2} + … + γ _{i, i +1} + D),

В* (i, D) + ϕ _i+1 (γ _{0, 1} + γ _{1, 2} +…+ γ _{i,, i+1} + D + М (i + 1))}; (35)

здесь i ∈ {1, 2, …, n – 2}.

Вычисляемое по формуле (35) значение В* (i + 1, D) оказывается равным +∞ в том и только том случае, когда определяемая парой (i + 1, D) ситуация возникнуть не может.

При определении значений В* (n, D) следует иметь в виду, что по принятому соглашению объект o_n обслуживается при завершении движения λ ₊, _, т.е. n ∈ V. Поэтому каждой рассматриваемой паре (n, D) непосредственно предшествует только ситуация (n – 1, D – τ _n). Следовательно,

В* (n, D) = В* (n – 1, D – τ _n) + ϕ _n (γ _{0, 1} + γ _{1, 2} +…+ γ _{n –1, n} + D).(36)

Каждая вычисляемая величина В* (n, D) – это минимально возможный суммарный штраф по всем объектам, если в рейсе λ ₊ на их обслуживание затрачивается время D.

Оптимальное значение критерия К _opt рассматриваемой задачи I-1 определяется по формуле

(37)

Равенства (32)–(37) суть рекуррентные соотношения динамического программирования для решения задачи (I-1).

В соответствующей вычислительной процедуре сначала по формулам (32)–(33) определяются значения В* (1, 0) и В* (1, τ ₁). В соответствии с формулой (34) для D ∉ {0, τ ₁} величины В* (1, D) полагаются равными +∞. Далее, на основании формулы (35) сначала определяются все значения В* (2, D), затем все значения В* (3, D) и т.д. Последними по данной фор-муле для всех возможных значений D определяются величины В* (n – 1, D). Используя формулу (36), по известным величинам В* (n – 1, D) определяем значения В* (n, D). Оптимальное значение критерия решаемой задачи находится по формуле (37).

Процесс вычислений по соотношениям (32)–(37) удобно представлять как последовательное заполнение клеток таблицы значений функции В* (i, D). Строки этой таблицы соответствуют возможным значениям параметра i, i ∈ {1, 2, …, n }, а столбцы – возможным значениям параметра D, D ∈ {0, 1, 2, …, A₁ⁿ}. В каждую клетку (i, D) вносится величина В* (i, D).Таблица заполняется по строкам, в порядке роста их номеров. Заметим, что в процессе счета найденное значение В* (i, D) оказывается бесконечным в том и только том случае, когда при определяемом строкой значении параметра i фиксируемое столбцом значение параметра D невозможно.

Зафиксировав для каждого найденного в процессе вычислений по формуле (35) значения В* (i + 1, D) номер компоненты, на которой реализуется минимум правой части этой формулы, и определив затем значение параметра D, на котором достигается минимум правой части (37), легко строим искомую оптимальную стратегию.

Будем считать, что функции индивидуального штрафа либо заданы таблично, либо значение каждой из них в любой точке вычисляется путем выполнения ограниченного, не превышающего некоторой константы C, числа элементарных операций. В таком случае общее число выполняемых изложенным алгоритмом элементарных операций имеет верхней оценкой величину, прямо пропорциональную числу клеток в заполняемой таблице, т.е. произведению n × (A₁ⁿ+1).

Пример 2.5. Требуется определить оптимальную стратегию обслуживания пяти стационарных объектов при условиях: γ ₀₁ = 2, γ ₁₂ = 1, γ ₂₃ = 3, γ ₃₄ = 2, γ ₄₅ = 1, γ ₅₄ = 2, γ ₄₃ = 2, γ ₃₂ = 2, γ ₂₁ = 1, γ ₁₀ = 3 (значение γ ₁₀ для синтеза оптимальной стратегии фактической роли не играет); τ ₁ = 1; τ ₂ = 1; τ ₃ = 2; τ ₄ = 3; τ ₅ = 2;

j ₄(t) = t;

j ₅(t) = 2 t.

Легко вычисляются необходимые для применения рекуррентных соотношений величины М (i):

М (1) = 23; М (2) = 20; М (3) = 14; М (4) = 8.

Далее подсчитываем значения функции В* (i, D). По условиям решаемой задачи параметр i принимает значения 1, 2, 3, 4, 5; целочисленный параметр D принимает значения из отрезка [0, 9]. Результаты вычислений удобно фиксировать в табл. 2.3 значений функции В* (i, D), параметру i соответствуют строки таблицы, параметру D – ее столбцы. Символы бесконечности в таблицу не вносим.

По формулам (32) и (33) получаем: В* (1, 0) = ϕ ₁(25) =20; В* (1, 1) = ϕ ₁(3) =0.

Далее по формуле (35) имеем:

В* (2, 0) = В* (1, 0) + ϕ ₂ (23) = 36;

В* (2, 1) = min{ В* (1, 0) + ϕ ₂ (4); В* (1, 1) + ϕ ₂ (24)} =

= min {20 + 0; 0 + 18} = 18

(минимум в правой части рекуррентного соотношения достигается на второй компоненте, что отмечается цифрой в скобках после записи числа 18 в клетку (2, 1) табл. 2.3);

В* (2, 2) = ϕ ₁(3) + ϕ ₂(5) = 0;

В* (3, 0) = В* (2, 0) + ϕ ₃(20) = 36; В* (3, 1) = В* (2, 1) + ϕ ₃(21) = 22;

В* (3, 2) = min{ В* (2, 0) + ϕ ₃(8); В* (2, 2) + ϕ ₃(22)} =

= min {36 + 0; 0 + 8} = 8

(минимум в правой части рекуррентного соотношения достигается на второй компоненте);

В* (3, 3) = В* (2, 1) + ϕ ₃(9) = 18; В* (3, 4) = В* (2, 2) + ϕ ₃(10) =0.

В* (4, 0) = 52; В* (4, 1) = 39; В* (4, 2) = 26;

В* (4, 3) = min {36 + 11; 18 + 19} = 37

(минимум в правой части рекуррентного соотношения достигается на второй компоненте);

В* (4, 4) = min {22 + 12; 0 + 20} = 20

(минимум в правой части рекуррентного соотношения достигается на второй компоненте);

В* (4, 5) = 21; В* (4, 6) = 32; В* (4, 7) = 33.

Далее по формуле (36) находим:

В* (5, 2) = В* (4, 0) + ϕ ₅(11) = 74; В* (5, 3) = В* (4, 1) + ϕ ₅(12) = 63;

В* (5, 4) = В* (4, 2) + ϕ ₅(13) = 52; В* (5, 5) = В* (4, 3) + ϕ ₅(14) = 65;

В* (5, 6) = В* (4, 4) + ϕ ₅(15) = 50; В* (5, 7) = В* (4, 5) + ϕ ₅(16) = 53;

В* (5, 8) = В* (4, 6) + ϕ ₅(17) = 66; В* (5, 9) = В* (4, 7) + ϕ ₅(18) = 67.

Согласно (37), оптимальное значение критерия рассматриваемой задачи – это минимальное из вычисленных значений В* (5, D). Оно равно 50, соответствующее значение параметра D равно 6. Таким образом, оптимальная стратегия предусматривает, что на непосредственное обслуживание объектов в прямом рейсе должно затрачиваться 6 единиц времени. При этом на обслуживание объекта о ₅ уходит время τ ₅ = 2, на непосредственное в прямом рейсе обслуживание первых четырех объектов остается 4 единицы времени. При вычислении В* (4, 4) минимум реализуется на второй компоненте правой части рекуррентного соотношения; значит объект о ₄ в прямом рейсе обслуживать не следует, все четыре единицы времени должны быть затрачены на обслуживание в этом рейсе объектов из числа первых трех.

Таблица 2.3

Значения функции В* (i, D)

Ситуация, непосредственно предшествующая той, что описывается парой аргументов (3, 4) функции В*, единственна – это (2, 2); таким образом, объект о ₃ должен быть обслужен в прямом рейсе. На непосредственное обслуживание в этом рейсе первых двух объектов остаются две единицы времени. Ситуация, непосредственно предшествующая той, что описывается парой аргументов (2, 2) функции В* единственна – это (1, 1), объект о ₂ должен быть обслужен в прямом рейсе. Оставшаяся единица времени уходит на обслуживание в прямом рейсе объекта о ₁. Таким образом, оптимальная стратегия в рассмотренном приме-ре V _opt = {1, 2, 3, 5}; объекты о_j, где j ∈ V _opt, в реализации данной стратегии должны обслуживаться при выполнении прямого рейса, оставшийся объект о ₄ – при выполнении обратного рейса.

Отметим, что в случае, когда все функции индивидуального штрафа линейны (ϕ _i (t) = а_i t + b_i, i = 1,..., n), имеется возможность применения перестановочного приема, и задача I-1 решается очень просто. Пусть Q_j; вся совокупность вводимых характеристик Q_j, j ∈ {1, 2, …, n – 1}, вычислима путем выполнения линейно зависящего от n числа операций. Для любой стратегии V и любого элемента j ∈ V переход от обслуживания объекта о_j в прямом рейсе к его обслуживанию в обратном рейсе влечет увеличение индивидуального штрафа по этому объекту на а_j (М (j) – τ _j) и уменьшение суммарного штрафа по всем остальным объектам на Q_j τ _j. Очевидно, что при реализации оптимальной стратегии объект о_j должен обслуживаться в обратном рейсе, если а_j (М (j) – τ _j) < Q_j τ _j; объект о_j должен обслуживаться в прямом рейсе, если а_j (М (j) – τ _j) > Q_j τ _j; в случае а_j (М (j) – τ _j) = Q_j τ _j объект о_j может быть обслужен в любом из рейсов. Изложенное правило обеспечивает возможность синтеза оптимальной в задаче I-1 с линейными функциями индивидуального штрафа стратегии за время, линейно зависящее от числа подлежащих обслуживанию объектов.

Задача I-2, алгоритм решения. При решении данной задачи используется следующий факт.

Утверждение 4.1. Пусть V – любая стратегия в модели обслуживания I, удовлетворяющая условию k ∉ V, и пусть V* = = V ∪ { k }, здесь k ∈ {1, 2, …, n – 1}. Тогда t * _k (V) > t * _k (V*), t * _j (V) = = t * _j (V*) для j < k и t * _j (V*) > t * _j (V) для j > k, здесь j ∈ {1, 2, …, n – 1}.

Доказательство данного утверждения очевидно.

Стратегию, при реализации которой значение максимального из индивидуальных штрафов не превышает константы F, будем именовать F -стратегией. Для заданной константы F поставим вопрос, существует ли в рассматриваемой задаче I-2 какая-либо F -стратегия. Ответ дает следующий, основанный на утверждении 4.1 и обозначаемый через А(F), алгоритм:

1. Полагаем V = { n }; проверяем, обеспечивает ли стратегия V индивидуальный штраф по объекту о_n не больший, чем F; если это так, переходим к п. 2; в противном случае в рассматриваемой задаче F -стратегии отсутствуют, ответ на поставленный вопрос отрицательный, алгоритм работу заканчивает;

2. Полагаем k = 1;

3. Вводим стратегии V* = V и V** = V ∪ { k };

4. Проверяем, обеспечивает ли стратегия V* по объектам о_n и о_k индивидуальные штрафы, не большие F; если это так, пере-ходим к п. 6; в противном случае – к п. 5;

5. Проверяем, обеспечивает ли стратегия V** по объектам о_n и о_k индивидуальные штрафы не большие F; если это не так, в рассматриваемой задаче F -стратегии отсутствуют, ответ на поставленный вопрос отрицательный, алгоритм работу заканчивает; в случае положительного ответа полагаем V = V** и переходим к п. 6;

6. Если k = n – 1, полученное множество V является F -стратегией; ответ на поставленный вопрос положительный, алгоритм работу заканчивает; в противном случае следует увеличить имеющееся значение k на 1 и перейти к п. 3.

Благодаря описанному алгоритму, экстремальная задача I-2 решается методом деления пополам. Процесс решения начинается с назначения левой границы S ₁ и правой границы W ₁ диапазона, в котором локализовано искомое оптимальное значение критерия.

Можно положить:

Далее выполняется процедура, состоящая не более чем из log₂ (W ₁ – S ₁) + 1 однотипных этапов. На произвольном k -м этапе имеющийся отрезок [ S_k, W_k ], в котором локализовано оптимальное значение критерия, делится пополам; координату середины отрезка обозначаем через F_k. Затем к решаемой задаче применяется алгоритм А (F_k); если получаемый в результате ответ положителен, оптимальное значение критерия локализовано в левом полуотрезке; в противном случае это значение находится в правом полуотрезке. Поэтому в случае положительного ответа полагаем S_{k +1} = S_k и W_{k +1} = F_k ; в случае отрицательного ответа устанавливаем S_{k +1} = F_k и W_{k +1} = W_k. Далее переходим к выполнению следующего этапа. Процесс заканчивается в ситуации, когда в полученном отрезке локализации имеется только одна целочисленная точка.

Будем считать, что все функции индивидуального штрафа либо заданы таблично, либо значение каждой из них в любой точке вычисляется путем выполнения ограниченного, не превышающего некоторой константы числа элементарных действий. Тогда алгоритм А (F) имеет линейно зависящую от n оценку количества выполняемых элементарных операций и вычисли-тельная сложность изложенной процедуры решения задачи I-2 имеет оценку Сn log₂(W ₁ – S ₁), где С – не зависящая от параметров решаемой задачи константа.

Задача II-1, алгоритм решения. Для решения задачи II-1 применим метод динамического программирования. Пусть В' (i, D) – минимально возможная величина суммарного штрафа по объектам совокупности { о ₁, о ₂, …, о_i } при условии, что в рей-се λ ₊ общее время, затрачиваемое на обслуживание объектов из этой совокупности равно D. Отметим, что так же, как при рас-смотрении задачи I-1, возможные значения параметра D целочисленны и лежат в числовом диапазоне [0, ]. nA 1

По определению В' (1, 0) – это величина индивидуального штрафа по объекту о₁ в случае, когда его обслуживание реализуется в рейсе λ _–, т.е. завершается в момент времени γ _{0, 1} + τ ₁ + Т. В то же время В' (1, τ ₁) – величина индивидуального штрафа по объекту о ₁, если его обслуживание выполняется в рейсе λ ₊, т.е. завершается в момент γ _{0, 1} + τ ₁. Получаем:

В' (1, 0) = ϕ ₁(γ _{0, 1} + τ ₁ + Т), (38)

В' (1, τ ₁) = ϕ ₁(γ _{0, 1} + τ ₁). (39)

При D ∉ {0, τ ₁ } величины В' (1, D) смысла не имеют. Удобно положить

В' (1, D) = +∞ при D ∉ {0, τ ₁}. (40)

Предположим, что все значения В' (i, D) уже найдены. При отыскании значений В' (i + 1, D), где i ∈ {1, 2, …, n – 1}, надо учитывать две возможности:

1. Объект o_{i +1} обслуживается в рейсе λ _+. Тогда рассматриваемой паре (i + 1, D) непосредственно предшествует ситуация (i, D – τ _{i +1}).

2. Объект o_{i +1} обслуживается в рейсе λ _–. В этом случае рассматриваемой паре непосредственно предшествует ситуация (i, D).

С учетом указанных возможностей получаем:

В' (i + 1, D) = min{ В' (i, D – τ _{i +1}) + ϕ _{i +1}(γ _{0, 1} + γ _{1, 2} + … + γ _{i, i +1} + D),

В' (i, D) + ϕ _{i +1}(γ _{0, 1} + γ _{1, 2} +…+ γ _{i,, i +1} +τ ₁ + τ ₂ +…+ τ _{i +1} – D + Т) }; (41)

здесь i ∈ {1, 2, …, n - 1}.

Вычисляемое значение В' (i + 1, D) оказывается равным +∞ в том и только том случае, когда определяемая парой (i + 1, D) ситуация реально возникнуть не может.

Каждая определяемая по формуле (41) величина В' (n, D), D ∈ {0, 1, 2, …, }, – это минимально возможный суммарный штраф по всем объектам, если в рейсе λ nA 1 ₊ на их обслуживание затрачивается время D. Оптимальное значение критерия К _opt рассматриваемой задачи II-1 определяется по формуле

(42)

Формулы (38) – (42) суть рекуррентные соотношения динамического программирования для решения задачи (II-1). Процесс вычислений по этим соотношениям удобно представлять как последовательное заполнение таблицы, строки которой соответствуют значениям параметра i, i ∈ {1, 2, …, n }, а столбцы – значениям параметра D, D ∈ {0, 1, 2, …, A₁ⁿ}. Таблица заполняется по строкам, в порядке роста их номеров. Зафиксировав в процессе вычислений по формуле (41) для каждого найденного значения В' (i + 1, D) номер компоненты, на которой реализуется минимум правой части, и определив значение параметра D, на котором достигается минимум правой части (42), легко строим искомую оптимальную стратегию.

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

Задача II-2, алгоритм решения. Легко видеть, что для модели II утверждение 4.1 неверно. Поэтому предложенный для задачи I-2 решающий метод к задаче II-2 неприменим. Задачу II-2 можно решить методом динамического программирования. Пусть В" (i, D) – минимально возможная величина максимального из индивидуальных штрафов по объектам совокупности о₁, о₂, …, о_i при условии, что в рейсе λ ₊ общее время, затрачиваемое на обслуживание объектов из этой совокупности, равно D. Так же, как при рассмотрении предыдущих задач, возможные значения параметра D целочисленны и лежат в числовом диапазоне [0, ]. nA 1

В" (1, 0) – это величина индивидуального штрафа по объекту о ₁ в случае, когда его обслуживание реализуется в рейсе λ _-, т.е. завершается в момент времени γ _{0, 1} + τ ₁ + Т. В то же время В" (1, τ ₁) – величина индивидуального штрафа по тому же объекту о ₁, если его обслуживание выполняется в рейсе λ ₊, т.е. завершается в момент γ _{0, 1} + τ ₁. Поэтому

В" (1, 0) = ϕ ₁(γ _{0, 1} + τ ₁ + Т), (43)

В" (1, τ ₁) = ϕ ₁(γ _{0, 1} + τ ₁). (44)

При D ∉ {0, τ ₁} величины В" (1, D) смысла не имеют. Полагаем

В" (1, D) = +∞ при D ∉ {0, τ ₁}. (45)

Предположим, что все значения В" (i, D) найдены. Для отыскания величин В" (i +1, D), с учетом имеющихся возможностей обслуживания объекта o_{i +1} записываем:

В" (i + 1, D) = min {max [ В" (i, D – τ _{i +1}), ϕ _{i +1}(γ _{0, 1} + γ _{1, 2} + … +

+ γ _{i, i +1} + D)], max [ В" (i, D), ϕ _{i +1}(γ _{0, 1} + γ _{1, 2} +…+

+ γ _{i,, i +1} +τ ₁ + τ ₂ +…+ τ _{i +1} – D + Т) ]}; (46)

здесь i ∈ {1, 2, …, n − 1}.

Вычисляемое значение В" (i + 1, D) оказывается равным +∞ в том и только том случае, когда определяемая парой (i + 1, D) ситуация возникнуть не может.

В итоге итерационного процесса каждая вычисленная по формуле (46) величина В" (n, D), D ∈ {0, 1, 2, …, }, – это минимально возможная величина наибольшего из индивидуальных штрафов по всем объектам в ситуации, когда в рейсе λ nA 1₊ на их обслуживание затрачивается время D. Оптимальное значение критерия К _opt рассматриваемой задачи II-2 определяется по формуле

(47)

Равенства (43)–(47) суть рекуррентные соотношения динамического программирования для решения задачи (II-2).

Оценка вычислительной сложности изложенного алгоритма решения задачи (II-2) такая же, как для приведенных общих алгоритмов решения задач I-1 и II-1.

Тема 12. Труднорешаемые задачи. Полиномиально разрешимые конкретизации, приближенные и эвристические алгоритмы

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

В данном разделе изучаются вопросы вычислительной сложности задач и алгоритмов. Выделяются класс задач, разрешимых в полиномиальном времени, и класс труднорешаемых задач. Алгоритм решает задачу в полиномиальном времени, если число выполняемых им элементарных операций не превышает Р (L), где Р – некоторый полином от L – объема входной информации по задаче. Число элементарных операций, гарантирующих получение искомого результата в труднорешаемой задаче, в лучшем случае имеет оценку, экспоненциально зависящую от L. Для ряда труднорешаемых задач выделяются полиномиально разрешимые конкретизации; излагаются общие принципы построения приближенных и эвристических алгоритмов; строятся процедуры, позволяющие синтезировать качественные в том либо ином смысле решения за реально приемлемое время. Вопросы построения приближенных и эвристических алгоритмов рассматриваются во многих посвященных дискретной оптимизации монографиях и учебниках. В этой связи отметим.