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

• Шепеток, Богдан Дмитриевич
• кандидат технических наук
• 1983

Оглавление диссертации кандидат технических наук Шепеток, Богдан Дмитриевич

Введение.

1. Исследование процесса распределения программного обеспечения в многомашинных и мультипроцессорных вычислительных комплексах АСУ .,.#

1.1. Организация параллельного вычислительного процесса. .*

1.2. Определение графовых моделей программного обеспечения

1.3. Задачи рациональной организации вычислительного процесса в вычислительных системах АСУ .,.

1*4. Задачи разбиения на билогических двухграфовых моделях программного обеспечения .«.#«.

2. Методы построения расписаний на графах управления

2,1» Определение оптимального расписания для двухцепного гамака

2.2. Определение оптимального расписания для л -цепного гамака

3. Алгоритмы построения распределенного программного обеспечения АСУ •*.•.».••.•••.•.,.•.•.•.•.*••

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

3.2. Прямая и обратная задачи распределения программного обеспечения .*.

4. Распределение задач в двухмашинном вычислительном комплексе АСУ на стане 2000 Новолипецкого металлургического завода

4.1» Применение УВМ для управления процессом прокатки ••••.*. ИЗ

4.2. Структура автоматизированной системы регулирования толщиной полосы

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

4.4. Синхронизация вычислительного процесса в распределенных системах.

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

Совершенствование системы управления общественным развитием страны возможно лишь при комплексном подходе к решению этой проблемы. ХХУ и ХХУ1 съезды КПСС наметили комплекс мероприятий, обеспечивающих совершенствование техники и стратегии планирования, максимальное использование экономических рычагов управления. Составной частью этого комплекса является необходимость дальнейшего внедрения автоматизированных систем управления (АСУ) как основы комплексной автоматизации производства.Важность этих работ заключается в том, что АСУ способствует повышению интенсификации общественного производства, поднимает общую культуру производства, позволяет широко использовать электронно-вычислительные машины для сбора и обработки информации.Широкое внедрение в производство АСУ на базе мини-ЭВМ, особенно для непосредственного управления объектами, представляет повышенные требования к надежности и быстродействию их программного обеспечения (ПО), к сокращению сроков проектирования, разработки и внедрения [б0] .Удовлетворение этих, в совокупности гфотиворечивых, тре бований к ПО представляет достаточно сложную задачу, В процессе развития вычислительной техники потребности в производительности и объеме памяти вычислительных систем значительно опережают возможности техники в каждый момент времени [59] . Это обстоятельство стиьоглирует развитие техничес ких средств и, с другой стороны, разработку методов эффективного использования ресурсов существующих вычислительных сие тем [б2] . Экономное распределение и использование важнейших ресурсов (памяти и производительности) вычислительных систем (ВС) позволяет в значительной мере скомпенсировать реально существующий дефицит этих характеристик у современных ВС [эо].Кроме того, эффективное использование ресурсов ВС обеспечивает решение сложных комплексов задач на вычислительных системах, обладающих невысокими показателями по производительности и объемам памяти и, соответственно, имеющих небольшую стоимость.При проектировании, создании и эксплуатации АСУ возникает ряд проблемных вопросов, от успешного решения которых зависит функционирование системы. Важнейшим из них является оптималь ное, с точки зрения производительности системы, распределение программного обеспечения между машинами ВС. В зависимости от степени территориальной разобщенности основных элементов эта проблема будет решаться по разному. В системах совмещенного типа она решается без учета потерь времени на обмен информацией между машинами, поскольку эти потери пренебрежительно малы по сравнению с временем реализации программ на машинах. В системах разобщенного типа время передачи информации от одной машины к другой соизмеримо со временем решения задачи на машине, поэтому потери времени на обмен между машинами должны учиты ваться гфи решении проблемы оптимального распределения прог раммного обеспечения [34, 109] • Для вычислительных систем, называемых в литература [б1, 67, 79J системами реального времени, к классу которых относятся автоматизированные системы управления, время является важ нейшим параметром, определяющим результаты работы системы.Прекращение измерения времени в этом случае эквивалентно полному отказу системы, так как теряется временная связь вычислительного процесса с состоянием источников внешней информации и потребителей вырабатываемых данных [59| . Таким образом, при распределении программ шеищу машинами проблема эффективности использования производительности ВС в реальном масштабе времени весьма актуальна.Целью диссертационной работы является разработка и исследование методов и алгоритмов построения распределенного программного обеспечения АСУ и применение разработанных алгоритмов для решения практических задач проектирования и внедрения программных комплексов в многомашинных и мультипроцессорных вычислительнБК системах.Для достижения поставленной цели в диссертационной работе выполнено следующее: осуществлена постановка основных задач оптимального построения распределенного программного обеспечения и разработаны принципы их решения; получена модель исследуемых объектов; исследован вопрос выбора методов оптимального разбиения на разработанных графовых моделях программного обеспечения; получен метод разметки ребер графа управления и определена величина информационной связности программного обеспечения; исследована сложность и эффективность разработанного субоптимального метода разбиения на графе управления; разработаны методы и алгоритмы решения задач расписания на графе управления; разработана методика расчета основных временных характеристик распределенного программного обеспечения; решены вопросы синхронизации распределенного программного обеспечения.Предметом исследований явилась двухграфовая билогическая модель программного обеспечения [9, 53, 74, 89] . Ограничения на порядок вьшолнения ПО задаются некоторым билогическим ориентире BaHnbttf графом &и , а информационные связи - некоторым неориентированным графом В диссертационной работе сформулированы задачи эффективного построения программного обеспечения, распределенного между машинными комплексами или процессорами вычислительной системы, и разработаны методы их решения. Для различных графовых моделей по управлению разработаны методы определения оптимальных и локально-оптимальных расписаний [47] . Предложена мето дика определения временных характеристик распределенного программного обеспечения.Результаты исследований и разработок апробированы при проектировании и внедрении АСУ на широкополосном стане 2000 Новолипецкого металлургического завода (НЖЗ), которая сдана в промышленную эксплуатацию.Материалы диссертации изложены в четырех главах и приложении. Основной материал занимает 134 страниц машинописного текста, содержит б таблиц и 35 рисунков. Список использованной литературы содержит 139 наименований.В первой главе исследован процесс комплексирования ЭВМ в вычислительные системы. Проведен анализ публикаций по вопросам классификации вычислительных систем и задачам организации расписаний выполнения параллельных программ. Рассмотрены постановки задач рациональной организации вычислительного процесса в вычислительных системах на примерах различных конкретных конфигураций вычислительных комплексов, сформулированы основные задачи распределения ПО для двухмашинного и двухпроцессорного вычислительных комплексов. Проведен обзор методов решения за дач распределения на графовых моделях. Исследованы вопросы оптимального быстродействия ПО, заданного различными граф-моделями управления. Рассмотрены основные виды информационной связности программ, разработана методика определения величины информационной связности программ. Исследованы вопросы оптимальности распределения ПО, заданного двухцепным гамаком. Разработан метод определения субоптимального разреза П -цепного га мака, исследована сложность и эффективность данного метода, предложена методика поиска локально-оптимального разреза на информационном графе.Во второй главе разработаны алгоритмы решения задач разбиения на графе управления. Разработан метод решения задачи поиска оптимального расписания для ПО, заданного двухцепным гамаком, на котором задан произвольный разрез. Для данного случая разработана гфоцедура определения множеств вершин, составляющих расписание. Исследована задача построения оптимального расписания для ПО, заданного п - цепным гамаком, в случае определения на данном гамаке параллельного и произвольного разреза. Для этих видов р£1зреза разработан метод поиска оптимального расписания.В третьей главе исследованы и предложены алгоритмы построения распределенного программного обеспечения. Разработана методика преобразований логик "входа-выхода" вершин билогического графа управления ПО путем введения фиктивных вершин и из бавления от транзитивных замыканий на некоторых моделях данного графа управления.В четвертой главе рассмотрена АСУ на стане 2000 НЛМЗ, в разработке которой непосредственное участие принимал автор при решении задач распределения программного обеспечения меж ду двумя вычислительными комплексами. Исследован вопрос применения УВМ для управления процессами прокатки. Описана структура данной АСУ, разработаны вопросы синхронизации вычислитель ного процесса в распределенных системах программного обеспечения.В приложении даны описания применения и листинги пакета прикладных программ анализа граф-моделей, который является реализацией предлагаемой методики, документы, подтверждающие использование и внедрение результатов диссертации. I. И С С Щ О В А Ш Е ПРОЦЕССА РАСПРЕДЕЛЕНИЯ ПР0ГРА11Ш0Г0 ОБЕСПЕЧЕНИЯ В МНОГОМАШИННЫХ И МУЛЬТИПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ КОМПЛЕКСАХ АСУ

Заключение диссертации по теме «Автоматизация и управление технологическими процессами и производствами (по отраслям)», Шепеток, Богдан Дмитриевич

Выводы по четвертой главе

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

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

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

- подсистема 1-го ВК, реализующая функции слежения за полосой, выдачи управляющих воздействий для настройки валков,ведение ОЗУ-резидентной базы данных;

- подсистема 2-го ВК, реализующая функции оперативного управления станом и ведения диск-резидентной базы.

Таким образом, первоначальная подсистема "Ведение базы данных" была разбита на две подсистемы: "Ведение ОЗУ-резидентной базы данных" и "Ведение диск-резидентной базы данных".

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

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

ЗАКЛЮЧЕНИЕ

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

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

2. Разработан критерий оптимальности произвольного разреза двухцепного гамака и методика субоптимального распределения

Л -цепного гамака.

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

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

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

6. На базе алгоритмов преобразования графовых моделей ПО разработана методика определения временных характеристик рас -пределенного ПО.

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

8. Разработан пакет прикладных программ анализа граф-моделей, обеспечивающий эффективную организацию вычислительного процессп на двухпроцессорном вычислительном комплексе типа

СМ-2.

9. Результаты исследований использованы при разработке и внедрении в промышленную эксплуатацию АСУ САРТ на стане 2000 Новолипецкого металлургического завода.

Список литературы диссертационного исследования кандидат технических наук Шепеток, Богдан Дмитриевич, 1983 год

1. Авен О.И., Коган Я.М. Математические модели сложных вычислительных систем (обзор).- Автоматика и телемеханика, 1971, № 1. с.109-128.

2. Автоматизация проектирования вычислительных систем. Языки, моделирование и базы данных. Под ред.Брейера Н.~ М.: Мир, 1979.- 463 с.

3. Автоматизация прокатных станов. Сб.статей Института автоматики. Под ред.Б.Б.Тимофеева.- М.: Металлургия, 1976.- 272 с.

4. Автоматизация технологических процессов в прокатном производстве. По ред.Б.Б.Тимофеева.- М.: Металлургия, 1979.174 с.

5. Акинфеев В.К., Мамиконов А.Г., Новиков В.Н., Двиркун А.Д. 0 рациональном распределении функций в АИСу летальными аппаратами.- Автоматика и телемеханика. 1978, № 5, с.141-153.

6. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.- М.: Мир, 1979.- 535 с.

7. Барский А.Б. 0 построении диспетчеров для вычислительных систем.- Изв.АН СССР.- Техническая кибернетика, 1971, № I, C.II3-II8.

8. Беллман Р. Динамическое программирование.- М.: Иностранная литература, 1959.- 400 с.

9. Берж К. Теория графов и ее применение.- М.: Иностранная литература, 1962.- 319 с.

10. Ю.Берштейн Л.С., Селянкин В.В. 0 минимальном разрезании графов со взвешенными ребрами.- Электронная техника АСУ. Вып. 4(20). 1976.

11. П.Бородкин А.Н.,Бородкин Л.И., Турин Н.Н., Коган Я.Н. Оптимизация размещения информационных массивов на магнитных дисках.- Автоматика и телемеханика, 1977, № 10, с.15-23.

12. Брановицкий В.И., Рабинович 3.JI. Вопросы классификации вычислительных систем.- В кн.: Вычислительные системы. Новосибирск, ИМ СО АН СССР, I97T, вып.48, с.3-15.

13. Брунченко А.В. О разбиении цифровых устройств на модули.-Автоматика и телемеханика, 1977, № 10, с.159-167.

14. Бусленко Н.П., Калашников В.В., Коваленко И.Н. Лекции по теории сложных систем.- М.: Советское радио, 1973.- 440 с.

15. Бутыльский Ю.Т., Брунченко А.В. Алгоритм разрезания двудольного графа для построения цифровых устройств на основе больших интегральных схем.- Автоматика и вычислительная техника, 1976, № 4, с.72-76.

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

17. Васенков А.А. Микропроцессоры.- Электронная промышленность, 1978, № 5, с.7-9.

18. Виленкин С.Я., Трахтенгерц Э.А. Математическое обеспечение управляющих вычислительных машин.- М.: Энергия, 1972.392 с.

19. Гайничеру М.И. Некоторые вопросы исследования и оптимизации структуры моделей систем управления. Дие. канд.тех. наук.- Киев, 1980.- 150 с.

20. Герман В.А. 0 расчете времени машинных программ.- Цифровая вычислительная техника и программирование, 1972, № 7, с. 35-38.

21. Гильбурд М.М., Кухар Р.Б. Об одной задаче разбиения мно -жества взаимосвязанных элементов на подмножестве.- Автоматика и телемеханика. 1982, № 3, с.106-112.

22. Глушков В.М. Введение в АСУ.- Киев: Техн1ка, 1974.- 320 с.

23. Головкин Б.А. Классификация методов диспетчеризации работы многопроцессорных и многомашинных вычислительных систем.-Управляющие системы и машины. 1982, № 3, с.3-11.

24. Головкин Б.А, Графовые модели программ с вероятностными параметрами (современное состояние).- Вопр. радиоэлектроники. Сер. Электронная вычислительная техника. 1976,вып.б, с.3-26.

25. Головкин Б.А. Исследование некоторых расписаний работы мультипроцессорных вычислительных систем. XX научная конференция МФТИ. г.Долгопрудный, 1974.- Тр.МФТИ.Радиотехника и электроника, 1975, № 10, с.65-74.

26. Головкин Б.А. Методы и средства параллельной обработки информации.- В кн.: Итоги науки и техники. Теория вероятностей. Математическая статистика. Теоретическая кибернетика.-М.: ВИНИТИ, 1979, том 17, с.85-193.

27. Головкин Б.А. Параллельные вычислительные системы.- М.: Наука, 1980.- 520 с.

28. Голубев-Новожилов Ю.С. Многомашинные комплексы вычислительных средств.- М.: Советское радио, 1967.- 424 с.

29. Горинштейн Л.А. 0 разрезании графов.- Известия АН СССР, Техническая кибернетика. 1969, № I, с.79-85.

30. Давиденко К.Я., Левин А.А., Шенброт М.И. Децентрализованные системы управления технологическими процессами.- В кн.: Измерения, контроль, автоматизация.- М.: Наука, 1979, № 2 (18), с.54-65.

31. Дал У., Дийкстра Э., Хоор К. Структурное программирование.-М.: Мир, 1975.- 250 с.

32. Дийкстра Э. Взаимодействие последовательных процессов.- Вкн.: Языки программирования.- М.: Мир, 1972, с.9-84.

33. Донован Дж. Системное программирование.- М.: Мир, 1975.539 с.

34. Дроздов Е.А., Пятибратов А.П. Основы построения и функционирования вычислительных систем.- М.: Энергия, 1973.-368с.

35. Дружинин Н.Н. Непрерывные станы как объект автоматизации.-М.: Металлургия, 1975.- 336 с.

36. Дьяченко В.Ф. Определение времени выполнения алгоритмов.-В кн.: Управление сетями связи и синтез управляющих уст -ройств. М.: Наука, 1969, с.28-34.

37. Ершов А.П. Введение в теоретическое программирование.М.: Наука, 1977.- 286 с.

38. Ершов А.П., Котов В.Е., Летичевский А.А. и др.; Теоретическое программирование в СССР. В кн.: Системное и теоретическое программирование.- Новосибирск, ВЦ СО АН СССР, 1972,с.9-78.

39. Знак В.И. Алгоритмы априорной оценки времени реализации программы.- Автометрия, 1972, № I, c.IOI-IIO.

40. Зыков А.А. Теория конечных графов.- М.: Наука, 1969.- 542с.

41. Йодан Э. Структурное программирование и конструирование программ.- М.: Мир. 1979.- 415 с.

42. Калинова М.Д. Классификация многомашинных систем. Тр.Моск. энерг.ин-та, 1974, вып.183, с.15-20.

43. Квиттнер П. Задачи, программы, вычисления, результаты.-М.: Мир, 1980.- 422 с.

44. Кирпичников В.М., Руденко А.П. Алгоритм размещения файлов во внешних запоминающих устройствах.- Управляющие системы и машины. 1977. № 5, с.46-50.

45. Козлик Г.А., Карась В.М., Завадский А.С. Разбиение АлСуна две непересекающиеся подсистемы с минимальной величиной суммарного потока между подсистемами,- В кн.: Автоматизация управления промышленными предприятиями.- Киев. Техн1-ка. 1975.

46. Козлик Г.А., Карась В.М. К вопросу о декомпозиции алгоритмических систем управления.- В кн.: Автоматизированные системы управления промышленными предприятиями.- Киев,Тех-н1ка. 1975.

47. Конвей Р.В., Максвел В. Л., Миллер Л.В. Теория расписаний» М.: Наука, 1975.- 360 с.

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

49. Корниенко А.В., Погребной В.К. Модель и алгоритм для разбиения цифровых вычислительных устройств на функциональные блоки.- Управляющие системы и машины. 1976, № 5, с.94-98.

50. Королев Л.Н. Операционные системы.- М.: Знание, 1977.-64с.

51. Королев Л.Н. Структуры ЭВМ и их математическое обеспечение.- М.: Наука, 1978.- 352.

52. Котов В.Е. Теория параллельного программирования. Прикладные аспекты,- Кибернетика, 1974, № I, с.Т-16, № 2, с.1-18.

53. Кофман А. Введение в прикладную комбинаторику,- М.: Наука, 1975,- 450 с.

54. Кутепов В.П., Кораблик Ю.П. Язык граф-схем параллельных алгоритмов.- Программирование, 1978, № I, с.З-П.

55. Кутепов В.П., Хентя Т. Эвристические методы составления расписаний для одного класса параллельных алгоритмов.-Труды МЭИ, 1974, вып.183, с.62-72.

56. Лебедев В.И., Липанов В.Д. Составление оптимального графикарешения задач на мультипрограммной ЭВМ.- Управляющие системы и машины. 1976, № 5, с.69-71.

57. Левин В.И. Логический метод оптимизации порядка решения задач в вычислительных системах.- Автоматика и вычислительная техника. 1982, № 3, с.55-61.

58. Липаев В.В. Проектирование математического обеспечения в АСУ.- М.: Советское радио, 1977.- 400 с.

59. Липаев В.В. Распределение ресурсов в вычислительных системах.- М.: Статистика, 1979.- 247 с.

60. Липаев В.В. Надежность программного обеспечения АСУ.- М.: Энергоиздат, 1981.- 240 с.

61. Липаев В.В., Колин К.К., Серебровский Л.А. Математическое обеспечение управляющих ЦВМ.- М.: Советское радио, 1972.526.

62. Липаев В.В., Яшков С.Ф. Эффективность методов организации вычислительного процесса в АСУ.- М.: Статистика, 1975.255 с.

63. Майерс Г. Надежность программного обеспечения,- М.: Мир, 1980.- 360 с.

64. Максимей И.В. Динамика функционирования вычислительных систем.- М.: Советское радио, 1978.- 150 с.

65. Максименков А.В. Анализ алгоритмов диспетчеризации задач мультипроцессорной ЭВМ,- Управляющие системы и машины. 1978, № 3, с.62-68.

66. Мартин Дж. Организация баз данных в вычислительных системах.- М.: Мир, 1978.- 616 с.

67. Мартин Дж. Программирование для вычислительных систем реального времени.- М.: Наука, 1975.- 360 с.

68. Палагин А.В., Писарский А.В., Погорельский С.Д, Об одной задаче оптимизации размещения данных,- Управляющие системы и машины. 1976, № 4, с.54-59.

69. Поляков А.С. Приближенный алгоритм нахождения наибольшего полного подграфа.- В кн.: Алгоритмы решения логико-комбинаторных задач, вып.2, Минек, 1976, с.104-108.

70. Поспелов Д.А. Введение в теорию вычислительные систем.-М.: Советское радио, 1972.- 280 с.

71. Прат Т. Языки программирования. Разработка и реализация.-М.: Мир, 1979.- 574 с.

72. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика.- М.: Мир, 1980.- 476 с.

73. Рыжков А.П. Алгоритм разбиения графа на минимально связные подграфы.- Известия-АН СССР, Техническая кибернетика. 1975, № 6, с.28-48.

74. Сбитнев А.И. 0 методах разбиения в задачах структурного анализа и синтеза программного обеспечения.- В кн.: Разработка и внедрение АСУ и средств автоматизации.- Киев.изд. Института автоматики, 1977, сЛ8-23.

75. Сбитнев А.И., Бубнов Г.М., Волков Ю.Д., Цареградский Д.Е. Об одном подходе к проектированию программного обеспечения АСУ ТП. В кн.: Вопросы проектирования программного обеспечения систем управления.- Киев, изд. ИК АН УССР, 1977,сЛ8-29.

76. Сбитнев А.И. Структурная организация и проектирование программного обеспечения АСУ ТП.- Управляющие системы и машины, 1982, № 5, с.38-42.

77. Сбитнев А.И., Шепетюк Б.Д. Декомпозиция программного обеспечения в многомашинных системах управления.- Киев, 1982.31 е.- Рукопись представлена Киевским ин-том автоматики. Деп. в Укр НИИНТИ 16 июля 1982, № 3698-82.

78. Сипсер Р. Архитектура связи в распределенных системах.-М.: Мир, 1981, т.1,2.- 744 е.

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

80. Тимофеев Б.Б., Архангельский В.И. Опыт создания АСУ ТП листопрокатных станов.- В кн.: Автоматизация прокатных станов.- М.: Металлургия, 1976, с.5-22.

81. Трахтенгерц Э.А. Программное обеспечение автоматизированных систем управления.- М.: Статистика, 1974,- 288 с.

82. Трусов С.С. Об эффективности простых диспетчеров.- Известия АН СССР. Техническая кибернетика, 1973, № 4, с.150-160.

83. Уздемир А.П. Декомпозиция при решении комбинаторной задачи определения моментов ввода предприятий.- Автоматика и телемеханика, 1977. № 10, с.110-121,

84. Управляющие вычислительные машины в АСУ технологическими процессами. Под ред. Т.Харрисона.- М.: Мир, т.1,2, 531 е., 532 с.

85. Флорес А. Организация вычислительных машин.- М.: Мир,1972т 428 с.

86. Харрари Ф. Теория графов.- М.: Мир, 1973.- 293 с.

87. Ху Т.С. Параллельное упорядочивание и проблема линии сборки.- В кн.: Кибернетический сборник.- М.: Мир, 1967, вып.4, с.43-56.

88. ЮО.Цареградский Д.Е. Организация функционирования программного обеспечения в АСУ ТП на широкополосных станах горячей прокатки. Дис.канд.тех.наук.- Киев, 1979.- 243 с.

89. Ю1.Цикритзис Д.,Бернстайн Ф. Операционные системы.- М.:Мир, 1977. 336 с.102» Шахбазян К.В., Сохранская B.C. Статистические испытания различных методов диспетчеризации для многопроцессорных систем»- Программирование» 1976» № 4, с.91-100.

90. Шахбазян К.В., Т^ушкина Т.А. Обзор методов составления расписаний для многопроцессорных систем. Зап.научн. семинаров Ленингр.отд. Мат. ин-та АН СССР, 1975, вып.54, с.229-258.

91. Шахбазян К.В., Т^шкина Т.А. О статистической эффективности алгоритмов решения одной задачи разбиения вершин графа.- Кибернетика. 1977. № 5, с.38-43.

92. Шварц Ю.С. Автоматический процесс упорядочения модулей и его приложение к параллельному программированию,- В кн.: Кибернетический сборник.- М.: Мир, 1964, вып.9, с.240-269.

93. Шепетюк Б»Д. Одна задача оптимального распределения. -Киев, 1982.-6 с.-Рукопись представлена Киевским ин-том автоматики. Деп. в УкрНИИНТИ 14 июля 1982, № 3685-82.

94. Шепетюк В.Д. Задачи оптимального быстродействия распределенного программного обеспечения.- В кн.: Математические методы и модели в автоматизированных системах управления и переработки информации. Киев, изд. Института автоматики, 1982, C.II-I6.

95. Шоу А. Логическое проектирование операционных систем.-М.: Мир, 1981.- 360 с.

96. Штрик А.А. Оценка затрат производительности на обмен данными в управляющих многомашинных комплексах систем реального времени.- Управляющие машины и системы. 1978. № 2.-с.38-44.

97. НО. Brinch. Hansen., P. Operating System, Principles, Prentice HaM, Inc., tdgewd Cei/Js, MS, 1975.

98. Hi. Charney И. R, Ptato D.L. Syyccient partitioning oj compononis. Jn Proc. Ann. Des.

99. Au tarnation Wareshop. July 15-18, 1968, p. 16-21. u2- Chrisio-fides Nicos., Brooier P. The optima?partitioning oj graphs. Si AM J. Appl. /lath., 1976, 30tA//>p.55-69.

100. Cof-fman E.G., eta? System Deadloc&s. Computing-Surveys, June /971 , Vol. J, No. 2 , p. 67-68.1Ц- Computer and Jo6- shop scheduling theory. / Ed. E. G • Co/man . Neb? York. John Wiley and Sons, 1976. - zoo p.

101. ConzaEez /l.J . deterministic processor scheduling. Computing Juroeye. W77. Vol. 9, N3 , p.-175-204.

102. Daly 1-5. Management oj Soflis-are Deve Сортеnt. IEEE Transactions on S.7. /977, N S. V. SE. 3. p. 229-242.

103. H9. Gligor V.D, Shaituci S.H.On dead foci detection en distributed systems. IE EE Trans. <£о/J ware £ng . t /98 о, 6f NS, p. 435-/1/10.

104. Ignall С., Schrade L . Application о J the Branch and Bound to some Flour-shop scheduling proSlems. J.O.R.S. 13 . N3 , /965, p. 400-A 12.

105. Iensen Paul A . Optimum Netiaori Partitioning. Operat. Ressearch. Vol. 19, No.4, i971, p. 9/6-932 .m. Johnson S.M. Optimal Tw-and Three Stage Productinon

106. Schedules With Setup Times JncEuded. flaw. Res. Log. Quart. Vol. /, Af-j, /954, p. 15-25.

107. Jones A. , Schwarz P. Sjaperience using multiprocessor systems a status repot. Compui. Surv., /980 . 12.1. A/2, p. 124 465.

108. Kernigh.au 5.W., lens. An Efficient Heuristic Procedure J or Partitioning. Graphs. Belt System Tech. Jorпа E. 1970, Vol. 49, A12г p. 43-56.

109. Kernighau 3. к/. OptimaE Sequent cat Partitions of Graphs. Journal of the Ass. /or Сотр. /lath /97-/, Vol. 18, ///.

110. Lampson &.W. A scheduEing, philosophy /or multiprocessing systems. Comrnuns ACM, /968, 44, A/5, p. 54 7 360.

111. Lehman /1.И. Programs , life, eye Ees , and Eai&s of Software evolution. Proc. IEEE. , /980 , 68 ,A/9, p. /060-/076.

112. Lin <S. Computer Solutions 0/ the Trav-eEing. Salesman

113. ProSEem. b.S.T.J. /965, VoE. U ,fl/0. 1st Low* T.C. Analysis of informations system mode EEvHih thansfer penalties. IEEE Trans .Comput./073 Vol. 22, N5, p.469-480.

114. Luies J. A . ComBinatoral solution in the Partitioningof Genera ( Graphs. IBM, j- Pes. DeveEop. 197SVoE.19,a/2. 155. Manacher 6. К. Production and staSiEization of reaE timetasl schedules. J-Assoc. Comput. flach/967, /4,/V5, p. 459 -465.

115. Ramamoorthy С. V.,Ckandy K.M., Conzafes /У.-7. OpiimaB schedaBing si rate gees in a muiiiprocessor system. IEEE Trans. Comput., 1972 , С-24 ,N2 . p. 137-146.

116. Schfageter G- Sine Ktasse von ProSternen der Arfails -tasiverteitung- in. Computernetzw-erken. AngeUandte Informatil 74. N12. Universila-L Kartsrufie.

117. Настоящий акт составлен в том, что Киевский институт автоматики имени ХХУ съезда Ю1СС сдал, а Новолипецкий металлургический завод принял в промышленную эксплуатацию АСУ толщиной полосы стана 2000 г.п. с УВГМ-6000.

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

119. Система создана в творческом содружестве Киевского института автоматики, ЦЯАМ и отдела АСУ НЛМЗ.

120. При создании системы разработаны новые технические решения, защищенные авторскими свидетельствами СССР №780917, №797813, №735350 и заявками на изобретение №2846445, №3241666, №3245679, №3279138 / см. приложение №1/.

121. Оцытно-промышленная эксплуатация и приемо-сдаточные испытания системы /протокол прилагается/ подтвердили работоспособность системы и ее соответствие требованиям технического задания.1. П о д п и с И:1. От НЛМЗ От КИА5.

122. Нач. Управления автоматизации и механизации

123. В.С.Журавлев Начальник ЛПЦ-3

124. A.Д.Белянский Начальник ОАСУ 'НЛМЗ

125. B.П.Саклаков Зам. начальника ЛПЦ-3

126. Ю.А.Аркадьев Начальник стана 2000

127. Г.В.Рассомахин Начальник уч-ка АСУ ЛПЦ-3 Н.В.Бочаров Начальник АСУ лпц-3

128. Ю.А.Ольшевский Начальник уч-ка ЦЛАМ НЛМЗ В.С.Доронин автоматике Щегольков

129. Зав. лабораторией, отв.исполнитель Е.В.Лео нидо в-Кане в-ский1. Зав. отделом

130. A.Й.Сбитнев Ведущий инженер

131. Г.М.Бубнов Ведущий инженер

132. B.Н.Петренко Ст.научный сотрудник

133. В. 11. Коже вин научный сотрудник

134. Д.Е.Цареградский научный сотрудник1. Л.Т.Ставнийчук1. Электрик1. Ст. Мл. Мл. мл.научный сотрудник

135. Т.В.Владимиренко научный сотрудник1. Б.Д.Шепетюком верно: етарь Киевского втоматикиъезда КПСС, к.т.н.1. Л.А.Пономаренко

136. УТВЕРЩАЮ" Директор Киевского института гч^ву|*матики им.ХХУ съезда КПСС ^'^ш^Й&к АН УССР•'•л. -r,-it /1 х * О \ ^-ч1. Тимофеев 1983г.1. ШШШШл" в.в.'i "LiSPi^• utt1. СПРАВКА

137. Справка выдана для представления по месту защиты диссертации на соискание степени кандидата технических наук.

138. Председатель объединенного научно-технического совета отделов "Вычислительный центр" и "Методов алгоритмического и программного обеспечения АСУ", зав. отделом, кандидаттехнических наук А.И.Сбитнев

139. Ученый секретарь НТС Л.И.Андреенко