Автоматика и телемеханика, № 5, 2020

(Объединенный институт проблем информатики НАН Беларуси, Минск)

ОБЛАСТЬ ОПТИМАЛЬНОСТИ ПЕРЕСТАНОВКИ

ОБСЛУЖИВАНИЯ НА ОДНОМ ПРИБОРЕ ТРЕБОВАНИЙ

С НЕОПРЕДЕЛЕННЫМИ ДЛИТЕЛЬНОСТЯМИ

Исследуется задача оптимизации расписания обслуживания заданно-

го множества требований на одном приборе. При составлении расписа-

ния для каждого требования известны нижняя граница и верхняя гра-

ница допустимой длительности его обслуживания. В качестве крите-

рия оптимальности расписания рассматривается минимизация суммарно-

го времени обслуживания заданного множества требований. Исследова-

ны свойства области оптимальности перестановки обслуживания требова-

ний. Разработаны полиномиальные алгоритмы построения области опти-

мальности перестановки обслуживания требований и вычисления объема

области оптимальности. Определены условия существования пустой об-

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

новлен критерий существования перестановки обслуживания требований

с максимально возможным объемом области оптимальности.

Ключевые слова: теория расписаний, неопределенные длительности об-

служивания требований, минимизация суммарного времени, область оп-

тимальности.

DOI: 10.31857/S0005231020050050

1. Введение

Оперативно-календарное планирование производства включает этап со-

ставления календарных планов выполнения поступивших заказов (составле-

ние расписаний обслуживания заданного множества требований) на имею-

щемся оборудовании (на множестве обслуживающих приборов). Оптималь-

ное расписание производственного процесса является важным фактором его

эффективности, поскольку позволяет сократить производственные расходы

предприятия, уменьшить время реализации заявок заказчиков на продукцию

предприятия, своевременно снабжать прозводственный процесс сырьем, ма-

териалами и комплектующими деталями, необходимыми для изготовления

конечной продукции предприятия. Оптимальное расписание производствен-

ного процесса позволяет уменьшить расходы на хранение сырья, комплектую-

щих деталей и материалов и в итоге повысить эффективность использования

имеющихся ресурсов (обслуживающих приборов) и капитала.

Для практических задач оперативно-календарного планирования, как

правило, не удается заранее определить точные значения длительностей об-

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

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

ются алгоритмы построения расписаний, близких к оптимальным, в условиях

неопределенности числовых параметров [1-9].

В разделе 2 данной статьи рассматривается задача построения близко-

го к оптимальному расписания обслуживания требований множества J =

= {J₁, . . . , J_n} на одном приборе с критерием

∑C_i минимизации суммы мо-

ментов C_i завершения обслуживания всех требований J_i ∈ J при условии,

что при построении расписания известны только нижняя граница p^Li > 0 и

верхняя граница p^Ui ≥ p^Li возможной длительности p_i ∈ [p^Li, p^Ui ] обслужива-

ния требования J_i. В разделе 3 определяется область оптимальности для пе-

рестановки π_k = (Jk1 , . . . , Jkn ) обслуживания требований множества J , кото-

рая содержит параллелепипед оптимальности для той же перестановки. Па-

раллелепипед оптимальности для перестановки π_k был исследован в [10-17].

В разделе 4 разработаны полиномиальные алгоритмы для определения обла-

сти оптимальности для перестановки π_k и для определения объема области

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

нении которых область оптимальности для перестановки обслуживания за-

данных требований является пустым множеством. В разделе 5 исследованы

свойства перестановки π_k обслуживания требований множества J , которая

имеет максимальный объем области оптимальности.

2. Постановка задачи и обзор известных результатов

Множество требований J = {J₁, . . . , J_n} необходимо обслужить на одном

приборе. Точное значение длительности p_i обслуживания требования J_i ∈

∈ J не известно на момент построения расписания обслуживания требо-

ваний J . Прерывания обслуживания требования запрещены. При реализа-

ции расписания обслуживания требований J длительность p_i обслужива-

ния требования Ji [ J мо]жет принимать любое действительное значение из

заданного отрезка

p^Li,p^Ui

, где p^Ui ≥ p^Li > 0. Точное значение длительности

[

]

p_i ∈

p^Li,p^Ui

становится известным лишь в момент C_i завершения обслужи-

вания требования J_i. Пусть Rⁿ обозначает пространство n-мерных действи-

тельных векторов, а Rⁿ⁺ - подмножество Rⁿ всех неотрицательных n-мерных

действительных векторов, Rⁿ⁺ ⊂ Rⁿ. В пространстве Rⁿ множество всех век-

торов (p₁, . . . , p_n) допустимых длительностей обслуживания требований мно-

жества J представляет собой n-мерный параллелепипед, т.е. множество всех

векторов p = (p₁, . . . , p_n) ∈ Rⁿ⁺, удовлетворяющих следующей системе нера-

венств:

p^L1 ≤ p₁ ≤ p^U1; ... ; p^Ln ≤ p_n ≤ p^Un .

Множество допустимых длительностей (p₁, . . . , p_n) = p ∈ Rⁿ⁺ обслуживания

требований множества J представим как декартово {роизведение отрезков

[p^Li, p^Ui ]:

×ⁿⁱ⁼¹[p^Li,p^Ui ] := [p^L1,p^U1 ] × ... × [p^Ln,p^Un ] = T =

p∈Rⁿ⁺:p^Li ≤p_i ≤p^Ui,

}

i ∈ {1,...,n}

. Вектор p ∈ T будем называть сценарием. Пусть множе-

ство Π = {π₁, . . . , π_n!} содержит все перестановки π_k = (Jk1 , . . . , Jkn ) тре-

бований J . Для фиксированных сценария p ∈ T и перестановки π_k ∈ Π

пусть C_i = C_i(π_k, p) обозначает момент завершения обслуживания требова-

ния J_i ∈ J в активном расписании [5, 18], однозначно определенном переста-

новкой π_k. Критерий

∑C_i обозначает минимизацию суммы моментов завер-

шения обслуживания требований J :





∑

∑



(1)

C_i(π_t,p) = min

C_i(π_k,p)

πk∈Π





J_i∈J

Указанная в (1) перестановка π_t = (Jt1 , . . . , Jtn ) ∈ Π является оптимальной

перестановкой обслуживания требований J для фиксированного сценария

p∈T.

Поскольку число требований n = |J | известно на момент составления рас-

писания π_t обслуживания требований J , то критерий

∑C_i означает также

∑

C_i(π_k,p)

минимизацию среднего времени^Ji∈J

обслуживания требований мно-

жества J .

Сформулированная неопределенная задача обозначается как 1|p^Li ≤ p_i ≤

≤p^Ui|

∑C_i, если использовать введенную в [19] трехпозиционную фор-

му α|β|γ обозначения задач теории расписаний. Здесь и далее α обозначает

тип обслуживающей системы, β - условия обслуживания требований, а γ -

целевую функцию.

Если сценарий p ∈ T известен к моменту построения расписан [я, ины]ми

словами, для каждого требования J_i ∈ J выполняется равенство

p^Li,p^Ui

= [p_i, p_i], то неопределенная задача 1|p^Li ≤ p_i ≤ p^Ui |

∑C_i превращается в де-

терминированную задачу 1||

∑C_i. Обозначение 1|p|∑ C_i будем использовать

для детерминированной задачи 1||

∑C_i, в которой зафиксирован сценарий

p ∈ T к моменту построения оптимального расписания. Как показано в [20],

задачу 1|p|

∑C_i можно решить за время O(nlogn) в силу следующего кри-

терия оптимальности перестановки π_k ∈ Π.

Теорема 1. Перестановка π_k = (Jk1,...,Jkn) ∈ Π обслуживания требо-

ваний множества J является оптимальной для задачи 1|p|

∑C_i тогда и

только тогда, когда выполняются следующие неравенства:

(2)

pk1 ≤ ... ≤ pkn.

Если pku < pkv , то требование Jku предшествует требованию Jkv в любой

перестановке π_k ∈ Π, которая является оптимальной для задачи 1|p|

∑C_i.

Поскольку в неопределенной задаче 1|p^Li ≤ p_i ≤ p^Ui |

∑C_i сценарий p ∈ T

не фиксирован на момент построения перестановки π_k ∈ Π обслуживания

требований J , то точное время C_i завершения обслуживания требования

J_i ∈ J определить невозможно до момента завершения обслуживания тре-

бования J_i. Следовательно, значение целевой функции

∑C_i для перестанов-

ки π_k обслуживания требований J остается неизвестным вплоть до момента

завершения обслуживания всех требований множества J , если для требова-

ний J_i ∈ J выполняются строгие неравенства p^Li < p^Ui .

Для неопределенной задачи α|p^Li ≤ p_i ≤ p^Ui |γ, как правило, не существу-

ет расписания, которое оставалось бы оптимальным для всех сценариев из

множества T мощности, большей единицы. Поэтому в литературе по ис-

следованию таких некорректных задач теории расписаний вводят дополни-

тельные целевые функции и (или) используют те или иные предположе-

ния. В частности, использование стохастического метода для решения зада-

чи α|p^Li ≤ p_i ≤ p^Ui |γ основано на предположении о том, что все длительности

обслуживания требований являются случайными величинами с известными

законами распределения вероятностей [7, 18].

Если нет достаточной информации о распределении вероятностей случай-

ных длительностей, то используют другие методы [5, 21]. Так, при использо-

вании робастного метода [2, 22-24] лицо, принимающее решение, предпочи-

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

ния, которое предлагается для реализации [4, 9, 23]. Для любой перестановки

π_k ∈ Π и любого сценария p ∈ T разность γ^kp - γ^tp = r(π_k,p) принято называть

сожалением (regret) для перестановки π_k со значением целевой функции γ,

равным γ^kp для сценария p. Значение Z(π_k) = max{r(π_k, p) : p ∈ T } называет-

ся абсолютным сожалением в наихудшем случае (worst-case absolute regret), а

{

}

значение Z^∗(π_k) = max

r(π_k,p) : p ∈ T

- относительным сожалением в наи-

γ^tp

худшем случае (worst-case relative regret).

Несмотря на то, что задача 1|p|

∑w_iC_i полиномиально разрешима [20]

при любых весах w_i > 0, заданных для множества требований J_i ∈ J , по-

строение перестановки π_t ∈ S с наименьшим значением Z(π_t) (или переста-

новки с наименьшим значением Z^∗(π_t)) для задачи 1|p^Li ≤ p_i ≤ p^Ui |

∑C_i явля-

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

[21, 24, 25].

В [3] разработан метод ветвей и границ для построения перестанов-

ки π_t с минимальным значением абсолютного сожаления Z(π_t) для задачи

1|p^Li ≤ p_i ≤ p^Ui |

∑w_iC_i. Вычислительные эксперименты на компьютере пока-

зали, что предложенный метод позволяет строить такую перестановку π_t для

задачи 1|p^Li ≤ p_i ≤ p^Ui |

∑w_iC_i при условии, что число n заданных требований

не превосходит 40.

Использование метода, основанного на нечетких множествах, позволяет

строить расписания, которые являются оптимальными при нечетких дли-

тельностях обслуживания требований множества J на приборах заданного

множества M [8, 9, 26]. Этот метод позволяет решать неопределенные задачи

теории расписаний только при малых значениях числа n заданных требова-

ний.

В [1] было протестировано несколько эвристик для решения задачи

1|p^Li ≤ p_i ≤ p^Ui |

∑w_iC_i. В проведенных вычислительных экспериментах для

n ∈ {100,300,400,600,800,1000} использовались различные законы распреде-

ления вероятностей для выбора фактических длительностей обслуживания

требований. Вычислительные эксперименты позволили выделить наилучшую

эвристику U2, которая по всем решенным тестовым примерам давала сред-

нюю погрешность целевой функции

∑w_iC_i, равную 1,1% от значения целе-

вой функции, полученного для фактических длительностей обслуживания

требований.

Метод, основанный на устойчивости расписаний [6, 10-17] включает ана-

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

тельностей обслуживания требований множества J и построение на основе

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

любого сценария p ∈ T минимальное доминирующее множество содержит хо-

тя бы одно оптимальное расписание. В отличие от стохастического метода, ро-

бастного метода и метода, основанного на нечетких множествах, цель метода,

основанного на устойчивости расписаний, заключается в поиске расписания,

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

стимых сценариев из заданного множества T . В частности, если существует

одноэлементное доминирующее множество {π_t} для задачи α|p^Li ≤ p_i ≤ p^Ui |γ,

то расписание π_t является оптимальным для задачи α|p|γ при всех сценариях

p ∈ T, несмотря на неопределенность длительностей обслуживания требова-

ний множества J .

В [10-12, 14, 15] метод, основанный на устойчивости расписаний, исполь-

зовался для решения задачи 1|p^Li ≤ p_i ≤ p^Ui |

∑w_iC_i. В [15] доказан кри-

терий существования одноэлементного доминирующего множества для за-

дачи 1|p^Li ≤ p_i ≤ p^Ui |

∑w_iC_i. В [12] для n ∈ {50,100,500,1000, 5000, 10000}

были случайным образом сгенерированы сложные примеры задачи

1|p^Li ≤ p_i ≤ p^Ui |

∑w_iC_i, которые были решены приближенно разработанным

алгоритмом MAX-OPTBOX со средней погрешностью, равной 1,5%. В [10]

примеры задачи 1|p^Li ≤ p_i ≤ p^Ui |

∑C_i были случайным образом сгенерирова-

ны для n ∈ {10, 20, . . . , 100, 200, . . . , 1000, 2000, . . . , 10000} и решены прибли-

женно разработанным алгоритмом 3 со средней погрешностью, равной 0,74%.

Алгоритм MAX-OPTBOX (алгоритм 3) строит перестановку π_k ∈ Π, для

которой параллелепипед оптимальности имеет наибольший полупериметр

(наибольший относительный полупериметр соответственно). Алгоритм 3 учи-

тывает следующую особенность целевой функции

∑C_i: увеличение δ значе-

ния целевой функции в результате нарушения неравенства (2) из-за факти-

ческой длительности pki требования Jki влечет увеличение значения целевой

функции на величину δ(n - i + 1). Поэтому ошибка при выборе порядка об-

служивания требования Jki важнее такой же по величине ошибки при выборе

порядка обслуживания требования Jkj , если i < j.

Определение параллелепипеда оптимальности приведено в [10, 12]. Пусть

M = (ki1,...,ki|M|) представляет собой упорядоченное подмножество мно-

жества

{1, . . . , n}, для которого выполняются следующие соотношения:

{k₁, . . . , k_|M|} ⊆ {1, . . . , n}, |M| ≤ n и ki1 < . . . < ki|M| .

Определение 1. Максимальный по включению параллелепипед

[

]

[

]

[

]

OB(π_k,T) = l^optk

,u^optk

×...× l^optk

,u^optk

=: ×kir ∈M l^optk

,u^opt

⊆T

i|M|

k_ir

называется параллелепипедом оптимальности для перестановки π_k =

= (Jki1 , . . . , Jkin ) ∈ Π, если перестановка π_k, будучи оптимальной для

задачи 1|p|

∑C_i со сценарием p = (p₁,...,p_n) ∈ T, остается оптимальной

и для задачи 1|p^′|

∑C_i с любым сценарием p^′ = (p^′1,...,p^′n) ∈ [p₁,p₁] × ...

[

]

[

]

[

]

...×

pkir -1, pk_ir -1

× l^optk,uoptk

pkir +1, pk_ir +1

× ... × [p_n,p_n] ∈ T.

Если

нет сценария p ∈ T, для которого перестановка π_k является оптимальной

для задачи 1|p|

∑C_i, то полагаем OB(π_k,T) = ∅.

Любая вариация p′ki

длительности pkir обслуживания требования J

k_ir

∈

[

]

∈ J, принадлежащая максимальному (по включению) отрезку l^optk,uopt

k_ir

указанному в определении 1, гарантирует оптимальность перестановки π_k ∈

∈ Π для любого сценария p^′ = (p^′1,...,p^′n), если для него выполняется вклю-

[

]

[

]

чение p′ki

∈ l^optk,uoptk

. Максимальный отрезок l^optk,uoptk

длины u^optk

-lopt ≥0,_k

l^optk

≤ u^opt, указанный в определении 1, будем называть отрезком оптималь-_k

ности для требования Jkir ∈J в перестановке π_k. Если не существует такого[

]

отрезка оптимальности l^optk,uoptk

, l^optk

≤u^optk, для требования J

k_ir

∈J , то бу-

дем говорить, что требование J

k_ir

не имеет отрезка оптимальности в пере-

становке π_k.

3. Область оптимальности перестановки требований π_k ∈ Π

Определим область оптимальности OR(π_k, T ) для перестановки π_k ∈

∈ Π, которая содержит параллелепипед оптимальности перестановки π_k:

OB(π_k,T) ⊆ OR(π_k,T).

Определение 2. Максимальное по включению замкнутое подмноже-

ство OR(π_k,T) ⊆ T множества Rⁿ⁺ называется областью оптимально-

сти для перестановки π_k = (Jk1 ,... ,Jkn ) ∈ Π относительно T, если пере-

становка π_k является оптимальной для задачи 1|p|

∑C_i при любом сцена-

рии p = (p₁,... ,p_n) ∈ OR(π_k,T). Если не существует сценария p ∈ T, для

которого перестановка π_k является оптимальной для задачи 1|p|

∑C_i, то

полагаем OR(π_k, T ) = ∅.

В силу теоремы 1 будем различать три типа отрезков для каждого требова-

ния Jkr ∈ J в фиксированной перестановке π_k = (Jk1 , . . . , Jkn ) ∈ Π, а именно:

[

]

[

]

отрезок оптимальности l^optk,uoptk

⊆

pLkr ,p^U

;

[

]

[

]

отрезок условной оптимальности l^coptk,ucoptk

⊆

pLkr ,p^U

[

]

[

]

отрезок неоптимальности

l^nonk,unonk

⊆

pLkr ,p^U

[

]

Отрезок оптимальности l^optk

,u^optk

для требования Jkr в перестановке π_k

указан в определении 1 параллелепипеда оптимальности.

Отрезком неоптимальности для требования Jkr в перестановке π_k =

[ (Jk1 , . . .]Jk[) ∈ Π б]удем называть максимальный по включению отрезок

l^nonk,unonk

⊆

pLkr ,pUkr

, для которого перестановка π_k = (Jk1 , . . . , Jkn ) не мо-

жет быть оптимальной для задачи 1|p^′|

∑C_i ни при каком сценарии p^′ =

= (p^′1, . . . , p^′n) ∈ T таком, что

{

[

]}

[

]

{

[

]}

(p^′1, . . . , p^′n) ∈

×^r-1i=1

p^Lk

,p^Uk

l^nonk,unonk

×^ni=r+1

p^Lk

,p^U

k_i

В силу необходимых и достаточных условий (2) оптимальности переста-

новки π_k ∈ Π для задачи 1|p|

∑C_i для каждого отрезка неоптимальности

[l^nonk,unonk] либо существует требование Jkv ∈ J такое, что r < v и выполняют-

ся соотношения

(3)

p^Uk

=l^nonk

<u^nonk

=p^Uk

либо существует требование Jkw ∈ J такое, что w < r и выполняются соотно-

шения

(4)

p^Lk

=l^nonk

<u^nonk

=p^Lk

Из определения 1 также следует, что открытый интервал неоптимально-

сти (l^nonk,unonk) для требования Jkr в перестановке πk = (Jk1 , . . . , Jkn ) ∈ Π не

[

]

может иметь общих точек с отрезком оптимальности l^optk,uopt

, т.е.

⋂[

]

(5)

(l^nonk,unonk)

l^optk,uopt

= ∅.

Для демонстрации приведенных определений будем использовать при-

мер

задачи

1|p^Li ≤ p_i ≤ p^Ui |

∑C_i с 18 требованиями, n = 18. Отрезки

[

]

p^Li,p^Ui

, определяющие допустимые длительности обслуживания требова-

[

]

ний J_i ∈ J = {J₁, . . . , J₁₈}, заданы в таблице. Отрезки

p^Li,p^Ui

представле-

ны также на рис. 1 в системе прямоугольных координат для перестановки

π₁ = (J₁,... ,J₁₈) ∈ Π. На рис. 1 ось абсцисс определяет отрезки [p^Li,p^Ui ] до-

пустимых длительностей обслуживания требований J_i ∈ J . На оси ординат

указаны требования J_i из множества J .

Отрезком условной оптимальности для требования Jkr в перестанов-

ке π_k = (Jk1 , . . . , Jkn ) ∈ Π называется максимальный по включению отрезок

[

]

[

]

[

]

l^coptk,ucoptk

⊆

pLkr ,pUkr

такой, что любая точка p∗kr

∈ l^coptk,ucopt

не принад-

лежит открытому интервалу неоптимальности, p∗kr ∈ (l^nonk,unon), и при этомk

существует хотя бы одно требование Jkd ∈ J , d = r, для которого выполня-

[

]

ется включение p∗kr

∈ pLkd,p^U

k_d

Из определен[я отрезк] условной оптимальности следует, что существу-

ют точки p∗kr

∈ l^coptk,ucoptk

такие, что перестановка π_k ∈ Π является опти-

мальной для задачи 1|p^′|

∑C_i со сценарием p^′ = (p^′1,...,p^′n) ∈ [pk1,pk1] × ...

... × [pkr-1,pkr-1] × [pkr,pkr] ×[[pkr+1,pkr]1] × ... × [pkn,pkn], и при этом су-

ществуют другие точки p^∗∗k

∈ l^coptk,ucoptk

такие, что перестановка π_k ∈ Π не

является оптимальной для задачи 1|p^′′|

∑C_i со сценарием p^′′ = (p^′′1,...,p^′′n) ∈

∈ [pk1 , pk1 ] × . . . × [pkr-1, pkr-1] × [pk∗r, pk∗r] × [pkr+1, pkr +1] × . . . × [pkn , pkn ]. На

рис. 1 отрезки условной оптимальности для требований J_i ∈ J в перестанов-

ке π₁ = (J₁, . . . , J₁₈) заштрихованы горизонтальными отрезками.

Исходные данные для примера 1 задачи 1|p^Li ≤ p_i ≤ p^Ui |

∑C_i

p^Li

p^Ui

Требования J_i

J₁₈

J₁₇

J₁₆

J₁₅

J₁₄

J₁₃

J₁₂

J₁₁

J₁₀

J₉

J₈

J₇

J₆

J₅

J₄

J₃

J₂

J₁

1 2 3 4 5 6 7 8 9 10

Длительности p_i

Рис. 1. Отрезки оптимальности, отрезки условной оптимальности (заштрихо-

ваны горизонтальными отрезками) и отрезки неоптимальности (заштрихова-

ны горизонтальными и вертикальными отрезками) для требований J_i ∈ J в

перестановке π₁ = (J₁, . . . , J₁₈) для примера 1 задачи 1|p^Li ≤ p_i ≤ p^Ui |

∑C_i.

Отметим также, что в любой фиксированной перестановке π_k = (Jk1 , . . .[

]

...,Jkn) ∈ Π отрезок l^coptk,ucoptk

условной оптимальности для требования Jkr

не имеет общих точек с открытым интервалом оптимальности (l^optk,uopt) и сk

открытым интервалом неоптимальности (l^nonk,unon). Иными словами, выпол-k

няются следующие равенства:

[

]⋂(

)

(6)

l^coptk,ucoptk

l^optk,uopt

= ∅,

[

]⋂(

)

(7)

l^coptk,ucoptk

l^nonk,unonk

= ∅.

Если не существует отрезка [l^coptk,ucoptk], lcoptk

< u^copt, условной оптималь-_k

ности для требования Jkr ∈ J в перестановке π_k, то будем говорить, что тре-

бование Jkr не имеет условной оптимальности в перестановке π_k.

На рис. 1 для всех требований J_i ∈ J в перестановке π₁ = (J₁, . . . , J₁₈)

представлены отрезки оптимальности, отрезки условной оптимальности и от-

резки неоптимальности. Отрезки неоптимальности для требований J_i ∈ J в

перестановке π₁ зашрихованы дважды (горизонтальными и вертикальными

отрезками).

Замечание 1. В силу теоремы 1 для каждого требования J_i ∈ J в пе-

рестановке π_k ∈ Π может существовать не более одного отрезка оптимально-

сти, не более двух отрезков условной оптимальности и не более двух отрезков

неоптимальности.

Как показано на рис. 1, для требования J₃ в перестановке π₁ ∈ Π имеет-

ся два отрезка неоптимальности [2, 3] и [6, 8], один отрезок [3, 5] условной

оптимальности и один отрезок [5, 6] оптимальности. Для требования J₅ в пе-

рестановке π₁ имеется два отрезка неоптимальности [2, 7] и [6, 10] с непустым

пересечением [6, 7] = [2, 7]

⋂[6, 10].

Из определений отрезков оптимальности, неоптимальности и условной оп-

тимальности для требования Jkr , r ∈ {1, . . . , n}, в перестановке π_k ∈ Π следует

Лемма 1. Отрезок [pLkr,p^U ] длительностей обслуживания требования_k

Jkr ∈ J можно представить в виде объединения всех отрезков оптималь-

ности, неоптимальности и условной оптимальности для требования Jkr ,

r ∈ {1,... ,n}, в перестановке π_k = (Jk1,...Jkn) ∈ Π. Для любого отрез-

ка неоптимальности [l^nonk,unon] выполняется хотя бы одно из равенствk

l^nonk

= pLkr или u^nonk

=p^U ._k

Построение области оптимальности OR(π_k, T ) перестановки π_k = (Jk1 ,

...,Jkn) ∈ Π можно свести к построению области оптимальности перестанов-

ки π_k для соответствующей задачи 1|p^Li ≤ p_i ≤ p^Ui |

∑C_i с сокращенными от-

[

]

[

]

резками допустимых длительностей

p^Li, p^Ui

⊆

p^Li,p^Ui

. Сокращенные отрез-

[

]

ки

pLkr , p^Uk

, Jkr ∈ J, для перестановки π_k = (Jk1,...,Jkn) определяются по

формулам

(8)

p^Lk

= max

p^Lk

p^Uk

= min

p^U

k_j

1≤j≤r≤n

1≤r≤j≤n

для каждого требования Jkr ∈ {Jk1 , . . . , Jkn } = J . Множество сокращенных

[

]

сценариев, определенных по формулам (8), обозначим ка

T =

p^L1, p^U1

×...

[

]

...×

p^Ln, p^Un

Теорема 2. Область оптимальности OR(π_k,T) для перестановки

π_k = (Jk1 ,... ,Jkn ) ∈ Π для задачи 1|pLi ≤ pi ≤ pUi |

∑C_i совпадает с обла-

стью оптимальности OR(π_k

T) для той же перестановки для задачи

1|p^Li ≤ p_i ≤ p^Ui |

∑C_i с множеством

T допустимых сценариев.

Доказательство. Из необходимых и достаточных условий (2) опти-

мальности перестановки π_k для задачи 1|p|

∑C_i получаем, что из выполне-

ния соотношений

p^Lk

≤pkr <p^Lk

= max

p^Lk

1≤j≤r≤n

хотя бы для одной длительности pkr следует, что перестановка π_k = (Jk1 ,

...,Jkr,...,Jkn) не может быть оптимальной для задачи

1|p|

∑C_i

{

[

]}

[

]

с каким-либо сценарием p = (p₁, . . . , p_n) ∈

×^r-1i=1

pLki,pUki

l^nonk,unon

{

}

×^ni=r+1[pLki,p^U ]

k_i

Аналогично, из выполнения соотношений

min

p^Uk

= p^Uk

<pkr ≤p^Uk

1≤r≤j≤n

хотя бы для одной длительности pkr следует, что перестановка π_k =

= (Jk1 , . . . , Jkr , . . . , Jkn ) не может быть оптимальной для задачи 1|p|

∑C_i

{

[

]}

[

]

с каким-либо сценарием p = (p₁, . . . , p_n) ∈

×^r-1i=1

pLki,pUki

l^nonk,unon

{

[

]}

×^ni=r+1

pLki,p^U

k_i

Таким образом, справедливо следующее утверждение: множество всех

сценариев p ∈ T , для которых перестановка π_k является оптимальной

для задачи 1|p^Li ≤ p_i ≤ p^Ui |

∑C_i, содержится во множестве всех сценари-

ев p ∈ T, для которых перестановка π_k является оптимальной для задачи

1|p^Li ≤ p_i ≤ p^Ui |

∑C_i с множеством

T допустимых сценариев.

Из включени

T ⊆ T следует обратное утверждение:

Утверждение. Множество всех сценариев p ∈ T, для которых пере-

становка π_k является оптимальной для задачи 1|p^Li ≤ p_i ≤ p^Ui|

∑C_i, содер-

жится во множестве всех сценариев p ∈ T , для которых перестановка π_k

является оптимальной для задачи 1|p^Li ≤ p_i ≤ p^Ui |

∑C_i.

Из доказанных утверждений следует, что для исходной задачи 1|p^Li ≤

≤p_i ≤p^Ui|

∑C_i и для задачи 1|p^Li ≤ p_i ≤ p^Ui|∑C_i с множеством сценариев

[

]

[

]

T =

p^L1, p^U1 ×

×...×

p^Ln, p^Un ×

области оптимальности совпадают для лю-

бой фиксированной перестановки π_k ∈ Π: OR(π_k, T ) = OR(π_k

T). Tеорема 2

доказана.

Из определения 2 и теоремы 2 нетрудно получить следующее утверждение.

∑C_i с множеством сценариев

Лемма 2. Для задачи 1|p^Li ≤ p_i ≤ p^U(i^|

)

открытый интервал оптимальности l^optk,uoptk

для требования Jkr в пере-

[

]

становке π_k ∈ Π не имеет общих точек с отрезком pLkd,p^U

допустимых

k_d

длительностей любого другого требования Jkd ∈ J , d = r, т.е. выполняется

следующее равенство:

⋂

(9)

(l^optk,uoptk)

[p^Lk

,p^U

] = ∅.

k_d

Докажем небходимые и достаточные условия, при выполнении которых об-

ласть оптимальности для перестановки π_k ∈ Π является пустым множеством.

Теорема 3. Область оптимальности OR(π_k,T) для перестановки

π_k = (Jk1 ,... ,Jkn ) ∈ Π является пустым множеством, OR(π_k,T) = ∅, то-

гда и только тогда, когда существует хотя бы одно требование Jkr ∈ J ,

r ∈ {1,... ,n}, в перестановке π_k = (Jk1,...,Jkn) ∈ Π, которое не имеет

условной оптимальности и одновременно не имеет отрезка оптимально-

сти.

Доказательство.

Достаточность. Пусть существует требование Jkr ∈ J в перестановке

π_k = (Jk1 ,... ,Jkn ) ∈ Π, которое не имеет условно[ оптимал]но[ти и не]име-

ет отрезка оптимальности. По лемме 1 получаем

l^nonk,unonk

pLkr ,p^U

= ∅.

Следовательно, либо существует требование Jkv ∈ J такое, что r < v и вы-

полняются соотношения (3), либо существует требование Jkw ∈ J такое, что

w < r и выполняются соотношения (4). В первом случае не[равенст]о pkv<pkr

выполняется для каждой допустимой длительности pkr ∈

pLkr ,p^U

обслужи-

[

]

вания требования Jkr и для каждой допустимой длительности pkv ∈

pLkv ,p^U

обслуживания требования Jkv . Во втором случае нера[енство]pkw > pkr вы-

полняется для каждой допустимой длительности pkr ∈

pLkr ,p^U

обслужива-

[

]

ния требования Jkr и для каждой допустимой длительности pkw ∈

pLkw ,p^U

обслуживания требования Jkw .

В силу теоремы 1 в обоих случаях перестановка π_k не может быть оп-

тимальной для задачи 1|p|

∑C_i при каком-либо сценарии p ∈ T. Следова-

тельно, согласно определению 2 область оптимальности для перестановки

π_k = (Jk1 ,... ,Jkn ) ∈ Π является пустым множеством, OR(π_k,T) = ∅. Доста-

точность доказана.

Необходимость. Докажем необходимость методом от противного. Пусть

равенство OR(π_k, T ) = ∅ выполняется. Однако предположим, что не суще-

ствует ни одного требования Jkr ∈ J , r ∈ {1, . . . , n}, в перестановке π_k =

= (Jk1 , . . . , Jkn ) ∈ Π, которое не имеет условной оптимальности и не имеет

отрезка оптимальности.

Согласно определению 2 pавенство OR(π_k, T ) = ∅ означает, что не суще-

ствует ни одного сценария p ∈ T такого, что перестановка π_k является оп-

тимальной для задачи 1|p|

∑C_i со сценарием p ∈ T. Тем не менее покажем,

как построить сценарий p^∗∈ T , который содержится в области оптимальности

для перестановки π_k.

Если для требования Jki существует отрезок оптимальности [l^optk,uopt],k

[

]

l^optk≤uoptk, в перестановке πk, то существует хотя бы одна точка p∗ki∈ loptk,uopt

k_i

Выберем такое значение p^∗ в качестве длительности обслуживания требова-_k

ния Jki .

Если же не существует отрезка оптимальности для требования Jkj в пере-

[

]

мальности l^coptk,ucoptk

для требования Jkj . Выберем значение l^copt в качестве_k

длительности обслуживания требования Jkj : p∗kj = l^copt._k

При таком выборе длительностей p∗kj обслуживания всех требований Jkj ∈

∈ {Jk1 , . . . , Jkn } = J получаем сценарий p^∗ = (p∗k1 , . . . , p^∗ ) ∈ T . Из равенств_k

(6), (7) и леммы 2 с равенством (9) следует, что перестановка π_k являет-

ся оптимальной для задачи 1|p^∗|

∑C_i. Следовательно, имеет место вклю-

чение p^∗ ∈ OR(π_k, T ), которое противоречит предполагаемому равенству

OR(π_k, T ) = ∅. Полученное противоречие завершает доказательство теоре-

мы 3.

Из теоремы 3 следует, что если OR(π_k, T ) = ∅, то в перестановке π_k =

= (Jk1 , . . . , Jkn ) ∈ Π для каждого требования Jkr ∈ J , r ∈ {1, . . . , n}, существу-

ет хотя бы один отрезок оптимальности или отрезок условной оптимально-

сти. Поэтому размерность непустой области оптимальности OR(π_k, T ) равна

n = |J|. Поскольку из теоремы 3 следует и обратное утверждение, то полу-

чаем

Следствие 1. Размерность области оптимальности OR(π_k,T) равна

n = |J| тогда и только тогда, когда OR(π_k,T) = ∅.

На рис. 1 для отрезка неоптимальности [l^non4, u^non4] = [7, 9] требования J₄

в перестановке π₁ = (J₁, . . . , J₁₈) выполняются равенства [l^non4, u^non4] = [7, 9] =

= [p^L4, p^U4 ], т.е. требование J₄ не имеет условной оптимальности и одновремен-

но не имеет отрезка оптимальности в перестановке π₁. Из теоремы 3 следует,

что область оптимальности для перестановки π₁ является пустым множе-

ством, OR(π₁, T ) = ∅.

4. Построение области оптимальности и вычисление ее объема

В результате использования теоремы 3 разработан алгоритм 1 сложности

O(n) для проверки выполнения равенства OR(π_k, T ) = ∅ для фиксированной

перестановки π_k ∈ Π.

Если алгоритм 1 устанавливает, что для перестановки π_k справедливо со-

отношение OR(π_k, T ) = ∅, то в соответст[вии с т]оремой 2 алгоритм 1 строит

по формулам (8) сокращенные отрезки

p^Li, p^Ui

допустимых длительностей

обслуживания требований J_i ∈ J . Тем самым определяются исходные данные

для задачи 1|p^Li ≤ p_i ≤ p^Ui |

∑C_i смножеством

T допустимых сценариев.

Алгоритм 1.

ВХОД: Отрезки [p^Li, p^Ui ] длительностей обслуживания требований J_i ∈ J ;

перестановка π_k = (Jk1 , . . . , Jkn ) ∈ Π обслуживания требований J .

ВЫХОД: Отрезки [p^Li, p^Ui ] для требований J_i ∈ J , если установлено, что

OR(π_k, T ) = ∅.

Шаг 1:

p^Lk

= pLk1, t_L = p^L , r = 2;_k

Шаг 2: IF pUkr ≥ t_L THEN GOTO шаг 3 ELSE GOTO шаг 5;

Шаг 3: IF pLkr > t_L THEN t_L = pLkr , p^Lk

= t_L, r := r + 1;

ELSE p^Lk

= t_L, r := r + 1;

IF r ≤ n THEN GOTO шаг 2 ELSE p^Uk

=pUkn, t_U =p^U ;_k

Шаг 4: FOR r = n - 1 to 1 STEP -1 DO

IF pUkr < t_U THEN t_U = pUkr , p^Uk

= t_U ELSE p^Uk

=t_U;

END FOR STOP.

Шаг 5: OR(π_k, T ) = ∅ STOP.

На шагах 1, 2 и 5 алгоритма 1 проверяется равенство OR(π_k, T ) = ∅. На

шагах 2-4 строятся сокращенные отрезки допустимых длительностей обслу-

живания требований множества J для задачи 1|p^Li ≤ p_i ≤ p^Ui |

∑C_i. Соглас-

но теореме 2 область оптимальности для перестановки π_k ∈ Π обслужива-

ния требований для задачи 1|p^Li ≤ p_i ≤ p^Ui |

∑C_i совпадает с областью опти-

мальности для той же перестановки π_k обслуживания требований для зада-

чи 1|p^Li ≤ p_i ≤ p^Ui |

∑C_i с множеством

T сокращенных сценариев. Нетрудно

убедиться в том, что для реализации алгоритма 1 требуется выполнить O(n)

элементарных операций.

4.1. Область оптимальности для перестановки π_k ∈ Π

в частных случаях

Построим область оптимальности OR(π_k, T ) для двух частных случаев пе-

рестановки π_k = (Jk1 , . . . , Jkn ) ∈ Π и вычислим объем Vol (π_k, T ) области оп-

тимальности OR(π_k, T ). В первом случае область оптимальности OR(π_k, T )

определяется только отрезками оптимальности всех требований Jkr ∈ J (лем-

ма 3). Во втором случае область оптимальности определяется только отрез-

ками условной оптимальности всех требований Jkr ∈ J (лемма 4).

Лемма 3. Если OR(π_k,T) = ∅ и каждое требование Jkr∈J не име-

ет условной оптимальности в перестановке π_k = (Jk1 ,... ,Jkn ) ∈ Π, то об-

ласть оптимальности для перестановки π_k совпадает с параллелепипедом

оптимальности для той же перестановки:

[

]

(10)

OR(π_k, T ) = ×^nr=1 l^optk,uoptk

= OB(π_k

,T).

Объем такой области оптимальности OR(π_k, T ) равен

∏

(11)

Vol (π_k, T ) =

(u^optk

-l^opt

J_kr ∈{J : l^optk<uoptk

}

Доказательство. В силу теоремы 2 вместо задачи 1|pLi ≤pi ≤pUi |

∑C_i

будем рассматривать задачу 1|p^Li ≤ p_i ≤ p^Ui |

∑C_i. Поскольку OR(π_k,T) = ∅,

то по теореме 3 не существует ни одного требования Jkr ∈ J , которое не имеет

условной оптимальности и одновременно не имеет отрезка оптимальности в

перестановке π_k.

Поскольку каждое требование Jkr ∈ J не имеет условной оптимальности в

перестановке π_k и для него существует не более одного отрезка оптимально-

сти (замечание 1), то для каждого требования Jkr ∈ J выполняется равенство

[

]

[

]

p^Lk,pUk

= l^optk,uopt

. Следовательно, в соответствии с определениями 1 и 2

область оптимальности OR(π_k, T ) для перестановки π_k совпадает с паралле-

лепипедом оптимальности для т[ой же пе]естановки πk и представляет собой

opt

n-мерный параллелепипед ×ⁿ

r=1

l_k

,u^optk

= OB(π_k,T), объем которого равен

∏

(u^optk

- l^opt). Лемма 3 доказана._k

J_kr ∈{J : l^optk<uoptk}

На рис. 2 представлена перестановка π₂ = (J₁, . . . , J₁₀) требований множе-

ства J = {J₁, . . . , J₁₀} для примера 2 задачи 1|p^Li ≤ p_i ≤ p^Ui |

∑C_i. Поскольку

Требования J_i

J₁₀

J₉

J₈

J₇

J₆

J₅

J₄

J₃

J₂

J₁

8 9 10

Длительности p_i

Рис. 2. Отрезки оптимальности и неоптимальности (заштрихованы) для тре-

бований J_i ∈ J в перестановке π₂ = (J₁, . . . , J₁₀) для примера 2 задачи 1|p^Li ≤

≤p_i ≤p^Ui|

∑C_i.

перестановка π₂ удовлетворяет условию леммы 3, то область оптимальности

OR(π₂, T ) представляет собой следующий 10-мерный параллелепипед:

[

]

[

]

OR(π₂, T ) = OB(π₂, T ) = l^opt1, u^opt

×...× l^opt10,u^opt

= [4, 8] × [8, 8] × [9, 12] × [13, 16] × [16, 16] × [16, 18] ×

× [19, 19] × [19, 22] × [22, 22] × [22, 24],

объем которого вычисляется по формуле (11), а именно:

∏

Vol (π₂, T ) =

(u^optr - l^optr) =

Jr∈{J : l^rpt<u^rpt}

= (8 - 4)(12 - 9)(16 - 13)(18 - 16)(22 - 19)(24 - 22) = 432.

В соответствии с теоремой 2 вместо задачи 1|p^Li ≤ p_i ≤ p^Ui |

∑C_i будем рас-

сматривать задачу 1|p^Li ≤ p_i ≤ p^Ui |

∑C_i с множеством

T сокращенных сце-

нариев.

Определение 3. Секцией перестановки π_k ∈ Π называется макси-

1≤v≤v+

мальная по включению перестановка sπkv ( (Jkv , . . . , J

)v+mv

+m_v ≤ n, такая что для любого числа d ∈

p^Lk, pU

существует тре-

k_v+mv(

)

бование Jkv+i, i ∈ {0,... ,m_v}, для которого d ∈

p^Lk

p^Uk

. Отрезок

v+i

[

]

p^Lk,

p^Uk

v+mv

называется охватом секции sπkv .

Отметим, что множество S(π_k) = {sπkv , . . . , swk }, 1 ≤ v < . . . < w ≤ n, всех

секций каждой перестановки π_k ∈ Π определено однозначно.

Замечание 2. Из определения 3 следует, что каждое требование Jki ∈ J

либо содержится в единственной секции перестановки π_k, либо не содержится

ни в одной секции перестановки π_k. Если существует хотя бы одно требование

Jki ∈ J , которое не содержится ни в одной секции перестановки π_k, то по

теореме 3 получаем равенство OR(π_k, T ) = ∅.

Из замечания 2 и доказательства теоремы 3 получаем следующее утвер-

ждение.

Следствие 2. Для того чтобы область оптимальности перестановки

π_k = (Jk1 ,... ,Jkn ) ∈ Π не была пустым множеством, OR(π_k,T) = ∅, необ-

ходимо и достаточно, чтобы выполнялось равенство π_k = (sπk1 , . . . , swk ).

Для перестановки π₂ = (J₁, . . . , J₁₀) в примере 2, представленном на

рис. 2, каждая секция состоит из единственного требования sπ21 = (J1), . . . ,

). Секцию, состоящую

из единственного требования, будем называть тривиальной.

[

]

Для доказательства леммы 4 разобьем охват

p^Lk, pU

каждой секции

k_j+mj

sπkj ∈ S(πk) на максимальныe (по включению) подынтервалы условной опти-

мальности

[

]

[

(

)

(

))⋃

⋃[

(

)

(

))⋃

p^Lk,

p^Uk

= l^j

sπk

,u^j

l^j

sπk

,u^j

j+mj

sπkj

(12)

⋃[

(

)

(

)]

π_k

l^j

n(j)

которые отличаются один от другого тем, что для разных подмножеств Jj }{i=

{

}

= Jki,...,J_k

множества Jkj , . . . , Jkj+mj

, j ≤ i ≤ j + m_j, выполняют-

(

)

(

)]

[

]

ся включения l^ji sπk

,u^j

sπk

⊆

p^Lk,pUk

для всех требований Jkr ∈ J^ji.

(

)

Пуст

Jji = J_k

,...,J_k

обозначает перестановку требований множества

{

}

J^ji = J_k

,...,J_k

Для иллюстрации введенных обозначений рассмотрим разбиения охва-

тов секций sπ21 и s82 перестановки π2 = (J1, . . . , J10) в примере 3, представ-

ленном на рис. 3. Секция sπ21 состоит из семи упорядоченных требований

, pU7 ] = [4,20]. Получаем следующее раз-

sπ21 =(J1,... ,J7) и имеет охват [

биение (12): [4, 20] = [4, 8) ∪ [8, 9) ∪ [9, 13) ∪ [13, 16) ∪ [16, 17) ∪ [17, 18) ∪ [18, 20]

охвата [p^L1, p^U7 ] на подынтервалы условной оптимальности. Здесь

[

)

[

)

l¹¹ (J₁,J₂) ,u¹¹ (J₁,J₂)

= [4, 8);

l¹² (J₁,... ,J₄),u¹² (J₁,... ,J₄)

= [8, 9);

[

)

[

)

l¹³ (J₂,J₃,J₄),u¹³ (J₂,J₃,J₄)

= [9, 13);

l¹⁴ (J₃,J₄) ,u¹⁴ (J₃,J₄)

= [13,16);

[

)

l¹⁵ (J₃,... ,J₆) ,u¹⁵ (J₃,... ,J₆)

= [16, 17);

[

)

l¹⁶ (J₃,... ,J₇) ,u¹⁶ (J₃,... ,J₇)

= [17, 18];

[

]

l¹⁷ (J₄,... ,J₇) ,u¹⁷ (J₄,... ,J₇)

= [18,20] .

Требования J_i

J₁₀

J₉

J₈

J₇

J₆

J₅

J₄

J₃

J₂

J₁

Длительности p_i

15161718

2223

Рис. 3. Отрезки условной оптимальности (заштрихованы) и отрезки неопти-

мальности (заштрихованы дважды) для требований J_i ∈ J в перестановке

π₂ = (J₁, . . ., J₁₀) для примера 3 задачи 1|p^Li ≤ p_i ≤ p^Ui |

∑C_i.

Отметим равенства

J¹¹ = (J₁,J₂),

J¹² = (J₁,... ,J₄),

J¹³ = (J₂,J₃,J₄),

J¹⁴ =

= (J₃, J₄),

J¹⁵ = (J₃,... ,J₆),

J¹⁶ = (J₃,... ,J₇),

J¹⁷ = (J₄,... ,J₇). Секция sπ28

, p^U10]= [22,28].

состоит из трех требований sπ28 = (J8, J9, J10) и имеет охват [

Получаем разбиение [22,28] = [22,25)∪[25,28] охвата [22,28] на подынтервалы

условной оптимальности [l²¹(J₈, J₉), u²¹(J₈, J₉)) и [l²²(J₈, J₉, J₁₀), u²²(J₈, J₉, J₁₀)].

Отметим равенств

J²¹ = (J₈,J₉)

J²² = (J₈,J₉,J₁₀).

Поскольку любая секция sπkj ∈ S(πk) перестановки πk и любое упорядочен-

ное множеств

J ji требований множества J^ji ⊆ J сами являются перестанов-

ками соответствующего подмножества требований множества J , то для них

можно рассматривать области оптимальности для всех тех требований, из

которых состоят эти перестановки. Для обозначения таких областей опти-

J ji ,T),

мальности будем использовать те же обозначения OR(sπkj , T ) и OR

что и для области оптимальности OR(π_k, T ) для перестановки π_k ∈ Π всего

множества требований J . Для обозначения объемов областей оптимально-

сти OR(sπkj , T ) и OR

J ji ,T) будем использовать обозначения Vol(sπkj,T) и

Vol

J ji ,T) соответственно.

Доказательство следующей леммы 4 приведено в Приложении. Там же

дано определение d-мерной пирамиды оптимальности P ir^optĴ^ji , представляю-

щей собой область оптимальности для перестановки требований J^ji ⊆ J , т.е.

показано, что выполняются равенства d = |J^ji| и OR

J ji ,T) = Pir^optĴji .

Лемма 4. Если OR(π_k,T) = ∅ и каждое требование Jkr∈J не имеет

отрезка оптимальности в перестановке π_k = (Jk1 ,... ,Jkn ) ∈ Π, то область

оптимальности OR(π_k,T) для перестановки π_k представляет собой декар-

J₄

(9, 9, 13)

(13, 9, 13)

(9, 13, 13)

(13, 13, 13)

J₁

J₂

(9, 9, 9)

(4, 4)

(8, 4)

(13, 9, 9)

(4, 8)

(8, 8) = (J₁, J₂)

(9, 13, 9)

(13, 13, 9) = (J₂, J₃, J₄)

J₂

J₃

Рис. 4. (a) - Треугольник оптимальности Piropt(J1, J2) с основани-

ем [(4, 8), (8, 8)] и высотой [(4, 8), (4, 4)] для подынтервала условной

оптимальности [4, 8) для перестановки π₂

= (J₁, . . . , J₁₀) в приме-

ре 3. (b) - Пирамида оптимальности Piropt(J2, J3, J4) с основанием

[(9, 9, 13), (9, 13, 13), (13, 13, 13)] и высотой [(9, 9, 13), (9, 9, 9)] для подын-

тервала условной оптимальности [9, 13) для перестановки π₂ в приме-

ре 3.

тово произведение |S(π_k)| областей оптимальности OR(sπkj,T) всех секций

S(π_k):

(

)

(

)

(13) OR (π_k, T ) = OR (sπk1 , T ) × . . . × OR sjk , T

×...×OR s

S(π_k)|

где OR(sπkj , T ) определяется как следующее объединение d-мерных пирамид{}

оптимальности Pir^optĴ^ji в пространстве Rⁿ, d ∈

|J^ji|, . . . , |J^jn(j)|

^n(j)⋃

(14)

Jji,T)=

P ir^optĴ^ji.

OR(sπkj , T ) =

i=1

Объем области оптимальности для перестановки π_k определяется равен-

ством

(

)

(

))_|J j

n(j)

|S(π_k)|∏

∑

u^j

sπk

-l^j

sπk

(15)

Vol (π_k, T ) =

|J_i

j=1

i=1

На рис. 3 представлена перестановка π₂ = (J₁, . . . , J₁₀) требований множе-

ства J = {J₁, . . . , J₁₀} для примера 3 задачи 1|p^Li ≤ p_i ≤ p^Ui |

∑C_i. По теоре-

ме 3 область оптимальности для перестановки π₂ не является пустым множе-

ством, и поскольку перестановка π₂ удовлетворяет условию леммы 4, то объем

области оптимальности OR(π₂, T ) вычисляется по формуле (15), а именно:

(

)

(

))_|J j

n(j)

∏∑

u^j

sπk

-l^j

sπk

Vol (π₂, T ) =

|J_i

j=1 i=1

[ (8 - 4)

(9 - 8)⁴

(13 - 9)³

(16 - 13)²

(17 - 16)⁴

]

(18 - 17)

(20 - 18)⁴

][(25 - 22)²

(28 - 25)³

]

[ 16

][9

= 210

120

На рис. 4,a представлен указанный в равенстве

(14) треугольник

P ir^optĴ¹¹ = P ir^opt(J₁, J₂) для подынтервала условной оптимальности [4, 8),

принадлежащий области оптимальности OR(π₂, T ) для перестановки π₂ =

= (J₁, . . . , J₁₀) в примере 3, а на рис. 4,b представлена указанная в (14)

3-мерная пирамида P ir^optĴ¹³ = P ir^opt(J₂, J₃, J₄) для подынтервала услов-

ной оптимальности [9, 13), принадлежащая той же области оптимальности

OR(π₂, T ).

4.2. Объем области оптимальности для перестановки π_k ∈ Π

в общем случае

Пусть S^∗(π_k) обозначает подмножество тривиальных секций множества

S(π_k).

Отметим, что перестановка π₂ = (J₁, . . . , J₁₀) в примере 2 удовлетворяет

условию леммы 3 и все секции множества S(π₂) являются тривиальными:

S(π₂) = S^∗(π₂).

Перестановка π₂ = (J₁, . . . , J₁₀) в примере 3 удовлетворяет условию лем-

мы 4, и множество S^∗(π₂) ее тривиальных секций - пустое множество:

S^∗(π₂) = ∅.

Теорема 4. Если OR(π_k,T) = ∅, то область оптимальности

OR(π_k, T ) представляет собой декартово произведение

(13) областей

оптимальности секций S(π_k) такое, что

(

)

(

)

[

]

= l^optk,uopt

OR sπkj,T

= OB sπkj,T

для каждой тривиальной секции sπkj^=(Jkr^)и

^n(j)⋃

Jji,T)=

P ir^optĴ^ji

OR(sπkj , T ) =

i=1

для каждой нетривиальной секции sπkj ∈ S(πk) \ S^∗(πk). Объем области оп-

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

(16)

Vol (π_k

,T)=

(

)

(

))_|J j

∏

(

)

∏

∑

u^j

sπk

-l^j

sπk

u^optk-lopt

|J_i

i=1

(J_kr )∈{S^∗(πk) : l^optkr<u^optkr}

s^πkj∈S(πk)\S∗(πk)

Доказательство. В силу теоремы 2 вместо задачи 1|pLi ≤pi ≤pUi |

∑C_i

будем рассматривать задачу 1|p^Li ≤ p_i ≤ p^Ui |

∑C_i. Поскольку OR(π_k,T) = ∅,

то размерность области оптимальности OR(π_k, T ) равна n (следствие 1). Из

теоремы 3 следует, что не существует ни одного требования Jkr ∈ J , которое

не имеет условной оптимальности и одновременно не имеет отрезка опти-

мальности в перестановке π_k.

Поскольку OR(π_k, T ) = ∅, то из замечания 2 следует, что каждое требо-

вание Jki ∈ J содержится в единственной секции перестановки π_k. При этом

согласно следствию 2 справедливо равенство π_k = (sπk1 , . . . , swk ).

На основе перечисленных свойств перестановки π_k покажем, как доказать

равенство (13) и равенство (16) в результате последовательного применения

леммы 3 или леммы 4 в частных случаях, когда очередная рассматриваемая

перестановка состоит из единственной секции sπkv ∈ S(πk) перестановки πk.

Вначале рассмотрим первую секцию sπk1 = (Jk1 , . . . , J

) перестанов-

k_1+m1

ки π_k. Если секция sπk1 является тривиальной, т.е. s1k = (Jk1 ), то по лемме 3

получаем первый сомножитель [l^optk,uoptk

] = OR(sπk1,T) в искомом декартовом

произведении (13) и первый сомножитель (u^optk

- l^opt) в первом произведении_k

равенства (16) при условии, что имеет место строгое неравенство l^optk

<u^optk

(если l^optk

=u^optk, то сомножитель (uoptk

- l^opt) = 0 в равенство (16) не добав-_k

ляется в соответствии с леммой 3).

Если же секция sπk1 не является тривиальной, т.е.

sπk1 ∈ S(πk)\S^∗(πk),

то по лемме 4 получаем первый сомножитель

ⁿ⁽¹⁾⋃

J¹ⁱ,T) =

P ir^optĴ¹ⁱ

OR(sπk1 , T ) =

i=1

в декартовом произведении (13) и первый сомножитель

n(1)

∑ (u¹ⁱ(sπk1 ) - lⁱ(s1k ))^|

|J¹ⁱ|!

i=1

во втором произведении равенства (16). Здесь необходимо отметить, что в

разбиение (12) секции sπk1 на подынтервалы условной оптимальности могут

входить и подынтервалы [l¹ⁱ(sπk1 ), uⁱ(s1k )), для которых выполняется равен-

ство |J¹ⁱ| = 1 (такая возможность в условии леммы 4 не предусмотрена). По-

кажем, однако, что равенство

(sπkj ) - lⁱ (sjk ))^|

Jji,T)=

|J^ji|!

содержащееся в (16), справедливо и для случая |J^ji | = 1. Действительно, если

|J^ji | = 1, то

(

)

(

))_|J j

(

)

(

))₁

π_k

u^j

-l_i

u^j

sπk

-l^j

sπk

(

)

(

))

= u^j

sπk

-l^j

sπk

|J^ji |!

что и требуется для выполнения равенства (16).

Аналогично рассмотрим вторую секцию sπk2 = (Jkm1+1 , . . . , J

) пе-

k_m1+1+m2

рестановки π_k. Применяя лемму 3, если секция sπk2 тривиальная, или лемму 4,

если секция sπk2 не является тривиальной, дополним уже построенную часть

декартова произведения (13) вторым сомножителем и дополним вторым со-

множителем одно (соответствующее) произведение из двух произведений ра-

венства (16).

Продолжив описанный процесс вплоть до рассмотрения последней сек-

ции sπkw перестановки πk и добавления соответствующих сомножителей, по-

лучим оба равенства (13) и (16). Теорема 4 доказана.

Следующий алгоритм вычисления объема Vol (π_k, T ) области оптимально-

сти OR(π_k, T ) = ∅ для перестановки π_k ∈ Π основан на теоремах 2, 3 и 4.

Алгоритм 2.

ВХОД:

Перестановка π_k = (Jk1 , . . . , Jkn ) ∈ Π, для которой OR(π_k, T ) = ∅;

отрезки [p^Li, p^Ui ] длительностей обслуживания требований J_i ∈ J .

ВЫХОД: Объем области оптимальности OR(π_k, T ) для перестановки π_k.

Шаг 1:

Определить множество секций{

}

,...,s^π

;

+m₁

+m_j

Шаг 2:

j = 1, Vol = 1, Vol^∗ = 1, Sum = 0;

Шаг 3:

IF секция sπkj = (Jkj , . . . , Jkj+mj ) тривиальная sjk = (Jkj ) THEN

GOTO шаг 7;

Шаг 4:

k_j+mj

) построить разбиение (12)

ELSE для секции sπkj = (Jkj , . . . , J

[

]

охвата

p^Lk,pU

на подынтервалы условной оптимальности:

k_j+m_j

[

(

)

(

)

(

)) ⋃

⋃[

)) ⋃

π_k

l^j

sπk

,u^j

sπkj

[

(

)

(

)]

⋃

π_k

l^j

;

n(j)

(s^πkj )-l^ji (s^πkj ))^|Ji|

Шаг 5:

FOR i = 1 to n(j) DO вычислить OS =

;

|J^ji|!

Sum := Sum + OS END FOR

Шаг 6:

Vol := Vol · Sum, j := j + m_j IF j ≤ w THEN GOTO шаг 3;

ELSE GOTO шаг 10;

Шаг 7:

j := j + m_j, OS^∗ = u^optk

-l^optk

IF u^optk

> l^opt THEN GOTO шаг 9;_k

ELSE IF j ≤ w THEN GOTO шаг 3;

Шаг 8:

ELSE GOTO шаг 10;

Шаг 9:

Vol^∗ := Vol^∗ · OS^∗ IF j ≤ w THEN GOTO шаг 3 ELSE

Шаг 10:

Vol (π_k, T ) = Vol · Vol^∗ STOP.

Рис. 5. Отрезки оптимальности, условной оптимальности (заштрихованы) и

отрезки неоптимальности (заштрихованы дважды) для требований J_i ∈ J =

= {J₁, . . . , J₁₈} в перестановке π₃ = (J₁, . . . , J₃, J₆, J₅, J₄, J₇, . . . , J₁₈) для при-

мера 1.

Для реализации шага 1 требуется O(n) операций. Выполнение шагов 3-6

требует O(n²) операций. Выполнение шагов 7-9 требует O(n) операций. Все-

му алгоритму 2 требуется выполнить O(n²) операций для вычисления объема

Vol (π_k, T ) области оптимальности OR(π_k, T ) для фиксированной перестанов-

ки π_k ∈ Π.

На рис. 5 представлена перестановка π₃ = (J₁, . . . , J₃, J₆, J₅, J₄, J₇, . . . , J₁₈)

требований множества J = {J₁, . . . , J₁₈} для примера 3 задачи 1|p^Li ≤ p_i ≤

≤p^Ui|

∑C_i. По теореме 3 область оптимальности для перестановки π₃ не пу-

стая, поэтому вычислим ее объем по формуле (16) из теоремы 4, учитывая

равенство S^∗(π₃) = ∅.

∏

∑

(u^ji (sπ3j) - lⁱ(sj3 ))^|

Vol (π₃, T ) =

|J_i

s^π3j∈S(π3)

i=1

]

[ (3 - 1)¹

(4 - 3)³

(5 - 4)⁵

(6 - 5)³

(7 - 6)¹

(9 - 7)²

]

[ (12 - 11)

(14 - 12)³

(15 - 14)⁵

(18 - 15)³

(23 - 18)¹

[ (30 - 27)

(32 - 30)³

(36 - 32)¹

(37 - 36)²

(38 - 37)³

]

(40 - 38)

(41 - 40)¹

120

]

= 657,85.

120

5. Перестановка π_k с максимальной областью оптимальности

Если существует одноэлементное доминирующее множество {π_k} для за-

дачи 1|p^Li ≤ p_i ≤ p^Ui |

∑C_i, то перестановка π_k обслуживания требований мно-

жества J является оптимальной для задачи 1|p|

∑C_i при любом сценарии

p ∈ T. В соответствии с определением 2 для такой перестановки π_k должно

выполняться равенство OR(π_k, T ) = T .

5.1. Максимально возможная область оптимальности

для заданных сценариев

Докажем необходимые и достаточные условия для существования пере-

становки π_k ∈ Π с максимально возможной областью оптимальности для за-

данного множества сценариев T , т.е. докажем критерий существования пере-

становки π_k, для которой справедливо равенство OR(π_k, T ) = T .

Теорема 5. Область оптимальности для перестановки π_k = (Jk1,

...,Jkn) ∈ Π является максимально возможной для заданного множества

сценариев T , т.е. OR(π_k, T ) = T , тогда и только тогда, когда в перестанов-

ке π_k для каждого требования Jkr ∈ J выполняется следующее равенство:

[

]

[

]

(17)

l^optk,uoptk

p^Lk

,p^Uk

Доказательство.

Достаточность. Пусть равенство (17) выполняется для каждого тре-

бования Jks ∈ J в перестановке π_k = (Jk1 , . . . , Jkn ). Тогда по определе-[

]

нию 1 должны выполняться и равенства OB(π_k, T ) = ×kir ∈M lkpti,uopt

k_ir

[

]

= ×kir∈M pki

,pUki

= T, такие что множество M = (ki1,...,ki|M|), ki1 < ...

... < ki|M|, представляет собой упорядоченное множество

{k₁, . . . , k_n} =

= {1, . . . , n}, для которого n = |M|. Из определения 1 следует, что пере-

становка π_k является оптимальной для задачи 1|p^′|

∑C_i при любом сце-

нарии p^′ ∈ OB(π_k, T ) = T . Согласно определению

получаем равенство

OR(π_k, T ) = T . Достаточность доказана.

Необходимость. Пусть справедливо равенство OR(π_k, T ) = T . Однако

предположим (от противного), что существует требование Jkr ∈ J в пере-

становке π_k = (Jk1 , . . . , Jkn ) ∈ Π такое, что равенство (17) не выполняется.

Тогда в силу леммы 1 существует непустой отрезок неоптимальности

[l^nonk,unon] или (и) существует непустой отрезок условной оптимальностиk

[l^coptk,ucoptk] для требования Jkr ∈ J в перестановке πk = (Jk1 , . . . , Jkn ).

Если существует отрезок неоптимальности

[l^nonk,unon], то выполняет-k

ся равенство (5). Если же существует отрезок условной оптимальности

[l^coptk,ucopt], то выполняется равенство (7). В обоих случаях существует сцена-k

рий p^∗ ∈ (l^nonk,unonk)

⋃(l^coptk

,u^coptk) ⊆ T такой, что перестановка πk не является

оптимальной для задачи 1|p^∗|

∑C_i со сценарием p^∗ ∈ T. Следовательно, в

соответствии с определением 2 получаем соотношение OR(π_k, T ) = T , проти-

воречащее предположению о том, что равенство OR(π_k, T ) = T выполняется.

Это противоречие завершает доказательство теоремы.

Из теоремы 5 и следствия 1 получаем следующее утверждение.

Следствие 3. Если для каждого требования Jkr∈J в перестановке

π_k = (Jk1 ,... ,Jkn ) выполняется равенство (17), то область оптимально-

сти OR(π_k,T) является n-мерным параллелепипедом T ⊂ Rⁿ⁺ c объемом

∏

Vol (π_k, T ) =Ji∈{J : pLi<pUi }(pi -pi).

Перестановка π_k = (Jk1 , . . . , Jkn ), для которой равенства (17) выполняются

для всех требований Jkr ∈ J , является оптимальной для задачи 1|p|

∑C_i с лю-

бым допустимым сценарием p ∈ T . Следовательно, множество {π_k} является

минимальным доминирующим множеством для задачи 1|p^Li ≤ p_i ≤ p^Ui |

∑C_i.

5.2. Как использовать перестановку

с максимальной областью оптимальности

Оптимальная для задачи

1|p^Li ≤ p_i ≤ p^Ui |

∑C_i перестановка π_k, кри-

терий существования которой представлен в теореме

и следствии 3,

встречается на практике довольно редко. Однако для конкретной задачи

1|p^Li ≤ p_i ≤ p^Ui |

∑C_i, возникающей на практике, как правило, одна переста-

новка должна быть выбрана из множества Π и затем реализована при обслу-

живании требований множества J .

На основе доказанных в разделах 3-5.1 результатов можно рекомендо-

вать выбирать для реализации такую перестановку π_t обслуживания требо-

ваний множества J , для которой объем области оптимальности OR(π_t, T )

является максимальным среди всех перестановок множества Π. Если ока-

жется, что фактический сценарий p ∈ T обслуживания требований J бу-

дет принадлежать области оптимальности OR(π_t, T ), то реализованная пе-

рестановка π_t будет оптимальной для фактического сценария обслужива-

ния требований J . Вообще говоря, чем больше объем области оптималь-

ности OR(π_k, T ), тем больше вероятность того, что перестановка π_k бу-

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

Поэтому важными задачами для дальнейших исследований представля-

ются разработка эффективных алгоритмов построения перестановки π_t с

максимальным объемом Vol^max(π_t, T ) = max{Vol^max(π_k, T ) : π_k ∈ Π} обла-

сти оптимальности OR(π_t, T ) и тестирование таких алгоритмов на задачах

1|p^Li ≤ p_i ≤ p^Ui |

∑C_i практической размерности.

В общем случае задачи 1|p^Li ≤ p_i ≤ p^Ui |

∑C_i разность

Vol^max(π_k, T )

∏

=: µ

J_i∈{J : l^opti<u^opti}(pi -pi)

можно рассматривать как меру неопределенности (или меру сложности) за-

дачи. В частности, если µ = 0, то имеется гарантия того, что перестановка π_t

с максимальным объемом Vol^max(π_t, T ) области оптимальности OR(π_t, T ) бу-

дет оптимальной для фактического сценария обслуживания требований мно-

жества J , несмотря на неопределенность заданных сценариев T . Наоборот,

если значение µ равно единице (или близко к единице), то вероятность того,

что перестановка π_t будет оптимальной для фактического сценария обслужи-

вания требований множества J , равна нулю (близка к нулю). В таких случа-

ях для решения неопределенной задачи 1|p^Li ≤ p_i ≤ p^Ui |

∑C_i можно рекомен-

довать использование приближенных алгоритмов таких, как алгоритм U2,

описанный в [1], или описанный в [10] алгоритм 3, который ориентирован на

достижение наименьшей погрешности полученного решения.

6. Заключение

Задачи составления расписаний обслуживания требований с неопределен-

ными числовыми данными на одном приборе возникают, например, при пла-

нировании рабочего времени работника на определенный период времени (ра-

бочий день, неделю или месяц). Как правило, можно заранее оценить диапа-

зоны возможных длительностей планируемых работ. Можно предполагать,

что множество планируемых работ существенно не меняется в ходе реализа-

ции расписания. Критерий минимизации суммы моментов завершения обслу-

живания требований (среднего времени обслуживания требований) можно

рассматривать как суммарный показатель эффективности выполнения ра-

ботником заданного множества работ.

В [27] описан другой пример задачи 1|p^Li ≤ p_i ≤ p^Ui |

∑C_i, возникающей

при поиске оптимального расписания доставки продукции от изготовителя

в торговую сеть города при использовании одного транспортного средства.

Время доставки продукции в магазин зависит от множества факторов та-

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

средства и дорожного покрытия.

Задачи 1|p^Li ≤ p_i ≤ p^Ui |

∑C_i могут возникать и в некоторых многостадий-

ных обслуживающих системах, если один обслуживающий прибор является

“узким местом” производственного процесса и для длительностей обслужи-

вания требований на этом приборе известны только границы возможных зна-

чений.

Полученные в разделах 3-5 результаты и алгоритмы 1 и 2 можно исполь-

зовать при построении перестановки π_t ∈ Π обслуживания заданных требова-

ний с наибольшим объемом Vol^max(π_t, T ) области оптимальности OR(π_t, T ).

Использование перестановки π_t для обслуживания заданных требований поз-

воляет повысить вероятность получения фактически оптимального распи-

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

длительностей обслуживания требований не известны при построении рас-

писания для задачи 1|p^Li ≤ p_i ≤ p^Ui |

∑C_i.

ПРИЛОЖЕНИЕ

При доказательстве леммы 4 будем рассматривать задачу

∑

1|p^Li ≤ p_i ≤ p^Ui |

C_i

вместо задачи 1|p^Li ≤ p_i ≤ p^Ui |

∑C_i (теорема 2). Поскольку OR(π_k,T) = ∅, то

согласно теореме 3 не существует ни одного требования Jkr ∈ J , которое не

имеет условной оптимальности и одновременно не имеет отрезка оптималь-

ности в перестановке π_k. По условию леммы 4 каждое требование Jkr ∈ J не

имеет отрезка оптимальности в перестановке π_k.

Учитывая замечание 1 и лемму 1, получаем равенство

[

]

p^Lk,

p^Uk

= [l^coptk,ucopt],k

которое выполняется для каждого требования Jkr ∈ J . Из полученного ра-

венства следует, что множество S(π_k) секций перестановки π_k не содержит[

]

ни одной тривиальной секции. Построим разбиение (12) охватов

p^Lk,

p^U

k_j+mj

всех секций sπkj ∈ S(πk) на следующие подынтервалы условной оптимально-

сти:

[

(

)

(

))⋃

⋃[

(

)

(

))⋃

π_k

l^j

sπk

,u^j

sπkj

⋃[

(

)

(

)]

[

]

π_k

l^j

= p^Lk, pU

n(j)

k_j+mj

Далее методом математической индукции по мощности |Jj ( )[( ))|множества

π_k

докажем, что для каждого подынтервала l^j

условной опти-

мальности в построенном разбиении (12) выполняются следующие равенства:

(

)

(

))_|J j

(

)

sπk

-l^j

sπk

(Π.1)

Vol

Jji

|J^ji |!

(

)

(

)

(Π.2)

Jji,T

= Pir^optĴ^ji = Pir^opt J_k

,...,J_k

(

)

где основанием |J^ji|-мерной пирамиды P ir^optĴ^ji = P ir^opt J_k

,...,J_k

яв-

(яется (|J^j() i| (1)-)) наяпирамида,адлинавысотывсехпирамидравна

u^ji sπk

-l^j

sπk

Покажем вначале, что при |J^ji | = 2 пирамида P ir^optĴ^ji = P ir^opt(J_k

,Jki+1)

превращается в треугольник (как вырожденный случай пирамиды) с основа-[

(

)

(

)]

(

)

(

))

π_k

нием l^j

и высотой той же длины u

-l_i

, что и

длина основания треугольника. Такой треугольник P ir^optĴ¹¹ = P ir^opt(J₁, J₂)

представлен на рис. 4,a для подынтервала

[

)

[4, 8) = l¹¹(J₁, J₂), u¹¹(J₁, J₂)

условной оптимальности для перестановки π₂ = (J₁, . . . , J₁₀) ∈ Π для приме-

ра 3. Из теоремы 1 следует, что для того, чтобы порядок (Jki , Jki+1 )

J ji двух

требований был оптимальным в перестановке π_k ∈ Π, необходимо и доста-

точно, чтобы длительности pki и pki+1 требований Jki и Jki+1 удовлетворяли

неравенству pki ≤ pki+1 , а с учетом принадлежности допустимого сценария

(pk1 , . . . , pkn ) заданному множеству T допустимые длительности pki и pki+1

должны удовлетворять следующей системе неравенств:





pki ≤ pki+1,

(Π.3)

pLki ≤ pki ≤ p^U ,_k



pLki+1 ≤ pki+1 ≤ p^U

k_i+1

Система (Π.3) определяет треугольник P ir^optĴ^ji = P ir^opt(J_k

,Jki+1). Ины-

ми словами, системе (Π.3) удовлетворяют все точки, принадлежащие тре-

угольнику P ir^optĴ^ji, и только они. Таким образом, равенство (Π.2) доказано

для случая |J^ji | = 2. Поскольку площадь треугольника P ir^optĴ^ji равна про-

(s^πkj )-l^ji (s^πkj ))²

изведению основания на половину высоты:

, то и равенство

(Π.1) доказано для случая |J^ji| = 2.

Рассмотрим следующее по мощности множество J^ji , т.е. |J^ji | = 3, и пока-

жем, что в этом случае область оптимальности

J ji ,T) = OR((J_k

,Jki+1,Jki+2),T)

представляет собой 3-мерную пирамиду P ir^optĴj ( ) ( ))(i,длинавысотыкоторойрав-

π_k

на u^j

-l_i

и основанием которой является треугольник с высо-

(

)

(

))

[

(

)

(

)]

π_k

той той же длины u^j

-l_i

и с основанием l_i

Отметим, что такая пирамида оптимальности P ir^optĴ¹¹ = P ir^opt(J₂, J₃, J₄)

представлена на рис. 4,b для подынтервала

[

)

[9, 13) = l¹³(J₂, J₃, J₄), u¹³(J₂, J₃, J₄)

условной оптимальности для перестановки π₂ = (J₁, . . . , J₁₀) для примера 3.

Из теоремы 1 следует, что для того, чтобы порядок (Jki , Jki+1 , Jki+2 )

Jji

трех требований был оптимальным в перестановке π_k ∈ Π, необходимо и до-

статочно, чтобы длительности pki , pki+1 и pki+2 требований Jki , Jki+1 и Jki+2

удовлетворяли неравенствам pki ≤ pki+1 ≤ pki+2 , а с учетом принадлежности

допустимого сценария (pk1 , . . . , pkn ) заданному множеству T длительности

pki, pki+1 и pki+2 должны удовлетворять следующей системе неравенств:



pki ≤ pki+1 ≤ pki+2,





pLki ≤ pki ≤ pU,

k_i

(Π.4)



pLki+1 ≤ pki+1 ≤ p^U

k_i+1



pLki+2

≤pki+2 ≤p^U

k_i+2

Система (Π.4) определяет 3-мерную пирамиду

P ir^optĴ^ji = P ir^opt(J_k

, Jki+1, Jki+2),

основанием которой является треугольник

[(

)

(

)

(

)]

p^Lk

, p^Lk

, p^Uk

p^Lk

, p^Uk

p^Uk

, p^Uk

, p^U

i+1

i+2

i+1

i+2

i+1

k_i+2

а высотой - отрезок

[(

)

(

)]

p^Lk

, p^Lk

, p^Uk

p^Lk

, p^Lk

, p^L

k_i+2

i+1

i+2

i+1

Следовательно, системе (Π.4) удовлетворяют все точки пирамиды P ir^optĴ^ji =

= Pir^opt(Jki,Jki+1,Jki+2) и только они. Таким образом, равенство (Π.2) дока-

зано и для случая |J^ji| = 3. Поскольку объем 3-мерной пирамиды P ir^optĴ^ji

равен произведению площади основания, т.е. площади треугольника

[(

) (

)]

p^Lk

,p^Lk

,p^Uk

, p^Lk

,p^Uk

, p^Uk

,p^Uk

,p^U

k_i+2

i+1

i+2

i+1

i+2

i+1

на треть высоты:

(

)

(

))₂

(

)

(

))

π_k

u^j

-l_i

u^j

sπk

-l^j

sπk

(

)

(

))₃

π_k

-l_i

(

)

= Vol

Jji,T

то равенство (Π.1) доказано и для случая |J^ji | = 3.

Сделаем индуктивное предположение, т.е. предположим, что оба ра-

венства (Π.1) и (Π.2) выполняются в случае |J^ji | = d, т.е. область опти-

мальности OR

J ji ,T) представляет собой d-мерную пирамиду Pir^optĴ^ji =

= Pir^opt(Jki,...,Jkt), основанием которой является (d - 1)-мерная пирамида,

a (u^ji (sπkj ) - lⁱ (sjk )) - это длина высоты каждой из этих пирамид. Покажем,

что на основе индуктивного предположения можно получить равенства (Π.1)

и (Π.2) для случая |Jji | = d + 1.

[

(

)

(

))

π_k

Рассмотрим подынтервал

l^j

условной оптимальности,

для которого

(

)

Jji = J_k

,...,J_k

,J_k

|J^ji | = d + 1.

|-1

Из и{дукти}ного предположения следует, что для множества требований

J^ji \ J_k

оба равенства (Π.1) и (Π.2) выполняются, и область оптималь-

((

)

ности OR Jki , . . . , J_k

,T представляет собой d-мерную пирамиду

|-1

((

)

P ir^opt (J_k

,...,Jkt)=OR

Jki ,... ,J_k

|-1

Сле

(

)

ний Jki , . . . , J_k

был оптимальным в перестановке π_k ∈ Π, необходимо

|-1

и достаточно, чтобы длительности pki , . . . , p_k

требований Jki , . . . , J_k

|-1

удовлетворяли следующей системе неравенств:



pki ≤ ... ≤ p_k



|-1





pLki ≤ pki ≤ p^U ,_k

(Π.5)



 p^Lk

≤p_k

≤p^Uk

j|-1

|-1

Добавив к системе (Π.5) неравенства

p_k

≤p_k

и p^Lk

≤p_k

≤p^Uk

|-1

получим следующую систему неравенств:





pki ≤ ... ≤ p_k

|-1



p_k

≤p_k



|-1





pLki ≤ pki ≤ p^U ,_k

(Π.6)



p^Lk

≤p_k

≤p^Uk

|-1



 p^Lk

≤p_k

≤p^Uk

которая определяет (d + 1)-мерную пирамиду

(

)

P ir^optĴ^ji = P ir^opt J_k

,...,J_k

(

)

основанием которой является d-мерная пирамида P ir^opt

Jki ,... ,J_k

,а

|-1

(

)

(

))

π_k

разность u^j

-l_i

равна длине высоты каждой из двух пирамид.

Из сдел((ного предпол)же)я и теоремы 1 следует, что область оптималь-

ности OR Jki , . . . , J_k

,T представляет собой (d+1)-мерную пирамиду

(

)

((

)

P ir^opt Jki , . . . , J_k

= OR Jki,... ,J_k

. Следовательно, равенство

(Π.2) установлено и для случая |J^ji| = d + 1. Поскольку объем (d + 1)-мерной

пирамиды P ir^optĴ^ji равен произведению объема основания, т.е. объема d-мер-(

)

((

)

ной пирамиды P ir^opt Jki , . . . , J_k

= OR Jki,... ,J_k

,T на вы-

|-1

соту, деленную на (d + 1):

(

)

(

))_d

(

)

(

))

π_k

u^j

-l_i

u^j

sπk

-l^j

sπk

d+1

(sπkj ) - lⁱ(sjk ))^d+1

= Vol

J_i

,T),

(d + 1)!

то равенство (Π.1) установлено и для случая |J^ji | = d + 1. Таким образом,

равенства (Π.1) и (Π.2) доказаны методом математической индукции.

Равенство (14) следует из равенства (Π.2) и того, что при любом сцена-

рии p ∈ T длительность каждого требования J_i ∈ J принимает единственное

значение p_i. Равенство (13) следует из замечания 2 и равенства (14). Равен-

ство (15) следует из равенств (13), (14) и (Π.1). Лемма 4 доказана.

СПИСОК ЛИТЕРАТУРЫ

1. Allahverdi A., Aydilek H., Aydilek A. Single machine scheduling problem with inter-

val processing times to minimize mean weighted completion times // Comput. Oper.

Res. 2014. V. 51. P. 200-207.

2. Goren S., Sabuncuoglu I. Robustness and stability measures for scheduling: single-

machine environment // IIE Transact. 2008. V. 40. P. 66-83.

3. Pereira J. The robust (minmax regret) single machine scheduling with interval pro-

cessing times and total weighted completion time objective // Comput. Oper. Res.

2016. V. 66. P. 141-152.

4. Lu C.-C., Lin S.-W., Ying K.-C. Robust scheduling on a single machine total flow

time // Comput. Oper. Res. 2012. V. 39. P. 1682-1691.

5. Sotskov Y.N., Werner F. Sequencing and Scheduling with Inaccurate Data. N.Y.,

USA: Nova Science Publishers, Hauppauge, 2014.

6. Braun O., Lai T.C., Schmidt G., Sotskov Y.N. Stability of Johnson’s schedule with

respect to limited machine availability // Int. J. Product. Res. 2002. V. 40. No. 17.

P. 4381-4400.

7. Davis W., Jones A. A real-time production scheduler for a stochastic manufacturing

environment // Int. J. Product. Res. 1988. V. 1. No. 2. P. 101-112.

Grabot B., Geneste L. Dispatching rules in scheduling: a fuzzy approach // Int. J.

Product. Res. 1994. V. 32. No. 4. P. 903-915.

Kasperski A., Zielinski P. Possibilistic minmax regret sequencing problems with

fuzzy parameters // IEEE Transact. Fuzzy Syst. 2011. V. 19. P. 1072-1082.

10.

Sotskov Y.N., Egorova N.G. Single machine scheduling problem with interval pro-

cessing times and total completion time objective // Algorithms. 2018. V. 11. No. 66.

P. 21-40.

11.

Sotskov Y.N., Lai T.-C. Minimizing total weighted flow time under uncertainty

using dominance and a stability box // Comput. Oper. Res. 2012. V. 39. No. 6.

P. 1271-1289.

12.

Lai T.-C., Sotskov Y.N., Egorova N.G., Werner F. The optimality box in uncertain

data for minimising the sum of the weighted job completion times // Int. J. Product.

Res. 2018. V. 56. No. 19. P. 6336-6362.

13.

Сотсков Ю.Н., Егорова Н.Г. Многогранники устойчивости оптимальной пере-

становки обслуживания требований // АиТ. 2014. № 7. С. 136-154.

Sotskov Y.N., Egorova N.G. Stability polyhedra of optimal permutation of jobs ser-

vicing // Autom. Remote Control. 2014. V. 75. No. 7. P. 1267-1282.

14.

Sotskov Y.N., Lai T.-C., Werner, F. Measures of problem uncertainty for scheduling

with interval processing times // OR Spectrum. 2013. V. 35. P. 659-689.

15.

Sotskov Y.N., Egorova N.G., Lai T.-C. Minimizing total weighted flow time of a

set of jobs with interval processing times // Math. Comput. Modell. 2009. V. 50.

P. 556-573.

16.

Lai T.-C., Sotskov Y.N., Sotskova N., Werner F. Optimal makespan scheduling with

given bounds of processing times // Math. Comput. Modell. 1997. V. 26. No. 3.

P. 67-86.

17.

Сотсков Ю.Н., Егорова Н.Г., Вернер Ф. Минимизация суммарного взвешен-

ного времени обслуживания требований с неопределенными данными: метод,

основанный на устойчивости // АиТ. 2010. № 10. С. 26-49.

Sotskov Y.N., Egorova N.G., Werner F. Minimizing total weighted completion time

with uncertain data: a stability approach // Automat. Remote Control. 2010. V. 71.

No. 10. P. 2038-2057.

18.

Pinedo M. Scheduling: Theory, Algorithms and Systems. N.J., USA: Prentice-Hall,

Englewood Cliffs, 2002.

19.

Graham R.E., Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G. Optimization and

approximation in deterministic sequencing and scheduling: a survey // Ann. Discret.

Math. 1979. V. 5. P. 287-326.

20.

Smith W. Various optimizers for single-stage production // Naval Res. Logist. Quar-

terly. 1956. V. 3. No. 1. P. 59-66.

21.

Kouvelis P., Yu G. Robust Discrete Optimization and its Application. Boston, USA:

Kluwer Academ. Publish., 1997.

22.

Burdett R.L., Kozan E. Techniques to effectively buffer schedules in the face of

uncertainties // Comput. Industr. Engineer. 2015. V. 87. P. 16-29.

23.

Kasperski A., Zielinski P. A 2-approximation algorithm for interval data minmax

regret sequencing problems with total flow time criterion // Oper. Res. Lett. 2008.

V. 36. P. 343-344.

24.

Daniels R.L., Kouvelis P. Robust scheduling to hedge against processing time

uncertainty in single stage production // Management Sci. 1995. V. 41. No. 2.

P. 363-376.