Пример применения метода динамического программирования

2.6. Динамическое  программирование (ДП) - продолжение

Пример  применения метода ДП

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

 

 

3. Алгоритмы с гарантированной оценкой точности

3.1. Минимизация взвешенной суммы моментов завершения обслуживания требований.

Рассмотрим задачу P//ΣwjCj,

где

P – обозначение системы параллельных приборов с одинаковой производительностью

C_j – момент завершения обслуживания требования j

w_j – весовой коэффициент, характеризующий относительную важность требования j

В этой задаче расписание однозначно определяется разбиением множества  требований на подмножества N₁,..., Nm,

где требования множества N_l обслуживаются прибором l,

При этом достаточно ограничиться рассмотрением расписаний, в которых требования каждого подмножества упорядочены по правилу SWPT, т.е. по неубыванию значений p_j/w_j. Это можно доказать при помощи перестановочного приема.

Приведем приближенный алгоритм решения задачи P//ΣwjCj, для которого имеются гарантированная оценка точности.

1. Перенумеруем требования в порядке SWPT так, что p₁/w₁ < … < p_n/w_n.

Далее будем последовательно, начиная с 1-го назначать требования приборам 1, .., n, пусть требования 0, … k, где 0 – фиктивное требование, соответствующее начальной ситуации, k < n, уже назначены.

2. Требование k + 1 назначается тому прибору l, сумма длительностей обслуживания ранее назначенных требований которого минимальна.

Т.е. если

P_l - сумма длительностей обслуживания требований, назначенных на прибор l, где l = 1, … , m.

то прибор l, выбирается исходя из условия P_l = min_1<h<m P_h.

Назначаем требование k +1 на прибор l

3. Если k+1=n, т.е все требования назначены - прекращаем процесс, иначе переходим к назначению тр-ия k+2.

Заметим, что полученное про мощи алгоритма значение целевой функции является, в общем случае, оценкой сверху точного решения. Данный алгоритм относится к категории приближенных с гарантированной оценкой точности. Для него известна оценка величины ΔН=F^h/F* (где F^h – реш. посредством алгоритма, F* - точ. реш.).

Рассмотрим пример задачи P//ΣwjCj.

3 параллельно работающих станка обрабатывают 8 изделий. Изделия поступили на линию одновременно и требуют специальных условий хранения при пребывании на линии. Стоимость хранения изделия j в единицу времени w_j и длительность его обработки p_j указаны в таблице. Найти расписание, минимизирующее суммарную стоимость хранения изделий.

 

 

 

 

 

 

 

 

 

 

 

 

3.2. Минимизация числа используемых приборов

Рассмотрим задачу P/dj=d/Cj ≤ dj

d≥max p_j, для j=1…т, а также m=n

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

* * *

Обозначим R_l – резерв времени прибора l, то есть разницу между d и суммарной длительностью работ, уже назначенных на прибор l.

Обозначим π некоторую перестановку всех требований.

* * *

Для данной задачи известно 4 алгоритма с гарантированной  оценкой точности. Вначале первому прибору назначается фиктивная работа p₀.

На k-м шаге (k=1, …,n) для назначения выбирается требование, находящееся на месте k перестановки π.

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

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

Для третьего и  четвертого алгоритма предполагается, что в перестановке π требования расположены в порядке LPT невозрастания значений p_j, а назначения работ требованиям осуществляются также, как и в первом и втором алгоритмах.

 

4. Один прибор, максимальный штраф.

Рассмотрим задачу 1/ prec / f_max

где f_max = maxf_j(C_j) - максимальная стоимость – функция от моментов завершения обслуживания.

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

Пусть отношения  предшествования заданы ориентированным бесконтурным графом Gn

Следующий алгоритм предложен Е. Лоулером.

Обозначим через N-(Gn) множество всех висячих вершин графа Gn. т.е. множество всех вершин, не имеющих потомков в графе Gn

1. Вычислим момент завершения всех требований, просуммировав их длительность. Pn = Σp_j

Очевидно, что  обслуживание одного из требований множества N-(Gn) завершается в момент времени Pn.

Если этим требованием  является требование i, то стоимость его обслуживания равна fi(Pn). Поскольку функции стоимости являются неубывающими, нетрудно убедиться, что последним обслуживаемым требованием в оптимальной перестановке является требование i N- (Gn) такое, что значение fi(Pn) минимально.

Πусть i_n является таким требованием. Тогда момент завершения обслуживания оставшихся требований равен

P_n-1=P_n - p_in .

Построим граф G_n-1 путем удаления из графа Gn вершины i_n и всех входящих в нее дуг. В графе G_n-1 определим вершину (требование) i_n-1 аналогично тому, как была определена вершина i_n. Процесс повторяется до тех пор, пока не будет построена последовательность (i₁,... ,i_n), являющаяся оптимальным решением задачи 1/prec/fmax.

* * *

Рассмотрим пример задачи 1/prec/L_max, (L=C-d) в которой имеется 10 требований. Требование 3 предшествует требованию 4, которое, в свою очередь, предшествует требованиям 1, 7 и 9. Длительности  p_j и директивные сроки d_j заданы в таблице.

j	1	2	3	4	5	6	7	8	9	10
pj	4	2	3	5	7	4	1	2	9	4
dj	14	23	17	25	17	14	10	7	9	24