Технология программирования в терминах служб и ее применение для задач календарного планирования тема автореферата и диссертации по математике, 01.01.10 ВАК РФ

ВВЕДЕНИЕ.

ГЛАВА I UPOIPAI^'MPOBAHME В ТЕРМИНАХ СЛУЖБ.

§ I Понятие "служба" и цель его введения

§ 2 Требования, предъявляемые к службам

§ 3 Способы программирования служб.

§ 4 Модульный подход к программированию и службы

§ 5 Понятия, близкие к службам.

§ 6 Особенности программирования служб на языке ПЛ/ в операционной системе ОС ЕС.

ГЛАВА 2 ПРИМЕНЕНИЕ СЛУЖБ В ЗАДАЧАХ КАЛЕНДАРНОГО

ПЛАНИРОВАНИЯ.

§ I Постановка задачи.

§ 2 Возможные подходы к решению задачи

§ 3 Выделение служб

§ 4 Служба Исходных данных.

§ 5 Служба Хранения расписания.

§ 6 Служба Составления и изменения расписания.

§ 7 Режим составления расписания

§ 8 Служба Диалога.

§ 9 Служба Ввода-вывода.

§ 10 Информационно-справочная служба.

ГЛАВА 3 ПРАКТИЧЕСКАЯ РАБОТА С СИСТЕМОЙ.

§ I Возможные реализации В-службы.

§ 2 Решение некоторых иллюстративных задач теории расписаний.

§ 3 Генератор задач-тестов

§ 4 Решение задач-тестов

§ 5 Преимущества диалогового подхода и технологии программирования в терминах служб.

§ 6 Перспективы развития системы

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

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

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

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

Технология программирования в терминах служб, разрабатываемая в лаборатории Исследования операций ЛГУ имени А.А.Жданова под руководством И.В.Романовского при активном и непосредственном участии диссертанта, может применяться (и уже применяется для решения широкого круга научных и производственных задач (например, [5] , [8], [9], [35] , [37] и др.).

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

Под службой понимается совокупность программных единиц (процедур, подпрограмм, входов в процедуры, подпрограмм и т.д.)» объединенных общей информацией, недоступной, вообще говоря, программному окружению [9] , [34] . Составляющие службу программные единицы будем называть режимами, а информацию, объединяющую режимы - собственной информацией службы или служебной информаци о ей.

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

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

- внешняя независимость службы от выбранной программной реализации,

- простота обращений к режимам,

- возможность существования нескольких Э-служб одновременно,

- возможность одновременного присутствия в программе нескольких Р-служб,

- возможность замены отдельных режимов в Э- и Р-службах без изменений остальных режимов,

- возможность включения новых режимов в службу.

Выполнение этих требований зависит от рассматриваемой задачи и от выбранного языка программирования. Службу можно программировать различными способами. Основные способы программирования служб в наиболее употребительных языках программирования высокого уровня (фортран, ПЛ/1, Алгол-60, Алгол-68 и др.) следующие,

1. Многорежимная процедура,

2. Многовходовая процедура.

3. Отдельные процедуры с общей областью для служебной информации.

4. Отдельные процедуры с параметрически заданной общей областью.

5. Структурное представление.

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

В последние годы довольно значительное число работ ( [з] , [12], [15], [17], [20], [25], [33], [44], [47] и многие другие) посвящено развитию принципов структурно-модульного подхода к программ мированию. Поэтому в данной работе анализируются различия структурно-модульного подхода (если здесь можно говорить о едином подходе) и технологии программирования в терминах служб. Рассматриваются ситуации, когда применение технологии программирования в терминах служб приносит ощутимые преимущества.

Необходимость введения понятий более общих, чем простая процедура или замкнутая подпрограмма, осознается многими программистами. Начиная с Симулы-67 [12], [l3] , где было введено понятие "класса" эта идея получает свое материальное воплощение. К настоящему моменту времени введено большое число понятий, родственных службам и классам: "кластер" в КЛУ [63] , [64] , его развитие в [18] , "пакет" в АДЕ [б] , [50] , метаструктуры данных в [68] . Вот почему в диссертации проводится подробный анализ различий нашего подхода и подходов, упомянутых выше. Основные отличия следующие [34] :

- следует исходить из нужд программирования реально встретившихся алгоритмов;

- выделение понятия "служба" вне связи с конкретным языком программирования позволяет найти и оценить способы программ мирования служб в имеющихся языках;

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

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

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

Пусть И - множество типов деталей, f\l - множество рабочих мест. На множестве М введено отношение частичного порядка, порождающее технологических граф сборки изделий С=(М,А, U), U • .М * М А , где А - множество дуг графа. V t^M задано: pi. - план производства детали, Si - время поступления детали в систему, Ttj- привязка операции Oij по обработке детали L к рабочему месту j, , j £ N , tf,j - время выполнения операции Oij, , V ЬА задана

Q - црименяемость (краткость) дуги. Временной интервал планирования предполагается равным (0?Т). Необходимо составить оптимальное по быстродействию расписание.

Среди всех моделей, описывающих данный класс задач, будем рассматривать только модель простого процесса обслуживания ( [23] , стр.16). Этот класс задач относится к задачам упорядочения. Последние концентрируют в себе "временный" аспект оперативно-календарного планирования, резко выделяясь среди других задач [41] . По своей структуре задачи упорядочения относятся к числу довольно сложных комбияаторых задач.

Методы целочисленного ( [55] , [65] , [69] ) и динамического программирования ( [51] , [бб] ), ветвей и границ ( |43] , [5J§, [56] , J60Jи другие) пригодны для получения точного решения лишь для задач небольших размеров. Метод ветвей и границ может использоваться для получения приближенного решения задач средних и больших размеров, однако, трудоемкость его велика. Поэтому для решения задач рассматриваемого класса применялись эвристические алгоритмы, разработанные автором. Все алгоритмы являются однократными и, как правило, не составляют оптимальных расписаний. Возникает задача улучшения полученных расписаний.

Для составления расписаний и их корректирования в режиме диалога "человек-ЭВМ" автором создана большая программная система, включающая в себя ряд эвристических алгоритмов, составляющих расписания, и обширный набор команд для внесения изменений в полученные расписания. Проектирование, программирование, отладка, тестирование и сопровождение такой системы в виде одной программы практически невозможно. Применение принципов структурно-модульного программирования, хотя и разрешает большую часть возникающих трудностей, однако, не обеспечивает систему надлежащей гибкостью при сопровождении. Возникает ряд проблем, связанных с одновременной работой с несколькими различными ал-горитами, хранением и корректированием нескольких расписаний, обеспечением возможности работы с различными терминалами и т.д. Применение технологии программирования в терминах служб позволило разрешить указанные трудности, и создать систему в приемлемые сроки. Возможно решение не только задач описанного выше класса, но и так называемой общей задачи теории расписаний, а также задачи to* и Беллмана-Джонсона.

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

- Исходных данных,

- Хранения расписания,

- Составления и изменения расписания,

- Диалога,

- Ввода-вывода,

- Информационно-справочная.

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

- открытие,

- чтение информациии о вершине,

- запись информации о вершине,

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

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

- открытие,

- занесение операций в расписание,

- чтение операций из расписания,

- очистка расписания,

- очистка части расписания,

- запись расписания,

- чтение расписания,

- удаление операции из расписания.

Различные реализации службы, в зависимости от формы представления расписания, могут иметь режимы, необходимые только для соответствующей формы. В частности, если расписание хранится в форме диаграмм Гаята [53] (а у нас такое представление выбрано в качестве основного), необходимы режимы:

- чтение символа,

- запись символа,

- чтение строки символов,

- запись строки символов.

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

- открытие,

- составление расписания,

- сдвиг части расписания,

- копирование части расписания,

- занесение узла врасписание,

- удаление узла из расписания,

- занесение группы узлов в расписание,

- удаление группы узлов из расписания,

- занесение группы операций в расписание,

- удаление группы операций из расписания,

- ограниченный сдвиг расписания влево,

- сдвиг расписания влево,

- сдвиг узла. функции по организации и поддержанию диалога выполняют службы Диалога, Ввода-вывода и Информационно-справочная. Непосредственное общение пользователя с системой осуществляется через службу Диалога. При этом для работы с системой достаточно знания системы команд диалога. Независимость диалога от используемого терминала обеспечивает служба Ввода-вывода. В систему включено три реализации этой службы: для работы с дисплеями, с консолью оператора и "альтернативной консолью" - ввод из последовательного файла и вывод в другой последовательный файл (для имитации диалога в режиме пакетной обработки). Перечислим основные режимы службы Ввода-вывода:

- ввести часть расписания,

- ввести расписание,

- ввести часть графика работы станка,

- ввести строку,

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

Интерактивная работа с системой требует получения различного рода информации о состоянии процесса составления расписания. Эту информацию выдает пользователю Информационно-справочная служба. Ее основные режимы следующие:

- открытие,

- занятость оборудования,

- плановая загрузка рабочих мест,

- учет производства деталей,

- разузлование,

- оценка времени сборки узла,

- проверка расписания на допустимость,

- обработка ошибок,

- помощь пользователю.

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

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

На защиту выносятся следующие результаты:

- приведено подробное описание технологии программирования в терминах служб»

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

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

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

- показаны преимущества работы в режиме "человек-ЭВМ" и технологии программирования в терминах служб на примере рассмотренной диалоговой системы,

- система прошла экспериментальную проверку на ряде задач календарного планирования.

1. Алгоритмический язык Алгол-60, пересмотренное сообщение, пер. с англ., М.,: Мир, 1965.

2. Безбородов Ю.М., Индивидуальная отладка программ, М.,: Наука, 1982, 190 с.

3. Браун П. (ред.), Мобильность программного обеспечения, М.: Мир, 1980.

4. Брукс Ф.П., мл., Как проектируются и создаются программные комплексы, М.: Наука, 1979.

5. Брэгман Л.М., Романовский И.В., Сурин С.С. и др., Пакет прс грамм по линейному программированию в терминах служб, В кн.: Системы программного обеспечения решения задач оптимального планирования. У Всесоюзный симпозиум. Нарва-Йыэссуу, М., 1978,с.192.

6. Вегнер П., Программирование на языке Ада, М.: Мир, 1983, 239 с.

7. Воденин Д.Р., Диалоговый режим для корректирования эвристических расписаний, рукопись деп. В ВИНИТИ 18 июля 1979г. № 2647-79.

8. Воденин Д.Р., Применение служб для решения задач календарного планирования в диалоговом режиме, рукопись деп. в ВИНИТИ10 апреля 1979г. Л 1249-79.

9. Воденин Д.Р., Романовский И.В., Программирование в терминах служб, Кибернетика, 1979, № 5, с.70-75.

10. Григас Г.К., Кластероподобный стиль программирования на языке ПЛ/1, В сб. "Алгоритмы и организация решения экономических задач", М.: Статистика, 1980, вып.14, с.96-104.

11. Григас Г.К., Купчунас Г., Абстрактные типы данных, Программирование ЭВМ, Вильнюс, 1980, № 3, с.9-49.- 139

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

13. Дал У., Мюрхауг Б., Нюгорд К., Симула-67, Универсальный язык программирования, М.: Мир, 1969, 99 с.

14. Дейкало Г.Ф., Новиков Б.А., Организация программы работы с устройством ЕС-7066 в операционной системе ОС-ЕС, сб. "Вопросы судостроения", серия матем, методы программирования и эксплуатация ЭВМ, вып.16, Л., 1979.

15. Дзйкстра Э., Дисциплина программирование, М.: Мир, 1968. 275 с.

16. Дкермейн К., Программирование на Ш1/360, М.: 1973.

17. Дзержинский Ф.Я., Тер-Сааков А.И., Технология программирования структурный поход , М.: ЦНИИатоминформ, 1978.

18. Иванников В.П., Использование кластеров в операционнойсистеме, ДАН, 1977, т.237, Л 2.- *

19. Илюшин A.M., Шгаркман B.C., Соглашение о связях между процессом и подсистемой, В кн.: Тезисы докладов и сообщений I Всесоюзной конференции по технологии программирования, секция П, К., 1979.

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

21. Келехсаев А.А., Беляев А.Н., Система интеграции и обработки данных СИ0Д1 и СИ0Д2, М.: Статистика, 1977.

22. Конвей Р.В., Джонсон Б., Максвелл У., Экспериментальные исследования распределения работ в соответствии с фиксированными правилами очередности их выполнения, сб. "Применение статистических методов в производстве", М.: 1963, с.212-232*

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

24. Лавров С.С., Универсальный язык программирования (алгол-бС М.: Наука, 1967, 196 с.

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

26. Майерс Г.Дж., Искусство тестирования программ, М.: Финансы и статистика, 1983, 176 с.

27. Мут Д., Томпосн Г., Календарное планирование, М.: Прогресс1966.

28. Пейгая Ф., Практическое руководство по Алголу-68, М.: Мир, 1979, 240 с^

29. Пересмотренное сообщение об Алголе-68, ред. Ван-Вайн-Гаар-ден и др., М.: Мир., 1979, 533 с.

30. Подчасова Т.П., Об оценке правил предпочтения, сб. "Автоматизированные системы управления предприятиями, труды семинара", вып.X, К., 1968, с.5-46.

31. Португал В.М., Решение задач календарного планирования с помощью правил предпочтения, сб. "Прикладная матем, и кибер-нет. Материалы к Всесоюз. межвузовскому симпозиуму по прикл. матем. и кибернет.", Горький, 1967, 1967, с.254-258.

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

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

34. Романовский И.В., Анализ понятия "служба", Кибернетика, 1981, № 4, с.66-72.

35. Романовский И.В., Опыт программирования оптимизационных пакетов, в кн., Тезисы докл. и сообщ. Всесоюз. конференции "Методы мат. логики в проблемах искуственяого интеллекта и систематич. программирование", ч.2, Вильнюс,. 1980, с.244-248.

36. Романовский И.В., О технологии программирования сложных алгоритмов, в кн.: "Тез. докл. I Всесоюз. конф. по технологии программирования, секция П", К., 1979, с.52.

37. Романовский И.В., Пакетный вариант симплекс-метода. Эволюционно описание основных конструкций, в кн. Исследование операций и ститистич. моделирование, Л., 1979, с.55-71.

38. Сакман Г., Решение задач в системе "человек-ЭВМ", М.: Мир, 1973.

39. Семенов А.И., Португал В.М., Задачи теории расписаний в календарном планировании мелкосерийного цроизводства, М: Наука, 1972.

40. Синсер Р., Архитектура связи в распределенных системах, М.: Мир, 1982.

41. Смоляр Л.И., Модели оперативного планирования в дискретном производстве, М.: Наука, 1978, 320 с.

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

43. Тютюкин В.К., Нахождение оптимальных планов в многооперационных процессах обработки изделий методом "ветвей и границ",сб. "Применение матем. в эконом.", вып.6, Л., Ленингр. ун-т, 1970, с.29-45.

44. Турский В., Методология программирования, М.: Мир, 1981, 265 с.

45. Фролов Г.Д., Олюнин В.Ю., Практический курс программирования на языке ПД/I, М.: Наука, 1983, с.384.

46. Харари Ф., Теория графов, М.: Мир, 1973, 300 с.

47. Хьюз Дк., Мичтом Дж., Структурный подход к программированию, М.: Мир, 1980, 178 с.

48. Шкурба В.В., Подчасова Т.П., Пшичук А.П., Тур Л.П., Задачи календарного планирования и методы их решений, К., Наумкова думка, 1966.

49. Шойхет Б.П., Симплекс-метод для ускоренной оптимизации, М., Экономика и мат.методы, т.9, № 4.

50. Язык программирования Ада, предварительное описание, -Пер. с англ., М.: Финансы и статистика, 1982, 190 с.

51. Bellman R.,Gross О*, Some combinatorial problems arising in the theorv of multistage processes, J. Soc. Industr. and Appl. Math. 2, N3, 1954, p. 175 183

52. Brown A.P., T.»mnicki Z.A., Some applications of the branch and bound algorithm to the machine scheduling problem,Oper. Res. Quart 17, N 2, 1966, p. 173 181

53. Clark W., The Guntt chart, (3-d Edition), London, Pittman and sons, 1952

54. Dijkstra E.W., Structured programming, Software engeneering techniques, NATO scientific affairs division, Bruesel 39, Belgium, p. 84 m 88

55. Giglio R.J., Wagner H.M., Approximate solution to the three machine scheduling problem, Oper. Res. 12, N 2, 1964,p. 305 324

56. Greenberg H.H., A branch -boiirid solution to the general scheduling problem, Oper. Res. 16, N 2, 1968, p. 353-361

57. IBM Operating System/360, Supervisor and data management services, « 1Ш corporation data process division, New York

58. Jacks on J.R., An extension of Johnsons results on job^lot scheduling,Nav. Res. Log. Quart, 3, N 31, 1956,p. 201 203

59. Johnson S.M., Optimal two and three stage productionschedules with setup times included, Hav. Res. Log. Quart 1, 11, 1954, p. 61 68

60. Lawler E.L., Wood P.E., Branch and bound methods: a survey , Oper. Res. 14, N 4, 19 66, p. 699 719