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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Кропанов, Владимир Александрович

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

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

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

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.