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

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

ВЛАСОВ ВАЛЕНТИН СЕРГЕЕВИЧ

УПОРЯДОЧЕНИЕ РАБОТ И РАСПРЕДЕЛЕНИЕ РЕСУРСОВ В КАНОНИЧЕСКИХ СИСТЕМАХ «КОНВЕЙЕР-СЕТЬ»

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

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

-3 ДЕК 2009

Нижний Новгород - 2009

003486650

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

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

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

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

Прилуцкий Михаил Хаимович

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

Федосенко Юрий Семенович

кандидат физико-математических наук доцент

Шапошников Дмитрий Евгеньевич

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

Институт проблем управления РАН (г. Москва)

Че

Защита состоится « УУ » л 2009 г. в

УН

часов на заседании

Диссертационного Совета Д ¿12 166.13 при Нижегородском Государственном Университете им. Н.И.Лобачевского по адресу: 603950, Нижний Новгород, проспект Гагарина, 23.

С диссертацией можно ознакомиться в библиотеке Нижегородского Государственного Университета им. Н.И. Лобачевского.

Автореферат разослан «_»_

2009 г.

Ученый секретарь диссертационного совета кандидат физико-математических нау доцент /£/

Савельев Владимир Петрович

Актуальность темы исследования

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

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

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

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

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

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

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

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

Цели и задачи исследования

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

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

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

- выделен класс задач, относящихся к каноническим системам типа «конвейер-сеть»;

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

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

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

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

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

2. Построены математические модели канонических систем с конвейерными и сетевыми технологиями. Проведено их исследование.

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

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

5. Создана диалоговая программная система решения задач, относящихся к классу задач «конвейер-сеть».

Теоретическая и практическая ценность диссертационной работы

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

Результаты диссертационной работы используются в учебном процессе Нижегородского государственного университета им. Н.И. Лобачевского на факультете вычислительной математики и кибернетики при преподавании курса «Теория систем и системный анализ».

Апробация результатов

Научные результаты диссертационной работы изложены в 14 работах: в 4 статьях в научно-технических журналах, 2 из которых рекомендованы ВАК РФ, 10 тезисов докладов с выступлений на научно-технических конференциях. Результаты докладывались и обсуждались на Всероссийской научно-технической конференции «Информационные системы и технологии» ИСТ-2005 (Н.Новгород, 2005г.), Международных научно-технических конференциях «Информационные системы и технологии» ИСТ-2006, ИСТ-2007, ИСТ-2009 (Н.Новгород, 2006г., 2007г., 2009г.), конференциях «Технологии Microsoft в теории и практике программирования» (Н.Новгород, 2006,2007,2008,2009), XI Нижегородской сессии молодых ученых (Н.Новгород, 2006г.), Международной конференции «Высокопроизводительные параллельные вычисления на кластерных системах» (Н. Новгород 2007г.), Отраслевой конференции Росатом «Высокие технологии атомной отрасли. Молодежь в инновационном процессе» (Н. Новгород, 2007), на семинарах кафедры информатики и автоматизации научных исследований факультета ВМК ННГУ.

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

Структура и объем диссертации.

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

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

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

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

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

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

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

б

При этом

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

• продолжительность осуществления деятельности должна принадлежать заданному интервалу длительностей,

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

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

• деятельности могут объединяться в группы (групповые деятельности), которые должны выполняться последовательно и без перерывов,

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

Перечисленные требования образуют группу условий технологического

типа.

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

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

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

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

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

Глава 2 посвящена рассмотрению математических моделей упорядочения работ и распределения ресурсов в сетевых канонических системах.

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

являются Г = {0,1.....Г0} - множество тактов планирования, 3 - множество всех

работ (деятельностей), а КЦ) - множество работ, непосредственно предшествующих работе с номером}, ки)с У./ - множество различных ресурсов. Через л,- обозначим срок годности ресурса /, ¡е 1,п, е N. Тогда Iм =1'К =1.16/)- множество нескладируемых ресурсов, Iе =(¡1«, >Т0,1'е /}-множество складируемых ресурсов, а = {/12</г,¡<Т0,1е /}- множество частично-складируемых ресурсов.

Пусть V =|| уц || - матрица поступлений ресурсов в систему, где у„ обозначает количество ресурса с номером ¡, которое поступит в систему в такт Г, /е /,/е Т. Я =|| /V || - матрица ресурсоемкостей, где г:1 обозначает количество ресурса с номером /, которое требуется для выполнения работы с номером ], /е 1.

Обозначим через т^Мц - минимальную и максимальную интенсивности потребления работой с номером] ресурса с номера /, 0<ти < А/ < е У, а

через г],г* - минимальную и максимальную длительность выполнения работы Л ■

Пусть С( ./',) - множество групповых работ, начинающихся с работы 6'( Д ] = .Л и,е ^ • Введем множество работ, являющихся начальными для соответствующих им групп - С = 1Х],...,Хк)Л,,—Лк е У. Обозначим через г™" -время пролеживания _/-й работы, где У™ - множество работ, для

которых определено время пролеживания; - межоперационное время

работы, ]е J"'", где ]"" - множество работ, для которых определено межоперационное время.

Через I" обозначим множество работ, имеющих директивные сроки окончания, JDQJ, <¡1 - директивный срок окончания выполнения работы с номером у,

В качестве варьируемых параметров модели выступают вектора X = - вектор времен начала выполнения работ,У = (у,.....у^) - вектор

времен окончания выполнения работ, а также г =|| г,, || - матрица интенсивностей, где гф - интенсивность потребления ресурса с номером / работой с номером} в такт времени Г, ¡е У,ге Т.

Ограничения математической модели Естественные ограничения на переменные: х, е Т,у/ б ТЛц, г о, 16 Т.

Ограничения каноничности модели: лг,>у„ ЫK{j\j^J.

Ограничения на интенсивность потребления ресурсов: ™„ ^ < М,,если Г е / хгу/] 1ц, = о,если Ч[х),у/]; Ограничения на длительности выполнения работ: Ч - У¡~Х1 -'

Ограничения на использование ресурсов:

/еТ

Ограничения для групповых работ:

= у, ./М.уе ССЛ, А Я, б О. Ограничения по времени пролеживания:

Ограничения по межоперационному времени:

yt<xl<yl+tr,ks(K(j)nJm"),jeJ.

Ограничения для директивных сроков выполнения работ:

yj<djf je J".

Ресурсные ограничения:

Обозначим через

I t+tij-I ft

Р„ =Zl'.,-E X V - 1^тах(0,Р„. ),

1=1 JeJ |W 1=1

где тах(0,Ра)- потери i-ro ресурса, поступившего в систему в такт t, из-за

о

истечения срока его годности, iel.teT. Здесь ^тах(0,Ра. ) = 0. Тогда W„ =Xvi-XXZp-ZtmaxlO.Pr■) - количество i-ro ресурса, которое может быть

1=1 je]l=l 1=1

использовано в такт t для выполнения работ, ie l.te Т. С учетом введенных обозначений, ресурсные ограничения примут вид: s3Va,ie/,/er

Jul

Проводится исследование построенной математической модели. Показано, что проблема существования допустимого решения для общей математической модели является NP-полной.

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

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

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

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

Здесь уи - параметр, определяющий штрафные санкции, связанные с неиспользованием 1% ресурса I в такт (, а 4 - параметр, определяющий штрафные санкции, связанные с недостатком 1% ресурса / в такт /, / е /,/еГ.

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

Здесь а, - коэффициент штрафа за «отставание» выполнения работы у от ее директивного срока £>; на 1% от величины, ¡<¿1°.

Раздел 3.2. посвящен описанию основных процедур метода ветвей и границ для решения задачи построения расписания в канонических системах типа «конвейер-сеть». Приводится описание алгоритмов определения

у и-—— * 100, если V,

¡00, если V, г,

-400, если V, <]Гг,

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

Раздел 33. посвящен стохастическим и детерминированным алгоритмам решения задач упорядочения работ и распределения ресурсов. Приводится описание алгоритмов-построителей расписания, зависящих от перестановки р, и предназначенных для получения допустимой перестановки, удовлетворяющей ограничениям конкретной модели. Описаны стохастические алгоритмы для построения перестановок в канонических системах «конвейер-сеть». Приводится описание адаптированных для работы с построенными моделями алгоритмов отжига, генетического алгоритма и роевых алгоритмов. В результате работы всех алгоритмов генерируются перестановки. Так, алгоритм отжига основывается на имитации физического процесса, который происходит при кристаллизации вещества из жидкого состояния в твёрдое, в том числе при отжиге металлов. В основе роевого алгоритма используется аналогия между решением оптимизационной задачи и моделированием поведения колонии «муравьев». Колония рассматривается как многоагентная система, в которой каждый агент (муравей) функционирует по простым правилам, и при этом поведение всей системы (колонии муравьев) приводит к приемлемым результатам. Это качество многоагентной системы следует из так называемой «роевой» логики. В основе эволюционно-генетических алгоритмов заложена идея наследственности в биологических популяциях

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

13

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

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

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

Для конвейерной задачи серия экспериментов проводилась на тестовых примерах, для которых заранее известны найденные оптимальные решения. Библиотека тестовых задач поддерживается профессором Лондонского Университета Brunei по исследованию операций на сайте http://people.brunel.ac.uk/~mastjjb/jeb/info.html.

Эксперименты проводились сериями из 5 тестовых задач в каждой по 20, 50, 100, 200 и 500 операций. Время проведения каждого эксперимента составляло 10 минут. Эксперименты проводились на ПЭВМ со следующей конфигурацией: процессор AMD Athlon(tm) 64 Х2 Dual Core processor 6000+

3.01 Ггц, 2 Гб оперативной памяти. Результаты эксперимента приведены в таблице 1.

Число работ Число станков F 1 огтг F - 1 нанд

20 5 1278 1278 =0,001

20 5 1359 1359

20 5 1293 1297

20 5 1236 1236

20 5 1195 1195

50 5 2724 2729 =0,005

50 5 2834 2859

50 5 2621 2625

50 5 2751 2757

50 5 2863 2886

100 5 5493 5495 =0,004

100 5 5268 5292

100 5 5175 5212

100 5 5014 5023

100 5 5250 5290

200 10 10868 11316 =0,046

200 10 10494 11095

200 10 10922 11373

200 10 10889 11331

200 10 10524 11216

500 20 26189 28228 =0,08

500 20 26629 28780

500 20 26458 28390

500 20 26549 28412

500 20 26404 29041

Таблица 1

В таблице 1 приведены средние относительные отклонения значений критерия задачи на найденном решении (^¡¡д) от известных значений оценок (Рот)- Проведенный вычислительный эксперимент показал высокую степень качества разработанных алгоритмов оптимизации, с отклонением значения критериев от оптимальных не более чем на 8% для исследуемого класса задач.

Для канонических систем типа «конвейер-сеть» были сгенерированы тестовые задачи, состоящие из последовательности конвейерных и сетевых

технологий. Эксперименты проводились для серии из 5 задач по 20,50,100,500 и 1000 операций. При этом каждая из задач решалась двумя способами:

- Полное решение исходной задачи как сетевой канонической структуры;

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

В таблице 2 приведены результаты эксперимента. Показано решение, полученное после декомпозиции задачи (Рк.с), решение задачи как сетевой структуры (Б^) и среднее отклонение полученных решений^,).

Число работ Число станков Рк-с р 1 кал

20 10 837 837 0

20 10 938 938

20 10 954 954

20 10 911 911

20 10 894 894

50 20 1916 1935 =0,012

50 20 2012 2039

50 20 1954 1978

50 20 1987 1987

50 20 1953 1989

100 20 4816 4893 =0,02

100 20 4765 4802

100 20 4824 4916

100 20 4911 5023

100 20 4832 4954

500 30 21349 22064 =0,042

500 30 20931 21853

500 30 21096 21985

500 30 21716 22971

500 30 21533 22847

1000 40 43528 45832 =0,049

1000 40 43719 45374

1000 40 43101 45630

1000 40 44235 46012

1000 40 43562 45961

Таблица 2

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

Приводится общая схема решения задач в канонических системах типа «конвейер-сеть» и описаны конкретные примеры решения производственных задач управления процессом изготовления микроэлектронных изделий (производство БИС и ГИС), изделий инструментального производства (изготовление пресс-форм), продукции опытного производства (изделия машиностроения).

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

Основные результаты диссертационной работы.

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

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

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

17

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

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

Публикации.

Статьи в журналах, периодических изданиях, включенных в список ВАК РФ

1. Прилуцкий М.Х. Метод ветвей и границ с эвристическими оценками для конвейерной задачи теории расписаний. / Прилуцкий М.Х., Власов B.C. //Вестник Нижегородского государственного университета. Математическое моделирование и оптимальное управление. Нижний Новгород: Изд-во ННГУ, 2008. Вып. 3 стр. 147-153.

2. Прилуцкий М.Х. Оптимизационные задачи распределения ресурсов при планировании производства микроэлектронных изделий. /Прилуцкий М.Х., Власов B.C. //Системы управления и информационные технологии, Воронеж, 2009, №1(35), с. 38-43

Статьи и материалы конференций

3. Прилуцкий М.Х. Об одной задаче построения конвейерных расписаний. /Прилуцкий М.Х., Власов B.C. //Тезисы докладов всероссийской научно-технической конференции ИСТ-2005, Нижний Новгород, 2005, стр. 116117

4. Прилуцкий М.Х. Использование процедур метода ветвей и границ для решения задач многоресурсного сетевого планирования. /Прилуцкий М.Х., Власов B.C. //Тезисы докладов международной научно-технической конференции ИСТ-2006, Нижний Новгород, 2006, стр. 59

5. Власов B.C. Дискретно-управляемые системы распределения ресурсов в сетевых структурах. /Власов B.C. //Материалы докладов XI Нижегородской сессии молодых ученых. Технические науки, 2006, стр. 910

6. Власов B.C. Распределение ограниченных ресурсов в сетевых канонических дискретно-управляемых системах. /Власов B.C., Прилуцкий М.Х. //Материалы конференции 'Технологии Microsoft в теории и практике программирования", Нижний Новгород, издательство ННГУ, 2006, стр. 49-51

7. Прилуцкий М.Х. Метод комбинирования эвристических алгоритмов для конвейерных задач теории расписаний. / Прилуцкий М.Х., Власов B.C. //Электронный журнал "Исследовано в России", 086, стр. 901-905, 2007 http://zhurnal.ape.relarn.ru/articIes/2007/086.pdf

8. Власов B.C. Метод комбинированных эвристик построения конвейерных расписаний. /Власов B.C., Прилуцкий М.Х. //Материалы конференции "Технологии Microsoft в теории и практике программирования", Нижний Новгород, издательство ННГУ, 2007, стр. 211-212

9. Прилуцкий М.Х. Стохастические алгоритмы для конвейерных расписаний. /Прилуцкий М.Х., Власов B.C. //Тезисы докладов

19

международной научно-технической конференции ИСТ-2007, Нижний Новгород, 2007, стр. 215-217

Ю.Власов B.C. Распараллеливание метода ветвей и границ решения конвейерной задачи построения оптимального по быстродействию расписания. /Власов B.C. //Материалы Седьмой Международной Конференции "Высокопроизводительные параллельные вычисления на кластерных системах ", 2007, стр. 86-89

П.Власов В. С. Использование эвристических алгоритмов для ускорения поиска точного решения конвейерной задачи. /Власов B.C. //Материалы конференции 'Технологии Microsoft в теории и практике программирования", Нижний Новгород, издательство ННГУ, 2007, 2008, стр. 73-75

12.Власов B.C. Результаты вычислительного эксперимента для анализа эффективности алгоритмов решения конвейерной задачи теории расписаний. /Власов B.C. //Материалы конференции 'Технологии Microsoft в теории и практике программирования", Нижний Новгород, издательство ННГУ, 2009, стр. 66-67

13.Власов B.C. Стохастические алгоритмы решения задач распределения ресурсов в канонических структурах. /Власов B.C. //Тезисы докладов международной научно-технической конференции ИСТ-2009, Нижний Новгород, 2009, стр. 299-300

14.Власов B.C. Задачи упорядочения и распределения ресурсов при изготовлении изделий микроэлектронного производства. /Власов B.C. //Труды Нижегородского государственного технического университета. Серия: Системы обработки информации и управления. Вып. 16. Нижний Новгород: Изд-во НГТУ, 2009, с. 31-36.

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

Отпечатано в ФГУП «ФНПЦ НИИИС им. Ю.Е. Седакова». 603950, г. Нижний Новгород, ГСП-486

Введение.

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

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

1.1.1. Место задач теории расписаний в классе задач математического программирования.

1.1.1.1. Задачи планирования перевозок.

1.1.1.2. Задачи размещения и специализации.

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

1.1.1.4. Задачи распределения вычислительной памяти.

1.1.1.5. Задачи синтеза логических сетей.

1.1.1.6. Задачи нахождения маршрутов перевозки груза.

1.1.2. Классификация задач теории расписаний.

1.1.2.1. Сетевое представление.

1.1.2.2. Иерархическое представление.

1.1.2.3. Задачи упорядочения работ.

1.1.2.4. Задачи согласования.

1.1.2.5. Задачи распределения.

1.2. Упорядочение работ и распределение ресурсов при заданных отношениях предшествования.

1.2.1. Общее описание задачи упорядочения работ и распределения ресурсов при заданных отношениях предшествования.

1.2.2. Классификация моделей по учету внешних воздействий.

1.2.2.1. Детерминированные модели.

1.2.2.2. Вероятностные (стохастические) модели.

1.2.2.3. Статистические модели.

1.3. Содержательная постановка задач упорядочения и распределения ресурсов в канонических структурах типа «конвейер-сеть».

1.3.1. Оптимальное планирование и управление процессом производства изделий микроэлектроники.

1.3.1.1. Производство больших интегральных схем (БИС).

1.3.1.2. Производство гибридных интегральных схем (ГИС).

1.3.2. Задача планирования опытного производства изделий машиностроения.

1.3.3. Задача планирования процесса изготовления пресс-форм в инструментальном производстве.

1.3.4. Общие особенности задачи планирования производства микроэлектронных изделий и задачи опытного производства изделий машиностроения.

1.3.5. Содержательное описание объекта.

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

Глава 2. Математические модели упорядочения работ и распределения ресурсов в канонических системах.

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

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

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

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

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

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

2.2.1. Математическая модель и ее исследование.

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

2.3.1. Математическая модель.

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

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

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

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

3.1.1. Критерии оптимизационных задач.

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

3.1.3. Постановка оптимизационной задачи для систем «конвейер-сеть».

3.2. Метод ветвей и границ построения расписаний для систем типа «конвейер-сеть».

3.2.1. Описание основных процедур метода ветвей и границ.

3.2.2. Алгоритмы определения граничных значений метода ветвей и границ для систем типа «конвейер-сеть».

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

3.3.1. Алгоритм-построитель расписания.

3.3.1.1. Алгоритм-построитель допустимого расписания.

3.3.2. Стохастические алгоритмы.

3.3.2.1 .Алгоритм Метрополиса (Simulated Annealing).

3.3.2.2.Муравьиный алгоритм (Ant Colonies).

3.3.2.3.Генетический алгоритм.

3.3.3. Детерминированные алгоритмы.

3.3.3.1 .Фронтальный алгоритм.

3.3.3.2.Алгоритм решения задачи о назначениях.

3.3.4.Метод комбинирования алгоритмов.

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

Глава 4. Диалоговые программные средства решения оптимизационных задач упорядочения работ и распределения ресурсов в канонических системах типа «конвейер-сеть».

4.1. Описание структуры и возможностей диалоговой системы.

4.1.1. Модель работы с каноническими системами типа «конвейер-сеть».

4.1.2. Архитектура диалоговой программной системы.

4.1.3. Алгоритмический блок программной системы.

4.1.4. Функциональный блок программной системы.

4.1.5. Системные требования.

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

4.3. Решение задач упорядочения работ и распределения ресурсов.

4.3.1. Решение задач упорядочения работ и распределения ресурсов в микроэлектронном производстве.

4.3.1.1. Общее описание программного комплекса.

4.3.1.2. Решение задач планирования в программном комплексе «Кристалл».

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

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

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

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

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

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

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

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

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

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

- управление производственной деятельностью;

- планирование научно-исследовательских и опытно-конструкторских работ;

- изготовление сложных изделий;

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

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

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

Актуальность исследования.

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

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

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

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

Цели и задачи исследования

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

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

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

- выделен класс задач, относящихся к каноническим системам типа «конвейер-сеть»;

- построены математические модели и поставлены оптимизационные задачи распределения ресурсов и упорядочения работ, для которых проведено исследование и показана их КР-трудность;

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

- создана диалоговая система решения задач упорядочения и распределения ресурсов для канонических систем типа «конвейер-сеть», которая используется в практике планирования и оперативного управления процессом изготовления изделий микроэлектронного производства.

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

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

2. Построены математические модели канонических систем с конвейерными и сетевыми технологиями. Проведено их исследование.

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

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

5. Создана диалоговая программная система решения задач, относящихся к классу задач «конвейер-сеть».

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

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

Результаты диссертационной работы используются в учебном процессе Нижегородского государственного университета им. Н.И. Лобачевского на факультете вычислительной математики и кибернетики при преподавании курса «Теория систем и системный анализ».

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

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

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

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

Заключение

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

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

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

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

1. Акоф Р., Сасиени М. Основы исследования операций. М.: Мир, 1971, -536 с.

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

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

4. Беллман Р. Динамическое программирование. М.: Изд-во иностранной литературы, 1960, -400с.

5. Булгак A.C. Многокритериальная задача теории расписаний с ресурсами складируемого типа. АиТ. 1987. №12. С. 143-146.

6. Бурков В.Н., Ланда Б.Д., Ловецкий С.Е., Тейман А.И., Чернышев В.Н. Сетевые модели и задачи управления. М.: Советское радио, 1967, -144 с.

7. Бушминский И.П., Гудков А.Г., Дергачев В.Ф. Конструкторско-технологические основы проектирования полосковых микросхем. Под ред. И.П.Бушминского. М.: Радио и связь, 1987. 272 с.

8. Вагнер Г. Основы исследования операций. М.: Мир, 1972, -336 с.

9. Васильев Ф. П. Методы оптимизации. М.: Издательство "Факториал Пресс", 2002. - 824 с.

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

11. Власов В. С. Использование эвристических алгоритмов для ускорения поиска точного решения конвейерной задачи. Материалы конференции "Технологии Microsoft в теории и практике программирования", Нижний Новгород, издательство ННГУ, 2008, -стр. 73-75

12. Власов B.C. Дискретно-управляемые системы распределения ресурсов в сетевых структурах. Материалы докладов XI Нижегородской сессии молодых ученых. Технические науки, Нижний Новгород, издательство ННГУ, 2006, -стр. 9-10

13. Власов B.C. Стохастические алгоритмы решения задач распределения ресурсов в канонических структурах. Тезисы докладов международной научно-технической конференции ИСТ-2009, Нижний Новгород, 2009, стр. 299-300

14. Власов B.C., Прилуцкий М.Х. Метод комбинированных эвристик построения конвейерных расписаний. Материалы конференции "Технологии Microsoft в теории и практике программирования", Нижний Новгород, издательство ННГУ, 2007, стр. 211-212

15. Гасс С. Линейное программирование М.: Физматгиз, 1961. — 304 с.

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

17. Гофман А.Дж., Краскал Дж.Б. Целочисленные граничные точки выпуклых многогранников. Сб. «Линейные неравенства и смежные вопросы», М.: ИЛ, 1959, с. 325-347.

18. Губко М.В. Математические модели оптимизации иерархических структур. М.:ЛЕНАНД, 2006. - 264 с.

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

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

21. Давыдов Э.Г. Исследование операций. М.:Высшая школа, 1990, -383 с.

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

23. Дж. Макконнелл Основы современных алгоритмов. Москва: Техносфера, 2004. 368с.

24. Евтушенко Ю. Г. Методы решения экстремальных задач и их применение в системах оптимизации. М.: Наука, Главная редакция физико-математической литературы, 1982 — 432 с.

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

26. Зуховицкий С.И., Авдеева Л.И. Линейное и выпуклое программирование. М., 1964 -348 с.

27. Калбертсон Дж. Математика и логика цифровых устройств. М.: Просвещение, 1965 -267с.

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

29. Конвей Р. В., Максвелл В. Л., Миллер Л. В. Теория Расписаний. Москва: Главная редакция физико-математической литературы изд-ва "Наука", 1975 -360с.

30. Корбут A.A., Финкелыптейн Ю.Ю. Дискретное программирование. М.: Наука, 1969, -с. 368.

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

32. Кривцов A.M., Шеховцев В.В. Сетевое планирование и управление. М.: Экономика. 1978. -с. 191.

33. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б., Математическое программирование. М.: Высшая школа, 1980, -с. 300.

34. Майника Э. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1981.-с. 323.

35. Меткин Н.П., Лапин М.С., Деньдобренко Б.Н., Доморацкий И.А. Автоматизация проектирования и производства микросборок и электронных модулей. М.: Радио и связь, 1986. с. 280.

36. Мину М. Математическое программирование. Теория и алгоритмы: М.: Наука. Гл. ред. физ.-мат. лит., 1990. -с. 488.

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

38. Моудер Дж., Элмаграби С. Исследование операций: В 2х томах. Пер. с англ. М.: Мир, 1981.- 677 с.

39. Палатник Л. С, Сорокин В. К. Материаловедение в микроэлектронике. — М.: Энергия, 1977, —280 с.

40. Пономарев М.Ф. Конструкции и расчет микросхем и микроэлементов ЭВА: Учебник для вузов. М.: Радио и связь, 1982. - 288 с.

41. Прилуцкий М. X., Афраймович Л.Г. Многоиндексные задачи распределения ресурсов в иерархических системах. Автоматика и телемеханика, 2006,№ 6, с. 194—205.

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

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

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

45. Прилуцкий М.Х., Власов B.C. Метод комбинирования эвристических алгоритмов для конвейерных задач теории расписаний. Электронный журнал "Исследовано в России", 086, с. 901-905, 2007 http://zhurnal.ape.relarn.ru/articles/2007/086.pdf

46. Прилуцкий М.Х., Власов B.C. Использование процедур метода ветвей и границ для решения задач многоресурсного сетевого планирования. Тезисы докладов международной научно-технической конференции ИСТ-2006, Нижний Новгород, 2006, с. 59

47. Прилуцкий М.Х., Власов B.C. Об одной задаче построения конвейерных расписаний. Тезисы докладов всероссийской научно-технической конференции ИСТ-2005, Нижний Новгород, 2005, стр. 116-117

48. Прилуцкий М.Х., Власов B.C. Стохастические алгоритмы. для конвейерных расписаний. Тезисы докладов международной научно-технической конференции ИСТ-2007, Нижний Новгород, 2007, стр. 215-217

49. Прилуцкий М.Х., Власов B.C. Оптимизационные задачи распределения ресурсов при планировании производства микроэлектронныхизделий. Системы управления и информационные технологии, Воронеж, 2009, №1(35), с. 38-43

50. Прилуцкий М.Х., Вяхирев Д.В. Распределение ресурсов в сетевых структурах с интервальными значениями параметров. Вестник Нижегородского государственного университета, серия «Математическое моделирование и оптимальное управление» 1(25), 2002, с. 224-233.

51. Прилуцкий М.Х., Кумагина Е. А. Управляемый фронтальный алгоритм решения задачи распределения ресурсов в сетевых канонических структурах. Вестник Нижегородского университета им. Н.И. Лобачевского. № 6 -Н. Новгород: Изд-во ННГУ, 2008. с. 126—129.

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

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

54. Пшеничный Б.Н., Данилин Ю.М. Численные методы в экстремальных задачах. М.: Наука, 1975 -320с.

55. Степаненко И.П. Основы микроэлектроники. Учеб. пособие для вузов. -2-е изд., 2001.-488 с.

56. Танаев В.С, Шкурба В.В. Введение в теорию расписаний. М.: Наука, 1975, 256 с.

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

58. Танаев B.C. 1С теории расписаний. ДАН БССР 8, №12, 1964, с. 792794.

59. Таха, Хемди А. Введение в исследование операций. 7-е издание.: Пер. с англ. — М.: Издательский дом "Вильяме", 2005. — 912 с

60. Триус Е. Б. Задачи математического программирования транспортного типа. М.: Наука, 1967, 208 с.

61. Трифонов А.Г. Постановка задачи оптимизации и численные методы ее решения. "Дело", Москва, 2002г.

62. Хелд М., Карп P.M., Применение динамического программирования к задачам упорядочения. Кибернетический сборник, вып. 9, М.: Мир, 1964, с. 202-218.

63. Хеллер И., Томпкинс Ч.Б. Обобщение одной теоремы Данцига. Сб. «Линейные неравенства и смежные вопросы», М.: ИЛ, 1959, с. 348-354.

64. Шикин Е. В., Шикина Г. Е. Исследование операций. М. : ТК Велби, Изд-во Проспект, 2006. 280 с.

65. Шкурба В.В. Задача трех станков. Главная редакция физико-математической литературы изд-ва "Наука", М., 1976 -92с.

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

67. Simulated annealing: A proof of convergence. IEEE Transactions on Pattern Analysis and Machine Intelligence 16 (6): 652-656. June 1994. doi:l 0.1109/34.295910

68. A. Kenneth, De Jong, and W. M. Spears. Using genetic algorithms to solve NP-complete problems, in Proc. 3rd Int. Conf. Genetic Algorithms, George Mason University, 1989, pp. 124-132.

69. Antill J.M. Woodhead R.W. Critical Path Methods in Construction Practice. Wiley, New York, 1970.

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

71. Balas E. Machine sequencing via disjunctive graphs: an implicit enumeration algorithm. Operat. Res. 17, №6, 1969, p. 941-957.

72. Bellman R. Mathematical aspects of scheduling theory. J. Soc. Industr. and Appl. Math. 4, №3, 1956, p. 168-205.

73. Bellman R. Dynamic programming treatment of the traveling salesman problem. J. Assoc. Comput. Mach., 1962, 9, №1, p. 61-63.

74. Bellman R., Gross O. Some combinatorial problems arising in the theory of multistage processes. J. Soc. Industr. and Appl. Math. 2, №3, 1954, p. 175-183.

75. C.H. Papadimitriou, K. Steiglitz. Combinatorial Optimization. NJ: Prentice Hall, Englewood Cliffs, 1982 -496p.

76. D. Abramson & J. Abela. A Parallel Genetic Algorithm for Solving the School Timetabling Problem. Technical report, Division of Information Technology, C.S.I.R.O, 1991.

77. Dorigo M., Maniezzo V., Colorni A. The Ant System: Optimization by a colony of cooperating objects. IEEE Transactions on Systems, Man, and Cybernetics Part B, 26(1), 1996, p. 29- 41.

78. E. Aarts and J. Korst, Simulated Annealing and Boltzmann Machines-A Stochastic Approach to Combinatorial Optimization and Neural Computing. New York: Wiley, 1989.

79. Even S., Itai A., Shamir A. On the complexity of timetable and multicommodity flow problems. SIAM J: Comput. 5, 1976, p. 691-703.

80. Feng-Tse Lin, Cheng-Yan Kao, and Ching-Chi Hsu. Applying the Genetic Approach to Simulated Annealing in Solving Some NP-Hard Problems. IEEE Transaction On System, Man, And Cybernetics, Vol. 23. No. 6, November-December 1993

81. Goldberg D. E. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Reading, MA. 1989, 412 p.

82. Gonzalez T., Sahni S., Flowshop and jobshop schedules: complexity and approximation. Oper. Res. 26, 1978, p. 36-52.

83. H. Arntzen & A. Lokketangen. A tabu search heuristic for a university-timetabling problem. MIC 2003, Fifth Metaheuristies International Conference pp02-l, 02-7.

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

85. Heller J., Logemann G., An algorithm for construction and evaluation of feasible schedules. Manag. Sci. 8, №2, 1962, p. 168-183.

86. J. De Vicente, J. Lanchares, R. Hermida, Placement by Thermodynamic Simulated Annealing. Physics Letters A,Vol. 317, Issue 5-6, 2003, pp.415-423.

87. Johnson S.M. Discussion: sequencing «-jobs on two machines with arbitrary time lags. Manag. Sci. 5, №3, 1959, p. 299-303.

88. Johnson S.M. Optimal two- and three-stage production schedules with setup times included. Nav. Res. Log. Quart. 1, №1, 1954, p. 61-68.

89. Kirkpatrick S., Gelatt C.D. Optimization by Simulated Annealing, Science, Vol. 220, Number 4598

90. Kuhn H.W. Variants of the Hungarian Method for Assignment Problems. Naval Research Logistics Quarterly, 1956, 3, p. 253-258.

91. L. Davis and F. Ritter. Schedule optimization with probabilistic search, in Proc. 3rd IEEE Conf. Artific. Intellig. Applicat., 1987, pp. 231-236

92. L. Davis, Genetic Algorithms and Simulated Annealing. Los Altos, CA: Morgan Kaufmann, 1987.

93. Land A.H., and Doig A.G. An autmatic method of solving discrete programming problems. Econometrica. v28 (1960), pp 497-520.

94. Little J.D.C., Murty K.G., Sweeny D.W., ICarel C. An algorithm for the traveling salesman problem. Operat. Res., 1963, 11, №6, p. 972-989.

95. Maxwell W.L., Mehra M. Multiple-factor rules for sequencing with assembly constraints. Nav. Res. Log. Quart. 15, №2, 1968, p. 241-254.

96. Miller С.E., Tucker A.W., Zemlin R.A. Integer programming formulation of traveling salesman problems. J. Assoc. Comput. Mach., 1960, 7, №4, p. 326329.

97. Mitten L.G. Sequencing «-jobs on two machines with arbitrary time lags. Manag. Sci. 5, №3, 1959, p. 293-298.

98. Главный инженер В .И. Антипов

99. Зам. директора по МЭ Л.А. Синегубко

100. Зам. директора по ИТ /Ю.А. Хохловin1. Актвнедрения результатов диссертационной работы B.C. Власова «Упорядочение работ и распределение ресурсов в канонических системах «конвейер-сеть» в учебный процесс факультета ВМК

101. Зав. кафедры ИАНИ профессор1. Батищев Д.И.1. СПРАВКАоб использовании результатов диссертационной работы1. В.С.Власова

102. Упорядочение работ и распределение ресурсов в каноническихсистемах «конвейер-сеть»

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