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

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

ПОПОВ Денис Валериевич

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

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

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Нижний Новгород 2004

Работа выполнена на кафедре "Информатики и автоматизации научных исследований" Нижегородского государственного университета им. Н.И. Лобачевского

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

доктор технических наук, профессор, ПРИЛУЦКИЙ М.Х. Официальные оппоненты:

Доктор технических наук, профессор ФЕДОСЕНКО Ю.С.

Кандидат технических наук, старший научный сотрудник ВЛАСОВ С.Е.

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

Институт Проблем Управления РАН

Защита диссертации состоится «2-У» Сд-ОиЯ. 2004г.

в « /&> часов на заседании диссертационного совета Д.212.166.13 в Нижегородском Государственном Университете им. Н.И. Лобачевского по адресу 603600, Нижний Новгород, пр. Гагарина 23, корп. 2, конференц-зал.

С диссертацией можно ознакомиться в фундаментальной библиотеке ННГУ. Автореферат разослан «2-/ » 2004г.

Ученый секретарь диссертационного совета

Д.212.166.13 в ННГУ к.ф.-м.н., доцент

В.П.Савельев

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

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

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

Экстремальные задачи распределения ресурсов были сформулированы в 50-х годах. До этого момента планирование носило не систематический характер. Начались интенсивные и систематические исследования по построению и анализу математических моделей календарного планирования. Появились новые методы решения задач распределения ресурсов, которые легли в основу сетевого планирования.

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

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

РОС. национальная] ,

библиотека i ст

03

Шкурба В.В., Подчасова Т.П., Бурдюк В.Я., Танаев B.C., Гордон B.C., Михалевич B.C., Шор Н.З., Мироносецкий Н.Б. и другие. Из зарубежных ученых это Конвей Р., Джонсон Б., Максвелл У., Гиффлер Б., Томпсон Ж. и другие. Следует отметить школу Нижегородского университета и ученых Батищева Д.И., Прилуцкого М.Х., Когана Д.И., Федосенко Ю.С.

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

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

описывать недетерминированные стоимостные и временные параметры производственных систем.

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

В соответствии с этой целью в диссертационной работе поставлены и решены следующие задачи:

• проведена классификация моделей распределения ресурсов и упорядочения работ;

• проведена классификация и сравнительный анализ методов многоресурсного сетевого планирования;

• построена общая математическая модель и поставлены оптимизационные задачи распределения ресурсов и упорядочения работ в многостадийных системах, как в каноническом случае, так и в случае с нечеткими стоимостными и временными характеристиками;

• разработаны методы решения задач рассматриваемого класса;

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

Научная новизна. В диссертационной работе получены следующие основные результаты:

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

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

ранце, классические задачи теории расписаний (Задачи Джонсона, задачи Беллмана-Джонсона, задачи Гиффлера-Томпсона и др.)

3. Разработана совокупность эвристических алгоритмов, использующих "greedy" - идеологию, процедуры направленного перебора, стохастического поиска (алгоритм Метрополиса) и другие.

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

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

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

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

В 2004 году диалоговая программная система "Распределение и упорядочение работ", составляющая прикладную часть диссертационной работы, была передана для опытной эксплуатации в ФГУП НИИИС им. Ю.Е. Седакова (Н.Новгород). Результаты прошли практическую апробацию при составлении оптимальных план -графиков по работам и по ресурсам в инструментальном производстве при планировании процесса производства пресс-форм. Эффективность полученных результатов свидетельствует об адекватности используемых математических моделей условиям производства. Результаты диссертационной работы используются в

А

учебном процессе Нижегородского государственного университета им. Н И. Лобачевского на факультете вычислительной математики и кибернетики-

Апробация работы. Результаты диссертационной работы докладывались на Всероссийских совещаниях-семинарах «Математическое обеспечение информационных технологий в технике, образовании и медицине» (Воронеж, 1996г., 1997г.). на XII Международной конференции «Проблемы теоретической кибернетики» (Н. Новгород, 1999г.)» на ХЬой Всероссийской конференции "Математическое программирование и приложения» (Екатеринбург, февраль 1999г.), на Всероссийской конференции. «Интеллектуальные информационные системы» (Воронеж 1999), на конференции, посвященной- 80-летию Ю. И. Неймарка (Н Новгород, 2000), на семинарах кафедры информатики и автоматизации научных исследований факультета ВМК ННГУ.

Публикации. Научные результаты были изложены и опубликованы в 10 работах, названия которых приведены в конце автореферата.

Структура и объем диссертации. Работа состоит из введения, четырех глав, заключения, списка литературы и приложений. Основное содержание изложено на 120 страницах машинописного текста и иллюстрировано 26 рисунками. Список литературы содержит 135 наименований.

Содержание диссертации

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

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

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

взаимозаменяемыми- станками. Классификация задач проведена по следующим критериям: степень информированности при решении задачи, структура объекта, характер выполнения работ, вид сетевой модели. В параграфе также рассмотрены такие хорошо известные методы решения задач на сетевых графиках как метод критического пути (Critical Path Method - СРМ) а также метод типа метода оценки и пересмотра программ (Program Evaluation and Review Technique - PERT).

В параграфе 1.2 рассматриваются задачи распределения и упорядочения в многостадийных системах на примере задачи Гиффлера-Томпсона.

В параграфе 1.3 вводятся понятия нечеткого множества; функции принадлежности нечеткого множества, нечетких чисел. Рассматриваются различные способы задания нечетких чисел. Вводятся арифметические операции на множестве нечетких чисел при помощи обобщения принципа расширения. Отмечается, что подобный способ задания операций на множестве нечетких чисел эквивалентен методам, применяющимся при нечетких рассуждениях. Пусть заданы два нечетких числа Л =<fj-,R> uB=</ij,R>, где jj* и Mg> соответственно, функции

принадлежности нечетких чисел А и в, R- множество действительных чисел. Если через X обозначить бинарную < операцию (сложение, вычитание, умножение, деление), то нечеткое число С = АХВ может быть определено следующим образом:

С =<^(г) = шах[^/-(л)лni(у)],R>, где ал£> = тш(а,£), ае R,be R

В параграфе также рассматриваются-различные подходы, применяемые при сравнении нечетких чисел между собой. Пусть заданы два нечетких числа А »В. Будем творить, что нечеткое число А меньше или равно нечеткого числа.в и записывать это как А*=В, если,- COG(ftA) S COG(fit), где- COG-операция нахождения центра тяжести функции принадлежности. Отсюда нетрудно определить и понятие равенства нечетких чисел: (С(Ю(рц)£С(Ю(рг) и СОС(//4)5COG(jix)).

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

к

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

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

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

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

Пусть J - конечное множество работ, L(j) - конечное множество операций, соответствующих работе, ¡е}. На множествах L(j) заданы антирефлексивные транзитивные отношения линейного порядка - означает,

что операция аj работы j должна быть выполнена раньше операции Ь, работище,!.

I - конечное множество машин, на котором задано отношение эквивалентности П, разбивающее множество I на классы эквивалентности - стадии (однотипных машин). Пусть К - множество стадий. Линейный порядок, заданный на множествах

операций определяет для каждой работы j набор 7* — {г^г^^—гГ^ ) где г*— номер

I

стадии, на которой должна выполняться /-тая операция работы

Временные характеристики (могут быть заданы нечеткими числами):

Обозначим через 7 .- время выполнения /-ой операции работы у (на стадии г..) на Щ У'

машине »',

время переналадки машины I с работы а на работу ¡е

Гф - время наладки машины »' на /-тую операцию работы]\

а-Директивный срок завершения последней операции работы ] ^У,

Стоимостные характеристики (могут быть заданы нечеткими числами) су - затраты за единицу времени выполнения работы ] на машине {стадии /;

затраты за единицу времени переналадки машины / с работы $ на работу };

¡5 - затратный коэффициент, определяющий штрафные санкции, связанные с

нарушением работой ) определенного для этой работы директивного срока, Варьируемые параметры математической модели Детерминированные параметры

Обозначим через У={ув|, ¡€1,/ = 1,* уи|б (0,1}, Уу1=1. если 1-ая операция

.¡-ой работы выполняется на ¡-ой машине; -Уу/=0. если 1-ая операция .¡-ой работы не

выполняется на ¡-ой машине;

2 =| г,/е/, jeJ, / = 1,Лу), где г^ - номер по'порядку выполнения 1-ой

операции ¡-ой работы на 1-ой машине, г }, ЛГ= £ к, ¡е!;/=ц

Нечеткие варьируемые параметры

Обозначим через X = ( х..^, /£/, / = 1,ку'е У), где х^- время выполнения

операции / работы у на машине /.

В параграфе 2.1.3. рассматриваются ограничения математической модели. 0|раничения математической модели также распадаются на два типа: детерминированные ограничения и нечеткие ограничения.

Летерминированиые ограничения

/€/ 1

(Каждая операция любой работы выполняется на одной машине)

уе (0,11, г„,е{0,1...../У)иеи = иу, jeJ.

(Естественные условия на введенные переменные). Нечеткие ограничения • Ее л и у и| = 1 то ЗГ.( 5 х^ _, + 7у _,, 1=2ТТ, <6/.

(Начало любой операции может наступить лишь после завершения всех операций, ей предшествующих по технологии)

Если у. =1 у. =1, г...-г. Н тог... Ъх. +Г...+?. .. |'е/, *=Ц, /=ЕГ, уе/, У б У.

'у/ (VI у/ IV* у/ (И у/ ну * 1

(Начало выполнения любой ■ работы - на машине может начаться лишь после завершения выполнения на этой машине предыдущей работы). х^ Ъгф.еитг,), =1Де1,/ = 1,*; jeJ.

(Момент начала выполнения самой первой для машины операции может наступить лишь после наладки машины на эту работу)

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

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

• частные критерий, учитывающие штрафные санкции, связанные с нарушением директивных сроков, определенных для работы '¡,

• частные критерии, связанные с затратами на переналадки машины Ц ¡61:

• частные критерии, связанны с затратами на выполнение на машинах операций для работы с номером

В качестве свертки частных критериев оптимальности выбирается аддитивная свертка как внутри групп частных критериев, так и между группами:

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

В главе 3 рассматриваются эвристические алгоритмы решения оптимизационных задач распределения ресурсов и упорядочения работ в многостадийных системах с нечеткими временными и стоимостными характеристиками. Разработаны эвристические алгоритмы решения оптимизационных задач, в основу которых заложены "greedy" - идеология, процедуры направленного перебора, стохастического поиска (алгоритм Метрополиса) и другие.

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

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

jeJ «I JtJ

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

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

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

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

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

Разработанные алгоритмы были реализованы в виде диалоговой программной системы «Распределение ресурсов и упорядочение работ» (среда Windows XP, компилятор Visual C++ 7.0). С помощью программной системы были решены как тестовые задачи, позволяющие определять оценки используемых алгоритмов, так и реальные задачи составления расписаний выполнения работ

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

Основные результаты

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

• Проведена классификация моделей распределения ресурсов и упорядочения работ

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

• Отмечено, что ее средствами можно описать такие известные оптимизационные задачи как различного типа задачи коммивояжера, задача о назначениях, задача о ранце (в том числе многомерном) и др.; при этом допускаются как канонические постановки, так и постановки с нечеткими параметрами

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

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

• Рассмотрены способы задания нечетких арифметических операций на множестве нечетких чисел.

• Разработаны эвристические алгоритмы решения оптимизационных задач, в основу которых заложены "greedy" - идеология, процедуры направленного перебора, стохастического поиска (алгоритм Метрополиса), стратегии локального улучшения расписания.

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

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

' использующий геометрический кластерный алгоритм силовой укладки графа.

• Показана применимость способа визуализации произвольного нечеткого бинарного отношения при помощи указанного алгоритма.

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

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

Публикации.

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

1.Прилуцкий М.Х., Попов Д.В. Реализация "жадных" алгоритмов для одного класса задач теории расписаний. // Тезисы докладов Всероссийского совещания "Математическое обеспечение информационных технологий в технике, образовании и медицине", Воронеж, 1996, С.53-54.

2.Прилуцкий М.Х., Попов Д.В. Эвристические процедуры решения большеразмерных задач упорядочения. // Тезисы докладов Всероссийского совещания "Математическое обеспечение информационных технологий в технике, образовании и медицине", Воронеж, 1998, С. 27

3.М.Х.Прилуцкий, Д.В.Попов, Многостадийные большеразмерпые задачи теории расписаний. // Тезисы доклада на М-ой Всероссийской конференции "Математическое программирование и приложения", Екатеринбург, февраль 1999г., С. 124

4.М.Х.Прилуцкий, Д.В.Попов "Распределение и упорядочение работ в многостадийных системах"// Моделирование и оптимизация сложных систем.

Межвузовский тематический сборник научных трудов. ВГАВТ Н.Новгород, 1999, С. 123-130

5.Попов Д.В. "Программные средства решения многостадийных задач теории расписаний. Результаты вычислительного эксперимента" // Моделирование и оптимизация сложных систем. Межвузовский тематический сборник научных трудов ВГАВТ. Н. Новгород, 1999, С. 117-122

6.Прилуцкий М.Х., Кумагина Е.А., Попов Д.В. Многостадийные задачи распределения и упорядочения // Тезисы докладов на XII Международной конференции "Проблемы теоретической кибернетики", часть II — М.: Изд-во механико-математического ф-та МГУ, 1999, С. 193

7.Д.В. Попов. Многостадийные задачи теории расписаний. Алгоритмы и реализации. // Вестник ННГУ. Математическое моделирование и оптимальное управление, 1(20) Н.Новгород, 1999, С. 262

8.Прилуцкий М.Х., Попов Д.В. Многостадийные задачи распределения и упорядочения с нечеткими характеристиками // Электронный журнал "Исследовано в России", 2001,043/010331, С. 476-484 (http://zhurnal.ape.relarn.ru/articles/2001/043.pdf.

9.Прилуцкий М.Х., Нефедов Д.С., Попов Д.В. Распределение ресурсов в дискретно управляемых системах // Электронный журнал "Исследовано в России", 2002,032/020228, С. 322-337 (httn://zhurnal.ape.relam.ru/articles/2002/032.pdf)

10.Прилуцкий М.Х., Попов Д.В. Многостадийные задачи теории расписаний с нечеткими характеристиками // Сборник научных статей «Математика и кибернетика», ННГУ, Н.Новгород 2003, С. 243-252

Подписано в печать 17.05.2004. Формат 60x84 1/16. Бумага офсетная. Печать офсетная. Усл. печ. л. 1. Тнр. 100 экз. Зак. 664.

Типография Нижегородского госуниверситета. Лицензия № 18-0099. 603000, Н. Новгород, ул. Б. Покровская, 37.

Введение.

Глава 1. Задачи распределения ресурсов и упорядочения работ в сетевых структурах.

1.1 Задачи распределения и упорядочения в сетевых канонических структурах.

1.1.1. Классификация задач распределения и упорядочения.

1.1.2 Задачи распределения ресурсов.

1.1.3. Задачи сетевого планирования.

1.1.4. Задачи упорядочения.

1.2 Задачи распределения и упорядочения в многостадийных системах.

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

1.3.1 Нечеткие множества.

1.3.2. Нечеткие числа.

1.3.3. Операции над нечеткими числами.

1.3.4. Операции сравнения нечетких чисел.

1.3.5. Определение нечетких бинарных отношений <, =,> на множестве нечетких чисел

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

Выводы по главе 1.

Глава 2. Многостадийные задачи распределения ресурсов и упорядочения работ.

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

2.1.1. Исходные параметры математической модели.

2.1.2. Варьируемые параметры математической модели.

2.1.3. Ограничения математической модели.

2.2. Исследование общей математической модели.

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

2.3.1. Частные критерии оптимальности.

2.3.2. Постановка классических задач дискретной оптимизации в рамках построенной математической модели.

Выводы по главе 2.

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

3.1. Жадные алгоритмы решения задач распределения и упорядочения.

3.2. Детерминированные алгоритмы ограниченного перебора.

3.2.1. Алгоритм - построитель расписания А(Р).

3.2.2 Ар Алгоритм поиска перестановки Р с глубиной h.

3.2.3 A3: Метод локального улучшения расписания.

3.2.4 А*: Алгоритм критического пути.

3.3 Стохастические алгоритмы решения задач распределения и упорядочения

3.3.1. А2: Алгоритмы Метрополиса (Simulated Annealing).

3.3.3 Управление процессом решения задачи путем взаимозависимого применения различных алгоритмов.

3.3.4. Реализация нечетких расписаний при организации производственного процесса.

Выводы по главе 3.

Глава 4. Программные средства решения задач распределения ресурсов и упорядочения работ в многостадийных системах с нечеткими характеристиками.

4.1. Процедуры интерактивного взаимодействия.

4.2. Реализация механизма построений различных отображений задачи.

4.2.1. Сравнение различных схем отображений результатов решения задачи.

4.2.2. Математическая модель интерфейса с использованием аппарата нечетких множеств.

4.3. Реализация механизма сравнения различных отображений задачи.

4.4. Решение прикладных задач распределения и упорядочения.

4.4.1 Численный эксперимент для оценки производительности групп жадных алгоритмов для построения расписания в многостадийных системах.

4.4.2 Построение расписания изготовления пресс-форм в инструментальном цехе.

Выводы по главе 4.

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

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

Экстремальные задачи распределения ресурсов были сформулированы в 50-х годах. До этого момента планирование носило не систематический характер. Начались интенсивные и систематические исследования по построению и анализу математических моделей календарного планирования. Появились новые методы решения задач распределения ресурсов, которые легли в основу сетевого планирования.

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

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

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

Развитием этой научной области занимались такие ученые как Шкурба В.В., Подчасова Т.П., Бурдюк В.Я., Танаев B.C., Гордон B.C., Михалевич B.C., Шор Н.З., Мироносецкий Н.Б., Португал В.М. и многие другие. Из зарубежных ученых это Конвей Р., Джонсон Б., Максвелл У., Гиффлер Б., Томпсон Ж. и другие. Следует отметить школу Нижегородского университета и ученых Батищева Д.И., Прилуцкого М.Х., Когана Д.И., Федосенко Ю.С., которые рассматривали подобные проблемы.

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

• целевые разработки сложных систем (проектирование, опытное производство, испытания и т.д.);

• планирование деятельности предприятий типа НИИ, ОКБ, проектных институтов;

• строительство и монтаж промышленных и гражданских объектов;

• реконструкция и ремонт;

• подготовка и освоение производства новых видов продукции;

• материально-техническое снабжение крупных промышленных и гражданских объектов;

• ремонт промышленного оборудования;

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

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

В соответствии с этой целью в диссертационной работе поставлены и решены следующие задачи:

• проведена классификация моделей распределения ресурсов;

• проведена классификация и сравнительный анализ методов сетевого планирования;

• построена общая математическая модель и поставлены оптимизационные задачи распределения ресурсов и упорядочения работ в многостадийных системах как в каноническом случае, так и в случае с нечеткими стоимостными и временными характеристиками;

• разработаны методы решения задач рассматриваемого класса;

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

Научная новизна

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

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

3. Показано, что в рамках построенной модели формализуется широкий класс классических задач дискретной оптимизации, таких,как задача коммивояжера, нескольких коммивояжеров, задача о ранце, многомерная задача о ранце, классические задачи теории расписаний (Задачи Джонсона, задачи Беллмана-Джонсона и др.).

4. Разработана совокупность эвристических алгоритмов, использующих идеологию "жадных" алгоритмов как в детерминированном, так и в случае нечетких структур.

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

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

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

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

Практическая ценность диссертационной работы состоит в разработке и реализации диалоговой системы решения задач распределения ресурсов и упорядочения работ в сетевых канонических структурах. В 2004 году диалоговая программная система "Распределение и упорядочение работ", составляющая прикладную часть диссертационной работы, была передана для опытной эксплуатации в ФГУП НИИИС им. Ю.Е. Седакова (г. Нижний Новгород). Результаты прошли практическую апробацию при составлении оптимальных план - графиков по работам и по ресурсам в инструментальном производстве при планировании процесса производства пресс-форм.

Результаты диссертационной работы используются в учебном процессе Нижегородского государственного университета им. Н.И. Лобачевского на факультете вычислительной математики и кибернетики (курсы «Моделирование сложных систем» и «Современные технологии решения прикладных задач»). Научные результаты были изложены и опубликованы в 10 работах, обсуждались на Всероссийских совещаниях-семинарах «Математическое обеспечение информационных технологий в технике, образовании и медицине» (Воронеж, 1996г., 1997г.), на XII Международной конференции «Проблемы теоретической кибернетики» (Н. Новгород, 1999г.), на Всероссийской конференции «Интеллектуальные информационные системы» (Воронеж, 1999г.), на конференции, посвященной 80-летию Ю. И. Неймарка (Н.Новгород, 2000г.), на семинарах кафедры информатики и автоматизации научных исследований факультета ВМК ННГУ.

Структура и содержание работы

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

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

• Проведена классификация моделей распределения ресурсов и упорядочения работ.

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

• Отмечено, что ее средствами можно описать такие известные оптимизационные задачи как различного типа задачи коммивояжера, задача о назначениях, задача о ранце (в том числе многомерном) и др.; при этом допускаются как канонические постановки, так и постановки с нечеткими параметрами.

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

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

• Рассмотрены способы задания нечетких арифметических операций на множестве нечетких чисел.

• Разработаны эвристические алгоритмы решения оптимизационных задач, в основу которых заложены "greedy" - идеология, процедуры направленного перебора, стохастического поиска (алгоритм Метрополиса), стратегии локального улучшения расписания.

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

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

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

Заключение

1. Аснина А .Я., Чернышева Г.д. Об одном алгоритме решения задачи Джонсона 1. Тр. 4-й Межд. конф. женщин-матем. Волгоград, 27-31 мая, Т.4, Вып.1, Н.Новгород, 1997.- с. 82-86.

2. Ахьюджа Х.Н. Сетевые методы в проектировании и производстве. М.: Мир. 1979.-638с.

3. Батищев Д. И., Громницкий B.C. Распределение ограниченных ресурсов по принципу гарантированного результата // В кн. Кибернетика и ВУЗ. Вып. 17. Томск. 1982, с 34-41.

4. Батищев Д. И., Гудман Э.Д., Норенков И. П., Прилуцкий М.Х. Метод декомпозиций для решения комбинаторных задач упорядочения и распределения ресурсов. Информационные технологии, 1997 №1, с.28 -33.

5. Батищев Д. И., Гудман Э. Д., Норенков И.П., Прилуцкий М.Х. Метод комбинированных эвристик для решения комбинаторных задач упорядочения и распределения ресурсов. Информационные технологии, 1997 №2, с. 29-32.

6. Батищев Д. И., Прилуцкий М. X. Многокритериальное распределение разнородных ресурсов на совокупности канонических сетевых моделей // 33 Intern. Wiss. Koll. Thllmenau, 1998, c.35-42.

7. Булгак А.С. Многокритериальная задача теории расписаний с ресурсами складируемого типа // АиТ. 1987. №12. - С. 143146.

8. Вахания Н.Н. Построение сокращенного дерева вариантов для общей задачи теории расписаний // Дискр. Матем. Т.2.- Вып.З. 1990, с. 10-20.

9. Вахания Н.Н., Шафранский В.В. Алгоритмы решения обобщенных задач теории расписаний // Сообщения по прикладной матем. М.: ВЦ РАН, 1991 с. 1-46.

10. Витковский Я.Я. Основы сетевого планирования и управления.//Рига, 1966, 236с.

11. Волчкова Г.П. Один метод построения допустимых расписаний. //Тез. докл. Гродн. гос. уп-т. Гродно, 1992, 3536.

12. Гейл Д. Теория линейных экономических моделей — М.: Иностранная литература, 1963, 415с.

13. Гимади Э. X. О некоторых моделях и методах планирования крупномасштабных проектов // Тр. Ин-та Новосиб. 1988. Т.10, с. 89-115.

14. Голенко Д. И. Статистическое моделирование в технико-экономических системах Л.: Изд-во Лен. ун-та. 1977. 264с.

15. Гревцов О.И. Нахождение оптимального решения многокритериальных задач // Вестн. Самарск. гос. тех. у-та.-1998. №6. с.135-136.

16. Турин Л. С., Дымарский Я. С., Меркулов А. Д. Задачи и методы оптимального распределения ресурсов.- М.: Сов. радио, 1968, 245с.

17. Гэри Н., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1992.

18. Давыдов Э. Г. Игры, графы, ресурсы.- М.: Радио и связь, 1981.

19. Давыдов Э. Г Исследование операций М Вьисш шк, 1981 -383с

20. Давыдов Э. Г. О распределении ресурсов на сетях // Сб. Системы распределения ресурсов на графах.-М.: ВЦ АН СССР, 1970.

21. Давыдов Э. Г., Большаков С.Ю. Теоретико-групповые методы агрегирования в сетевых задачах.- М.: ВЦ АН СССР, 1986.

22. Давыдов Э. Г., Злобина С.В. Применение геометрического программирования к сетевому планированию.- М.: ВЦ АН СССР, 1981.

23. Давыдов Э. Г., Исиченко И. В. Некоторые дискретные задачи теории управления.- ВЦ АН СССР, 1988., 209с.

24. Деггярев Ю. И. Исследование операций. М.: Высшая школаД986 ,213с.

25. Задачи календарного планирования и методы их решения,-Киев: Наукова думка, 1966.

26. Заруба В.Я. Процедуры активного планирования при распределении ограниченного ресурса // АиТ.- 1990.- №7.-С.41-56.

27. Зуховицкий С.М., Радчик И.А. Математические методы сетевого планирования. М. :Наука,1965.

28. Исследование операций. Под ред. дж. Моудера, С. Эдмаграби-М.: Мир, 1981.

29. Калачев В.Н., Кривоноженко В.Е., Немчинов Б.В. Задачи планирования в гибких производственных системах /1 АиТ. — 1995. К26, с. 155-164.

30. Козлов М.К., Шафранский В.В. Календарное планирование выполнения комплексов работ при заданной динамике поступления складируемых ресурсов.- Известия АН СССР. Технич. кибернетика, 1977,У с. 75-8 1; 1977, К251, с. 38-43.

31. Компьютер и задачи выбора. М. :Наука,1989,125с.

32. Конвей Р.В., Максвелл B.JL, Миллер Л.В. Теория расписаний. М.:Наука, 1975.

33. Кривцов A.M., Шеховцев В.В. Сетевое планирование и управление — М.: Экономика. 1978.191с.

34. Кропачев С.В., Наумов Е.А. Программно-целевое управление решением научно-технических проблем / АН СССР Сиб. Отд. Ин-т эконом.и орг. пром. пр-ва. Новосибирск.: Наука Сиб. отд. 1989.

35. Кумагина Е.А. Задачи распределения ресурсов и упорядочения работ // Вычислительная математика и кибернетика 2000: Конференция, посвященная 80-летию Ю.И.Неймарка/ Тезисы докладов. Нижний Новгород: Изд-во 1-ЮГУ, 2000. С.49.

36. Кумагина Е.А. Об одном подходе к решению задач упорядочения. // Труды Всероссийской конференции

37. Интеллектуальные информационные системы" Воронеж 2325 июля 1999. С.61-63.

38. Курицкий Б.Я. Методы оптимизации сетевых планов,-Л.:ЛДНТП, 1976, 31с.

39. Левнер Е.В., Немировский А.С. Задача сетевого планирования в постановке «точно вовремя» и потоковые алгоритмы ее решения. // Численные методы оптимизации и анализа. Новосибирск: Сиб. энерг. ин-т, 1992, с. 18-35.

40. Липский В. Комбинаторика для программистов М.:Мир, 1988.

41. Майзер X., Эйджин Н., Тролл Р. Исследование операций / в 2-х томах. Пер. с англ. М.: Мир, 1981.

42. Максимов Ю.И. Сетевые модели в перспективном планировании отраслевых систем- Новосиб.: Наука Сиб. Отд. 1979.143с.

43. Мироносецкий Н.Б. Экономико-математические методы календарного планирования.- Новосибирск: Наука, 1973.

44. Михалевич B.C., Кукса А.И. Методы последовательной оптимизации в дискретных сетевых задачах оптимального распределения ресурсов. М.: Наука, 1983.-208 с.

45. Мищенко А.В. Устойчивость решений задачи оптимального распределения ресурсов при динамичеком изменении структуры сети М.ВЦАНСССР 1980. 12с.

46. Мищенко А.В. Устойчивость решений задачи оптимального распределения ресурсов при динамичеком изменении структуры сети М.-.ВЦАНСССР 1980.12с.

47. Мищенко А.В., Сушков Б.Г. Минимизация времени выполнения работ, представленных сетевой моделью, принефиксированньих параметрах сети- М.: ВЦ АН СССР 1980. 25 с.

48. Новицкий Н.И. Сетевое планирование и управление производством — Минск: Беларусь 1976. 80с.

49. Орловский С.А. Проблемы принятия решений при нечеткой исходной информации. М: Наука, 1981, 203с.

50. Палов А.А., Мисюра Е.Б., Михайлов В.В. Исследование задачи минимизации суммарного взвешенного момента окончания выполнения множества заданий с директивными сроками. II Киевский политехи, ин т. Киев, 1993.

51. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация.— М.: Мир, 1985.

52. Попова Е.В. Исследование мощности множества альтернатив двукритериальной задачи инвестора. // Карачаево-Черкесский Тех. Ин- т.- Черкесск, 1996. 16с.

53. Португал В.М., Семенов А.И. Модели планирования на предприятии- М.: Наука 1978. 269с.

54. Поспелов Г.С., Гейман А.И. Автоматизация процессов управления разработками больших систем или сложных комплексов,- М.: Известия АН СССР. Техническая кибернетика. 1963.

55. Поспелов Г.С., Ириков В.А., Курилов А.Е. Процедуры и алгоритмы формирования комплексных программ.- М.: Наука. 1985. 424с.

56. Прилуцкий М.Х. Математическая модель многокритериального распределения ресурсов на сетях и условие ее разрешимости П Сб. Принятие оптимальных решений в экономических системах. Горький, 1985, с. 62-65.

57. Прилуцкий М.Х. Многокритериальное распределение однородного ресурса в иерархических системах II Автоматика и телемеханика. 1996, С. 24-29.

58. Прилуцкий М.Х., Кумагина Е.А. Задача упорядочения работ как задача о назначениях II Вестник Нижегородского государственного университета. Математическое моделирование и оптимальное управление. Изд-во ИНГУ, 1999. Вып.2(21). С. 18-24.

59. Прилуцкий М.Х., Кумагина Е.А. Перестановочные процедуры решения задач распределения ресурсов. Межвузовский сборник научных трудов «Прикладные задачи моделирования и оптимизации» ч.П, Воронеж, 2000. С.81-90.

60. Прилуцкий М.Х., Кумагина Е.А., Попов д.В. Многостадийные задачи распределения и упорядочения 1/ Тезисы докладов XII Международной конференции теоретической часть II — М.:Изд-во механико-математического ф-та МГУ, 1999. С. 193.

61. Прилуцкий М.Х., Тарбеев А.Ф. Годовое и оперативноепланирование и управление НИОКР в условиях НПО // Сб. Анализ и моделирование экономических процессов. Горький, 1984, с. 68-73.

62. Прилуцкий М.Х., Попов Д.В. Эвристические процедуры решения большеразмерных задач упорядочения. // Тезисы докладов Всероссийского совещания "Математическое обеспечение информационных технологий в технике, образовании и медицине", Воронеж, 1998, С. 14.

63. М.Х.Прилуцкий, Д.В.Попов, Многостадийные болыперазмерные задачи теории расписаний. // Тезисы доклада на XI-ой Всероссийской конференции "Математическое программирование и приложения", Екатеринбург, февраль 1999г., С. 124.

64. М.Х.Прилуцкий, Д.В.Попов "Распределение и упорядочение работ в многостадийных системах"// Моделирование и оптимизация сложных систем. Межвузовский тематический сборник научных трудов. ВГАВТ Н.Новгород, 1999,1. С. 123-130.

65. Д.В.Попов. Многостадийные задачи теории расписаний. Алгоритмы и реализации. // Вестник ННГУ. Математическое моделирование и оптимальное управление, 1(20) Н.Новгород, 1999, С. 262.

66. Прилуцкий М.Х., Попов Д.В. Многостадийные задачи распределения и упорядочения с нечеткими характеристиками // Электронный журнал "Исследовано в России", 2001, 043/010331.С.476-484http.7/zhurnal.ape.relarn.ru/articles/2001/043.pdf).

67. Прилуцкий М.Х., Нефедов Д.С., Попов Д.В. Распределение ресурсов в дискретно управляемых системах // Электронный журнал "Исследовано в России", 2002, 032/020228, С. 322-337 (http://zhurnal.ape.reIarn.ru/articles/2002/032.pdf).

68. Прилуцкий М.Х., Попов Д.В. Многостадийные задачи теории расписаний с нечеткими характеристиками // Сборник научных статей «Математика и кибернетика», ННГУ, Н.Новгород 2003, С. 243-252.

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

70. Прилуцкий М.Х., Кумагина Е.А. Задачи распределения разнородных ресурсов в сетевых канонических структурах // Перспективные информационные технологии и интеллектуальные системы. 2000, №4, стр. 46-52 (http ://pitis .tsure.ru: 810 l/fails4/09 .htm).

71. Прилуцкий M.X., Казанцев Э.Н. Задача планирования для моделей двухстадийных стохастических систем. // Известия АН СССР. Техническая кибернетика. №1,1980, с.3-9.

72. Сетевое планирование при ограниченных нескладируемых ресурсах. Сб. статей под ред. Л.Я. Лефмана.- Новосибирск 1971.

73. Смоляр Л.И Оперативно-календарное планирование. М.: Экономика, 1979.

74. Смоляр Л.И. Теория расписаний и управление. М.: Знание, 1977.

75. Сорокин С.В. Разностные алгоритмы распределения неоднородных целочисленных ресурсов. // Изв. РАН Теория и системы управления 1995.-M26.-c. 2 18-222.

76. Танаев B.C. Теория расписаний. М. :Мир, 1988.

77. Танаев B.C., Гордон B.C., Шафранский Я.М. Теория расписаний. Одностадийные системы М.: Наука, 1984.- 384 с.

78. Танаев B.C., Сотсков Ю.Н., Струсевич В.А. Теория расписаний. Многостадийные системы М.: Наука, 1989.328 с.

79. Танаев B.C., Шкурба В.В. Введение в теорию расписаний. -М.:Наука,1975.

80. Теория расписаний и вычислительные машины. Под ред. Э.Г. Коффмана.- М.:Наука, 1984.

81. Топка В.В. вероятностная модель планирования исследований и разработок с линейными ограничениями. // АиТ. 1997. К с.232.

82. Черенков А.П. Задачи распределения разнотипных ресурсов с насыщением //Журнал вычисл. мат. и мат. физ. 1988. Т. 28, №7, с. 1102-1107.

83. Шахлевич Н.В. Оптимальное обслуживание двух требований в неоднородных системах с прерываниями // 6 Конф. Мат. Беларуси Тез докл. 4.4/ Гродн. Гос. Ун-т. Гродно, 1992. С 105.

84. Шмелев В.В. Динамические задачи календарного планирования // АиТ.-1997.-№1.-с.121-126.

85. Шмелев В.В. Точные штрафные функционалы в задачах календарного планирования // АиТ.- 1999.-№9.-с. 107-114.

86. Экономико-математические модели и методы // Сборник научных трудов. Воронеж ВГТУ 1989.

87. Юдин Д.Б., Гольдштейн Е.Г. Линейное программирование (теория, методы, приложения).- М.: Наука, 1969.

88. Abdul-Razaq T.S., Potts C.N. Dynamic Programming State-Space Relaxation Method For Single-Machine Scheduling // J. Oper. Res. Soc.- 1988.- Vol. 39.-pl41-152.

89. Antill J.M., Woodhead R.W. Critical Path Methods in

90. Construction Practice, Wiley, New York, 1970.

91. Archibald R.D., Villoria R.L, Network-Based Management Systems (PERT/CPM), Wiley, New York, 1968.

92. Artentano Vinicius A., Ronconi Debora P. Tabu-search for total tardiness minimization in flowshop problems // Сотр. and Oper. Res.-1999.- 26, №3, p.219-235.

93. Bar-Ilean, Peleg D. Scheduling job using common resources // Inf. And Сотр. -1996.-№1, p. 52-61.

94. Bellman R. Mathematical Aspects of Scheduling Theory // J. Soc. Indust. and Appl. Math. 1956. V.4 №3. p. 168-205.

95. Bellman R., Gross O. Some Combinatorial Problems Arising in the Theory of Multistage Processes // J. Soc. Indust. and Appl. Math. 1945. V.2№3.p. 175-183.

96. Biskup Dirk, Cheng T.C. Edwin, Multi-machine scheduling with earliness, tardiness and complexion time penalties // Сотр. and Oper. Res.- 1999.- 26,№1, p.45-57.

97. Chun Y., Moskowitz H., Plante R. Sequencing a set of alternatives under time constraints // J. Oper. Res. Soe. 1995.- №6, p. 11331144.

98. Daniel Richard L., Hua Stella Y., Webster Scott. Heuristics for parallel-machine flexible-resource scheduling problems with unspecified job assignment // Сотр. and Oper. Res.- 1999.-26, №2, p. 143-155.

99. Emmons H. One-Machine Sequencing to Minimize Certain Functions of Job Tardiness // Oper. Res. 1969. V.I7 №4. p. 701716.

100. Hariri A.M.A., Potts C.N. Single-machine scheduling with deadlines to minimize the weigthed number of tardy jobs // Man.

101. Sci. 1994.- Vol.40.-№ 12.-р.1712-1719.

102. Healy Thomas L. Activity subdivision and PERT probability statements // Oper. Res. 1961.V.9 №3.

103. Hoogeveen J.A. Oosterhout M., Velde S.L. A new lower bounds approach for single-machine multicriteria scheduling // Rept/ Cent. Math, and Comp.Sci.- 1990.-№BS-R9026. pp. 1-8.

104. Hoogeveen J.A. Oosterhout M., Velde S.L. New lower and upper bounds for scheduling around small common due date // Rept/ Cent. Math, and Comp.Sci.- 1990.-№BS-R9030.-p. 1-11.

105. Janiak A., Kobylaski P. Генетический алгоритм решения перестановочной задачи теории расписаний с ресурсами // Zesz. Nauk. Mech. PSI. 1993.-№4, p. 99-114.

106. Johnson S.M. Optimal Two- and Three-Stage Production Schedules with Setup Times Included //Nav. Res. Log. Quart. 1954 V.l №1. p. 61-68.

107. Khachaturov V.R. Multiextremal allocation problems (models and solutions) // Stud. sci. math, hung.-1992.- № 3, p. 243-260.

108. Lambourn S. Resource allocation and multi-project scheduling. A new tool in planning and control // Comp.J. 1963. № 3.

109. Man Sungsu , Ishii Hiroaki Lexicographical scheduling problem on three machine open shop // Math. Jap.-1991.- 36- №6. p. 10011014.

110. Manne A.S. On the Job-Shop Scheduling Problem // Oper. Res.-1960.-V.8 №2. p. 219-233.

111. Michael David J., Kamburowski J., Stallmann M. On the minimum dummy-arc problem// Rech. oper.-1993.- №2, p. 153-168.

112. Nowicki Eugeniusz Задачи теории расписаний с учетом изменения моментов поступления задач // Arch Autom: Rob1991.-36,№2,р.303-312.

113. Potts C.N., L.N. Van Wassenhove Algoritm For Scheduling a Single Machine To Mminimize the Weigthed Number of Late Jobs //Man. Sci.- 1988.-Vol.34.-p.843-858.

114. Rinnooy Kan A.H., Lageweg В J., Lenstra J.K. Minimizing Total Costs in One-Machine Scheduling // Rech. oper.-1975. vol 23 -№5, p. 908-925.

115. Rogers V.R., White K.P. Algebraic, Mathematical Programming and Network Models of the Deterministic Job-Shop Scheduling Problem // IEEE Trans. On Systems, Man, 1991, №3, p. 693-697.

116. Sharage L. Solving resource-constrained network problem by implicit enumeration: nonpreemptive case // Op. Res.- 1970.- №2, p. 263-278.

117. Velde S.L. & de. Dual composition of a single-machine scheduling problem // Math. Programming A. -1995-69, №3, p.413-428.

118. Volegant A., Teerhuis E. Improved heuristics for the n-job single-machine weighted tardiness problem// Сотр. and Oper. Res.-1999.- 26, №1, p.35-44.

119. Yu Chang Sok, Zimmermann Karol Optimal choice of parameters in machine-time scheduling problem with penalized earliness in start and tardiness in completing the operations // Acta Univ. Carol. Math, and Phys.- 1992.-33, №l.-p.53-61.

120. Yu G. Min-max optimization of several classical discrete optimization problems 11 J. Optimize. Theory and App.- 1998.-№l.-p.221-242.

121. Zaborowski M. Оптимизация планов в системах оперативного управления производством // Arch. Automat i Rob.- 1991.- №2, p. 313-32.

122. Zadeh L.A. Fuzzy set // Information and Control.-1965.-N 8. P. 338.

123. Zadeh L.A. Calculus of fuzzy restrictions // In "Fuzzy sets and its applications to cognitive and decision processes" ed. By Zadeh L.A.- Academic Press , 1975.-P. 1-39.

124. Kirkpatrick S., Gelat C.D., Jr., Veccihi M.P. Optimization by simulated annealing // Science 220,4598, 1983. pp. 671-680

125. Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H., and Teller, E., Equation of state calculations by fast computing machines //J. Chem. Phys. 21, 6, 1953., pp. 1087-1092.

126. Kosko, Bart, Fuzzy Engineering // ISBN 0-130124991-6, 1997., P. 549.131. http://www.primavera.msk.ru/Theorv/theorv.htm Статьи и публикации. Библиотека управления проектами.

127. Р.Беллман, Л.Заде Принятие решений в расплывчатых условиях. Сб. Вопросы анализа и процедуры принятия решений. М. Мир, 1976, с. 172-215.

128. D. Dubous, Н. Prade, Fuzzy Sets and Systems: Theory and Applications, Academic Press, New York, 1980. pp. 156-160

129. Прикладные нечеткие системы: Пер. с япон. // К. Асаи, Д. Ватада, С. Иваи и др. М: Мир, 1993.-368 с.

130. D.P. Filev, R.R. Yager Operations on Fuzzy numbers via fuzzy reasoning // Fuzzy Sets and Systems: Theory and Applications, Academic Press, 91 (1997) pp. 137-142.