Содержание к диссертации
Введение 4
Глава 1. Задачи распределения ресурсов и упорядочения работ в сетевых
структурах 12
1.1 Задачи распределения и упорядочения в сетевых канонических
структурах 13
1.1.1. Классификация задач распределения и упорядочения 13
1.1.2 Задачи распределения ресурсов 23
Задачи сетевого планирования 26
Задачи упорядочения 33
1.2 Задачи распределения и упорядочения в многостадийных системах........ 40
1.3 Нечеткие временные и стоимостные характеристики в задачах
распределения ресурсов и упорядочения работ 40
1.3.1 Нечеткие множества 42
1.3.2. Нечеткие числа 44
Операции над нечеткими числами 46
Операции сравнения нечетких чисел 48
Определение нечетких бинарных отношений <,=,> на множестве нечетких
чисел 49
1.3.6. Применение нечетких временных и стоимостных характеристик для описания
реальных производственных систем 52
Выводы по главе 1 54
Глава 2. Многостадийные задачи распределения ресурсов и упорядочения
работ 55
2.1. Общая математическая модель распределения ресурсов и упорядочения
работ в многостадийных системах 56
Исходные параметры математической модели 56
Варьируемые параметры математической модели 57
2.1.3. Ограничения математической модели 58
2.2. Исследование общей математической модели 59
2.3. Постановки оптимизационных задач распределения ресурсов и
упорядочения работ в многостадийных системах..................................................... 59
Частные критерии оптимальности 59
Постановка классических задач дискретной оптимизации в рамках построенной математической модели 61
Выводы по главе 2 63
Глава 3. Алгоритмы решения оптимизационных задач распределения
ресурсов и упорядочения работ в многостадийных системах с нечеткими
характеристиками 65
3.1. Жадные алгоритмы решения задач распределения и упорядочения......... 65
3.2. Детерминированные алгоритмы ограниченного перебора 65
3.2.1. Алгоритм - построитель расписания А(Р) 65
Ар Алгоритм поиска перестановки Р с глубиной h 66
A3: Метод локального улучшения расписания 67
А*: Алгоритм критического пути 69
/
3.3 Стохастические алгоритмы решения задач распределения и упорядочения
70
3.3.1. А2: Алгоритмы Метрополиса (Simulated Annealing) 70
3.3.3 Управление процессом решения задачи путем взаимозависимого применения
различных алгоритмов 71
3.3.4. Реализация нечетких расписаний при организации производственного процесса.... 73
Выводы по главе 3 75
Глава 4. Программные средства решения задач распределения ресурсов и
упорядочения работ в многостадийных системах с нечеткими
характеристиками 76
Процедуры интерактивного взаимодействия 77
Реализация механизма построений различных отображений задачи 80
Сравнение различных схем отображений результатов решения задачи 80
Математическая модель интерфейса с использованием аппарата нечетких множеств 82
Реализация механизма сравнения различных отображений задачи 85
Решение прикладных задач распределения и упорядочения 89
Численный эксперимент для оценки производительности групп жадных алгоритмов для построения расписания в многостадийных системах 89
Построение расписания изготовления пресс-форм в инструментальном цехе 91
Выводы по главе 4 99
Заключение 101
Литература 103
Приложения 118
Приложение 1 118
Приложение 2 120
Введение к работе
Одной из наиболее важных проблем, возникающих в различных областях человеческой деятельности (технической, экономической, организационной и др.), является проблема совершенствования управления. Очень часто эффективное управление состоит в использовании ресурсов оптимальным образом.
В различных моделях природа ресурсов может быть различна. Это и ресурсы типа «материалы», и энергетические ресурсы, и трудовые ресурсы, и время. В производственных системах в качестве ресурсов могут выступать обслуживающие приборы. Экстремальные задачи распределения ресурсов возникают в связи с тем, что объемы ресурсов являются ограниченными. При распределении ограниченных ресурсов возникают конфликтные ситуации. Сложность составления расписаний определяется еще и тем, что необходимо не только обеспечить необходимые условия проведения всего множества операций, но и согласовать их во времени. Основной целью планирования является создание такого расписания, которое обеспечит выполнение всего комплекса работ с минимальными затратами.
Экстремальные задачи распределения ресурсов были сформулированы в 50-х годах. До этого момента планирование носило не систематический характер. Начались интенсивные и систематические исследования по построению и анализу математических моделей календарного планирования. Появились новые методы решения задач распределения ресурсов, которые легли в основу сетевого планирования.
Основными методами управления в этих моделях являются метод критического пути (при заданных фиксированных длительностях работ) и метод оценки и пересмотра проектов (при неопределенности в длительностях работ).
Появилось понятие «проект», обозначающее комплекс взаимосвязанных работ, для выполнения которых выделены ресурсы и установлены сроки. Со временем масштабы проектов увеличивались, и стало невозможно «вручную» согласовывать огромное число операций. Стали развиваться математические методы решения задач распределения ресурсов. В задачах такого рода рассматриваются только «внутренние» ресурсы системы. В более общих задачах при планировании важно учитывать влияние внешних условий. Стали развиваться задачи динамического оперативного планирования. При таком подходе строится начальный план, а затем он корректируется с целью отразить изменившиеся внешние условия.
С другой стороны, проект выполняется только однажды, и хотелось бы не только эффективно выполнить работы, но и доказать, что выбранный план выполнения работ является лучшим из возможных планов.
Развитием этой научной области занимались такие ученые как Шкурба В.В., Подчасова Т.П., Бурдюк В.Я., Танаев B.C., Гордон B.C., Михалевич B.C., Шор Н.З., Мироносецкий Н.Б., Португал В.М. и многие другие. Из зарубежных ученых это Конвей Р., Джонсон Б., Максвелл У., Гиффлер Б., Томпсон Ж. и другие. Следует отметить школу Нижегородского университета и ученых Батищева Д.И., Прилуцкого М.Х., Когана Д.И., Федосенко Ю.С., которые рассматривали подобные проблемы.
В настоящее время системы сетевого планирования и управления используются как инструмент для решения задач планирования, возникающих в различных областях деятельности человека. Наиболее целесообразными областями применения сетевого планирования и управления являются:
целевые разработки сложных систем (проектирование, опытное
производство, испытания и т.д.);
планирование деятельности предприятий типа НИИ, ОКБ,
проектных институтов;
строительство и монтаж промышленных и гражданских объектов;
реконструкция и ремонт;
подготовка и освоение производства новых видов продукции;
материально-техническое снабжение крупных промышленных и гражданских объектов;
ремонт промышленного оборудования;
подготовка и проведение крупномасштабных мероприятий. Цели и задачи исследования
Целью диссертационной работы является исследование задач и методов распределения и упорядочения ресурсов в многостадийных производственных системах, построение общей математической модели, ее исследование, как в каноническом случае, так и в случае нечетких условий, постановки оптимизационных задач, разработка алгоритмов решения и создание на их основе диалоговой программной системы решения задач распределения ресурсов и упорядочения работ.
В соответствии с этой целью в диссертационной работе поставлены и решены следующие задачи:
проведена классификация моделей распределения ресурсов;
проведена классификация и сравнительный анализ методов сетевого планирования;
построена общая математическая модель и поставлены
оптимизационные задачи распределения ресурсов и упорядочения
работ в многостадийных системах как в каноническом случае, так и
в случае с нечеткими стоимостными и временными
характеристиками;
разработаны методы решения задач рассматриваемого класса;
создана диалоговая система решения задач распределения и
упорядочения в многостадийных системах с нечеткими
стоимостными и временными характеристиками.
Научная новизна
Проведена классификация моделей и методов решения задач распределения и упорядочения.
Построена общая математическая модель распределения и упорядочения, отличающаяся от известных ранее наличием как детерминированных, так и нечетких элементов.
Показано, что в рамках построенной модели формализуется широкий класс классических задач дискретной оптимизации, таких,как задача коммивояжера, нескольких коммивояжеров, задача о ранце, многомерная задача о ранце, классические задачи теории расписаний (Задачи Джонсона, задачи Беллмана-Джонсона и др.).
Разработана совокупность эвристических алгоритмов, использующих идеологию "жадных" алгоритмов как в детерминированном, так и в случае нечетких структур.
Предложена схема оценки результата решения задачи не только по значениям формализованных критериев оптимальности, но и по обобщенным характеристикам, следующим из иерархичности рассматриваемых задач -иерархичность изделий, иерархичность ресурсов, иерархичность во времени.
Создана диалоговая программная система, позволяющая решать болыиеразмерные многостадийные задачи распределения и упорядочения.
Практическая ценность
В рамках построенной общей математической модели ставятся различные оптимизационные задачи планирования и управления для производственных систем (задачи перспективного планирования и оперативного управления), для научно-исследовательских институтов, обладающих собственной производственной базой (планирование и управление НИОКР) и др.
Практическая ценность диссертационной работы состоит в разработке и реализации диалоговой системы решения задач распределения ресурсов и упорядочения работ в сетевых канонических структурах. В 2004 году диалоговая программная система "Распределение и упорядочение работ", составляющая прикладную часть диссертационной работы, была передана для опытной эксплуатации в ФГУП НИИИС им. Ю.Е. Седакова (г. Нижний Новгород). Результаты прошли практическую апробацию
при составлении оптимальных план - графиков по работам и по ресурсам в инструментальном производстве при планировании процесса производства пресс-форм.
Результаты диссертационной работы используются в учебном процессе Нижегородского государственного университета им. Н.И. Лобачевского на факультете вычислительной математики и кибернетики (курсы «Моделирование сложных систем» и «Современные технологии решения прикладных задач»). Научные результаты были изложены и опубликованы в 10 работах, обсуждались на Всероссийских совещаниях-семинарах «Математическое обеспечение информационных технологий в технике, образовании и медицине» (Воронеж, 1996г., 1997г.), на XII Международной конференции «Проблемы теоретической кибернетики» (Н. Новгород, 1999г.), на Всероссийской конференции «Интеллектуальные информационные системы» (Воронеж, 1999г.), на конференции, посвященной 80-летию Ю. И. Неймарка (Н.Новгород, 2000г.), на семинарах кафедры информатики и автоматизации научных исследований факультета ВМК ННГУ.
Структура и содержание работы
Диссертационная работа состоит из введения, четырех глав, заключения, списка использованной литературы и приложений.
Во введении отражена актуальность задач распределения ресурсов и упорядочения работ. Отражены цели и задачи исследования, научная новизна и практическая ценность диссертационной работы.
В первой главе проведена классификация задач распределения ресурсов и упорядочения работ. Проведен анализ моделей и методов решения задач распределения и упорядочения в сетевых
канонических структурах, а также в многостадийных системах. Введены понятия нечетких множеств, нечетких чисел. Рассмотрены подходы в задании арифметических операций над ними, а таюке операций сравнения нечетких чисел. Рассмотрена актуальность применения нечетких чисел в задачах распределения и упорядочения работ.
Во второй главе рассматривается общая математическая модель и постановки оптимизационных задач распределения ресурсов и упорядочения работ в многостадийных системах. Модель исследована на существование допустимых решений. Показано, что рассматриваемая проблема распределения ресурсов относится к классу NP-трудных. Приведены формулировки оптимизационных задач, в рамках которых ставятся такие хорошо известные классические задачи как задача коммивояжера, задача нескольких коммивояжеров, задача о ранце, задача о назначениях. Производится обобщение общей математической модели на случай нечетких стоимостных и временных характеристик.
В третьей главе описаны алгоритмы решения многостадийных задач распределения и упорядочения. Предлагаются ряд эвристических алгоритмов, относящихся к классу жадных алгоритмов. Использование жадных алгоритмов обусловлено большой размерностью задач. В настоящей работе, под жадными алгоритмами понимаются такие алгоритмы, в которых включенная в стоящееся расписание работа не может быть исключена из него на последующих шагах построения расписания. Рассматриваются алгоритмы стохастического направленного поиска. Например, алгоритм Метрополиса, основанный на аналогии между процессом поиска решения и моделью процесса охлаждения
термодинамической системы. Предлагается схема
последовательного использования алгоритмов для локального улучшения решения.
В четвертой главе описывается диалоговая программная система для решения задач рассматриваемого класса с помощью разработанных алгоритмов. Приводятся типовые сценарии решения прикладных задач и описываются конкретные примеры решения прикладных задач.
В приложении содержатся документы, подтверждающие внедрение результатов диссертационной работы, выходные формы и результаты решения задач.
Выполненные соискателем исследования поддержаны Российским фондом фундаментальных исследований (грант 97-01-01095 (1997/99 гг.) - "Многокритериальные задачи распределения и упорядочения", и грант 00-01-00384 (2000/02 гг.) - "Задачи распределительного типа с иерархическими критериями").
