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

• Афанасьева, Любовь Дмитриевна
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Афанасьева, Любовь Дмитриевна

Оглавление

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

Приложение

Введение диссертации (часть автореферата) на тему «Разработка моделей и алгоритмов дискретной оптимизации для задач формирования производственных групп»

Введение

Актуальность темы. Современный этап развития прикладной математики характеризуется активной разработкой и применением математических моделей и методов в планировании, проектировании, исследовании социально-экономических и технических систем [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, г е /, работ) с целью максимизации суммарного дохода. В этом случае Су - доход, получаемый предприятием при

назначении специалисту г работы ], переменная х^ - число работ у, выполняемых специалистом г, г 6 I, j £ 3 [26].

Указанные задачи имеют множество обобщений (на узкие места, многокритериальные и т.п. [21, 56, 59, 80, 88, 89]), которые целесообразно использовать при распределении работ между членами производственной группы. Далее рассмотрим несколько постановок, чтобы показать разнообразие таких задач.

1.1.3. Задача о назначениях на узкие места

Пусть для каждого претендента г известно время с^- выполнения им работы j, г £ I, j £ J. Как и прежде, требуется распределить работы между специалистами так, чтобы любой претендент выполнял не более одной из них и каждая работа была назначена только одному специалисту. Задача состоит в отыскании такого распределения претендентов по работам, чтобы длительность выполнения самой трудоемкой по времени работы была минимальной [80,88]. Приведем модель ЦЛП для этой задачи:

max (CijXij) —»■ min (1.9)

iei,jeJ

при условиях

5>ü = l, jeJ, (l.io)

iei

Y^xij <1, (l.ii)

jeJ

я:це{0,1}, iel, je J. (1.12)

Целевая функция (1.9) гарантирует, что длительность выполнения самой трудоемкой по времени работы будет минимальной. Ограничения (1.10), (1.11) те же, что и в модели (1.1)-(1.4). В [21] рассматривается обобщение этой задачи, а именно ТЗ с минимаксным критерием и ограниченными сверху целочисленными переменными.

1.1.4. Вероятностный вариант задачи о назначениях

Матрица стоимостей иногда обладает такими свойствами, что задача о назначениях решается значительно проще, чем в общем случае. Пусть п — т и специалисты отличаются по своей квалификации, причем квалификация каждого претендента % оценивается значением вероятности Pi Е [0,1] успешного выполнения им произвольной работы. Заметим, что тогда вероятность невыполнения работы равна 1 — Pi, iEl. Для каждой работы j известны вознаграждение за успешное ее выполнение bj и штраф a,j за невыполнение, j Е J. Сумма üj + bj в литературе называется степенью ответственности работы j Е J. В случае, если работа j будет назначена специалисту г, ожидаемый доход от данной работы будет равен Cij — bjPi — aj( 1 — Pi), г E /, j E J. По-прежнему требуется так распределить работы между претендентами, чтобы выполнялись ограничения задачи о назначениях, сформулированные выше, а общий ожидаемый доход был максимальным [80,89].

К настоящему времени опубликовано достаточно много обзорных работ и книг по рассматриваемым задачам. Хорошо исследованы в теоретическом и алгоритмическом плане варианты этих задач [88]. Естественным обобщением двухиндексных ЗН, ЗТ являются многоиндексные задачи, более полный обзор по которым приводится в [115]. Информация по указанным задачам также может быть найдена в [111]. Представляет интерес и квадратичная ЗН [35], например, в [56] изучается задача распределения работ в течение ряда дней.

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

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

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

1.2.1. Использование задачи о покрытии множества

Задача о покрытии множества может быть сформулирована

следующим образом. Пусть даны множества I — {l,...,m}, J = {1,...,п}.

Каждый элемент j G J покрывает подмножество Ij множества I.

Совокупность {Ij : j G К, К С J} называется покрытием множества

I, если Ij = I. Каждому Ij приписан вес Cj > 0. Требуется найти зек

покрытие, имеющее минимальный суммарный вес.

Приведем соответствующую этой задаче модель ЦЛП. Введем булевы переменные: Xj = 1, если множество Ij входит в покрытие, иначе Xj = 0, j G J. Определим матрицу А = (а^), г G /, j G J: aij = 1, если элемент г входит в множество Ij, а^ = 0, иначе.

Запишем модель ЦЛП для задачи о наименьшем покрытии множества:

^^CjXj —>• min (1-13)

ieJ

при условиях

aijxj ^ 1) i G /, (1.14)

jeJ

^■G{0,1}, j G J. (1.15)

Целевая функция (1.13) заключается в поиске покрытия минимального веса. Условия (1.14) означают, что все элементы множества I будут покрыты.

В литературе изучаются обобщения задачи о покрытии, в которых в правой части ограничений (1.14) используется вектор натуральных чисел Ъ — (Ьх, ■••, Ьт)Т. Это означает, что элемент j должен быть покрыт не менее bi раз, г G I.

Эта задача относится к числу TVP-трудных задач. К ней сводятся

известные задачи дискретной оптимизации: задача стандартизации [13], задача упаковки и разбиения множества, задача о наибольшей клике [23], задача минимизации полинома от булевых переменных [1] и др. Известны также и обратные сводимости задачи о покрытии к этим задачам [12,13,23].

На практике задачи о покрытии возникают при формировании производственных групп, размещении пунктов обслуживания [55,65], при назначении экипажей на транспорте [55], проектировании интегральных схем и т.д. Обобщения задач о покрытии использовались в задачах формирования оптимального комплекта тестов, позволяющего оценить знания отдельного студента и степень усвоения всего объема учебного курса потоком студентов [37].

Приведем интерпретацию задачи (1.13)—(1.15) в терминах проектирования производственных групп. Пусть даны множества работ I и специалистов 3, а также - множество всех работ, которые может выполнить специалист ^ £ 3. Известны затраты с^ > 0 на выполнение специалистом з £ 3 работ из 1у Определим матрицу А = (а^): а^ — 1, если работа г может быть назначена специалисту и в противном случае а^ = О, г £ I, з £ 3. При этом х^ — 1, если специалист з назначен на работы из множества 7^-, иначе Xj = 0, j £ 3. Требуется выбрать таких специалистов из множества ,/, чтобы все работы из / были выполнены с минимальными затратами.

Если неравенства (1.14) в задаче (1.13)—(1.15) заменить на равенства

№

то получим модель ЦЛП для задачи о наименьшем разбиении, которая

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

1з Я: I, 3 £ 3 не имеет попарных пересечений и = I.

зез

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

(1.16)

мультипроцессорных систем и в других областях можно использовать задачу разбиения [110]. При этом в качестве признаков распределяемых элементов по множеству могут служить длина, вес, стоимость, пропускная способность, уровень образования и т.д (см. раздел 2.3).

В следующем пункте представлен ряд задач формирования производственных групп, которые предложены на основе изучения работ из области оптимального размещения [12,18,63].

1.2.2. Приложения задач размещения

Сначала рассмотрим постановку, которая тесно связана с простейшей задачей размещения (ПЗР). Предположим, что некоторое предприятие планирует сформировать группу специалистов для выполнения комплекса работ. Имеется множество претендентов для включения в эту группу. Каждая работа может быть выполнена только одним специалистом. Известны затраты, связанные с приемом на работу каждого претендента, и затраты на выполнение работы каждым из них. Требуется создать группу, в которой число специалистов не превышает заданную величину, а суммарные расходы, необходимые для назначения сотрудников и выполнения работ, минимальны при выполнении указанных выше условий. Для построения математической модели используем обозначения:

I = {1, ...,п} - множество претендентов для включения в группу;

<7 — {1, ...,т} - множество работ;

вг - расходы, связанные с приемом на работу специалиста г, г £ /;

Су - затраты на выполнение работы ] специалистом г, % Е I, з Е <7;

р - максимальное количество специалистов, включаемых в формируемую группу.

Введем переменные задачи:

= 1, если специалист г принят в производственную группу, — 0, иначе, г Е /;

Хц = 1, если специалист г назначен на работу j, х^ = 0,

иначе, г € I, j G J.

У^ SiZi + CijXii min

iei iei jeJ

при условиях

= 1, jeJ, (1.18)

iei

iei

Xij <zu ie /, j e J, (1.20)

Е 0,1, г е I, 3 6 3. (1.21)

Целевая функция (1.17) направлена на минимизацию затрат предприятия. Равенства (1.18) показывают, что каждая работа должна быть выполнена, (1.19) ограничивает количество специалистов в группе. Неравенства (1.20) гарантируют выполнение работы только теми претендентами, которые приняты в группу.

Как и в случае ПЗР в указанную модель входят ограничения (1.18), (1.20), (1.21). Задача АГР-трудна, поскольку ПЗР, относящаяся к классу Л^Р-трудных задач [23], является ее частным случаем при р = п. Данная задача всегда разрешима при условии наличия претендентов.

Следующая постановка отличается от рассмотренной тем, что любой специалист может выполнять не более заданного числа работ. В этом случае задача также является ТУР-трудной. Ее модель ЦЛП строится из предыдущей путем добавления системы неравенств:

<г4> г€/, (1.22)

где Г{ - максимальное число работ, которые могут быть назначены специалисту г, г € I.

Указанная задача была применена для формирования производственных групп на одном из омских предприятий, помимо условий (1.17)—(1.22) в модели для данной задачи учитывались межличностные отношения. Постановки такого типа будут более подробно рассматриваться в главе 2. Имеются и другие работы, в которых обобщения задач размещения используются для проектирования производственных групп [79].

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

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

Основные определения, введенные в данном разделе, взяты из [29]. Множество вершин графа называется независимым, если никакие две вершины из этого множества не являются смежными. Независимое множество называется максимальным, если оно не является собственным подмножеством некоторого другого независимого множества. Наибольшее по мощности независимое множество называется наибольшим. Ясно, что наибольшее независимое множество является максимальным. Обратное, вообще говоря, неверно. Число вершин в наибольшем независимом множестве графа С? называется числом независимости этого графа и обозначается через ско(С). Если заданы веса вершин, то необходимо найти

независимое множество максимального суммарного веса (М\¥13).

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

Список литературы диссертационного исследования кандидат наук Афанасьева, Любовь Дмитриевна, 2013 год

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

[1] Агеев A.A. О сложности задач минимизации полиномов от булевых переменных // Управляемые системы. - Новосибирск, 1983. № 23. - С. 3-11.

[2] Аделынин A.B. Исследование задач максимальной и минимальной выполнимости с использованием L-разбиения // Автоматика и телемеханика. - 2004. - № 3. - С. 35 42.

[3] Армстронг М. Практика управления человеческими ресурсами. -СПб.: Питер, 2009. — 848 с.

[4] Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. - Ижевск: НИЦ «Регулярная и хаотичная динамика», 2001. - 288 с.

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

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

[7] Афанасьева Л.Д. О некоторых полиномиально разрешимых случаях задачи формирования производственных групп / / Материалы

Всероссийской молодежной школы-семинара «Дискретные модели и методы принятия решений». - Новосибирск: Изд-во Ин-та математики, 2013. - С. 207 208.

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

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

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

[11] Бахтин А.Е., Колоколов A.A., Коробкова З.В. Дискретные задачи производственно-транспортного типа. - Новосибирск: Наука, 1978. - 160 с.

[12] Береснев В.Л. Дискретные задачи размещения и полиномы от булевых переменных. - Новосибирск: Изд-во Ин-та математики, 2005. - 408 с.

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

[14] Булатов В.П. Методы погружения в задачах оптимизации. -Новосибирск: Наука, 1977. - 161 с.

[15] Бушинский С.Д., Шулепова Л.Д. О решении некоторых задач формирования малых производственных групп // Труды XXXIV

региональной научно-практической студенческой конференции «Молодежь III тысячелетия». - Омск: Изд-во ОмГУ, 2010. - С. 15-17.

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

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

[18] Васильев И.Л., Климентова К.Б., Кочетов Ю.А. Новые нижние оценки для задачи размещения с предпочтениями клиентов //

- Иркутск, 2008. - 12 с.

[19] Воронин A.A., Мишин С.П. Оптимальные иерархические структуры.

— М.: ИПУ РАН, 2003. 214 с.

[20] Гимади Э.Х., Дементьев В.Т. Вероятностный анализ децентрализованной версии одного обобщения задачи о назначениях // Дискретный анализ и исследование операций. - 2011. - Т. 18, № 3. -С. 11-20.

[21] Глебов Н.И. Об одном обобщении минимаксной задачи о назначениях // Дискретный анализ и исследование операций. -2004. - Сер. 1, Т. И, № 4. - С. 36 43.

[22] Горбачевская Л.Е., Дементьев В.Т., Шамардин Ю.В. Двухуровневая экстремальная задача выбора номенклатуры изделий // Препринт. Новосибирск: ИМ СО РАН, 1997. 26 с.

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

[24] Девятерикова М.В., Колоколов A.A. Анализ устойчивости некоторых алгоритмов дискретной оптимизации //Автоматика и телемеханика.

- 2004. - № 3. - С. 48-54.

[25] Дементьев В.Т., Ерзин А.И., Ларин P.M., Шамардин Ю.В. Задачи оптимизации иерархических структур. - Новосибирск: Изд-во НГУ, 1996. - 167 с.

[26] Дементьев В.Т., Пяткин A.B. О децентрализованной транспортной задаче // Дискретный анализ и исследование операций. - 2008. -Т. 15, № 3. С. 22-30.

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

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

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

[30] Еремеев A.B., Заозерская Л.А., Колоколов A.A. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования // Дискретный анализ и исследование операций. -2000. - Т. 7, - 2. - С. 22-46.

[31] Еремин И.И., Мазуров Вл.Д., Скарин В.Д., Хачай М.Ю. Математические методы в экономике. - Екатеринбург: УрГУ -Центр «Фактория Пресс», 2000. - 303 с.

[32] Железова Е., Измалков С., Сонин К. Теория и практика двусторонних рынков // Вопросы экономики. — 2013. - № 01.

- С. 4-26.

[33] Забиняко Г.И. Пакет программ целочисленного линейного программирования // Дискретный анализ и исследование операций. -1999. - Т. 6, № 2. - С. 32-41.

[34] Заблоцкая O.A., Колоколов A.A. Вполне регулярные отсечения в булевом программировании // Управляемые системы. - 1983. - Вып. 23. - С. 55-63.

[35] Забудский Г.Г., Лагздин А.Ю. Динамическое программирование для решения квадратичной задачи о назначениях на дереве // Автоматика и телемеханика, 2012. Вып. 2. - С.141-155.

[36] Заозерская Л.А., Колоколов A.A. Оценки среднего числа итераций для некоторых алгоритмов решения задачи об упаковке множества // ЖВМ и МФ. - 2010. Т. 50, № 2. - С. 242 248.

[37] Заозерская Л.А., Колоколов A.A., Планкова В.А. Об одной автоматизированной системе тестирования знаний студентов по экономико-математическим методам // Moscow Education Online 2010: тезисы докл. IV междунар. конф. — М.: Global Conferences, 2010. - С. 130-133.

[38] Картак В.М., Месягутов М.А., Мухачева Э.А., Филиппова A.C. Локальный поиск ортогональных упаковок с использованием нижних границ // Автоматика и телемеханика. - 2009. - № 6. - С. 167-180.

[39] Колоколов A.A. Регулярные разбиения в целочисленном программировании // Методы решения и анализа задач дискретной оптимизации. - Омск: ОмГУ, 1992. - С. 67-93.

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

[41] Колоколов A.A., Аделыпин A.B., Ягофарова Д.И. Исследование задач дискретной оптимизации с логическими ограничениями на

основе метода регулярных разбиений // Прикладная дискретная математика. - 2013. - № 1(19). - С.99-109.

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

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

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

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

[46] Колоколов A.A., Девятерикова М.В., Заозерская Л.А. Регулярные разбиения в целочисленном программировании. Учебное пособие. -Омск: Изд-во ОмГУ, 2007. - 60 с.

[47] Колоколов A.A., Заозерская Л.А. О среднем числе итераций некоторых алгоритмов для решения задачи об упаковке множества // Труды XIV Байкальской международной школы-семинара «Методы оптимизации и их приложения». - Иркутск, 2008. - Т. 1. - С. 388-395.

[48] Колоколов A.A., Косарев H.A., Рубанова H.A. Исследование отсечений Бендерса в декомпозиционных алгоритмах решения некоторых задач размещения // Омский научный вестник. - 2005. -№ 2(31). - С. 76-80.

[49] Колоколов A.A., Леванова Т.В. Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения // Вестник Омского университета. - 1996. -№ 1. ~ С. 21-23.

[50] Колоколов A.A., Леванова Т.В., Поздняков Ю.С. Алгоритмы искусственной иммунной системы для вариантной задачи размещения телекоммуникационных центров // Известия Иркутского государственного университета, Серия «Математика». - 2013. - Т. 6,

- № 1. - С. 35-44.

[51] Колоколов A.A., Орловская Т.Г., Рыбалка М.Ф. Исследование алгоритмов целочисленного программирования с использованием регулярных разбиений и унимодулярных преобразований / / Автоматика и телемеханика. - 2012. - JVfi 2. - С. 178-190.

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

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

[54] Колоколов A.A., Ярош A.B. Автоматизация проектирования сложных изделий с использованием дискретной оптимизации и информационных технологий // Омский научный вестник. - 2010.

- Т. 90, № 2 - С. 234-238.

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

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

[57] Кузнецова A.A., Стрекаловский A.C., Цевээндорж И. Об одном подходе к решению целочисленных задач оптимизации // ЖВМ и МФ. - 1999. - Т. 39, № 1. - С. 9-16.

[58] Кузюрин H.H., Фомин С.А. Эффективные алгоритмы и сложность вычислений. Учебное пособие. - М.: МФТИ, 2007. - 312 с.

[59] Ларин P.M., Пяткин A.B. Двухуровневая задача о назначениях // Дискретный анализ и исследование операций. - 2001. - Сер. 2, Т. 8, № 2. - С. 42-51.

[60] Леонтьев В.К. Устойчивость в линейных дискретных задачах // Проблемы кибернетики. - 1979. - Вып. 35. - С. 169-184.

[61] Лернер Э.Ю. Соответствие задач об устойчивом паросочетании и о назначении // Изв. вузов. Матем. - 2011. - № 11. - С. 34—40.

[62] Мазуров Вл.Д. Метод комитетов в задачах оптимизации и классификации. - М.: Наука, 1990. - 248 с.

[63] Маринова А.И. Об одной задаче формирования производственных групп / / Труды XIII Международной научно-инновационной конференции аспирантов, студентов и молодых исследователей с элементами научной школы «Теоретические знания — в практические дела». - Омск, 2012. - Ч. 2. - С. 204-206.

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

[65] Нечепуренко M.И., Попков В.К., Майнагашев С.М. и др. Алгоритмы и программы решения задач на графах и сетях. - Новосибирск: Наука, 1990. - 515 с.

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

[67] Пападимитриу X., Стайглиц К. Комбинаторная Алгоритмы и сложность. - М.: Мир, 1985. - 512 с.

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

[69] Попов Л.Д. Опыт многоуровневого распараллеливания метода ветвей и границ в задачах дискретной оптимизации // Автоматика и телемеханика. - 2007. - Вып. 5. С. 171-181.

[70] Сервах В.В. Сложность решения задач теории расписаний: учебное пособие. - Изд-во Омского гос. ун-та, 2012. 42 с.

[71] Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. - Киев: Наукова думка, 1988. - 472 с.

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

[73] Симанчев Р.Ю. Выпуклые многогранники и фасетные неравенства. Учебно-методическое пособие. - Омск: Изд-во ОмГУ, 1999. - 40 с.

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

[75] Хачай М.Ю. Вычислительная сложность комбинаторных задач, индуцированных коллективными процедурами обучения распознаванию образов // Труды Института математики и механики УрО РАН. - 2010. - Т. 16, 3. - С. 276-284.

формирования Издательство

оптимизация.

[76] Хачатуров В.Р., Веселовский В.Е., Злотов А.В. и др. Комбинаторные методы и алгоритмы решения задач дискретной оптимизации большой размерности. - М.: Наука, 2000. - 360 с.

[77] Ху Т. Целочисленное программирование и потоки в сетях. - М.: Мир, 1974. - 520 с.

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

[79] Шенмайер В.В. Приближенный алгоритм для иерархической задачи о назначениях // Дискретный анализ и исследование операций. - 2008.

- Т. 15, № 4. - С. 84—91.

[80] Шпиленко А.В. Экономико-математические модели управления персоналом на предприятии // Информационные технологии управления в социально-экономических системах, Росинформтехнологии, 2009. № 3. - С. 49-75.

[81] Щербина О.А. О модифицированном локальном алгоритме решения блочных задач дискретного программирования // ЖВМ и МФ. 1986. - Т. 26, № 9. - С. 1339-1349.

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

[83] Balas Е., Carrera М.С. A Dynamic Subgradient-Based Branch and Bound Procedure for Set Covering // Oper.Res. - 1996. - Vol. 44, № 6.

- P. 875-890.

[84] Balas E., Ho A. Set covering algorithms using cutting planes, heuristics, and subgradient optimization: a computational study // Math. Program. Study. - 1980. - Vol. 12. - P. 37-60.

[85] Beasley J.E., Chu P.C. A Genetic Algorithm for the SCP // European J. Oper. Res. - 1996. - Vol. 94, № 2. - P. 394-404.

[86] Beasley J.E., Chu P.C. A Genetic Algorithm for the Set Covering Problems // European Journal for Operation Research. - 1990. - Vol. 31.

P.85-93.

[87] Bertsimas D., Weismantel R. Optimization over Integers. - Belmont, Massachusetts: Dynamic Ideas, 2005. - 603 p.

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

[89] Burkard R.E., Klinz B., Rudolf R. Perspectives of Monge properties in optimization //Discr. Appl. Math. - 1996. - Vol. 70. P. 95—161.

[90] Cornuejols G., Liu X., Vuskovic K. A polynomial algorithm for recognizing perfect graphs // 44th Symposium on Foundations of Computer Science (FOCS 2003). - 2003. - P. 20 27.

[91] Sanjoy Dasgupta , Christos H. Papadimitriou, Umesh Vazirani Algorithms. — McGraw-Hill Science/Engineering/Math, 1 edition.

- 2006. — 336. p.

[92] Dorigo M., Stutzle T. Ant Colony Optimization. MIT Press, 2004.

- 319 p.

[93] Eremeev A. Modeling and Analysis of Genetic Algorithm with Tournament Selection // Proc. of Artificial Evolution Conference. Lecture Notes in Computer Science. - 2000. - Vol. 1829. - P. 84-95.

[94] Eremeev A.V., Kolokolov A.A., Zaozerskaya L.A. A hybrid algorithm for set covering problem // Proc. of Intern, workshop on discrete optimization methods in sheduling and computer-aided design. - Minsk, 2000.

P. 123-129.

[95] Gale D., Shapley L.S. College admissions and the stability of marriage // Amer. Math. Monthly. - 1962. - Vol. 69, № 1. - P. 9—15.

[96] GAMS Development Corporation, Website, http://www.gams.com/.

[97] Glover F., Laguna M. Tabu Search. - University of Colorado at Boulder Hardbound, 1997. - 408 p.

[98] Goldberg D. Genetic Algorithms in Search, Optimization and Machine Learning. - Reading: Addison Wesley, 1989. - 432 p.

[99] Gornory R.E. An algorithm for integer solutions to linear programs // Recent Advances in Mathematical Programming. - New York: McGraw-Hill, 1963. - P. 269-302.

[100] Graph^ Open Source Software, Website, http://graphsharp.codeplex.com/.

[101] Grotschel M. Lovasz L., Schrijver A. Polynomial algorithms for perfect graphs // Annals of Discrete Mathematics. - 1984. - № 21. - P. 325-356.

[102] Hochbaum D.S. Approximating Covering and Packing Problems: Set Cover, Vertex Cover, Independent Set, and Related Problems // Approximation Algorithms for NP-Hard Problems. - PWS Publishing Company, 1995. - P. 94-143.

[103] Knuth D.E. Stable marriage and its relation to other combinatorial problems: an introduction to mathematical analysis of algorithms. - AMS, Providence, RI, 1996. - 74 p.

[104] Kolokolov A.A., Afanasyeva 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.

[105] Kolokolov A.A., Afanasyeva L.D. On solving some production groups formation problems based on discrete optimization / / Abstracts of IV International conference «Optimization and applications» (OPTIMA-2013). - M.:BU, PAH, 2013. - P. 98.

[106] Kolokolov A.A., Kosarev N.A. Analysis of decomposition algorithms with Benders cuts for p-median problem // Journal of Mathematical Modeling and Algorithms. - 2006. - № 5. - P. 189-199.

[107] Korf Richard E. A complete anytime algorithm for number partitioning // Artificial Intelligence. - 1998. - Vol. 106, Issue 2. - R 181-203.

[108] Land A.H., Doig A.G. An automatic method of solving discrete programming problems // Econometrica. 1960. Vol. 28, № 3. - R 497-520.

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

[110] Joao Pedro Pedroso, Mikio Kubo Heuristics and exact methods for number partitioning // European Journal of Operational Research -EJOR. - 2010. - Vol. 202, № 1. - P. 73-81.

[111] Pentico D.W. Assignment problems: A golden anniversary survey // European Journal of Operational Research. 2007. - P. 774—793.

[112] Pirlot M. General local search methods // European Journal of Operational Reasearch. - 1996. - P. 493-511.

[113] Pochet Y., Wolsey L.A. Production Planning by Mixed Integer Programming. - New-York: Springer, 2006. - 500 p.

[114] Reeves C. Genetic Algorithms for the Operation Researcher // INFORMS Journal on Computing. - 1997. - Vol.9, № 3. - P. 231-250.

[115] Spieksma F.C.R. Multi index assignment problems: complexity, approximation, applications // Nonlinear assignment problems, algorithms and applications. Dordrecht: Kluwer Acad. Publ. - 2000. - P. 1—12.

[116] Wilcoxon F. Individual comparisons by ranking methods // Biometrics Bulletin. - 1945. Vol. 1, № 6. - P. 80- 83.