Упорядочение работ и распределение ресурсов в канонических системах "конвейер-сеть" тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат технических наук Власов, Валентин Сергеевич

• Власов, Валентин Сергеевич
• кандидат технических наук
• 2009

Оглавление диссертации кандидат технических наук Власов, Валентин Сергеевич

Введение.

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

Заключение

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Власов, Валентин Сергеевич, 2009 год

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. Полученные результаты позволяют говорить об адекватности математических моделей, заложенных в основу программной системы, условиям производства.