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

Кропанов, Владимир Александрович

Равномерность и минимальность стоимости в задаче о назначениях тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Кропанов, Владимир Александрович АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Ярославль МЕСТО ЗАЩИТЫ

2003 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

Диссертация по математике на тему «Равномерность и минимальность стоимости в задаче о назначениях»

Автореферат диссертации на тему "Равномерность и минимальность стоимости в задаче о назначениях"

На правах рукописи

КРОПАНОВ ВЛАДИМИР АЛЕКСАНДРОВИЧ

РАВНОМЕРНОСТЬ И МИНИМАЛЬНОСТЬ СТОИМОСТИ В ЗАДАЧЕ О НАЗНАЧЕНИЯХ

СПЕЦИАЛЬНОСТЬ 01.01.09 - ДИСКРЕТНАЯ МАТЕМАТИКА И МАТЕМАТИЧЕСКАЯ КИБЕРНЕТИКА

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Ярославль-2003

Работа выполнена в Ярославском государственном университете им. П.Г.Демидова

Научный руководитель

кандидат физико-математических наук, доцент Рублев Вадим Сергеевич

Официальные оппоненты:

доктор физико-математических наук, профессор Бондаренко Владимир Александрович,

кандидат физико-математических наук, доцент Корнилов Петр Анатольевич

Ведущая организация

Институт программных систем РАН

Защита состоится " ОМ " илОЛ&,_2003 года в_час._мин.

на заседании диссертационного совета КР 212.002.18 при Ярославском государственном университете им. П.Г.Демидова по адресу: 150000 г. Ярославль, ул. Советская, д. 14.

С диссертацией можно ознакомиться в библиотеке Ярославского государственного университета им. П.Г.Демидова по адресу г. Ярославль, ул. Полушкина роща, д.1.

Автореферат разослан " 01 " илОИ-Х_2003 года.

Ученый секретарь

диссертационного совета Яблокова С.И.

Q.OO?-A

Общая характеристика работы

Актуальность проблемы.

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

Ь\, Ь2, ■.. ,Ьп,

каждый из которых должен быть занят в некоторый из дней

, й'2,. ■ ■, <1п.

Стоимость занятости в день исполнителя Ьг равна сНужно распределить исполнителей по дням, то есть назначить по одному работнику на каждый день так, чтобы, во-первых, были заняты все дни и, во-вторых, минимизировать затраты. Данная задача широко исследована в работах таких известных математиков как Х.Кун1, Н.Кристофидес 2, Э. Эгервари 3 и многих других. Были получены эффективные алгоритмы решения классической задачи о назначениях (в частности Венгерский метод решения1), а также сформулированы и исследованы свойства различных её обобщений.

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

1 Kuhn H.W. The Hungary method for the assignment problem, nav. Res. Log. Quart., 1955, (стр. 83).

2Кристофидес H. Теория графов. Алгоритмический подход. - М. Мир, 1978. (стр. 404) (стр. 406)

3Egervary Е. On combinatorial properties of matrices, translated by H.W.Kuhn, Dept. math, Prinception Univercity, 1953.

"pOC. НАЦИОНАЛЬИАЯ

библиотека

С. Петербургу „ „ ОЭ

■ни/

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

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

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

Задача РНОВ является еще одним "естественным" обобщением задачи о равномерном назначении. Задается вектор, в котором для каждого

4 Рублев B.C. Задача о равномерном распределении работ. Ярославский госуниверситет. 1986. Деп ВИНИТИ С611-в87 26.01.87.

5Рублев B.C. Обобщения задачи о равномерном распределении работ. Сб.: Тезисы докладов юбилейной научной конференции ЯрГУ. Ярославль. 1995. С. 110-112

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

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

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

Цели работы.

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

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

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

Глава 5 посвящена исследованию задачи о равномерном назначении

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

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

Методы исследования.

В диссертационной работе были использованы идеи характеристиче-кого свойства задачи о равномерном назначении Рублева B.C.

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

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

Научная новизна работы.

1. Исследована задача РНМО, построен эффективный алгоритм решения этой задачи на основе декомпозиции исходной задачи на последовательность задач о наибольшем потоке и решении последней с помощью алгоритма Форда-Фолкерсона. Сформулировано характеристическое свойство задачи РНМО, обосновывающее этот алгоритм. Сформулирована вспомогательная ^/-задачи, частым случаем которой является I-задача, сформулированная Рублевым B.C.5

2. Сформулирована и доказана теорема о взаимной эквивалентности задачи РНМО и задачи РНОВ и предложены правила взаимного сведения этих задач.

3. Установлена теорема, обосновывающая сведение задачи РНМС к задаче РНМО и позволяющая построить эффективный алгоритм такого сведения.

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

5Рублев B.C. Задача о равномерном распределении работ. Ярославский госуниверситет, 1986. Деп ВИНИТИ G6U-B87 26.01.87.

5. Исследованы задачи МСРН для однокомпонентного и двухкомпо-нентного планов назначения. Найдены и доказаны их свойства, позволяющие строить эффективные алгоритмы решения сведение этих задач к задаче о потоке минимальной стоимости в двудольном графе.

Практическая ценность работы.

1. Доказанные в диссертационной работе свойства и построенный на основании их алгоритм позволяет получить оптимальное решение задачи РНМО.

2. Для задач РНОВ и РНМС приведены правила их сведения к задаче РНМО, что позволяет построить эффективные алгоритмы решения этих задач.

3. Сформулированное и доказанное свойство плана равномерного назначения работ позволяет использовать его как инвариант для исследования свойств задачи о равномерном назначении и ее обобщений.

4. Сформулированы и доказаны свойства решения задачи о МСРН для однокомпонентного и двухкомпонентного планов, позволяющие свести ее к задаче о потоке минимальной стоимости минимальной стоимости.

Апробация работы:

Основные результаты работы докладывались и обсуждались на научных

конференциях:

1. "Дискретная математика и ее приложения. VI Международный семинар" (Москва, 1998 год);

2. "Проблемы теоретической кибернетики. XII Международная конференция" (Нижний Новгород, 1999 год).

Публикации и вклад автора.

Материалы диссертации опубликованы в 5 печатных работах: 4 статьи

и 1 тезис доклада.

Структура и объем диссертации.

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

Краткое содержание работы.

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

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

В течение определенного периода т дней п работников должны выполнить некоторый объем работ, задаваемый вектором:

где Sj - число работ на каждый день.

Возможности каждого работника в каждый день этого периода задаются матрицей Я размерности п х т, элементы которой

_ Г 1, если 1-ый работник может работать в у-ый день, %3 \ 0, если г-ый работник не может работать в ]-ый день.

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

Т1

- ^ С?еТ~т).

¿=1

Задана матрица стоимостей С размерности пхт, элемент с^ которой характеризует стоимость выполнения работы г-ым работником в у-ый день (сг} > 0^.

Рассматривается задача построения матрицы X назначений работников по дням, элемент которой

_ ( 1, если г-ый работник назначен работать в у-ый день, гз \ 0, если 1-ый работник не назначен работать в у-ый день.

При этом матрица X должна удовлетворять следующим условиям:

Xij = 1 => rt] = 1 (¿6 T~n; j G T~m.), n

O'eTTm).

1=1

Такую матрицу X будем называть матрицей назначений.

То есть необходимо составить назначение, в котором весь требуемый объем работ был бы выполнен и каждый работник назначен только в те дни, когда он может выполнить работу. Вводятся функционал стоимости -ф:

п т

Ф{Х) = ^^CijXij, »=1 j=1

и функционал среднеквадратичного числа работ (функционал равномерности) /:

f(X) = - ¿(tft(X) - К)2, п 1=1

где

кг(Х) = ]Гхг; (¿ем), j=i

¿=1

Матрица назначений называется матрицей назначений минимальной стоимости, если она минимизирует функционал -ф.

Матрица назначений называется матрицей равномерного назначения или равномерным назначением, если она минимизирует функционал /.

В данной диссертационной работе будут исследованы следующие обобщения задачи о равномерном назначении: »

1. Назовем задачей о равномерном назначении работ относительно матрицы обязательных назначений (РНМО) следующую задачу. Заданы вектор 5 числа работ на каждый день, матрица R возмож-

ностей каждого работника на каждый день, удовлетворяющие условиям корректности, и матрица А = {«(¿¿} обязательных назначений,

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

ау = 1 => гц = 1 (г 6 1,п; .7 € 1 ,т) п

1=1

Требуется построить матрицу назначений X такую, что

а^ = 1 =>• хг} = 1 (г € 1,п;] £ 1,ш), и минимизирующую функционал равномерности /.

2. Назовем задачей о равномерном назначении работ относительно вектора распределения (РНОВ) следующую задачу. Заданы вектор 5 числа работ на каждый день, матрица Я возможностей каждого работника на каждый день, удовлетворяющие условиям корректности и вектор распределения Н = (Нг, Ъ,г, ■ ■ -, Ьп) (Нг €/?,»£ 1 ,п). Требуется построить матрицу назначений X, минимизирующую функционал

П *—'

г=1

где

Кг{Х) = ^хч (геТТп).

3-1

3. Назовем задачей о минимальной стоимости равномерного назначения работ (МСРН) следующую задачу. Заданы вектор 5 числа работ на каждый день, матрица Я возможностей каждого работника на каждый день, удовлетворяющие условиям корректности и матрица стоимостей выполнения работ С. Требуется построить матрицу равномерного назначения работ X, минимизирующую функционал стоимости ф.

4. Назовем задачей о равномерном назначении минимальной стоимости работ (РНМС) следующую задачу. Заданы вектор 5 числа работ на каждый день, матрица Я возможностей каждого работника на каждый день, удовлетворяющие условиям корректности, и матрица стоимостей выполнения работ С. Требуется построить матрицу назначений минимальной стоимости работ X, минимизирующую функционал равномерности назначения /.

Вторая глава посвящена исследованию задачи о равномерном назначении работ относительно матрицы обязательных назначений (РН-МО). Для ее решения вводится вспомогательная задача о максимальных назначениях при ограничении на число работ каждого работника или AI-задача. Заданы вектор S числа работ на каждый день, матрица R возможностей каждого работника на каждый день, удовлетворяющие условиям корректности, и матрица А обязательных назначений, удовлетворяющую условиям:

atJ = 1 п} = 1 (г 6 1 ,n;j € 1 ,m), «

Ylaij ^ sJ 61-™)-t=i

Требуется построить матрицу назначений X, удовлетворяющую следующим ограничениям:

a,ij = 1 => xl} = 1 (< £ l,n;j 6 1 ,m),

X] хгз < Я3 (i е l~m),

1=1

771 m

у^ Xij < тах{У^ atj, /} (i € Мг, / = 1,2,...), j=i j=l

и максимизирующую число выполненных работ:

n m

v(^)=max • i=l j=l

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

Для формулировки характеристического свойства решений задачи РН-МО вводится понятие AI—срезки матрицы X.

AI— срезкой матрицы X назовем любую матрицу, полученную следующим образом:

а) она содержит все единичные (равные 1) элементы матрицы Л;

б) в каждой i-ой строке матрицы X, содержащей более чем

771

з=1

элементов равных 1, оставлены равными 1 ровно

max{^ajj,/} j=1

любых элементов, а остальные обнулены;

в) все остальные строки матрицы А" оставлены без изменения.

Для сформулированных таким образом Л/-задачи и Л ¿—срезки устанавливается характеристическое свойство задачи РНМО.

Теорема 2.1. Матрица назначений X является решением задачи РНМО тогда и только тогда, когда любая ее А/-срезка является решением •AJ-задачи.

Из доказанной теоремы вытекает следующий алгоритм решения задачи РНМО.

1°. Полагаем I = 1 и X = А.

2°. Решаем Л/-задачу (алгоритм Форда-Фалкерсона), полагая в качестве начального потока матрицу X, полученную на предыдущем шаге, и получая в качестве решения новую матрицу назначений X, удовлетворяющую условиям А/-задачи.

771

3°. Если <р(Х) = ^Г^ я у, то задача решена — конец алгоритма, иначе j=i

выполняем шаг 4°. 4°. Увеличиваем I на 1 и переходим к шагу 2°.

Заметим, что при А = 0. мы получаем характеристическое свойство задачи о равномерном назначении работ, сформулированное и доказанное Рублевым B.C.6.

еРублев B.C. Задача о равномерном распределении работ. Ярославский госуниверситет, 1986. Деп ВИНИТИ G611-B87 26.01.87.

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

Теорема 3.1. Пусть задача РНМО определена заданием вектора числа работ S, матрицей возможностей R и матрицей обязательных назначений А, а задача РНОВ определяется заданием вектора числа работ S+, матрицей возможностей R+ и вектором желательных назначений Н для таких же значений параметров пит. Пусть ограничения обеих задач связаны следующими условиями:

1). R+ =R-А,

2). = aj - ЕГ=1 «»у U 6

3). hi = const - Кг{А) (г £ 17п).

Тогда справедливы следующие утверждения:

1). Если Х+ - решение задачи РНОВ, то X = Х+ + А - решение задачи РНОМ, причем

const = max Кг(А). »€l,n

2). Если X - решение задачи РНМО, то — X — А - решение задачи РНОВ, причем

const = max ht.

»61,71

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

_ Г 1, ctJ < dj и r^ = 1, lJ ~ \ 0, с1} > dj и гг) - 1,

где dj - Sj-ый минимум в j-м столбце матрицы С (в упорядоченном по возрастанию значений j-ro столбца на s^-m месте стоит dj).

Теорема 4-1- Пусть вектор 5, матрицы Ли С определяют задачу РНМС и матрица А строится по приведенному выше правилу. Тогда вектор 5 и матрицы Я и А определяют задачу РНМО, любое решение X которой является решением исходной задачи РНМС.

Теорема 4.1 обосновывает, а правило получения матрицы А представляет собой сведение задачи РНМС к задаче РНМО.

В пятой главе вводится понятие плана назначения и исследуются его свойства . План назначений включает в себя данные о том, сколько работников должны выполнять конкретный объем работ. Имеется в виду - сколько человек должны работать один день, сколько - два дня и так далее. Такое представление позволяет рассматривать некоторые частные случаи решения обобщений задачи о назначении. В этой главе сформулировано и доказано свойство, связывающее функционал равномерного назначения / и план равномерного назначения.

Определение 16. Назовем планом назначения работ Р{Х), построенном на основе матрицы назначения X, следующую последовательность пар:

Следующая теорема 5.1. является основополагающей для использования плана назначения. Она позволяет применять план назначения для решения задач наравне с функционалом равномерности /(X).

Теорема 5.1. Если существуют X, У - различные матрицы равномерного назначения, то Р(X) = Р(У).

Теорема 5.1 показывает, что план назначения является инвариантом для задачи о равномерном назначении работ, поскольку не зависит от выбора матрицы равномерного назначения.

Шестая глава посвящена исследованию задачи о минимальной стоимости равномерного назначения работ (МСРН). Рассматриваются отдельно частные случаи этой задачи: для о^нокомпонентного плана равномерного назначения, двухкомпонентного плана равномерного назначения и плана равномерного назначения особого вида.

План равномерного назначения вида Р = {(01,61)} назовем одноком-понентным. Для такой задачи МСРН в диссертационной работе представлено правило сведения к задаче о потоке минимальной стоимости.

Р(Х) = {(аг А): V* € 1,1 \{К<{Х) = Ьиг 6 1,п}| = а,

е=1

Далее в этой главе исследуется задача МСРН для двухкомпонентпного плана равномерного назначения, то есть плана вида

Р(Х) = {(а,Ь),(п-а,Ь + 1)}.

Для ее решения вводится понятие цепи матрицы назначений X - последовательность вида

Т Л ' ^ЧЛ ) х12]2 > -^гзН > • ■ • ) 7/ — э > 1

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

хиз, = 1 (* € 1,1 - 1),

= 0, =1 (£ € 2,/).

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

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

Теорема 6.2. Если существуют X и У - произвольные равномерные назначения и равномерный план назначения удовлетворяет свойству

Ь, - 64_! >1 \Zte2J,

то

К4(Х) = щу) V» ем.

В этом случае задача МСРН вновь может быть сведена к задаче о потоке минимальной стоимости, что и демонстрируется в диссертационной работе.

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

Список публикаций по теме диссертации.

1) Кропанов В.А., Рублев B.C. Обобщение задачи о равномерном расписании работ. //Сб.: Проблемы теоретической кибернетики. Тезисы докладов XII Международной конференции. Москва. 1999. Ч. I. С. 121.

2) Кропанов В.А. Задача о равномерном распределении работ относительно матрицы обязательных назначений. // Сб.: Современные проблемы математики и информатики. Ярославль. 1999. В.2. С. 123128.

3) Кропанов В.А., Рублев B.C. Задача о равномерном назначении работ и ее обобщения. // Моделирование и анализ информационных систем. Ярославль. 2000. Т. 7. 2. С. 3-12.

4) Кропанов В.А. Задача о минимальной стоимости равномерного назначения работ для двухкомпонентного плана. // Моделирование и анализ информационных систем. Ярославль. 2000. Т. 7. 2. С. 13-19.

5) Кропанов В.А., Рублев B.C. Равномерное назначение работ минимальной стоимости. //Дискретная математика.Москва. 2001. Т.13. В.4. С. 144-156.

Печ. л. 1.Формат 60x84 1/16. Заказ 1102. Тираж 100. Офсетная печать. Лицензия ПД 00661. Подписано в печать 2.06.2003 г. Типография Ярославского государственного технического университета, т. 30-56-63. 150028, г. Ярославль, ул. Советская, 14 а

I i

f t

""loÇST

» iíis^ (

i «

i i

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Кропанов, Владимир Александрович

1. Введение

2. Задача о равномерном назначении. Формулировка и обобщения.

3. Задача о равномерном назначении работ относительно матрицы обязательных назначений

3.1. Постановка задачи.

3.2. Постановка А1-задачи.

3.3. Характеристическое свойство решения задачи РНМО.

4. Задача о равномерном назначении работ относительно вектора желательных назначений.

4.1. Постановка задачи.

4.2. Эквивалентность задач РНОВ и РНМО.

4.3. Взаимное сведение и обобщение задач РНМО и РНОВ.

5. Задача о равномерном назначении минимальной стоимости.

6. План равномерного назначения работ.

6.1. Определение и основные свойства плана назначений.

6.2. Основное свойство плана равномерного назначения работ.

7. Задача о минимальной стоимости равномерного назначения работ

7.1. Решение задачи МСРН для однокомпонентного плана.

7.2. Решение задачи МСРН для двухкомпонентного плана.

7.3. Свойства решения задачи МСРН.

Введение диссертация по математике, на тему "Равномерность и минимальность стоимости в задаче о назначениях"

Диссертационная работа посвящена изучению некоторых обобщений задачи о назначениях - одной из классических задач дис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]). Было доказано, что критерий минимизации среднеквадратичного отклонения от средней занятости является более сильным по сравнению с другими критериями равномерности. Им же были сформулированы обобщения задачи о равномерном назначении, исследованию которых посвящена диссертационная работа.

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

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

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

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

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

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

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

Заключение диссертации по теме "Дискретная математика и математическая кибернетика"

8. Заключение.

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

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Кропанов, Владимир Александрович, Ярославль

1. Бондаренко В.Н. Технологические средства групповой технологии ГПС. Учебное пособие. - бел. ГТАСИ, 2000.

2. Васильев И.Л. Поиск глобального решения в задачах выпуклой максимизации: Дис. канд. физ.-мат. наук. М. Иркутский государственный университет. - 1998.

3. Воскресенский Е.А., Добровольский Н.М., Симонов А.С. Об одном классе задач о назначениях.// Информатика 1995. - Вып. 3. -Т. 1.

4. Деньдобренько Б.Н., Малика А.С. Автоматизация конструирования РЭА М. Высшая школа, 1980.

5. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.Наука., 1990.и

6. Иенсен П., Барнес Д. Потоковое программирование. М. Радио и связь, 1984. (стр. 392).

7. Киселев В.Д., Карелин Д.В. Метод ветвей и границ для решений задач целочисленного квадратичного программирования.// Информатика 1995. - Вып. 3. - Т.1.

8. Козловский В.А., Козловский Э.А., Макаров В.М. Эффективность переналаживаемых роботизированных производств. JI. Машиностроение., 1989.

9. Короткий Ю.Г. Стратегический анализ и проблемы создания сложных технических изделий.//Маркетинг в России и за рубежом. 1999.- 3.

10. Короткий Ю.Г. Системный подход к проектированию сложных технических изделий.//Оборонная техника. 1995. - 2

11. Кристофидес Н. Теория графов. Алгоритмический подход. -М. Мир, 1978.

12. Кузнецова А.А., Стрекаловский А.С., Цэвэнрдорж И. Об одном подходе к решению целочисленных задач оптимизации.// ВМиМФ 1999. - Т.39. - 1.

13. Кумагина Е.А., Прилуцкий М.Х. Задачи распределения разнородных ресурсов в сетевых канонических структурах.// Перспективные информационные технологии и интеллектуальные систему.- 2000. 4.

14. Прилуцкий М.Х. Многокритериальное распределение одного ресурса в иерархических системах.//Автоматика и телемеханика- 1996. 2.

15. Прилуцкий М.Х., Кумагина Е.А. Задача упорядочения работ как задача о назначениях.// Вестник Нижегородского государственного университета. Математическое моделирование и оптимальное управлдение. НН.,1999 - Вып. 21 - С.270-275.

16. Рублев B.C. Задача о равомерном распределении работ. //Ярославский госуниверситет, 1986. Деп ВИНИТИ G611-B87 26.01.87.

17. Селютин В.А. Машинное проектирование электронных устройств М. Советское Радио, 1977.

18. Стрекаловкий А.С., Васильев И.Л. Об одном подходе к решению квадратичной задачи о назначениях: Тез. докл. Конф. Математическое програмирование и приложения. Екатеринбург, 1999.

19. Ямпольский Л.С., Катан О.М., Ткач М.М. Автоматизированные системы технологической подготовки роботехнического производства. - Вища школа.- К. 1978.

20. Abreu N., Netto P., Querido T, Gouvea E., Classes of quadratic assignment problem instances: isomorphism and difficulty measure using a statistical approach. // Discrete applied mathematics. 2002. - 124.- C. 103-116.

21. Angel E., Zissimopoulos V. On the hardness of the quadratic assignment problem with metaheuristics.// Journal of heuristics. 2002 8. - C.399-414.

22. Angel E., Zissimopoulos V. On the quality of local search for the quadratic assignment problem.// Discrete applied mathematics. 1998.- 82.-C. 15-25.

23. Angel E., Zissimopoulos V. On the landscape ruggedness of the quadratic assignment problem.// Theoretical computer science. 1998.- 263(1/2). С.159-172.

24. Egevary Е. On combinatorial properties of matrices, translated by H.W.Kuhn. Dept. math, Prinception Univercity, 1953.

25. Golumbic,M.C. Algorithmic Graph Theory and Perfect Graphs. -Academic., 1980

26. Korvin A., Hashemi S., Quirchmayr G., Kleyle R. Assigning Tasks to Resource Pools: A Fuzzy Set Approach// DEXA. 2000. - C. 102114.

27. Korvin A., Kleyle R., Hashemi S., Quirchmayr G. Assignment of tasks to competing nodes when task duration times are fuzzy. // Journal of Intelligent and Fuzzy Systems. 1999

28. Kuhn H.W. The Hungary method for the assignment problem, nav. Res. Log. Quart., 1955.29. button J.-L., Dritan N., Jacques C. Assigning spare capacities in mesh survivable networks// Telecommunication Systems. 2000. - 13.- C. 441-451.

29. Meisels A., Ovadia E. Assigning Resources to Constrained Activities PATAT, 2000 - C.213 -223.

30. Meisels A., Schaerf A. Modelling and Solving Employee Timetabling Problems. Appl.Intell.submitted, 1999.