Равномерность и минимальность стоимости в задаче о назначениях

Диссертационная работа посвящена изучению некоторых обобщений задачи о назначениях — одной из классических задач дис7 кретной математики. Классическая задача о назначениях формулируется следующим образом. Имеется конечное число исполнителей.

61,62, • • • 5 6П, каждый из которых должен быть занят в некоторый из дней с?2, •., dn.

Стоимость занятости в день dj исполнителя Ь{ равна Cjj. Нужно распределить исполнителей по дням, то есть назначить по одному работнику на каждый день так, чтобы, во-первых, были заняты все дни и, во-вторых, минимизировать затраты. Данная задача широко исследована в работах таких известных математиков как Х. Кун (см. [28]), Н. Кристофидес (см. [11]), Э. Эгервари (см. [24]) и многих других. Были получены эффективные алгоритмы решения классической задачи о назначениях, в частности Венгерский метод решения, усовершенствованная схема алгоритма глобального поиска для квадратичной задачи о назначениях приведена в работах Васильева И. Л. и Киселева В. Д. (см. [2], [7]). Многие задачи дискретной оптимизации, сводятся к классической задаче о назначениях, классификации таких задач посвящены работы Abreu N., Netto Р., (см. [20]) Angel Е. (см. [21]-[23]), Korvin А. (см. [26], [27]) и других. Кроме того были сформулированы и исследованы свойства различных ее обобщений, которые невозможно свести к классической, и решение которых не является тривиальным.

Одним из таких обобщений является задача альтернативного распределения разнотипных средств (АРРС) исследованная Коротким Ю. Г. Селютиным В.А. и др. (см. 4], [9], [10], [17]). Внешне ее постановка близка к классической задаче о назначениях, в которой количество исполнителей и работ одинаково. Отличие задачи АРРС состоит в разрешении неоднократного назначения исполнителей, т. е. совместительства. Это разветвляет структуру множества возможных значений и увеличивает его мощность, что принципиально усложняет задачу. Разработан алгоритм решения задачи АРРС, дающий конечное точное решение. Он относится к классу «ветвей и границ». Общая идея метода состоит в последовательном разбиении исходного множества решений на подмножества с последующими оценкой и отбрасыванием неперспективных, выделении перспективных подмножеств и в дальнейшем их расчленении. В диссертационной работе также рассматривается задача о назначениях с возможностью совместительства.

Исследовались различные частные случаи задачи о назначениях. Например, в работах Воскресенского Е. А., Добровольского Н. М. и Симонова А. С. (см. 3]) исследуется задача о назначения следующего вида. Имеется квадратная матрица размерности пхп таки>- чисел, что любой их набор из п чисел, составленный по одному числу из каждой строки и столбца, имеет одну и туже сумму. Требуется найти алгоритм получения набора, имеющего наименьшую дисперсию среди всех возможных наборов, при условии, что числа, стоящие в строках и столбцах матрицы, образуют арифметическую прогрессию. В диссертационной работе также рассматривается квадратичное отклонение от средней занятости, но по отношению к числу работ, назначенному каждому исполнителю.

Многие обобщения задачи о назначениях формулируются в виде практических заданий, их решение ищется исходя из специфических условий работы предприятия или организации. Большое количество обобщений классической задачи о назначениях исследованы в работах Стрекаловского А. С. (см. [18]), Кузнецовой А. А. (см. [12]) (квадратичная задача о назначениях) — Козловского В. А., Козловского Э. А. (см. [8]) — Кумагиной Е. А., Прилуцкого М. Х. (задача распределения ресурсов)(см. [13], [14], [15]), Ямпольского JI.C., Бондаренко В. Н. (см. [1], [19]) и других.

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

Введение

сразу двух функционалов оптимизации приводит к тому, что такие задачи не удается свести к классической задаче о назначениях. Более того, не во всех задачах присутствует или является приоритетным функционал стоимости. Свойства задачи о равномерном назначении работ и алгоритм ее решения были представлены Рублевым B.C. (см. 16]). Было доказано, что критерий минимизации среднеквадратичного отклонения от средней занятости является более сильным по сравнению с другими критериями равномерности. Им же были сформулированы обобщения задачи о равномерном назначении, исследованию которых посвящена диссертационная работа.

В зависимости от того, какая из характеристик — минимальность стоимости или равномерность назначения является приоритетной, формулируются различные задачи. Если приоритетной является равномерность, то формулируется задача о минимальной стоимости равномерного назначения (МСРН), если на первом месте минимальность стоимости, то — задача о равномерном назначении работ минимальной стоимости (РНМС). Основной сложностью в задаче МСРН является сохранение минимальной стоимости при оптимизации равномерности назначения. Исследований этой задачи привело к формулировке новых обобщений задачи о назначениях, частным случаем одного из которых является задача МСРН. А именно, были сформулированы задачи о равномерном назначении относительно обязательных назначений (РНМО) и равномерном назначении относительно вектора желательных назначений (РНОВ).

Задача РНМО состоит в нахождении равномерного назначения при условии, что некоторые исполнители обязательно должны выполнять конкретные работы. К этой задаче легко сводится задача МСРН, существует полиномиальный алгоритм сведения, а для ре: шения задачи РНМО существует алгоритм полиномиальной трудоемкости, основанный на сведении к максимальному потоку в двудольном графе.

Задача РНОВ является еще одним «естественным» обобщением задачи о равномерном назначении. Задается вектор, в котором для каждого работника указан объем работ, который он должен был бы выполнить. Требуется построить такое назначение, чтобы каждый работник выполнял объем работ, наиболее приближенный к желательному. Решение этой задачи состоит в сведении ее к задаче РНМО, представлен эффективный алгоритм сведения.

Задача РНМС решена для двух частных случаев — однокомпо-нентного и двукомпонентного планов распределения. Представлены полиномиальные алгоритмы решения задачи РНМС для двух-компонентного и однокомпонентного планов.

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

В диссертационной работе формулируются и исследуются свойства и строятся алгоритмы решения для обобщений задачи о равномерном назначении работ, частным случаем которых являются результаты исследований Рублева B.C.

В главе 2 представлены постановки задач, рассматриваемые в диссертационной работе, введены основные обозначения.

Глава 3 посвящена исследованию задачи о равномерном назначении работ относительно матрицы обязательных назначений (РНМО), поиску свойств решения этой задачи, позволяющих построить эффективный алгоритм ее решения.

Целями Главы 4 ставятся исследование свойств задачи о равномерном назначении работ относительно вектора желательных назначений (РНОВ), доказательство эквивалентности задач РНМО и РНОВ, а также нахождение эффективных алгоритмов взаимного сведения этих задач.

Глава 5 посвящена исследованию задачи о равномерном назначении минимальной стоимости (РНМС). Ставится целью нахождение и обоснование алгоритма сведения задачи РНМС к РНМО.

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

В Главе 7 основной целью является исследование задачи о минимальной стоимости равномерного назначения работ (МСРН) и построение эффективных алгоритмов решения ее частных случаев.

8.

Заключение

.

В данной работе исследованы следующие задачи: задача о равномерном назначении с учетом некоторых обязательных назначений для некоторых работников (РНМО), поиск назначения наиболее близкого к заданному желательному количеству назначений для каждого работника (РНОВ), поиск равномерного назначения среди назначений минимальной стоимости (РНМС), поиск назначения минимальной стоимости среди равномерных назначений (МСРН). Были получены алгоритмы решения задач РНМО, РНМС. Удалось доказать и построить эффективный алгоритм сведения задачи РНОВ к задачи РНМО. Введен план назначений и доказана его инвариантность для задачи равномерного назначения. В работе представлены алгоритмы решения задачи МСРН для однокомпо-нентного и двухкомпонентного планов назначения. Исследованы свойства общего решения задачи МСРН, представлены правила ее декомпозиции на задачи МСРН с однои двухкомпонентыми планами назначения. Таким образом цели поставленные перед данным исследованием достигнуты.