АФРАЙМОВИЧ Л.Г., ННГУ им. Н. И. Лобачевского, Институт Информационных Технологий, Математики и Механики, кафедра «Информатики и автоматизации научных исследований»

 ТЮНТЯЕВ А.С., ННГУ им. Н. И. Лобачевского, Институт Информационных Технологий, Математики и Механики, кафедра «Информатики и автоматизации научных исследований»

 ТЮНТЯЕВА Л.А., ННГУ им. Н. И. Лобачевского, Институт Информационных Технологий, Математики и Механики, кафедра «Информатики и автоматизации научных исследований»

Исследование комбинированного
решения трехиндексной задачи о назначениях

Трехиндексная аксиальная задача о назначениях, подробно рассматриваемая в данной статье, является частным случаем многоиндексных задач о назначениях и имеет широкий спектр приложений, что говорит об ее актуальности. В статье изложено исследование задачи, в ходе которого: реализован алгоритм метода ветвей и границ с разными стратегиями ветвления и возможностью выбора алгоритма подсчета нижних оценок; проведен вычислительный эксперимент с решением задач разных размерностей; проведен анализ полученных результатов. Цель исследования – поиск наилучшей (с точки зрения затраченного времени) комбинации параметров алгоритма (стратегий ветвления, выбора алгоритма подсчета нижних оценок) для решения поставленной задачи

Введение

Многоиндексные задачи о назначениях (подкласс широкого класса прикладных задач, формализуемых в виде многоиндексных задач (целочисленного) линейного программирования транспортного типа) возникают:

• в теории расписаний:
  • при планировании изготовления скоропортящейся продукции,
  • при планировании прохождения практики студентами,
  • при планировании учебы клинических ординаторов по отделениям,
  • при составлении расписания занятий,
  • при планировании спортивных матчей [1, 4],
• в области технического анализа данных:
  • при сопровождении объектов в многосенсорных системах [1, 6],
• в военной области:
  • при назначении военной техники на цели [1, 7].

Класс многоиндексных задач о назначениях, начиная с трехиндексных, является NP (non-deterministic polynomial) – трудным, то есть на данный момент не известны эффективные алгоритмы для их решения.

Трехиндексная аксиальная задача о назначениях (далее просто задача), подробно рассматриваемая в данной статье, является частным случаем многоиндексных задач о назначениях и имеет широкий спектр приложений [1-4, 8, 9], что говорит об ее актуальности.

В статье изложено исследование задачи, в ходе которого:

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

Цель исследования – поиск наилучшей (с точки зрения затраченного времени) комбинации параметров алгоритма (стратегий ветвления, выбора алгоритма подсчета нижних оценок) для решения поставленной задачи.

В первом разделе представлены формальное описание и математическая модель задачи.

Второй раздел посвящен описанию алгоритмов, реализованных для решения задачи.

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

Формальная постановка задачи

Есть исполнители, работы и орудия труда, которыми исполнители могут пользоваться при исполнении работ. Заданы зарплаты от назначения исполнителей на работы при использовании того или иного орудия труда. Надо так назначить исполнителей на работы, чтобы:

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

Критерии и ограничения математической модели задачи представлены ниже:

(1)

(1’)

(2)

(3)

(4)

(5)

где I=J=K={1,2,…n} – множества работников, работ и орудий труда соответственно.

Критерий задачи (1’) записан с декомпозиционной матрицей стоимостей, где:

• c_ijk=m_1ij+m_2jk+m_3ik;
• C=||cijk||(n×n×n) – трехиндексная матрица зарплат порядка n;
• M₁=||m_1ij||(n×n×n) – матрица стоимости выполнения i-м работником j-й работы, ∀i∈I, ∀j∈J;
• M₂=||m_2jk||(n×n×n) – матрица стоимости выполнения j-й работы k-м орудием труда ∀j∈J, ∀k∈K;
• M₃=||m_3ik||(n×n×n) – матрица стоимости пользования i-го исполнителя k-м орудием труда, ∀i∈I, ∀k∈K.

Далее будет рассматриваться задача с математической моделью (1’) – (5), так как архитектура построенного алгоритма работает только для задач такого вида, задача также является NP – трудной [5].

Алгоритм решения задачи

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

Элемент разбиения представляет собой последовательное назначение i_k→j_k, ∀k∈K на k-м шаге ветвления. Для каждого элемента разбиения вычисляется верхняя и нижняя оценки. Также на каждом шаге элементы разбиения подвергаются процедуре отсева. Процедура отсева происходит следующим образом:

Если нижняя оценка p-го элемента разбиения (H_p,p∈{1,…n}), найденная на k-м шаге ветвления (k=(1,n)) не меньше, чем верхняя оценка s-го элемента разбиения на том же шаге ветвления (B_s,p∈{1,…n}), то ветка (подмножество решений исходной задачи), содержащая s-й элемент разбиения, отсекается (исключается из дальнейшего рассмотрения для поиска решения).

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

Hp≥Bs, p,s=(1,n)

Глобальный оптимум задачи ищется на листьях, у которых известны все назначения i→j симплекс-методом. Каждый такой лист содержит n! допустимых решений, оптимум среди которых можно найти за полиномиальное время за счет сведения задачи к двухиндексной задаче о назначениях.

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

Описание стратегий ветвления, использованных в алгоритме метода ветвей и границ:

• Ветвление в глубину (Length) – при использовании данной стратегии на k-м шаге ветвления выбирается такой элемент разбиения, количество назначений i_k→j_k которого наибольшее (k=(1,n));
• Ветвление в ширину (Width) – при использовании данной стратегии на k-м шаге ветвления выбирается такой элемент разбиения, количество назначений i_k→j_k которого наименьшее (k=(1,n));
• Ветвление по минимальной верхней оценке (EffectiveHB) – при использовании данной стратегии на k-м шаге ветвления выбирается такой элемент разбиения s, верхняя оценка которого наименьшая по сравнению с верхними оценками элементов разбиения, полученных до k-го шага включительно (В_s=minВ_k, где В_k – множество верхних оценок элементов разбиения, известных на k-м шаге алгоритма (k=(1,n));
• Ветвление по минимальной нижней оценке (LowMax-Branch) – при использовании данной стратегии на k-м шаге ветвления выбирается такой элемент разбиения s, нижняя оценка которого наименьшая по сравнению с нижними оценками элементов разбиения, полученных до k-го шага включительно (H_s=minH_k, где H_k – множество нижних оценок элементов разбиения, известных на k-м шаге алгоритма (k=(1,n));
• Ветвление по гибридной оценке (Gybrid) – при использовании данной стратегии на k-м шаге ветвления выбирается такой элемент разбиения s, отношение нижней оценки которого к верхней не менее 0,9 (H_s/B_s≥0,9). При этом на нижнюю оценку выбранного s-го элемента разбиения накладывается дополнительное условие: она должна отличаться от минимальной нижней оценки из множества, (H_k – множество нижних оценок элементов разбиения, известных на k-м шаге алгоритма (k=(1,n)) не более, чем на 10%. (Нижние оценки, удовлетворяющие данному условию, будем называть «хорошими»). Если нет элемента разбиения, удовлетворяющего данным условиям, то берется элемент с наименьшим количеством назначений i_k→j_k (k=(1,n));
• Ветвление по разностной оценке (Substraction) – при использовании данной стратегии на k-м шаге ветвления выбирается такой элемент разбиения s, разность между верхней и нижней оценкой которого минимальна (B_s–H_s→min);
• Ветвление по соотношению оценок (Ratio) – при использовании данной стратегии на k-м шаге ветвления выбирается такой элемент разбиения s, отношение нижней оценки которого к верхней максимально. (H_s/B_s→max). При этом на нижнюю и верхнюю оценки выбранного s-го элемента разбиения накладываются следующие дополнительные условия: они должны соответственно отличаться от минимальной нижней и верхней оценки из множеств H_k, B_k (где H_k, B_k – множество нижних и верхних оценок элементов разбиения, известных на k-м шаге алгоритма (k=(1,n)) не более, чем на 30%. Если нет элемента разбиения, удовлетворяющего всем данным условиям, то берется элемент с наименьшим количеством назначений i_k→j_k (k=(1,n)).

При подсчете верхней оценки листа используется жадный алгоритм (для каждого элемента ∀i∈I выбираются допустимые элементы ∀j∈J и ∀k∈K, при которых стоимость назначения минимальна).

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

• Симплекс метод. Идея метода – избавиться от целочисленности и изменить (5) ограничение задачи на ограничение вида:

(6)

• Потоковый алгоритм (алгоритм поиска потока минимальной стоимости с двусторонними пропускными способностями). Данный алгоритм находит оптимальное решение трех двухиндексных задач о назначениях, которые получаются при декомпозиции исходной трехиндексной матрицы с учетом уже известных (полученных ранее) назначений i→j элемента разбиения. Оптимально назначаются исполнители на работы, оптимально выбираются орудия труда для работ и оптимально выбираются орудия труда для исполнителей. Далее, подсчитывается общая суммарная стоимость от решения всех трех двухиндексных задач, которая и представляет собой нижнюю оценку для вершины.

Вычислительный эксперимент

Для решения задач данного класса описанным алгоритмом было написано программное приложение в интегрированной среде разработки Visual Studio Professional 2017 (Windows Forms, язык программирования C#).

Вычисления проводились на вычислительной технике фирмы ASUS. Процессор: Intel® Core ™ i5 – 3230M CPU @ 2.60GHz. Тип системы: 64 – разрядная операционная система, процессор х64, операционная система: Windows 8.

На рис. 1 представлено диалоговое окно приложения, в котором выбираются параметры для решения задач. В реализации алгоритма предусмотрены выбор параллельного или последовательного подсчета верхних и нижних оценок для «потомков» вершины, а также последовательный или же параллельный запуск стратегий ветвления. Приложение позволяет генерировать задачи случайным образом или решать предложенные задачи.

Рисунок 1. Диалоговое окно приложения, в котором выбираются параметры для решения задач

В ходе вычислительного эксперимента тестировались задачи размерностей (n) равных:

• 6 (2 задачи),
• 10 (2 задачи),
• 15 (2 задачи),
• 33 (задача с известным оптимумом и решением [10]).

Цели вычислительного эксперимента:

• путем вычисления задач с известными оптимальными решениями убедиться, что реализованный алгоритм работает верно;
• найти наилучшую, с точки зрения затраченного времени, комбинацию параметров алгоритма (стратегии ветвления, выбор алгоритма подсчета нижних оценок) для решения этого класса задач.

Стратегия подсчета нижней оценки для каждого листа выбиралась таким образом:

если у вершины «родителя» соотношение