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

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

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

Как показывают теоретические исследования и накопленный вычислительный опыт, многие дискретные задачи эквивалентны с точки зрения их вычислительной сложности [3,4]. Это так называемые универсальные или полиномиально полные задачи. В настоящее время существует значительное число задач, имеющих экспоненциальную оценку сложности [5,6]. К ним относятся задачи целочисленного и линейного программирования, задачи о коммивояжере, о размещениях, об обработке деталей на станках и т. д. [7,8]. Решением этих задач занимались известные отечественные ученые Алексеев О. Г., Романовский И. В., Поспелов Д. А., Тараканов В. Е., Горбатов В. Е. и многие другие. Существуют предположение, что все эти задачи неразрешимы за полиномиальное время.

Анализ вычислительной сложности задачи позволяет выделить классы задач, для которых существуют эффективные алгоритмы [9, 10, 11].

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

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

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

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

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

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

Разработка моделей планирования заданий актуальна не только для ВС. Подобные модели существуют и в промышленности (распределение заданий по станкам, по участкам и т. д.), на транспорте (планирование перевозок) и т. д. Поэтому в диссертационной работе использованы понятия из теории массового обслуживания: задание (задача) — канал обслуживания (любое устройство, выполняющее задание).

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

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

Важность выбора критерия загрузки определяется следующим. Если используется минимаксный критерий, то обеспечивается минимальное время решения всей совокупности задач. Если используется критерий равномерности, то эта задача обеспечивает максимальную равномерность загрузки. При использовании минимаксного критерия, задача в данной постановке сводится к задаче о куче камней, которая подробно исследована в работе [15].

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

В диссертационной работе решаются следующие задачи:

— разработка модели для оптимального планирования заданий по каналам обслуживания, согласно минимаксному критерию;

— разработка модели для оптимального планирования заданий по каналам обслуживания с учетом критерия равномерности;

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

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

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

Объектом исследования в диссертационной работе являются оптимизационные модели распределения m независимых заданий на п параллельно работающих каналов обслуживания.

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

В экспериментальных исследованиях применялось моделирование на ЭВМ.

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

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

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

— метод оценки отклонения минимаксного критерия по оптимальному критерию равномерности для трехканальной модели распределения;

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

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

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

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

Диссертационная работа состоит из пяти разделов, заключения и приложения.

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

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

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

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

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

Заключение

содержит основные выводы о работе.

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

Результаты работы внедрены: в Донском филиале Центра Тренажеростроения при выполнении опытно-конструкторских работ, в соответствии с Государственным контрактом № 041−8543/96−9.4.1.

— в госбюджетной НИР № 1 817 011 944 «Разработка принципов и создание автоматизированных обучающих систем»;

— в НИР «Моделирующий комплекс для исследования и отработки навыков управления шагающим экскаватором» .

Научные и практические результаты, полученные в диссертации и изложенные в 8 статьях, 2 отчетах по госбюджетным НИР.

Ожидаемый экономический эффект от внедрения составил 32 тыс. руб.

Результаты диссертационной работы докладывались и обсуждались:

— на республиканском совещании — семинаре «Задачи учебной САПР микропроцессорных систем обработки информации» от 26−28 января 1988 г., г. Новосибирск.

— на международной научно-технической конференции «Молодая наука новому тысячелетию» от 24−26 апреля 1996 г., г. Набережные Челны.

— на четвертой всероссийской научной конференции с международным участием молодых ученых и аспирантов от 15 ноября 2001 г., г. Таганрог.

— на третьей Всероссийской научной интернет-конференции от 19 ноября 2001 г., г. Тамбов.

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

Все результаты, представленные в диссертационной работе, получены автором лично.

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

5.5. Выводы.

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

При выполнении государственного контракта № 041−8543/96−9.4.1, был разработан один из основных пакетов прикладного программного обеспечения. Описаны разработанные программные составляющие данного.

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

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

ЗАКЛЮЧЕНИЕ

.

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

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

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

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

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

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

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

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

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

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

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

Теоретические и практические результаты, полученные в диссертационной работе, использованы в опытно-конструкторской работе, выполненной в соответствии с Государственным контрактом № 041−8543/969.4.1. Исследования автора выполнялись также в соответствии с планом выполнения госбюджетной НИР № 1 817 011 944, выполненной в рамках кафедральной тематики, а также в НИР «Моделирующий комплекс для исследования и отработки навыков управления шагающим экскаватором» .