Цена доставки диссертации от 500 рублей 

Поиск:

Каталог / ФИЗИКО-МАТЕМАТИЧЕСКИЕ НАУКИ / Математика

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

Диссертация

Автор: Воденин, Дмитрий Ростиславович

Заглавие: Технология программирования в терминах служб и ее применение для задач календарного планирования

Справка об оригинале: Воденин, Дмитрий Ростиславович. Технология программирования в терминах служб и ее применение для задач календарного планирования : диссертация ... кандидата физико-математических наук : 01.01.10 Ленинград, 1984 183 c. : 61 85-1/263

Физическое описание: 183 стр.

Выходные данные: Ленинград, 1984






Содержание:

ВВЕДЕНИЕ
Глава I UPOrPAIVMPOBAHME В ТЕРШНАК СЛУЖБ §I Понятие "служба" и цель его введения §Требования, предъявляемые к службам §Способы программирования служб §Модульный подход к программированию и службы §Понятия, близкие к службам §Особенности программирования служб на языке БЛ/1 в операционной системе ОС ЕС
Глава II ПРШУЕНЕНИЁ СЛУЖБ В ЗАДАЧАХ КАЛЕНДАРНОГО ПЛАНИРОВАНИЯ §I Постановка задачи §Возможные подходы к решению задачи §Выделение служб §Служба Исходных данных §Служба Хранения расписания §Служба Составления и изменения расписания §Режим составления расписания §Служба Диалога §Служба Ввода-вывода §Информационно-справочная служба
Глава III ШАКТИЧЕСКАЯ РАБОТА С СИСТЕМОЙ §I Возможные реализации В-службы §Решение некоторых иллюстративных задач теории расписаний §Генератор задач-тестов §Решение задач-тестов §Преимущества диалогового подхода и технологии программирования в тершшах служб §Перспективы развития системы ЖТЕРАТУРА
ПРИЛОЖЕНИЕ

Введение:
Начиная с пятидесятых годов задачи календарного планирования привлекают внимание спеодалистов по исследованию операций. Уже на начальной стадии развития теории расписаний стало ясно, что задачи оптимального календарного планирования исключительно трудоешш. Значительная доля полученных результатов носит негативный характер* Поскольку от выбора постановки и качества решения зависит рациональная организация работы и эффективность производства, задачи имеют важное народохозяйственное значение. Сложность рассматриваемых задач диктует и специфику подхода к их решению. Необходимо создание больших програхлмных систем и программных комплексов, тесно взаимодействующих с имеющимися базами данных и системами АСУ. Поэтому на первый план выдвигаются вопросы оптШальной организации вычислительного цроцесса, проектирования, отладки, тестирования и сопровождения систем. Все это предъявляет повышенные требования гибкости, простоты модификации и удобства сопровождения таких систем. Применение языков программирования высокого уровня, принципов модульного и структурного программирования позволяет разрешить многие возникающие трудности, однако, в ряде случаев необходимы новые принципы и новые технологии. Технология программирования в терминах служб, разрабатываемая в лаборатории Исследования операций ЛГУ имени А.А.Дданова под руководством И.В.Роглановского при активном и непосредственном участии диссертанта, может применяться (и уже применяется для решения широкого круга научных и производственных задач (например, [5] [8], [9j, [35] [37] и др.).Технология программирования в терлшнах служб, ее применение цри проектировании, программировании, отладке, тестировании и сопровождении интерактивной системы, предназначенной для составления и корректирования расписаний, решение ряда задач календарного планирования с помощью этой системы, преимущества диалогового похода и программирования в терминах служб и составляют основное содержание данной работы. Под службой понимается совокупность программных единиц (процедур, подпрограмм, входов в процедуры, подпрограмм и т.д.)» объединенных общей информацией, недоступной, вообще говоря, програьшному окружению [9] [34] Составляющие службу программные единицы будем называть режимами, а информацшо, объединяющую режимы собственной информацией службы или служебной информацией. Будем различать "вид" службы, определяемым совокупностью требований со стороны программного окружения, включая стандарты обмена и подразумеваемые обязанности, программную реализацию службы данного вида и информационную реализацию этого вида (возможно, в данном программном воплощении). Б случае, если потребуется различить эти уровни служб, будем говорить соответственно о В-, Р- и Э-службах (вид, реализация, экземпляр), используя в остальных случаях просто тершш "служба". Этого же соглашения будем придерживаться и для режимов. Рассмотрим требования, которые предъявляются к службам со стороны программного окружения, и на которые следует ориентироваться при программной реализации. Основные требования таковы: внешняя независимость службы от выбранной программной реализации, простота обращений к режимам, возможность существования нескольких Э-служб одновременно, возможность одновременного присутствия в программе нескольких Р-служб, возможность замены отдельных режимов в Э- и Р-службах без изменений остальных режимов, возможность включения новых режимов в службу, Выполнение этих требований зависит от рассматриваемой задачи и от выбранного языка програгймирования. Службу можно программировать различными способами. Основные способы программирования служб в наиболее употребительных языках программирования высокого уровня (фортран, ПЛ/!, 1лгол-60, Алгол-б8 и др.) следующие. 1. Шогорежимная процедура. 2. Шоговходовая процедура. 3. Отдельные процедуры с общей областью для служебной информации. 4. Отдельные процедуры с параметрически заданной общей областью. 5. Структурное представление. Одним из основных отличий службы от простой Щ)Оцедуры или замкнутой подпрограьшы является ее многорежимность. Важно также отсутствие глобальной информации (кроме системных средств). Последнюю службу должны получать извне и передавать во вне только через специальные оговорочные интерфейсы, не зависящие от внутреннего представления инф-ормации В последние годы довольно значительное число работ [з] [12], [15], [17], [20], [25], [33], [44], [47] и многие другие) посвящено развитию принципов структурно-модульного подхода к программмированйю. Поэтому в данной работе анализируются различия структурно-модульного подхода (если здесь можно говорить о едином подходе) и технологии программирования в терьшнах служб. Рассматриваются ситуации, когда применение технологии программирования в терминах служб приносит ощутимые преимущества, Необходимость введения понятий более общих, чем простая процедура или замкнутая подпрограмма, осознается многими црограммистами. Начиная с Симулы-67 (12], [l3] где было введено понятие "класса" эта идея получает свое материальное воплощение. К настоящему моменту времени введено большое число понятий, родственных службам и классам: "кластер" в М У [бЗ] [б4] его развитие в [IS] "пакет" в АДЕ [б] [50] метаструктуры данных в [бз] Вот почему в диссертации проводится подробный анализ различий нашего подхода и подходов, упомянутых выше. Основные отличия следующие [34] следует исходить из нужд программирования реально встретившихся алгоритмов; выделение понятия "служба" вне связи с конкретным языком программирования позволяет найти и оценить способы программ мирования служб в имеющихся языках; на основе служб можно построить (и это сделано) технологию программирования, обеспечивающую автономную разработку и отладку, а также тестирование фрагментов програьж со стандартными программными средствами, ввести модульную структуру, удобную для разработки пакетов; для новых языков программирования такое понятие и связанная с ним классификация дает возможность оценить современность и законченность вновь вводимых конструкций, задач небольших размеров. Метод ветвей и границ может использоваться для получения приближенного решения задач средних и больших размеров, однако, трудоемкость его велика. Поэтому для решения задач рассматриваемого класса применялись эвристические алгоритмы, разработанные автором. Все алгоритмы являются однократными и, как правило, не составляют оптимальных расписаний. Возникает задача улучшения полученных расписаний. Для составления расписаний и их корректирования в режиме диалога "человек-ЭВМ" автором создана большая программная система, включающая в себя ряд эвристических алгоритмов, составляющих расписания, и обширный набор команд для внесения изменений в полученные расписания. Проектирование, программирование, отладка, тестирование и сопровождение такой системы в виде одной программы практически невозможно. Применение принципов структурно-модульного программирования, хотя и разрешает большую часть возникающих трудностей, однако, не обеспечивает систему надлежащей гибкостью при сопровождении. Возникает ряд проблем, связанных с одновременной работой с несколькими различными алгоритами, хранением и корректированием нескольких расписаний, обеспечением возможности работы с различными терминалами и т.д. Применение технологии программирования в терминах служб позволило разрешить указанные трудности, и создать систему в приемлемые сроки. Возможно решение не только задач описанного выше класса, но и так называемой общей задачи теории расписаний, а также задачи mf И Беллмана-Джонсона. Разбиение системы на службы производилось при ее проектировании по принципу использования общей информации для выполнения ряда однотипных действий. Выделено шесть служб: Исходных данных, Хранения расписания, Составления и изменения расписания, Диалога, Ввода-вывода, Информационно-справочная. Служба Исходных данных необходима для уменьшения зависимости остальной части системы от исходных данных, их организации, размещения, конкретного представления. Б рассматриваемых реализациях службы вся исходная информация находится в цепных списках структур четырех типов: деталей-вершин, дуг, операций и рабочих мест. Основные режимы, составляющие службу, следующие: открытие, чтение информациии о вершине, запись инфорглации о вершине, получение следующей вершины в списке, и аналогичные режимы для дуг, операций и рабочих мест. Б случае, если источником исходной информации служит банк данных, большая нагрузка ложится на режим открытия, который становится интерфейсом между системой и банком данных. Алгоритьш, составляющие расписание, команды диалога, предназначенные для их корректировки, не должны зависеть от того, в каком виде, где и в какой форме хранится информация, описывающая расписание. Независиглость обеспечивает служба Хранения расписания. Перечислим основные режимы службы: открытие, занесение операций в расписание, чтение операций из расписания, очистка расписания, II очистка части расписания, запись расписания, чтение расписания, удаление операции из расписания. Различные реализации службы, в зависимости от формы представления расписания, могут иметь режимы, необходимые только для соответствугощей формы. В частности, если расписание хранится в форме диаграмм Ганта [53] (а у нас такое представление выбрано в качестве основного), необходимы режимы: чтение символа, запись символа, чтение строки символов, запись строки символов. Служба Составления и изменения расписания является основной в системе. Режим составления расписания реализуется с помощью нескольких эвристических алгоритмов, причем все они могут одновременно присутствовать в программе. Остальные режимы выполняют функций, связанные с корректировкой расписаний. Основные режимы службы следующие: открытие, составление расписания, сдвиг части расписания, копирование части расписания, занесение узла врасписание, удаление узла из расписания, занесение группы узлов в расписание, удаление группы узлов из расписания, занесение группы операций в расписание, удаление группы операций из расписания, ограниченный сдвиг расписания влево, сдвиг расписания влево, сдвиг узла. фикции по организации и поддержанию диалога выполняют службы Диалога, Ввода-вывода и Информационно-справочная. Непосредственное общение пользователя с системой осуществляется через службу Диалога. При этом для работы с системой достаточно знания системы команд диалога. Независимость диалога от используемого терминала обеспечивает служба Ввода-вывода. В систему включено три реализации этой службы: для работы с дисплеями, с консолью оператора и "альтернативной консолью" ввод из последовательного файла и вывод в другой последовательный файл (для имитации диалога в режиме пакетной обработки). Перечислим основные режимы службы Ввода-вывода: ввести часть расписания, ввести расписание, ввести часть графика работы станка, ввести строку, ввести группу параметров, а также аналогичные режимы вывода и режим открытия. Обеспечена возможность одновременного присутствия всех этих реализаций в системе и работа с различными их комбинациями. Интерактивная работа с системой требует получения различного рода информации о состоянии процесса составления расписания. Эту информацию выдает пользователю Информационно-справочная служба. Ее основные режимы следующие: открытие, занятость оборудования, плановая загрузка рабочих мест, учет производства деталей, разузлование, оценка времени сборки узла, проверка расписания на допустимость, обработка ошибок, помощь пользователю. Большое внимание было уделено тестированию системы. Вначале проверялась правильность работы каддой службы отдельно. В случае необходимости вставлялись режимы-заглушки, а иногда и службы-заглушки. Для полного и всестороннего тестирования системы была подготовлена програмьш генаратор задач-тестов. Использование датчика случайных чисел и большое число параметров позволило получить много разнообразных задач-тестов. Расписания, составленные для ряда задач-тестов с помощью эвристических алгоритмов, корректировались с применением всех команд диалога. Во всех рассмотренных задачах удалось улучшить полученные расписания, а в некоторых случаях были получены оптимальные расписания, Таким образом, применение технологии программирования в терминах служб позволило создать достаточно объемную и сложную программную систему, обладающую большой гибкостью, надежностью, простотой эксплуатации, хорошо приспособленную к дальнейшему совершенствованию и модификациям. Наличие в системе нескольких алгоритмов и развитой диалог позволяют получать оптимальные и близкие к оптимальным расписания для широкого круга задач календарного планирования, На защиту выносятся следующие результаты: приведено подробное описание технологии программирования в терминах служб» произведено сравнение модульного подхода к программированию и технологии программирования в терминах служб, рассмотрены понятия, близкие к службам, на основе этой технологии создана интерактивная система, предназначенная для решения задач календарного планирования, в составе системы разработан и запрограгширован ряд эвристических алгоритмов для составления расписаний, показаны преимущества работы в режиме "человек-ЭВМ" и технологии программирования в терминах служб на примере рассмотренной диалоговой системы, система прошла экспериментальную проверку на ряде задач календарного планирования.