В работе описывается новый класс неравенств, правильных относительно многогранника расписаний обслуживания единичных требований параллельными приборами без прерываний. Показано, что полученные неравенства могут служить отсекающими плоскостями в алгоритмах поиска оптимального расписания с различными критериями оптимальности. Проведено сравнение неравенств.
max () → m∈in .
∈ Пусть Вектор жество = 1, если () = , = 0 – в противном случае.
Заметим, что если < ′, то ⊂
′ (при этом полагаем, что пустое множество является подмножеством любого множества). Целесообразно значение брать не превосходящим , так как при ≥ всегда ̸= ∅.
Мы рассматриваем полиэдральную структуру множества безотносительно к целевой функции.
Множеству сопоставляется полиэдр, целочисленные вершины которого взаимно-однзначно соответствуют
расписаниям. В работе [4] описаны два класса неравенств, правильных относительно выпуклой оболочки
расписаний, получены условия их опорности. В настоящей работе представлен новый класс правильных
неравенств, предложена эвристическая процедура идентификции неравенств этого класса.
∈ – расписание. Сопоставим ему (
= (, ∈ , ∈ ) ∈ по правилу: будем также называть расписанием. Под многогранником расписаний будем понимать мно, = { ∈ | ∈ }.
Условия предшествования в обслуживании требований зададим в виде ациклического орграфа с множеством вершин и множеством дуг . При этом будем полагать, что не содержит транзитивных дуг, заведомо равны нулю. Формализуем это соображение следующим образом. то есть таких дуг (, ), что в существует путь из в , отличный от дуги (, ). Ясно, что в силу условий (i) и (ii) для каждой вершины ∈ имеются такие ∈ , что для любого ∈ компоненты будут Дополним орграф до орграфа ′ фиктивным источником и фиктивным стоком , то есть ′ = длинный путь из в . Если – расписание, то в силу условия (i) имеем соответственно. Для каждой ∈ обозначим через самый длинный путь из в , а через – самый = 0
= 0 при = 1, 2, . . . , || − 1 и = − |
| + 2, − | | + 3, . . . , . всех потомков – через = { ∈ | C }. Для любого ∈ в силу условия (ii) можем написать, что Обозначим множество всех предков вершины ∈ в орграфе через = { ∈ | C }, а множество при = 1, 2, . . . , ⌈ || ⌉ и = − ⌈ || + 1, − ⌈ || ⌉ + 2, . . . , .
вершины ∈ и каждого расписания ∈ имеем
Объединяя (
∑︁ = 1, ∈ , ∈ ∑︁ ≤ , ∈ , 0 ≤ ≤ 1, ∈ , ∈ , = 0, ∈ , ∈ ∖ . ≤ ∈ ∑︁ ∈,>
, (, ) ∈ , ∈ , Для упрощения дальнейших обозначений определим для каждой вершины ∈ множество = {, + 1, + 2, . . . , − }, а для каждого ∈ – множество = { ∈ | ∈ }.
Определим в пространстве полиэдр как множество решений системы линейных уравнений и неравенств:
В [4] было показано что целочисленные точки полиэдра и только они являются расписаниями,
причем данное соответствие взаимно-однозначно. Кроме того, там же описаны два класса правильных
относительно , неравенств. Неравенство ≤ 0 называется правильным относительно , , если оно
выполняется для всех ∈ , . Среди правильных неравенств важную роль играют такие неравенства,
для которых множество ∩ { ∈ | > 0} не пусто. На таких неравенствах основан широкий класс
алгоритмов решения задач целочисленного программирования, называемых алгоритмами отсечения.
(
(9)
∈ . Если
− 1
=2 ∈
В силу ограничений (
Случай а). ∑︀ ∑︀ ̸= 0. Тогда ∑︀ ∑︀ = 0 и ∑︀
∑︀ = 0. В силу неотрицательности компонент
вектора и ограничений (
Случай б). ∑︀
∑︀ ̸= 0. Тогда ∑︀ ∑︀ = 0 и ∑︀ ∑︀ = 0. Здесь рассуждения полностью
Случай в). ∑︀ ∑︀ ̸= 0. Тогда ∑︀ ∑︀ = 0 и ∑︀
∑︀ = 0. Следовательно, в силу
неотрица
телности компонент вектора и ограничений (
Свойство быть отсечением и сравнение -дольных неравенств > 0. Будем говорить, что правильное относительно , неравенство ≤ 0 отсекает точку ∈ , если Приведем пример точки, отсекаемой неравенством класса вида (9). множеством дуг = { 12, 17, 23, 34, 45, 47, 56, 69, 79, 89, 910} (см. рис.1). Пусть = 10, = 3. Пример 1. Рассмотрим орграф предшествований с множеством вершин = {1, 2, 3, 4, . . . , 10} и Рис. 1: Орграф рассмотрим точку ∈ , такую что ∑︀ ∑︀ > max{||, , = 1, . . . , }. В силу неотрицательности ком=1 ∈
+ понент точки будет верным неравенство ∑︀ ∑︀ ≤ ∑︀ ∑︀ . Осталось заметить, что по построению =1 ∈ =1 ∈ + max{||, = 1, . . . , } = max{||, = 1, . . . , + }. Таким образом, ∑︀ ∑︀ > max{||, , = 1, . . . , }. =1 ∈ То есть, если точка ∈ отсекается неравенством, построенным на орграфе , то она отсекается и неравенством, построенным на орграфе . Список литературы
The Class of -Share Inequalities for the Service Schedules of Requirements by
Parallel Devices Polytope
Ruslan Yu. Simanchev, Inna V. Urazova