Класс 𝑡-дольных неравенств для многогранника расписаний обслуживания требований параллельными приборами Р.Ю. Симанчев И.В. Уразова osiman@rambler.ru urazovainn@mail.ru Омский государственный университет им. Ф.М. Достоевского, Омск, Россия Аннотация В работе описывается новый класс неравенств, правильных отно- сительно многогранника расписаний обслуживания единичных тре- бований параллельными приборами без прерываний. Показано, что полученные неравенства могут служить отсекающими плоскостями в алгоритмах поиска оптимального расписания с различными кри- териями оптимальности. Проведено сравнение неравенств. Введение В настоящей работе рассматриваются расписания обслуживания идентичных требований параллельными приборами, которые описываются следующими условиями. Требования множества 𝑉 , |𝑉 | = 𝑛, обслужива- ются 𝑚 параллельными идентичными приборами. Все требования поступают в очередь на обслуживание одновременно (в момент времени 𝑘 = 0) и имеют одинаковые (равные 1) длительности обслуживания. Запрещены прерывания в обслуживании требований. Время дискретно. На множестве 𝑉 задано отноше- ние частичного порядка C, определяющее условия предшествования в обслуживании требований. Всякий порядок обслуживания требований на множестве 𝑉 , допустимый относительно частичного порядка C, на- зывается допустимым расписанием или просто расписанием (см., например, [1, 2]). Требуется построить такое удовлетворяющее частичному порядку расписание обслуживания требований, при котором общее время обслуживания будет минимальным. Отметим, что в [2] приведены полиномиальные алгоритмы ре- шения этой задачи для случаев, когда 𝑚 = 2 и когда 𝐺 является корневым деревом. Для иных случаев в [1, 3] эта задача упомянута как открытая в смысле 𝑁 𝑃 -трудности. Мы рассматриваем расписания, в которых все работы завершаются к моменту времени 𝑑. При этом очевидно, что если 𝑑 будет слишком мало, то множество определенных выше расписаний может оказаться пустым. Это множество расписаний допускает следующую формализацию [1]. Расписанием называется функция 𝜎 : 𝑉 → 𝐷 = {1, 2, . . . 𝑑} такая, что (i) соотношение 𝑖 C 𝑗 влечет неравенство 𝜎(𝑖) < 𝜎(𝑗); (ii) для любого 𝑘 ∈ 𝐷 имеется не более 𝑚 требований 𝑖 ∈ 𝑉 таких, что 𝜎(𝑖) = 𝑘 . Множество расписаний, определенных условиями (i) и (ii), обозначим через 𝑆𝑑 . Таким образом, рас- сматриваемая нами задача может быть записана как max 𝜎(𝑖) → min . 𝑖∈𝑉 𝜎∈𝑆𝑑 c by the paper’s authors. Copying permitted for private and academic purposes. Copyright ○ In: Sergey V. Belim, Nadezda F. Bogachenko (eds.): Proceedings of the Workshop on Data, Modeling and Security 2017 (DMS-2017), Omsk, Russia, October 2017, published at http://ceur-ws.org Заметим, что если 𝑑 < 𝑑′ , то 𝑆𝑑 ⊂ 𝑆𝑑′ (при этом полагаем, что пустое множество является подмножеством любого множества). Целесообразно значение 𝑑 брать не превосходящим 𝑛, так как при 𝑑 ≥ 𝑛 всегда 𝑆𝑑 ̸= ∅. Мы рассматриваем полиэдральную структуру множества 𝑆𝑑 безотносительно к целевой функции. Мно- жеству 𝑆𝑑 сопоставляется полиэдр, целочисленные вершины которого взаимно-однзначно соответствуют расписаниям. В работе [4] описаны два класса неравенств, правильных относительно выпуклой оболочки расписаний, получены условия их опорности. В настоящей работе представлен новый класс правильных неравенств, предложена эвристическая процедура идентификции неравенств этого класса. Пусть 𝜎 ∈ 𝑆𝑑 – расписание. Сопоставим ему (0, 1)-вектор 𝑥𝜎 = (𝑥𝜎𝑖𝑘 , 𝑖 ∈ 𝑉, 𝑘 ∈ 𝐷) ∈ 𝑅𝑛𝑑 по правилу: 𝑥𝜎𝑖𝑘 = 1, если 𝜎(𝑖) = 𝑘 , 𝑥𝜎𝑖𝑘 = 0 – в противном случае. Вектор 𝑥𝜎 будем также называть расписанием. Под многогранником расписаний будем понимать мно- жество 𝑃𝑑,𝑍 = 𝑐𝑜𝑛𝑣{𝑥𝜎 ∈ 𝑅𝑛𝑑 | 𝜎 ∈ 𝑆𝑑 }. Условия предшествования в обслуживании требований зададим в виде ациклического орграфа 𝐺 с мно- жеством вершин 𝑉 и множеством дуг 𝐴. При этом будем полагать, что 𝐺 не содержит транзитивных дуг, то есть таких дуг (𝑖, 𝑗), что в 𝐺 существует путь из 𝑖 в 𝑗 , отличный от дуги (𝑖, 𝑗). Ясно, что в силу условий (i) и (ii) для каждой вершины 𝑖 ∈ 𝑉 имеются такие 𝑘 ∈ 𝐷, что для любого 𝜎 ∈ 𝑆𝑑 компоненты 𝑥𝜎𝑖𝑘 будут заведомо равны нулю. Формализуем это соображение следующим образом. Дополним орграф 𝐺 до орграфа 𝐺′ фиктивным источником 𝑢 и фиктивным стоком 𝑣 , то есть 𝑉 𝐺′ = 𝑉 ∪ {𝑢, 𝑣} и 𝐸𝐺′ = 𝐸 ∪ {(𝑢, 𝑖), 𝑖 ∈ 𝐵} ∪ {(𝑗, 𝑣), 𝑗 ∈ 𝐵} ¯ , где 𝐵 и 𝐵 ¯ – вершинные база и антибаза орграфа 𝐺 соответственно. Для каждой 𝑖 ∈ 𝑉 обозначим через 𝑃𝑖 самый длинный путь из 𝑢 в 𝑖, а через 𝑄𝑖 – самый длинный путь из 𝑖 в 𝑣 . Если 𝜎 – расписание, то в силу условия (i) имеем 𝑥𝜎𝑖𝑘 = 0 (1) при 𝑘 = 1, 2, . . . , |𝑃𝑖 | − 1 и 𝑘 = 𝑑 − |𝑄𝑖 | + 2, 𝑑 − |𝑄𝑖 | + 3, . . . , 𝑑. Обозначим множество всех предков вершины 𝑖 ∈ 𝑉 в орграфе 𝐺 через 𝑈𝑖 = {𝑗 ∈ 𝑉 | 𝑗 C 𝑖}, а множество всех потомков – через 𝑊𝑖 = {𝑗 ∈ 𝑉 | 𝑖 C 𝑗}. Для любого 𝜎 ∈ 𝑆𝑑 в силу условия (ii) можем написать, что 𝑥𝜎𝑖𝑘 = 0 (2) при 𝑘 = 1, 2, . . . , ⌈ |𝑈𝑚𝑖 | ⌉ и 𝑘 = 𝑑 − ⌈ |𝑊 𝑖| |𝑊𝑖 | 𝑚 + 1, 𝑑 − ⌈ 𝑚 ⌉ + 2, . . . , 𝑑. Объединяя (1) и (2), положим 𝑝𝑖 = max{|𝑃𝑖 |, ⌈ |𝑈𝑚𝑖 | ⌉ + 1} и 𝑞𝑖 = max{|𝑄𝑖 | − 1, ⌈ |𝑊 𝑖| 𝑚 ⌉}. Теперь для каждой вершины 𝑖 ∈ 𝑉 и каждого расписания 𝜎 ∈ 𝑆𝑑 имеем 𝑥𝜎𝑖𝑘 = 0, 𝑘 = 1, 2, . . . , 𝑝𝑖 − 1, 𝑑 − 𝑞𝑖 + 1, 𝑑 − 𝑞𝑖 + 2, . . . , 𝑑. (3) Для упрощения дальнейших обозначений определим для каждой вершины 𝑖 ∈ 𝑉 множество 𝐷𝑖 = {𝑝𝑖 , 𝑝𝑖 + 1, 𝑝𝑖 + 2, . . . , 𝑑 − 𝑞𝑖 }, а для каждого 𝑘 ∈ 𝐷 – множество 𝑉𝑘 = {𝑖 ∈ 𝑉 | 𝑘 ∈ 𝐷𝑖 }. Определим в пространстве 𝑅𝑛𝑑 полиэдр 𝑀𝑑 как множество решений системы линейных уравнений и неравенств: ∑︁ 𝑥𝑖𝑘 = 1, 𝑖 ∈ 𝑉, (4) 𝑘∈ 𝐷𝑖 ∑︁ 𝑥𝑖𝑘 ≤ 𝑚, 𝑘 ∈ 𝐷, (5) 𝑖∈ 𝑉𝑘 ∑︁ 𝑥𝑖𝑘 ≤ 𝑥𝑗𝑙 , (𝑖, 𝑗) ∈ 𝐸, 𝑘 ∈ 𝐷𝑖 , (6) 𝑙∈𝐷𝑗 ,𝑙>𝑘 0 ≤ 𝑥𝑖𝑘 ≤ 1, 𝑖 ∈ 𝑉, 𝑘 ∈ 𝐷𝑖 , (7) 𝑥𝑖𝑘 = 0, 𝑖 ∈ 𝑉, 𝑘 ∈ 𝐷 ∖ 𝐷𝑖 . (8) В [4] было показано что целочисленные точки полиэдра 𝑀𝑑 и только они являются расписаниями, причем данное соответствие взаимно-однозначно. Кроме того, там же описаны два класса правильных относительно 𝑃𝑑,𝑍 неравенств. Неравенство 𝑎𝑥 ≤ 𝑎0 называется правильным относительно 𝑃𝑑,𝑍 , если оно выполняется для всех 𝑥 ∈ 𝑃𝑑,𝑍 . Среди правильных неравенств важную роль играют такие неравенства, для которых множество 𝑀𝑑 ∩ {𝑥 ∈ 𝑅𝑛𝑑 | 𝑎𝑥 > 𝑎0 } не пусто. На таких неравенствах основан широкий класс алгоритмов решения задач целочисленного программирования, называемых алгоритмами отсечения. 1 𝑡-дольные неравенства Назовем оргаф 𝐹 𝑡-дольным, если его множество вершин 𝑊 можно разбить на 𝑡 непересекающихся под- множеств 𝑊1 , 𝑊2 , . . . , 𝑊𝑡 так, что для всякой дуги (𝑖, 𝑗) графа 𝐹 найдется такой номер 𝑠 ∈ {1, 2, . . . , 𝑡 − 1}, что 𝑖 ∈ 𝑊𝑠 и 𝑗 ∈ 𝑊𝑠+1 . Если при этом для всякого 𝑠 множество 𝑊𝑠 ∪ 𝑊𝑠+1 индуцирует в 𝐹 полный двудольный граф, то 𝐹 назовем полным 𝑡-дольным. Полный 𝑡-дольный орграф будем обозначать че- рез 𝐹 (𝑊1 , 𝑊2 , . . . , 𝑊𝑡 ). Шириной графа 𝐹 = 𝐹 (𝑊1 , 𝑊2 , . . . , 𝑊𝑡 ) назовем величину 𝛼(𝐹 ) = max{|𝑊𝑠 |, 𝑠 = 1, 2, . . . , 𝑡 − 1} . Выбрав произвольно ∈ 𝐷, свяжем с полным 𝑡-дольным орграфом 𝐹 (𝑊1 , 𝑊2 , . . . , 𝑊𝑡 ) ⊆ 𝐺 линейное неравенство 𝑟𝑖 ∑︁ ∑︁ 𝑡−1 ∑︁ ∑︁ ∑︁𝑘 ∑︁ 𝑥𝑖𝑙 + 𝑥𝑖𝑘 + 𝑥𝑖𝑙 ≤ 𝛼(𝐹 ), (9) 𝑙=𝑘 𝑖∈𝑊1 𝑗=2 𝑖∈𝑊𝑗 𝑙=𝑠𝑖 𝑖∈𝑊𝑡 где 𝑟𝑖 ∈ {𝑘, 𝑘 + 1, . . . , 𝑑} и 𝑠𝑖 ∈ {1, 2, . . . , 𝑘}. Покажем, что неравенство (9) правильное относительно 𝑃𝑑,𝑍 . Действительно, пусть 𝜎 ∈ 𝑆𝑑 . Если 𝑟𝑖 ∑︀ 𝑡−1 𝑘 𝑥𝜎𝑖𝑙 = 𝜎 𝑥𝑖𝑙 = 0, то неравенство (9) очевидно выполняется для точки 𝑥𝜎 . ∑︀ ∑︀ ∑︀ ∑︀ ∑︀ 𝜎 𝑖∈𝑊𝑗 𝑥𝑖𝑘 = 𝑙=𝑘 𝑖∈𝑊1 𝑗=2 𝑙=𝑠𝑖 𝑖∈𝑊𝑡 В силу ограничений (4) и (6) требования, принадлежащие разным долям 𝑊1 , 𝑊2 , . . . , 𝑊𝑡 , не могут обслу- живаться одновременно. Следовательно, любые два или все три блока слагаемых в неравенстве (9) не могут быть одновременно не равными нулю. Таким образом, возникают три случая. 𝑟𝑖 ∑︀ 𝑡−1 𝑘 Случай а). 𝑥𝜎𝑖𝑙 ̸= 0. Тогда 𝑥𝑖𝑘 = 0 и 𝑥𝑖𝑙 = 0. В силу неотрицательности компонент ∑︀ ∑︀ ∑︀ 𝜎 ∑︀ ∑︀ 𝜎 𝑙=𝑘 𝑖∈𝑊1 𝑗=2 𝑖∈𝑊𝑗 𝑙=𝑠𝑖 𝑖∈𝑊𝑡 𝑟𝑖 ∑︀ вектора 𝑥 и ограничений (4) имеем 𝜎 𝑥𝜎𝑖𝑙 ≤ |𝑊1 | ≤ 𝛼(𝐹 ). ∑︀ 𝑙=𝑘 𝑖∈𝑊1 𝑘 𝑟𝑖 ∑︀ 𝑡−1 Случай б). 𝑥𝜎𝑖𝑙 ̸= 0. Тогда 𝑥𝜎𝑖𝑙 = 0 и 𝑥𝜎𝑖𝑘 = 0. Здесь рассуждения полностью ∑︀ ∑︀ ∑︀ ∑︀ ∑︀ 𝑙=𝑠𝑖 𝑖∈𝑊𝑡 𝑙=𝑘 𝑖∈𝑊1 𝑗=2 𝑖∈𝑊𝑗 аналогичны случаю а). 𝑡−1 𝑟𝑖 ∑︀ 𝑘 Случай в). 𝑥𝑖𝑘 ̸= 0. Тогда 𝑥𝜎𝑖𝑙 = 0 и 𝑥𝑖𝑙 = 0. Следовательно, в силу неотрица- ∑︀ ∑︀ 𝜎 ∑︀ ∑︀ ∑︀ 𝜎 𝑗=2 𝑖∈𝑊𝑗 𝑙=𝑘 𝑖∈𝑊1 𝑙=𝑠𝑖 𝑖∈𝑊𝑡 𝑡−1 телности компонент вектора 𝑥𝜎 и ограничений (4), в левой части неравенства (9) имеем 𝑥𝜎𝑖𝑘 ≤ ∑︀ ∑︀ 𝑗=2 𝑖∈𝑊𝑗 max{|𝑊𝑠 |, 𝑠 = 1, 2, . . . , 𝑡 − 1} = 𝛼(𝐹 ). 2 Свойство быть отсечением и сравнение 𝑡-дольных неравенств Будем говорить, что правильное относительно 𝑃𝑑,𝑍 неравенство 𝑎𝑥 ≤ 𝑎0 отсекает точку 𝑥 ¯ ∈ 𝑀𝑑 , если 𝑥 > 𝑎0 . 𝑎¯ Приведем пример точки, отсекаемой неравенством класса вида (9). Пример 1. Рассмотрим орграф предшествований 𝐺 с множеством вершин 𝑉 = {1, 2, 3, 4, . . . , 10} и множеством дуг 𝐴 = { 12, 17, 23, 34, 45, 47, 56, 69, 79, 89, 910} (см. рис.1). Пусть 𝑑 = 10, 𝑚 = 3. Рис. 1: Орграф 𝐺 Таблица 1: Задание точки 𝑥 ¯ 1 2 3 4 5 6 7 8 9 10 1 0 0.8 0 0 0.2 0 0 0 0 0 2 0.4 0 0.6 0 0 0 0 0 0 0 3 0 0.4 0 0.4 0.2 0 0 0 0 0 4 0 0 0.4 0.2 0.2 0.2 0 0 0 0 5 0 0 0 0.2 0.6 0 0.2 0 0 0 6 0 0 0 0 0 0.8 0 0.2 0 0 7 0 0 0 0.2 0.6 0 0 0.2 0 0 8 0 0 1 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0.8 0 0.2 0 10 0 0 0 0 0 0 0 0.8 0 0.2 Точку 𝑥¯ удобно задавать с помощью таблицы 10 × 10, строки которой соответствуют множеству 𝑉 , а столбцы – множеству 𝐷. Точка 𝑥 ¯ ∈ 𝑀𝑑 задана таблицей 1. Выберем двудольный орграф 𝐹 (𝑊1 , 𝑊2 ) ⊂ 𝐺 с 𝑊1 = {1, 4}, 𝑊2 = {5, 7} и 𝑘 = 5. Неравенство (9), отсекающее точку 𝑥 ¯, будет иметь вид: 𝑥51 + 𝑥52 + 𝑥53 + 𝑥54 + 𝑥54 + 𝑥71 + 𝑥72 + 𝑥73 + 𝑥74 + 𝑥75 + 𝑥15 + 𝑥16 + 𝑥17 + + 𝑥18 + 𝑥19 + 𝑥110 + 𝑥45 + 𝑥46 + 𝑥47 + 𝑥48 + 𝑥49 + 𝑥410 ≤ 1. Для процедур отсечения важную роль играет «глубина» отсекающей плоскости. Формально это свойство можно описать так. Будем говорить, что неравенство 𝑎𝑥 ≤ 𝑎0 не сильнее неравенства 𝑏𝑥 ≤ 𝑏0 относительно 𝑀𝑑 , если {𝑥 ∈ 𝑀𝑑 | 𝑎𝑥 > 𝑎0 } ⊆ {𝑥 ∈ 𝑀𝑑 | 𝑏𝑥 > 𝑏0 } (см. рис. 2). Разумеется, могут быть и нестравнимые неравенства в смысле этого определения. Рис. 2: Сравнение неравенств Рассмотрим полный 𝑡-дольный орграф 𝐹 (𝑊1 , 𝑊2 , . . . , 𝑊𝑡 ). Дополним его до орграфа 𝐹¯ следующим об- разом. К орграфу 𝐹 добавим 𝑞 долей так, чтобы 1) орграф 𝐹¯ был полным (𝑡 + 𝑞)-дольным орграфом и 𝑡 2) max{|𝑊𝑗 |, 𝑗 = 1, . . . , 𝑡} = max{|𝑊𝑙 |, 𝑙 = 1, . . . , 𝑡 + 𝑞}. Покажем, что неравенство 𝑥𝑖𝑘 ≤ 𝛼(𝐹 ), по- ∑︀ ∑︀ 𝑗=1 𝑖∈𝑊𝑗 𝑡+𝑞 строенное на орграфе 𝐹 не сильнее неравенства 𝑥𝑖𝑘 ≤ 𝛼(𝐹¯ ), построенного на орграфе 𝐹¯ . Для этого ∑︀ ∑︀ 𝑙=1 𝑖∈𝑊𝑙 𝑡 рассмотрим точку 𝑥 ¯ ∈ 𝑀𝑑 , такую что ¯𝑖𝑘 > max{|𝑊𝑙 |, , 𝑙 = 1, . . . , 𝑡}. В силу неотрицательности ком- ∑︀ ∑︀ 𝑥 𝑙=1 𝑖∈𝑊𝑙 𝑡 𝑡+𝑞 понент точки 𝑥 ¯ будет верным неравенство ¯𝑖𝑘 . Осталось заметить, что по построению ∑︀ ∑︀ ∑︀ ∑︀ ¯𝑖𝑘 ≤ 𝑥 𝑥 𝑗=1 𝑖∈𝑊𝑗 𝑙=1 𝑖∈𝑊𝑙 𝑡+𝑞 max{|𝑊𝑗 |, 𝑗 = 1, . . . , 𝑡} = max{|𝑊𝑙 |, 𝑙 = 1, . . . , 𝑡 + 𝑞}. Таким образом, ¯𝑖𝑘 > max{|𝑊𝑙 |, , 𝑙 = 1, . . . , 𝑡}. ∑︀ ∑︀ 𝑥 𝑗=1 𝑖∈𝑊𝑗 То есть, если точка 𝑥 ¯ ∈ 𝑀𝑑 отсекается неравенством, построенным на орграфе 𝐹 , то она отсекается и неравенством, построенным на орграфе 𝐹¯ . Список литературы [1] M.R. Garey, D.S. Johnson. Computers and intractability. A guide to the theory of NP-completeness. A Series of Books in the Mathematical Sciences. W.H. Freeman and Co., San Francisco, Calif., 1979. [2] V.S. Tanaev, V.S. Gordon, Ya.M. Shafranskiy. Schedules Theory. One-stage systems. М., Нauka, 1984, 381 p. (In Russian). [3] URL: http://www.mathematik.unisnabrueck.de/reseach/OR/class. [4] R.Yu. Simanchev, I.V. Urazova. The polytope of schedules of identical jobs on parallel processors. Diskretn. Anal. Issled. Oper., 18(1):85–97, 2011 (In Russian). The Class of 𝑇 -Share Inequalities for the Service Schedules of Requirements by Parallel Devices Polytope Ruslan Yu. Simanchev, Inna V. Urazova A new class of inequalities that are valid with respect to the service schedules single requirements with parallel devices without interrupts polytope are described. It is shown that the obtained inequalities can serve as cutting planes in algorithms for finding the optimal schedule with different optimality criteria. The comparison of this inequalities are conducted.