автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Разработка моделей и алгоритмов дискретной оптимизации для задач формирования производственных групп

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

АФАНАСЬЕВА Любовь Дмитриевна

РАЗРАБОТКА МОДЕЛЕЙ И АЛГОРИТМОВ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ ДЛЯ ЗАДАЧ ФОРМИРОВАНИЯ ПРОИЗВОДСТВЕННЫХ ГРУПП

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

5 ДЕК 2013

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Омск - 2013

005541485

Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Омский государственный университет им. Ф.М. Достоевского»

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

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

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

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

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

Быкова Валентина Владимировна,

доктор физико-математических наук, доцент, Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Сибирский федеральный университет», профессор базовой кафедры вычислительных и информационных технологий

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

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Уфимский государственный авиационный технический университет»

Защита состоится 17 декабря 2013 года в 16:30 часов на заседании диссертационного совета Д 003.061.02 на базе Федерального государственного бюджетного учреждения науки Института вычислительной математики и математической геофизики Сибирского отделения Российской академии наук (ИВМиМГ СО РАН) по адресу: 630090, г. Новосибирск, проспект Академика Лаврентьева, д. 6, тел. (383)330-71-59.

С диссертацией можно ознакомиться в библиотеке ИВМиМГ СО РАН. Автореферат разослан 15 ноября 2013 г.

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

диссертационного совета Сорокин Сергей Борисович

д.ф.-м.н.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Современный этап развития прикладной математики характеризуется активной разработкой и применением математических моделей и методов в планировании, проектировании, исследовании социально-экономических и технических систем. Весьма актуальными являются проблемы управления персоналом, в частности задачи формирования производственных групп. При создании таких групп необходимо рассматривать множество вопросов, касающихся назначения па должности, качества и своевременности выполнения работ, обеспечения условий труда, ресурсных и иных ограничений [13].

Одним из известных подходов к исследованию и решению задач формирования производственных групп является применение аппарата математического моделирования, в том числе дискретиой оптимизации. В настоящее время можно выделить ряд направлений в указанной области: разработка и использование моделей целочисленного линейного программирования (ЦЛП), построенных па основе задач о назначениях (ЗН) и их обобщений, задач о покрытии, оптимального разбиения и размещения, оптимизация на графах, анализ теоретико-игровых моделей. Указанные постановки и смежные с ними вопросы изучались в работах Берсспсва В.Л., Гимади Э.Х., Дементьева В.Т., Ерзина А.И., Колоколова A.A., Кочстова Ю.А., Новикова Д.А., Попкова В.К., Пяткипа A.B., Родионова A.C., Воронина A.A., Еремеева A.B., Забудского Г.Г., Заозерской Л.А., Лсрнера Э.Ю., Мишина С.П., Burkard R.E., Dell'Amico М., Gale D., Martello S., Pcntico D.W., Shaplcy L.S. и других авторов [8,14].

Отметим, что модели и методы ЦЛП широко используются при решении различных задач дискретной оптимизации [1,2,4,6,7,9-12,15]. Задачи формирования производственных групп требуют дальнейшего исследования как в теоретическом, так и в прикладном отношениях, в частности учета межличностных и иерархических отношений в коллективе, изучения структуры и сложности задач, выделения полиномиально разрешимых случаев и семейств трудных задач, разработки и анализа алгоритмов их решения, различных эвристик.

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

Для достижения поставленной цели решались следующие задачи.

1. Построить и изучить математические модели для задач формирования производственных групп с учетом межличностных и иерархических отношений.

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

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

4. Выполнить экспериментальные исследования рассматриваемых моделей и алгоритмов.

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

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

Практическая ценность. Разработанные алгоритмы для задач формирования производственных групп применимы в научно-исследовательской работе и для решения практических задач. Полученные результаты используются на кафедре прикладной и вычислительной математики Федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Омский государственный университет им. Ф.М. Достоевского» (ФГБОУ ВПО ОмГУ им. Ф.М. Достоевского), в лаборатории дискретной оптимизации Омского филиала Федерального государственного бюджетного учреждение пауки Института математики им. С.Л. Соболева Сибирского отделения Российской академии наук (ФГБУН ОФ ИМ СО РАН) при подготовке специалистов по методам оптимизации и исследованию операций, в Омском филиале ФГБОУ ВПО «Московский государственный университет технологий и управления им. К.Г. Разумовского».

4

Апробация работы. Результаты диссертации докладывались на XXXIV Региональной научно-практической студенческой конференции «Молодежь третьего тысячелетия» (г. Омск, 2010), Шестой, Седьмой и Девятой Международных Азиатских школах-семинарах «Проблемы оптимизации сложных систем» (Республика Казахстан, 2010 и 2013, Республика Узбекистан, 2011), XIV Всероссийской конференции «Математическое программирование и приложения» (г. Екатеринбург, 2011), XII и XIII Международных научно-инновационных конференциях с элементами научной школы «Теоретические знания - в практические дела» (г. Омск, 2011 и 2012), XV Байкальской международной школе-семинаре «Методы оптимизации и их приложения» (г. Иркутск, 2011), Всероссийской научно-практической конференции «Статистика, моделирование, оптимизация» (г. Челябинск, 2011), V Всероссийской конференции «Проблемы оптимизации и экономические приложения» (г. Омск, 2012), VIII Международной научно-тсхиичсской конференции «Динамика систем, механизмов и машин» (г. Омск, 2012), Международной конференции «Информационные технологии интеллектуальной поддержки принятия решений» и Российско-немецком семинаре «Модели и алгоритмы прикладной оптимизации» (г. Уфа, 2013), Международной конференции «Optimization and Applications ОРТ1МА-2013» (Черногория, 2013), па заседании научного семинара лаборатории прикладных систем ФГБУН Института вычислительной математики и математической геофизики СО РАН (г. Новосибирск, 2013), а также па заседаниях научного семинара «Математическое моделирование и дискретная оптимизация» лаборатории дискретной оптимизации ОФ ИМ СО РАН и Института математики и информационных технологий ОмГУ им. Ф.М. Достоевского (г. Омск, 2009-2013).

Публикации. Основные результаты диссертации опубликованы в 16 научных работах [18-31], две из них - в журналах из списка ВАК [16,17].

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

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

5

отношений на основе теоретико-графовых конструкций и ЦЛП [16-19, 2225, 28,29|. В разделе 2.1 рассматривается следующая задача (обозначим ее 0>1). Предположим, что предприятие планирует образовать производственную группу при условии наличия на рынке труда определенного множества претендентов, число которых не меньше количества имеющихся работ. Любому претенденту может быть назначено не более заданного числа работ, причем каждая из них должна выполняться только одним специалистом. Известны расходы па оплату труда каждого претендента. Кроме того, необходимо учесть межличностные отношения в коллективе: специалисты с напряженными отношениями ис допускаются к выполнению работ, предполагающих их взаимодействие. Требуется сформировать производственную группу с учетом указанных выше условий так, чтобы суммарные расходы на ее содержание были минимальными.

Перейдем к формулировке рассматриваемой задачи на графе. Пусть имеется п специалистов и т работ, ш < п. Определим граф С = (V, Е), где V = и Е = Е\ и ¿?2 и Ез такие, что \\ = {1,..., п} - множество вершин, соответствующих специалистам, претендующим на включение в производственную группу; VI = {1,... ,т} - множество вершин, отвечающих имеющимся работам. Дуга (гсодержится в Е\ С {(г,: г € VI,3 (Е ^г}, если претенденту г может быть назначена работа Каждой дуге присвоен вес Су - размер оплаты труда специалиста г при выполнении им работы j. Ребро (¿1, ¿г) принадлежит множеству Е2 С {(¿1,12) : г^г'г 6 VI, ц ф ¿2}, если между претендентами ¿1, ¿2 неблагоприятные для совместной деятельности отношения; ребро (л,¿2) содержится в£3С {(¿1..72) : Зък 6 ф 32}, сели работы связаны в производственном процессе.

Определим множество несогласованных межличностных отношений. Пусть специалист ¿1 претендует на работу а специалист ¿2 - на работу ]2- Межличностное отношение ((¿ь л), (¿2,^2)) называется несогласованным, если работы ,72 требуют взаимодействия специалистов ¿1, ¿2 при их выполнении, а отношения между ними рассматриваются как напряженные. Обозначим через Ш множество всех несогласованных отношений.

Построим модель ЦЛП для задачи Введем булевы переменные: хц = 1, если специалисту г назначена работа ], в противном случае ху = О, г е VI, {{,]) 6 Е\. Модель имеет вид:

при условиях

ХП <<к, ¿е У\

(¿¿)еД1

(2)

яу = 1, з е Ц,

(3)

(ьЛеЕ1

< 1, <(»1,л), (к,32)) е IV, агу € {0,1}, г е VI, (г,е Еъ

(4)

(5)

Отметим, что целевая функция (1), условия (2), (3), (5) соответствуют классической задаче о назначениях, (4) - неравенства, отражающие необходимость обеспечения условия согласованности отношений между претендентами. В (1)-(5) вместо межличностных отношений можно учитывать иерархические отношения в коллективе, т.е. более квалифицированный специалист должен выполнять работу более высокого уровня иерархии.

Поскольку задача о независимом множестве минимального суммарного веса заданной мощности (обозначим ее Мт\¥1Б — FC) достаточно хорошо изучена и для некоторых классов графов является полиномиально разрешимой [3,5], то МтУ/1Б — РС может быть использована для анализа сложности, построения алгоритмов решения задачи выделения полиномиально разрешимых случаев. В работе доказана

Теорема 2.1. Задача полиномиально сводится к Мт\У18 — РС.

Предложенное сведение может быть полезным при решении частных случаев для которых соответствующая задача МгпИ^/5 — FC полиномиально разрешима. Рассмотрим задачу в которой Су = с,;, где с» - величина оплаты труда специалиста г, г € У\, (г, з) € Е\. Для любых г е У\, з Е Уг существует дуга (г,з), принадлежащая Е\. Для произвольных 3\, 32 € Уг Р°б-ро (^1,^2) содержится в Е3. Подграф графа (7, порожденный множеством ребер £2, является деревом. В работе показано, что задача полиномиально разрешима.

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

Построим теоретико-графовую модель данной задачи. Определим граф б с множеством вершин V = {!,...,п} и множеством ребер £С {(г,^) : г, .7 € V, г ф Вершины графа соответствуют претендентам на включение в производственную группу, а ребра - отношениям между ними, т.е. Е = Е\ и где Е\ - множество ребер, отражающих комфортные отношения между специалистами; Е2 - множество ребер, отвечающих напряженным отношениям между ними (см. рис. 1). Пусть з^ - вес ребра (г,з) £ Е1 (степень комфортности отношений для специалистов г и

60, /

|с£::'.......

2<Х

49....................о'!..

%.................

ч «

\ \

----------

! \

ъ<

О ■ претенденты

............... - напряженные отношения

_______ - комфортные отношения

Рис. 1. Пример графа й для задачи ^

Задача оптимизации заключается в отыскании V С V такого, что подграф С графа (7, порожденный подмножеством V', не содержит ребер из Еъ а суммарный вес ребер из Е\ максимален.

Построим модель ЦЛП для задачи Введем булевы переменные: X] = 1, если специалист 3 включен в состав формирующегося коллектива, х^ = 0 - в противном случае, j € V; у^ = 1, если специалисты I и 3 входят в коллектив, иначе у^ = 0, (г,^) € Е\. Модель ЦЛП выглядит следующим образом:

при условиях

(¿¿)е£а

Хг + Х2 < 1, (г,.?) 6 Е2, (7)

Хг + X, - 2Уу > 0, (г, з) е Еи (8)

XI € {0,1}, з € V, (9)

У« €{0,1}, (»,.;) &ЕЪ (10)

Целевая функция (6) означает максимизацию суммарного веса ребер из множества Е\ в подграфе С. Неравенства (7) отвечают требованию отсутствия ребер из Е2 в С. Ограничение (8) обеспечивает выполнение следующего условия: переменная уу может принять значение, равное единице, только если обе вершины г и ], инцидентные одному ребру из Е\, входят в решение. В работе установлена связь задачи (6)—(10) с известной задачей о независимом множестве вершин в графе максимального суммарного веса (обозначим ее МШ1Б) с цслыо применения для £?г результатов, имеющих место для М\У1Б, а именно доказана

Теорема 2.2. Задача ¿Р2 полиномиально сводится к МШ1В.

В диссертации приводятся следствия из теоремы 2.2: например, задачи ¿Р2 на графах простая цепь, дерево полиномиально разрешимы, поскольку отвечающие им МШ1Б являются такими же по сложности.

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

В дайной работе доказано, что задачи ¿З2!, являются ЫР-

трудиыми.

Третья глава посвящена построению и исследованию алгоритмов решения задач формирования производственных групп, описанию научно-исследовательского комплекса программ и вычислительного эксперимента [16,17,20-27,29-31]. Модели ЦЛП и постановки на графах дают возможность применения общих алгоритмов, например, метода ветвей и границ, отсечения, перебора ¿-классов. Но для решения прикладных задач целесообразно разрабатывать и использовать алгоритмы, учитывающие их специфику. При построении алгоритмов нами опробовано три подхода: метод ветвей и границ, процедура отсечения, эвристики.

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

пять к подмножествам, условно называемым узлами дерева поиска. Каждое подмножество в этом разбиении представляется потомком узла-родителя, а исходная задача соответствует корню дерева.

Обозначим через /(х') значение целевой функции для допустимого решения х', гес - наилучшее значение этой функции на текущей итерации алгоритма СА\. В начале процесса полагаем, что гес - достаточно большое число, например, гес = 5, где 5 > ^ ^ Су. Рассмотрим подробнее алго-

ievi {i,j)eE¡

ритм С Ai.

Шаг 0. Находим оптимальное решение х' исходной ЗН (1)-(3), (5). Если все ограничения (4) выполняются для х', то процесс завершается: получено оптимальное решение исходной задачи. Иначе переходим на шаг 1. Шаг 1. Пусть для некоторой пары претендентов ц, ¿2 имеются напряженные отношения и связанные в производственной деятельности работы ji> 32 такие, что хотя бы одно из ограничений {xilj1 +xÍ2j2 < 1 и/или а;,и-2 + Xi2jl < 1) системы (4) не выполнилось. В этом случае задача делится на две подзадачи. В дереве ветвления это соответствует левой ветви (прстеидепт ц не принимается па работы j\, j2, т.е. полагаем х= О, xhh = 0 ) и правой ветви (претендент ¿2 не принимается на работы j\, j2, т.е. Xi2jí = 0, x¡2j2 = 0). Рассмотрим левую ветвь, переходим па шаг 2. Шаг 2. Если текущая ЗН типа (1)—(3), (5) с новыми исходными данными не имеет решения, то переходим па шаг 3. Иначе находим оптимальное решение х' текущей задачи, вычисляем /(х'). Если f(x') > гес, то движение по данной ветви не может привести к улучшению гес, переходим на шаг 3. Если /(х') < гес и все ограничения (4) выполнены для х', то обновляем гес := f{x') и переходим на шаг 3. Если /(х') < гес и хотя бы одно условие (4) не выполнено для х', то - на шаг 1. Шаг 3. Если текущий узел - корень дерева поиска и все узлы правой ветви рассмотрены, то переходим на шаг 4. Если текущий узел - не корень дерева поиска и все узлы правой ветви просмотрены, то переходим к его родительскому узлу на шаг 3. Если текущий узел - не корень дерева и имеются непросмотренные узлы правой ветви, тогда анализируем правую ветвь, описанную па шаге 1. Переходим на шаг 2. Шаг 4. Завершение процесса. Если гес < <5, то решение, соответствующее гес, является оптимальным для задачи (1)-(5). В противном случае задача не имеет допустимого решения.

Отметим ряд свойств предложенного алгоритма. Пусть h = |W|/2 и p(\V\) - трудоемкость некоторого алгоритма решения ЗН. Например, в каче-

стве такого алгоритма можно взять венгерский метод [14], вычислительная сложность которого равна 0(п3). В данной главе доказана

Теорема 3.1. Алгоритм С Ai за конечное число итераций либо находит оптимальное решение задачи либо доказывает, что она не имеет допустимых решений, его трудоемкость равна 0(р{\V\)2h).

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

В этом разделе также описан комбинаторный алгоритм CA2 решения задачи &2. Его отличие от СА\ состоит в том, что здесь не рассматриваются ЗН, а решение исходной задачи сводится к решению последовательности задач выбора специалистов с максимальной степенью комфортности отношений в коллективе. Пусть h = \Щ и р{\Е\) - трудоемкость некоторого алгоритма выбора специалистов с максимальной степенью комфортности отношений в коллективе. В разделе 3.1 доказано, что алгоритм СЛ2 за конечное число итераций находит оптимальное решение задачи его трудоемкость равна 0(p{\E\)2h). Нами показано, что верхние оценки трудоемкости алгоритмов СА\, СА2 достигаются.

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

В разделе 3.2 представлено описание разработанного в диссертации научно-исследовательского комплекса программ GroupForm, перечислены его основные функциональные возможности, указаны используемые форматы файлов данных. Приложение GroupForm разработано в среде Microsoft Visual Studio 2010, интерфейс реализован на языке С#, алгоритмы - на языке С++. Данное приложение позволяет генерировать и решать задачи ^i, с помощью описанных выше алгоритмов, их модификаций и пакета CPLEX, иллюстрировать решения на графе.

На базе созданного комплекса GroupForm проведены экспериментальные исследования с целыо анализа эффективности предложенных алгоритмов и их сравнения с пакетом CPLEX. В качестве тестовых использовались серии примеров со случайными исходными данными и прикладные задачи.

Расчеты выполнялись на компьютере с процессором Iritel(R) Core(TM)2 Duo CPU Т6600 @2.20GHz. Всего было решено 75 серий тестовых задач для каждая из которых содержала по 50 задач. Число специалистов и работ варьировалось от 25 до 1000, количество напряженных межличностных отношений и пар связанных работ изменялось от 10 до 2000. В тестовых задачах для число претендентов равнялось 50 и 100, количество комфортных отношений варьировалось от 25 до 1000, а напряженных - от 25 до 100.

В результате проведенных вычислительных экспериментов было установлено, что время решения большинства тестовых задач для 2?2 составляло не более 30 мин. При этом СА\ находил оптимальные решения для &>\ быстрее пакета CPLEX в случае, если число несогласованных межличностных отношений не превышало 10% от максимального возможного их количества и разрыв оптимальных значений целевых функций и ЗН являлся небольшим. В целом при постепенном росте числа используемых отсечений (4) процедура CUT\ оказалась достаточно эффективной. Процедура с применением сортировок решала задачи в отдельных случаях заметно быстрее пакета CPLEX. Эксперимент показал, что при использовании эвристик время вычислений алгоритма СА2 уменьшалось.

Кроме того, математическая модель для задачи ¿¡?2 была апробирована для формирования производственной группы на одном предприятии г.Омска. В разделе 3.3 приведена информация о проектировании учебных групп в условиях высокой гетерогенности контингента студентов. С этой целью задача была адаптирована к формированию таких групп Омского филиала Московского государственного университета технологий и управления им. К.Г. Разумовского.

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

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

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

2. Построена и изучена модель целочисленного линейного программирования для задачи распределения специалистов по производственным сме-

12

нам, которая использована при проектировании учебных групп, проведены расчеты с помощью пакета CPLEX 12.1.

3. Установлена полиномиальная сводимость рассматриваемых задач проектирования производственных групп к известным NP-трудным задачам оптимизации на графах. Выделены полиномиально разрешимые частные случаи.

4. Разработаны и исследованы точные алгоритмы комбинаторного типа, процедуры отсечения и эвристики для решения задач формирования производственных групп.

5. Создан научно-исследовательский комплекс программ, включающий реализацию разработанных в диссертации алгоритмов. Проведены экспериментальные исследования их эффективности, в том числе сравнение с программным пакетом CPLEX, на прикладных задачах и задачах со случайными исходными данными.

В приложении содержатся исходные данные ряда прикладных задач и результаты их решения с помощью указанного пакета.

Автор благодарит научного руководителя Колоколова A.A. за внимание и поддержку при выполнении дайной работы.

Список литературы

[1] Берсснев В.Л., Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации. - Новосибирск: Наука, 1978. - 333 с.

[2] Быкова В.В. Теоретические основы анализа параметризироваиных алгоритмов: монография. - Красноярск: СФУ, 2011. - 180 с.

[3] Гэри М., Джонсон Д. Вычислительные машины и трудпорсшасмыс задачи. - М.:Мир, 1982. - 416 с.

[4] Евтушенко Ю.Г., Посыпкин М.А. Варианты метода неравномерных покрытий для глобальной оптимизации частично-цслочислснных нелинейных задач // Доклады Академии наук. - Т. 437, № 2. - С. 168-172.

[5] Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация. - М.: Наука, 1981. - 344 с.

[6] Колоколов A.A. Регулярные разбиения и отсечения в целочисленном программировании // Сибирский журнал исследования операций. -1994. - № 2. - С. 18-39.

[7] Мухачсва Э.А., Валсева А.Ф., Мухачсва А.С. Методы локального поиска в дискретных задачах оптимального распределения ресурса. - Уфа: Изд-во УГАТУ, 2001.- 103 с.

[8] Новиков Д.А. Математические модели формирования и функционирования команд. - М.: Физматлит, 2008. - 186 с.

[9] Попков В.К. Математические модели связности. - Новосибирск: Изд. ИВМиМГ СО РАН., 2006. - 490 с.

[10] Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы. - М.: Физматлит, 2007. - 304 с.

[11] Схрейвер А. Теория линейного и целочисленного программирования: в 2 т. - М.:Мир, 1991. - 702 с.

[12] Шевченко В.Н. Качественные вопросы целочисленного программирования. - М.: Физматлит, 1995. - 190 с.

[13] Юсупова Н. И., Олейник Я.А. Ситуационные модели и антикризисное управление предприятием. - УНЦ РАН, 2009. - 53 с.

[14] Burkard R.E., Dell'Amico M., Martello S. Assignment problems. -Philadelphia: SIAM, 2009. - 382 p.

[15] Nemhauser G.L., Wolsey L.A. Integer and combinatorial optimization. A Wiley-Interscience Publication: John Wiley and Sons, inc. - 1999. - 784 p.

Опубликованные работы автора по теме диссертации

В рецензируемых журналах из списка ВАК

[16[ Афанасьева JI.Д., Колоколов А.А. Разработка и анализ алгоритма решения некоторых задач формирования производственных групп // Омский научный вестник. - 2012. - № 2(110). - С. 39-41.

[17] Kolokolov A.A., Afanasycva L.D. Research of Production Groups Formation Problem Subject to Logical Restrictions // Journal of Siberian Federal University, Mathematics к Physics. - 2013. - № 6(2). - P. 145-149.

В других изданиях

[18] Бушинский С.Д., Шулепова Л.Д. (Афанасьева Л.Д.) О решении некоторых задач формирования малых производственных групп // Труды XXXIV региональной научно-практической студенческой конференции «Молодежь III тысячелетия». - Омск: Изд-во ОмГУ, 2010. - С. 15-17.

[19] Колоколов A.A., Бушинский С.Д., Шулепова Л.Д. (Афанасьева Л.Д.) Формирование производственных групп с использованием дискретной оптимизации // Материалы Шестой азиатской международной школы-семинара «Проблемы оптимизации сложных систем». - 2010. -С. 220-224.

[20] Колоколов A.A., Шулепова Л.Д. (Афанасьева Л.Д.) Об одном алгоритме решения задач формирования малых групп // XIV Всероссийская конференция «Математическое программирование и приложения»: Информационный бюллетень № 12. - Екатеринбург, 2011. - С. 188.

[21] Бушинский С.Д., Шулепова Л.Д. (Афанасьева Л.Д.) Применение моделей и методов дискретной оптимизации для проектирования малых производственных групп // Сборник научных статей XII Международной паучно-шшовационной конференции с элементами научной школы «Теоретические знания - в практические дела». - Омск, 2011. - Ч. 2. -С. 118-119.

[22] Колоколов A.A., Серышева Ю.С., Шулепова Л.Д. (Афанасьева Л.Д.) Решение задач формирования малых групп с учетом межличностных отношений // Труды XV Байкальской международной школы-семинара «Методы оптимизации и их приложения». - Иркутск, 2011. - Т. 5. -С. С1-66.

[23] Колоколов A.A., Афанасьева Л.Д., Заборская С.А., Калинина О.Г. Формирование учебных групп в условиях гетерогенности с использованием дискретной оптимизации // Сборник трудов Всероссийской конференции «Статистика. Моделирование. Оптимизация». - Челябинск, 2011. - С. 203-205.

[24] Афанасьева Л.Д., Заборская С.А. Решение некоторых задач формирования учебных групп // Труды XIII Международной научно-инновационной конференции аспирантов, студентов и молодых исследователей с элементами научной школы «Теоретические знания - в практические дела». - Омск, 2012. - Ч. 2. - С. 175-177.

15

[25] Афанасьева Л.Д. Исследование и решение одной задачи формирования малых групп с учетом условия комфортности отношений // Труды V Всероссийской конференции «Проблемы оптимизации и экономические приложения». - Омск: Изд-во Ом. гос. ун-та, 2012. - С. 103.

[26] Колоколов A.A., Артемова A.B., Афанасьева Л.Д. Решение некоторых задач управления персоналом с использованием методов оптимизации // Материалы VIII Международной паучио-техничсской конференции «Динамика систем, механизмов и машин». - Омск: Изд-во ОмГТУ,

2012. - Т. 3. - С. 55-58.

[27] Афанасьева Л.Д. Разработка и экспериментальное исследование алгоритмов решения задач формирования производственных групп. Препринт. - Омск: Ом ГУ, 2013. - 23 с.

[28] Афанасьева Л.Д. О некоторых полиномиально разрешимых случаях задачи формирования производственных групп // Материалы Всероссийской молодежной школы-семииара «Дискретные модели и методы принятия решений». - Новосибирск: Изд-во Ин-та математики, 2013. -С. 207-208.

[29] Колоколов A.A., Афанасьева Л.Д. Анализ и решение некоторых задач формирования производственных групп // Материалы Международной конференции «Информационные технологии интеллектуальной поддержки принятия решений» и Российско-немецкого семинара «Модели и алгоритмы прикладной оптимизации». - Уфа: Изд-во УГАТУ,

2013. - С. 190-192.

[30] Афанасьева Л.Д., Колоколов A.A. Разработка и анализ алгоритмов решения одной задачи управления персоналом // Материалы Девятой азиатской международной школы-семинара «Проблемы оптимизации сложных систем». - Алматы: Изд-во Ин-та проблем информатики и управления, 2013. - С. 61-65.

[31] Kolokolov A.A., Afanasycva L.D. Оп solving some production groups formation problems based on discrete optimization // Abstracts of IV International conference «Optimization and applications» (OPTIMA-2013). - М.:ВЦ PAH, 2013. - P. 98.

Подписано в печать 15.11.2013 Формат 60x84/16. Бумага писчая. Оперативный способ печати. Усл. печ. л. 1,25. Тираж 130 экз. Заказ № 648

Отпечатано в «Полиграфическом центре КАК» тел. (3812) 24-70-79, 8-904-585-98-84.

E-mail: pc_kan@mail.ru 644050, г. Омск, ул. Красный Путь, 30 Лицензия ПЛД № 58-47 от 21.04.97

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Омский государственный университет им. Ф.М. Достоевского»

04201452582

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

АФАНАСЬЕВА Любовь Дмитриевна

РАЗРАБОТКА МОДЕЛЕЙ И АЛГОРИТМОВ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ ДЛЯ ЗАДАЧ ФОРМИРОВАНИЯ ПРОИЗВОДСТВЕННЫХ ГРУПП

05.13.18 - Математическое моделирование, численные методы и комплексы

программ

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель д.ф.-м.н., профессор Колоколов А.А.

Омск - 2013

Оглавление

Введение ..................................................................4

Глава 1. Математические модели оптимизации для задач планирования и управления персоналом ..........................11

1.1. Задачи оптимального назначения..................................11

1.2. Применение задач о покрытии, разбиения и размещения ... 15

1.3. Оптимизация на графах............................................20

1.4. Об устойчивом паросочетании ....................................22

1.5. О методах решения задач..........................................23

Глава 2. Исследование задач формирования производственных

групп на основе дискретной оптимизации....................28

2.1. Проектирование групп с учетом межличностных и иерархических отношений..................................................29

2.2. Образование групп с максимизацией степени комфортности отношений............................................................38

2.3. Распределение специалистов по производственным сменам . . 50

Глава 3. Разработка и реализация алгоритмов..................53

3.1. Построение и исследование алгоритмов..........................53

3.2. Описание комплекса программ....................................66

3.3. Результаты вычислительного эксперимента......................71

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

Список литературы......................................................85

Приложение............................... 98

Введение

Актуальность темы. Современный этап развития прикладной математики характеризуется активной разработкой и применением математических моделей и методов в планировании, проектировании, исследовании социально-экономических и технических систем [31, 75, 81]. Весьма актуальными являются проблемы управления персоналом, в частности задачи формирования производственных групп, что обусловлено появлением новых компаний, развитием торговых сетей, повышением требований к специалистам и рядом других факторов. При создании производственных групп приходится рассматривать множество вопросов, касающихся назначения на должности, качества и своевременности выполнения работ, обеспечения условий труда и т.д. Требуется также учитывать межличностные, иерархические отношения в коллективе, ресурсные и иные ограничения [3,82].

Одним из известных подходов к исследованию и решению задач формирования производственных групп является применение аппарата математического моделирования, в том числе дискретной оптимизации [17, 62,71,72]. В настоящее время можно выделить ряд направлений в указанной области:

- разработка и использование моделей целочисленного линейного программирования (ЦЛП), построенных на основе известных задач о назначениях (ЗН) и их обобщений;

- применение задач о покрытии, оптимального разбиения и размещения;

- оптимизация на графах;

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

Указанные постановки и смежные с ними вопросы изучались в работах Береснева B.JL, Гимади Э.Х., Дементьева В.Т., Ерзина А.И., Колоколова A.A., Кочетова Ю.А., Новикова Д.А., Попкова В.К., Пяткина A.B., Родионова A.C., Еремеева A.B., Забудского Г.Г., Заозерской JI.A., Burkard R.E., Dell'Amico М., Gale D., Martello S., Pentico D.W., Shapley L.S. и других авторов [5,6,8,9,15,16,20,21,25,26,42-45,52,53,56,59,61,63,65,66,68,79,80,87,88,95,103,104,111,115].

Отметим, что модели и методы ЦЛП широко используются при решении различных классов задач дискретной оптимизации, в частности задач о покрытии, об упаковке [38, 47, 51], выполнимости логической формулы [2, 41], проектирования с логическими ограничениями [54] и других [14,24,27,33,39,40,46,57,60,74,76-78,87,97,98,109,114].

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

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

Для достижения поставленной цели решались следующие задачи.

1. Построить и изучить математические модели для задач формирования производственных групп с учетом межличностных и иерархических отношений.

2. Разработать алгоритмы точного и приближенного решения указанных

задач, провести анализ алгоритмов.

4. Выполнить экспериментальные исследования рассматриваемых моделей и алгоритмов.

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

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

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

научно-исследовательской работе и для решения практических задач. Полученные результаты используются на кафедре прикладной и вычислительной математики Федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Омский государственный университет им. Ф.М. Достоевского» (ФГБОУ ВПО ОмГУ им. Ф.М. Достоевского), лаборатории дискретной оптимизации Омского филиала Федерального государственного бюджетного учреждение науки Института математики им. С.Л. Соболева Сибирского отделения Российской академии наук (ФГБУН ОФ ИМ СО РАН) при подготовке специалистов по методам оптимизации и исследованию операций, в Омском филиале ФГБОУ ВПО «Московский государственный университет технологий и управления им. К.Г. Разумовского» (филиал «МГУТУ им. К.Г. Разумовского» в г. Омске).

Апробация работы. Результаты диссертации докладывались на XXXIV Региональной научно-практической студенческой конференции «Молодежь третьего тысячелетия» (г. Омск, 2010), Шестой, Седьмой и Девятой Международных Азиатских школах-семинарах «Проблемы оптимизации сложных систем» (Республика Казахстан, 2010 и 2013, Республика Узбекистан, 2011), XIV Всероссийской конференции «Математическое программирование и приложения» (г. Екатеринбург, 2011), XII и XIII Международных научно-инновационных конференциях с элементами научной школы «Теоретические знания в практические дела» (г. Омск, 2011 и 2012), XV Байкальской международной школе-семинаре «Методы оптимизации и их приложения» (г. Иркутск, 2011), Всероссийской научно-практической конференции «Статистика, моделирование, оптимизация» (г. Челябинск, 2011), V Всероссийской конференции «Проблемы оптимизации и экономические приложения» (г. Омск, 2012), VIII Международной научно-технической конференции «Динамика систем, механизмов и машин» (г. Омск, 2012), Международной конференции «Информационные технологии интеллектуальной поддержки принятия решений» и Российско-немецком семинаре «Модели и алгоритмы

прикладной оптимизации» (г. Уфа, 2013), Международной конференции «Optimization and Applications ОРТ1МА-2013» (Черногория, 2013), на заседании научного семинара лаборатории прикладных систем ФГБУН Института вычислительной математики и математической геофизики СО РАН (г. Новосибирск, 2013), а также на заседаниях научного семинара «Математическое моделирование и дискретная оптимизация» лаборатории дискретной оптимизации ОФ ИМ СО РАН и Института математики и информационных технологий ОмГУ им. Ф.М. Достоевского (г. Омск, 2009-2013).

Публикации. Основные результаты диссертации опубликованы в 16 научных работах [5-8,10,15,16,42-45,52,53,105], две из них - в журналах из списка ВАК [9,104].

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

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

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

целочисленного линейного программирования и теоретико-графовая. Доказана полиномиальная сводимость указанной задачи к задаче поиска независимого множества минимального веса (при фиксированной мощности этого множества). Кроме того, выделены полиномиально разрешимые случаи.

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

Предлагается модель ЦЛП для задачи, в которой специалистов распределяют по производственным сменам.

Доказано, что рассматриваемые задачи являются Л^Р-трудными.

Третья глава посвящена построению и исследованию точных и приближенных алгоритмов решения задач формирования производственных групп с учетом межличностных и иерархических отношений, описанию разработанного научно-исследовательского комплекса программ и проведенного вычислительного эксперимента. Предлагаются методы решения задач, в которых выполняется назначение претендентов на работы при условии согласованности межличностных отношений и минимизации затрат. Изложены алгоритмы комбинаторного типа, идейно близкие методу ветвей и границ, а также процедура, основанная на использовании отсечений и пакета СРЬЕХ 12.1. Кроме того, представлены комбинаторные алгоритмы для решения задач проектирования групп с максимизацией степени комфортности отношений.

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

результаты экспериментальных исследований разработанных алгоритмов на практике и их сравнение на задачах со случайными исходными данными. Описывается применение математических моделей при формировании производственной группы на одном из омских прелприятий. Изучаются вопросы проектирования учебных групп, в том числе в условиях высокой гетерогенности контингента студентов. Приводятся результаты решения указанных задач с помощью пакета CPLEX.

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

В приложении содержатся исходные данные ряда прикладных задач и результаты их решения с помощью указанного пакета.

Автор благодарит научного руководителя д.ф.-м.н., профессора Колоколова A.A. за внимание и поддержку при выполнении данной работы.

и

Глава 1

Математические модели оптимизации для задач планирования и управления

персоналом

В главе дается обзор математических моделей и методов для решения задач управления персоналом, в частности задач формирования производственных групп. В разделе 1.1 представлены постановки задач и соответствующие модели целочисленного линейного программирования, полученные на основе известных задач о назначениях и их обобщений, в том числе задач транспортного типа. В разделах 1.2-1.4 изучаются задачи, возникающие при исследовании покрытий, разбиений множеств, размещений предприятий, оптимизации на графах, которые могут быть использованы при проектировании производственных групп. В разделе 1.5 содержится информация о некоторых алгоритмах решения указанных задач.

1.1. Задачи оптимального назначения

1.1.1. Классическая задача о назначениях

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

образом. Пусть имеется п специалистов и m работ, m < п, I = {1,...,п}, J = {1,..., т}. Для каждого специалиста i£l известны затраты Су на выполнение им работы j G J. Любая работа должна быть назначена только одному претенденту, при этом каждый из них может быть прикреплен не более, чем к одной работе. Требуется распределить специалистов по работам так, чтобы суммарные затраты на выполнение всех работ были минимальными.

Здесь и далее нами используются следующие переменные: х^ = 1, если специалисту г назначена работа j, в противном случае Xij = 0, г G /, j G </.

Модель ЦЛП имеет вид:

min (1Л)

iei jeJ

при условиях

= ¿GJ, (1.2)

гб/

te/, (1.3)

jeJ

хц G {0,1}, i G /, j G J. (1.4)

Целевая функция (1-1) заключается в минимизации суммарных затрат на выполнение всех имеющихся работ. Условия (1.2) гарантируют, что каждая работа будет выполнена и только одним специалистом, ограничения (1.3) означают, что любой претендент будет назначен не более одного раза.

Отметим, что в литературе изучаются варианты задачи, в которых п = m и условия типа (1.3) являются равенствами, в этом случае задача соответствует нахождению в двудольном графе совершенного паросочетания минимального веса [4]. Рассматривается также ЗН на максимум, при этом коэффициент C{j интерпретируется как эффективность назначения специалиста i для выполнения им работы j, i Е I, j G J, a оптимальное назначение должно максимизировать суммарную

эффективность.

В сформулированной ЗН некоторые факторы не принимаются во внимание, поэтому возникает необходимость использования более общих постановок, в частности учитывающих длительности работ. Это отражено в приводимых ниже задачах.

1.1.2. Задачи транспортного типа

Пусть щ - общее время, в течение которого специалист г е I выполняет работы, bj - длительность работы j е J. Требуется назначить претендентов на работы так, чтобы каждый из них оказался загруженным полностью, все работы были выполнены за указанное время, а суммарные затраты на обслуживание являлись минимальными.

Модель ЦЛП для этой задачи можно записать следующим образом:

~+ min (1 -5)

iei jeJ

при ограничениях

iei

5>i = i e /, (1-7)

jeJ

€{0,1}, iei, je J. (1-8)

Условия (1.6) означают, что все работы должны быть выполнены за установленное время, ограничения (1.7) гарантируют, что каждый специалист загружен полностью. Данная модель представляет собой задачу транспортного типа (ТЗ) [74].

Рассматривается также постановка ТЗ на максимум, которая состоит в централизованном распределении на предприятии т работ в количествах bj е N, je J, среди п специалистов (каждый претендент i должен выполнить ровно а,{ е N, г е /, работ) с целью максимизации суммарного дохода. В этом случае Су - доход, получаемый предприятием при

назначении специалисту