автореферат диссертации по приборостроению, метрологии и информационно-измерительным приборам и системам, 05.11.16, диссертация на тему:Планирование работы комплекса наземных средств обработки результатов дистанционного зондирования Земли

На правах рукописи

Склеймин Юрий Борисович

ПЛАНИРОВАНИЕ РАБОТЫ КОМПЛЕКСА НАЗЕМНЫХ СРЕДСТВ ОБРАБОТКИ РЕЗУЛЬТАТОВ ДИСТАНЦИОННОГО ЗОНДИРОВАНИЯ ЗЕМЛИ.

Специальность 05.11.16 -" Информационно-измерительные и управляющие системы' (авиационная и ракетно-космическая техника)

Автореферат диссертации на соискание ученой степени кандидата технических наук

Москва - 2004

Работа выполнена на кафедре "Информационные технологии" Московского авиационного института (государственный технический университет) "МАИ"

Научный руководитель - кандидат технических наук, доцент Максимов Н.А.

Официальные оппоненты:

Доктор технических наук, профессор Хахулин Г. Ф.

Кандидат технических наук Циклин Л. И.

Ведущая организация - Федеральное Государственное Унитарное Предприятие "НИИ Точных приборов".

Защита состоится_, на заседании диссертационного совета Д

212.125.11 при Московском авиационном институте (государственный технический университет) "МАИ" по адресу: 125993, А-80, ГСП-3, Москва, Волоколамское ш., 4, зал заседаний Ученого Совета МАИ.

Автореферат разослан

Ученый секретарь Диссертационного совета

Горбачев Ю. В.

Общая характеристика работы Актуальность проблемы.

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

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

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

Положения, выносимые на защиту:

Научная новизна.

1. Разработана классификация задач планирования, основанная на введенные семи признаков S, W, V, N R, Р, Е, которые могут характеризовать ту или иную постановку задачи. Признаки описывают отдельные компоненты задачи построения расписания.

2. Предложена модель сложного вычислительного процесса в виде графа G = (Т^ф, где J - множество задач обработки, подлежащих распределению, S - множество информационных связей между задачами, К - множество, определяющее различные типы связей между задачами

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

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

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

Достоверность результатов:

- обеспечивается корректным применением математических методов;

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

Практическая значимость и внедрение результатов.

1. Разработаны новые алгоритмы планирования загрузки технических средств ЛВС и алгоритмы составления расписаний запуска работ на выполнение в распределенной системе обработки данных.

2. Предложенные алгоритмы позволили автоматизировать процедуры составления плана загрузки вычислительных средств и запуска работ на выполнение и использовались при создании автоматизированного рабочего места (АРМ) планирования для автоматизированной системы архивного хранения изображений (АСАХ "Ретро-ГИС"). Это нашло отражение в полученном акте внедрения результатов диссертационной работы.

3. Выполненные разработки легли в основу лабораторных работ по дисциплине «Проектирование информационных систем», использованы при чтении лекций по одноименному курсу на кафедре № 308 МАИ.

Апробация работы.

Основные результаты работы докладывались и получили одобрение на следующих научных конференциях и семинарах:

1. Международная конференция по автоматическому управлению Московского авиационного института и Пекинского аэрокосмического университета. Москва, 1993г.

2. XI международный научно-технического семинар "Современные технологии в задачах управления, автоматики и обработки информации". Алушта, 2002 г.

4. Международная научная конференция "Информационные технологии в естественных науках, экономике и образовании". Саратов - Энгельс 2002 г. Публикации.

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

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

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

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

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

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

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

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

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

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

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

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

1) Признаки типа S. Среди них выделим:

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

прошествия некоторого заранее известного времени. Такую ситуацию будем обозначать с помощью признака 81 (£).

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

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

2) - признак, характеризующий систему средств обслуживания или обработки

задач. Целесообразно выделить следующие ситуации: и«, - имеется неограниченное число средств обслуживания.

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

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

3) V - имеются ресурсные ограничения, зависящие от времени, которые должны выполняться при реализации задачи на конкретном средстве обработки. Например, объем оперативной памяти, устройства ввода-вывода и т.д.

4) N - имеются ограничения на допустимый временной интервал выполнения каждой задачи (т. е. для задачи (задач) определены интервалы, в течение которых она должна быть выполнена).

5) R - признак, характеризующий время выполнения задачи на средствах обработки. Ситуацию, когда до составления расписания известны длительности выполнения каждой задачи на том или ином средстве обработки, будем обозначать Я,,. Если же

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

6) Р - признак, используется, если существует необходимость обмена информацией между средствами обработки при выполнении информационно или логически зависимых задач. Привлекается для описания в том случае, когда для передачи информации требуется время, сравнимое со временем выполнения задач. Если время передачи информации не учитывается - признак в описании задачи не указывается;

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

Введенные семь типов признаков S, ^ V, N R, Р, Е могут характеризовать ту или иную постановку задачи. Необходимо отметить, что если признаки V, N Р, и Е не указываются, то это означает, что соответствующих им условий в постановке задачи нет. Например, перечень характеризует такую постановку задачи

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

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

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

Таблица 1. Классификация задач построения расписания.

Признаки S и V N R P E

Задачи

Упорядочение работ во времени в системах конвейерного типа (задача Беллмана-Джонсона). S,(0) Uo Ro Есть

Сетевые задачи упорядочения. Si(0), SL(0) u. R. Есть

Задачи многостадийного планирования. s,(0) u„ - Есть Ro - Есть

Задачи распараллеливания в многопроцессорных вычислительных системах. Для однородных вычислительных сетей. s,(0) s,(0) U„ Uo Ro Ro Есть Есть Есть

Для неоднородных вычислительных сетей. s,(0). s,(0) U„ U„ Ro Ro Есть Есть Есть

Задача планирования работы ЛВС S,(Q U„ Есть Есть R® - -

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

Проведенный краткий обзор моделей и методов теории расписаний позволяет определить основные направления исследований, связанных с построением рационального плана функционирования ЛВС. Следует заметить, что постановка задачи не позволяет применить какой-либо из известных и рассмотренных методов (или их комбинацию) для формирования расписания обслуживания заявок. Как показывает анализ исследуемой задачи, рассматриваемая проблема является NP-сложной в вычислительном смысле. Речь может идти только о построении квазиоптимального эвристического алгоритма, обеспечивающего нахождение допустимого решения. Для приближенного решения большого количества комбинаторных задач может быть использован подход, называемый поиском в локальной окрестности (LNS - local neighborhood search). Алгоритм решения задачи планирования работы ЛВС будем строить в классе LNS с использованием перестановочного приема.

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

где J - множество задач обработки;

S - множество информационных связей;

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

J - множество задач обработки (множество узлов графа), которое образуют функциональные программы выполняющиеся в ЛВС.

Каждой задаче обработки присвоим условный порядковый номер, т.е. ,

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

- множество задач первого типа (обычные задачи);

- множество задач второго типа (задачи поддержки). Множество информационных связей S - включает 3 типа связей.

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

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

Формально связи S информационного графа (1) можно задать с помощью трех матриц смежности: элементы которых определяются следующим образом:

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

Естественно:

Параметры задач, подлежащих реализации на неоднородной вычислительной системе, можно записать с помощью трех матриц: и

и одного вектора

Элементы каждой матрицы определяются следующим образом: [е)| - время решения i -ой задачи (или 1-ой ее части, если /еЛ") на ¡-й вычислительной машине сети (/= 1,2,...,л;у—1,2,...,т). Если ьая задача не может выполняться на ¡-й вычислительной машине, то ъ, =оо.

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

вычислительной машине с номером Если i-я задача (/ е Л11) не может выполняться на ¡-ой вычислительной машине, то ¿¡/=оо. Для задач /еЛ1, ¿¡/ = 0 ( i=1,2,...,n; }=1,2,...,ш).

|7»| - время, которое должно разделять задачи с номерами / и информационно связанные между собой. Здесь i=1,2,...,n;j=1,2,...,n

|Л| - количество ресурса доступности V (см. характеристики ЛВС), который

необходим для выполнения ьой задачи, где i= 1,2,..,п Границы допустимых временных интервалов формализуем с помощью двух векторов:

[Л^!^. Здесь - левая граница допустимого интервала выполнения ьой

задачи, 1 е Л. X, - правая граница допустимого интервала выполнения ьой задачи, /6 Л

Необходимость учета допустимых временных интервалов значительно усложняет задачу. Для описания параметров ЛВС введем:

- множество средств обработки и (и=1,2,...,т, где т общее число вычислительных машин, образующих ЛВС);

Для каждой ЭВМ сети может существовать график доступности данной машины для выполнения задач. Для формализации этого условия введем в рассмотрение некоторый ресурс ЭВМ V (будем называть его ресурсом доступности).

УМ- ресурс доступности ьго вычислительного средства, г е и , который может быть выделен в момент времени 1 для решения задач, входящих в ОВП. ОВП -совокупность взаимосвязанных задач (функциональных программ - ФП), которые могут выполняться только последовательно. (В рассматриваемом случае - если ЭВМ доступна , иначе .) В общем случае, , где - граница

ресурса доступности ьой ЭВМ - неотрицательная ступенчатая функция времени 1

которое изменяется от 0 до 24 часов, т.е. , поскольку именно в таких

пределах определен общий интервал планирования задач, составляющих все ОВП.

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

, каждая компонента которого содержит две составляющие: и,]. Здесь /, - время начала выполнения задачи с номером 1, ; е J и, - номер средства обработки, на котором выполняется 1-ая задача. Действительно, располагая вектором X, всегда можно определить момент времени окончания любой задачи по формуле:

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

-требуется найти хотя бы один вектор удовлетворяющий

системам ограничений:

У) = У) V 8г(/, У)

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

13

пары задач i и у решаемых на одной и той же вычислительной машине (и,=щ=к) должно выполняться лишь одно из неравенств:

— /д > Т ^ - выполнению работы i предшествует выполнение работы ]

^ Т^ - выполнению работы предшествует выполнение работы i.

Введем целочисленную переменную:

1, если задача I предшеств>ет задаче ] на машине Л

(ннеобязатльно непосредственно); О, в противном случае;

Теперь сформулированные выше ограничения типа «или-или» можно записать в виде двух условий, каждое из которых должно быть выполнено:

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

, т. к. каждая машина выполняет каждую работу не более одного раза.

Пусть задача i предшествует то есть и = 1, тогда (7) в точности

совпадает со вторым условием «или-или», а первое условие благодаря большому параметру М превращается в избыточное ограничение, не противоречащее всей системе в целом.

Система ограничений (3), состоящая из (п-1)2 неравенств задает соотношения, которым в соответствии с информационным графом, должны удовлетворять моменты начала и окончания всех задач.

Система ограничений (4), состоящая из 2л неравенств, определяет условия выполнения всех задач в границах допустимых временных интервалов.

Система из п неравенств (5) задает условия проверки ресурса доступности средств обработки на интервалах времени, соответствующих продолжительности выполнения задач.

Системы неравенств (6) и (7) определяют тот факт, что в любой момент времени на любой ЭВМ сети может выполняться лишь одна из задач (для каждой

ЭВМ своя) множества .Г

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

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

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

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

задач обработки, порождаемых всеми N заявками, обрабатываемыми в РСОД в течение периода планирования; Лк - множество задач, порождаемых к-ой заявкой;

Б = {5(1,,/)} - множество ребер графа или множество связей, определяющих в соответствии с процессами обработки заявок временную последовательность выполнения задач. При этом, если задачи с номерами г и] порождены одной и той же заявкой, то

II-если выполнение задачи ) непосредственно (в соответствии с процессом

обработки заявки) предшествует выполнению задачи г, О-впротивном случае,

если же задачи г и ] порождены различными заявками, то 8(г1/)=0;

В данном случае матрица смежности S - только одна т.к. все связи между задачи

однотипны.

По аналогии с задачей планирования работы ЛВС задача планирования работы комплексов РСОД формулируется следующим образом: требуется найти вектор , каждая компонента которого содержит две составляющие:

Здесь 1/ - время начала выполнения задачи с номером ; (I с Л);

и, - номер РМО комплекса, в котором решается задача с номером /.

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

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

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

Предлагается следующая принципиальная схема построения алгоритма составления расписания (рис. 1).

Алгоритм состоит из ряда последовательно выполняемых этапов.

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

Для построения основной последовательности разработана специальная процедура.

На 2-ом этапе (на рисунке он выделен пунктирной линией) организуется последовательный просмотр списка П. По отношению к каждой задаче, расположенной в списке П на г - ом месте, принимается решение о ее назначении на одно из средств обработки. Для этих целей необходима процедура принятия решения /2.1/. Она может быть основана как на использовании числового критерия, так и представлять собой некоторое логическое правило. Весьма полезной с точки зрения сокращения вычислений может оказаться процедура проверки условий /2.2/, позволяющая прервать просмотр списка П, по причине того, что формируемое расписание заведомо не удовлетворяет ограничениям (3) - (7). Разработанная процедура является нетривиальной и играет немаловажную роль.

Если основная последовательность П, обработанная в соответствии с принятой процедурой принятия решения /2.1/, не приводит к получению расписания реализации задач, удовлетворяющему ограничениям (3) - (6), необходимо осуществить корректировку списка П /процедура 3.1/, его анализ /процедура 3.2/ на возможность продолжения поиска, и в случае положительного ответа, осуществить действия, соответствующие этапу 2 алгоритма, т.е. реализовать новую попытку поиска расписания.

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

Алгоритм составления расписания, изображенный на рис. 1, носит достаточно общий характер. В зависимости от конкретного способа реализации процедур /1/, /2.1/, /3.3/, /2.2/ и /3.2/ получится тот или иной алгоритм поиска.

г

1. Генератор основной последовательности задач П ч_>

Рис. 1. Блок-схема алгоритма поиска допустимого расписания.

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

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

Построение базовой диаграммы основано на графической интерпретации ограничений задачи планирования (3) - (7). Дадим следующее определение базовой диаграммы:

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

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

Свойства базовой диаграммы:

базовая диаграмма соответствует всем информационным связям между

задачами;

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

Исходя из определения и свойств базовой диаграммы, можно сделать вывод:

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

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

Следовательно, если в процессе составления расписания реализации ОВП обнаружится, что время завершения какой-либо задачи больше наиболее позднего срока ее окончания, то выполнение ограничений (3), (4) заведомо невозможно. Это обстоятельство и положено в основу построения процедуры /2.2/, изображенной на

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

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

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

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

Все ОВП должны завершаться как можно раньше.

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

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

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

Перестановкой назовем операцию перемещения задачи с номером j на такую позицию в последовательности П, которая расположена непосредственно перед задачей с номером k

Перестановка называется допустимой, если она не нарушает

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

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

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

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

Как было показано выше алгоритм состоит из ряда последовательно выполняемых этапов.

На 1-ом этапе осуществляется генерация основной последовательности задач П. В П должны входить все номера из множества задач . Для генерации основной последовательности используется базовая диаграмма. Построение базовой диаграммы выполняется один раз в процессе построения расписания и состоит из двух процедур. Первая процедура - разбиение множества задач на подмножества, выполняется один раз. Вторая процедура - собственно построение базовой диаграммы. Выбирается задача из последнего подмножества и устанавливается на диаграмме, исключается из списка, выбирается следующая задача и т.д. Для каждой задачи выполняется только проверка ограничений. Трудоемкость алгоритма построения базовой диаграммы линейно зависит от числа задач п, обозначим ее Q6д = 0{п)

На 2-ом этапе выполняется процедура построения расписания для полученной ранее последовательности задач.

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

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

где - трудоемкость построения расписания для заданной

последовательности задач,

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

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

уменьшается вдвое, т.е. п!/2. Каждое следующее условие предшествования между любыми двумя задачами, сокращает количество возможных последовательностей еще в два раза (т.е. число последовательностей п!/4). При наличии к - информационных связей количество возможных последовательностей п\

равно . Количество информационных связей к можно определить по исходным 2

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

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

И!

0 =

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

Таблица 1. Временные характеристики, алгоритма для различных задач составления расписания.

Наименование Количеств Количество Требуемое Время

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

обработки корректировок Сек.

ЛВС 44 5 16 2

ЛВС 44 4 16 2

КТС "Репер" 60 7 146 3.5

АСАХ "Ретро - ГИС 27 8 1 1

АСАХ "Ретро - ГИС' 27 6 1 1

В четвертой главе показано применение разработанных алгоритмов для решения задач планирования работы различных информационных систем. При планировании работы ЛВС рассмотрены два случая с разным количеством средств обработки. Планировалось выполнение 44 задач, среди них две задачи второго типа (задачи поддержки). Расписание строилось для 5 , а затем 4-х средств обработки различных типов. Для двух ЭВМ входящих в состав ЛВС (ЭВМ № 1 и №5) существуют ограничения в виде графиков доступности каждой из ЭВМ для выполнения задач.

При конфигурации технических средств из 5 ЭВМ (две типа Е, две типа Р1, одна типа Р2), расписание было построено за 16 корректировок основной последовательности задач. Для проверки возможностей алгоритма было построено расписание работы ЛВС в более жестких условиях - 4 ЭВМ (одна типа Е, две типа Р1, одна типа Р2 ). В данной ситуации алгоритм также справляется с задачей, позволяя отыскать допустимое решение задачи.

Применение разработанного алгоритма для решения задачи формирования допустимого расписания работы КТС "Репер".

В состав РСОД входит 7 РМО, принадлежащих четырем различным комплексам. В течение планируемого периода работы РСОД ( 7пл =36 единиц времени) на обработку в РСОД поступает 21 заявка. Множество заявок для данного примера порождает множество J, включающее /7=60 задач.

Допустимое расписание работы РСОД было получено с помощью 146 корректировок основной последовательности задач, затраченное время ~ 3.5 секунды.

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

Применение разработанного алгоритма в АСАХ "Ретро - ГИС". В модельной задаче рассматривалась следующая структура: в состав АСАХ входит 2 АРМ с планшетными сканерами, 2 АРМ с протяжными сканерами, одно АРМ привязки, одно АРМ выдачи информации внешним потребителям различным комплексам. В течение планируемого периода работы АСАХ ( 7пл =24 единицы времени) на обработку в АСАХ поступает 10 заявок, в том числе 4 для обработки на протяжных сканерах, 4 для обработки на планшетных сканерах, 2 от системы 21Л11. Множество заявок для данного примера порождает множество J, включающее п=27 задач. Работа средств временной буферизации и архивного хранилища может быть формализована в виде обязательного интервала времени между завершением обработки заявки на АРМ сканирования и началом обработки на АРМ привязки.

Для всех задач интервал между завершением сканирования и началом привязки - 22.5 мин. (время сохранения во временном буфере), между завершением привязки и началом работы АРМ выдачи - 45 мин. (перенос из временного буфера в основной архив).

Допустимое расписание работы АСАХ было получено с помощью одной корректировки основной последовательности задач. В реальной системе проводилось планирование обработки более 100 заявок, полученное множество задач I, включает около 300 задач. Время составления расписания не превышает 5 секунд.

Задача планирования работы АСАХ "Ретро - ГИС" с точки зрения предложенного алгоритма аналогична задаче планирования работы КТС "Репер". Все выводы сделанные для задачи планирования работы КТС "Репер" применимы и к задаче планирования работы АСАХ "Ретро - ГИС".

Сказанное показывает работоспособность и высокую эффективность алгоритма планирования работы АСАХ и позволяет сделать вывод о возможности его использования при планировании работы конкретной АСАХ по реальным исходным данным.

Основные выводы и результаты

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

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

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

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

5. Разработанный метод и программа используются для планирования работы реальной системы, что подтверждается актом о внедрении ФГУП НИИ точных приборов.

Основные результаты диссертационной работы отражены в следующих печатных

работах:

1. Гусев И.О., Максимов НА, Склеймин Ю.Б., Фомин В.Г., Шароватов А.В. Оценка устойчивости средств автоматизированных информационно-управляющих комплексов в позиционном районе. В сб.: Ракетно-космическая техника. Серия 7, 1990г.

2. Склеймин Ю. Б. Метод решения задачи планирования работы в сложной неоднородной вычислительной сети с множественными ограничениями. Журнал "Информационные технологии" №2, Москва, 2002 г.

3. Склеймин Ю. Б. Алгоритм диспетчеризации работы наземной системы распределенной обработки данных с многофазным обслуживанием заявок. Журнал "Авиакосмическое приборостроение" №2, Москва, 2002 г.

4. Filippov A. N., Gorbachev Yu. V., Skleymin Yu. B. Scheduling Operation in Heterogeneous Computer Networks with Limitations on problem Execution Time. Сборник трудов международной конференции по автоматическому управлению Московского авиационного института и Пекинского аэрокосмического университета. Стр. 26, Москва, 1993 г.

5. Склеймин Ю.Б. Классификация задач составления расписаний и метод решения задачи планирования работы вычислительной сети. Труды XI международного научно-технического семинара "Современные технологии в задачах управления, автоматики и обработки информации". Стр. 393, Алушта, 2002 г.

6. Склеймин Ю.Б. Принципы построения алгоритма планирования работы распределенной системы обработки данных с многофазным обслуживанием заявок. Труды международной научной конференции "Информационные технологии в естественных науках, экономике и образовании". Стр. 408, Саратов - Энгельс, 2002 г.

Введение

1. ПРОБЛЕМНЫЕ ВОПРОСЫ ТЕОРИИ И ПРАКТИКИ ПЛАНИРОВАНИЯ РАБОТЫ КОМПЛЕКСОВ ОБРАБОТКИ РЕЗУЛЬТАТОВ ДИСТАНЦИОННОГО ЗОНДИРОВАНИЯ ЗЕМЛИ.

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

1.2 Описание одностадийной системы (ЛВС "РУСЛАН").

1.3 Описание системы с многостадийной обработкой информации (КТС "Репер").

1.4 Описание автоматизированной системы архивного хранения видеоизображений (АСАХ "Ретро-ГИС").

1.5 Общие особенности задач планирования работы информационной системы.

2. ФОРМАЛИЗОВАННАЯ ПОСТАНОВКА ЗАДАЧИ СОСТАВЛЕНИЯ РАСПИСАНИЯ РАБОТЫ ЛВС.

2.1 Классификация задач построения расписаний.

2.2 Обзор методов решения задач известных классов. Место разрабатываемого метода в классификации.

2.3 Формализованная постановка задачи построения расписания в одностадийной системе.

2.3.1 Формализация исходных данных. Формирование графа задачи.

2.3.2 Описание информационной модели.

2.3.3 Характеристики задач, подлежащих реализации на неоднородной вычислительной системе.

2.4 Постановка задачи формирования расписания работы ЛВС.

2.5 Информационная модель и постановка задачи планирования работы РСОД.

2.5.1 Сведение многостадийной системы к одностадийной

2.5.2 Постановка задачи планирования работы РСОД.

2.5.3 Постановка задачи планирования работы АСАХ "Ретро - ГИС".

3. РАЗРАБОТКА АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ ПЛАНИРОВАНИЯ.

3.1 Общая схема построения алгоритма

3.2 Алгоритм построения базовой диаграммы.

3.2.1 Алгоритм построения базовой диаграммы.

3.2.2 Пример реализации алгоритма построения базовой диаграммы.

3.3 Наиболее поздние сроки окончания задач. Формирование основной последовательности задач.

3.4 Эвристическое правило принятия решения о назначении задачи на одно из средств обработки.

3.5. Процедура корректировки последовательности задач.

3.6. Приближенная оценка трудоемкости и оперативности алгоритма планирования. 105 3.7 Место алгоритма в контуре планирования работы ЛВС.

4. ПРИМЕНЕНИЕ РАЗРАБОТАННЫХ АЛГОРИТМОВ ДЛЯ РЕШЕНИЯ ЗАДАЧ ПЛАНИРОВАНИЯ РАБОТЫ РАЗЛИЧНЫХ ИНФОРМАЦИОННЫХ СИСТЕМ.

4.1 Применение разработанного алгоритма для планирования работы ЛВС.

4.2 Пример решения задачи формирования допустимого расписания работы РСОД (КТС "Репер").

4.3 Применение разработанного алгоритма в АСАХ "Ретро - ГИС" 122 ЗАКЛЮЧЕНИЕ 126 СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 128 ПРИЛОЖЕНИЕ 1. Список используемых терминов и сокращений 131 ПРИЛОЖЕНИЕ 2.Текст программы составления расписания

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

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

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

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

Научная новизна материалов заключается в следующем:

1. Разработана классификация задач планирования, основанная на введенные семи признаков S, U, V, N, R, Р, Е, которые могут характеризовать ту или иную постановку задачи.

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

2. Предложена модель сложного вычислительного процесса в виде графа G = (J,S,K), где J - множество задач обработки, подлежащих распределению, S - множество информационных связей между задачами, К - множество, определяющее различные типы связей между задачами. Построение графа вычислительного процесса как его абстрактой модели позволяет представить и проанализировать как общую структуру вычислительного процесса, так и связи между отдельными задачами, а также выявить формальные преобразования, приводящие к решению задачи планирования его выполнения.

3. Разработан алгоритм планирования работы локальной вычислительной сети (ЛВС). Этот алгоритм обеспечивает построение допустимого расписания для задачи класса (Si(Q, U„, V, N, R*,} (класс задачи определен введенными ранее признаками), с учетом большого количества ограничений.

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

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

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

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

1. Разработаны новые алгоритмы планирования загрузки технических средств ЛВС и алгоритмы составления расписаний запуска работ на выполнение в распределенной сети обработки данных.

2. Предложенные алгоритмы позволили автоматизировать процедуры составления плана загрузки вычислительных средств и запуска работ на выполнение и использовались при создании автоматизированного рабочего места (АРМ) планирования для комплекса АСАХ "Ретро-ГИС". Это нашло отражение в полученном акте внедрения результатов диссертационной работы.

3. Выполненные разработки легли в основу лабораторных работ по дисциплине «Проектирование информационных систем», использованы при чтении лекций по одноименному курсу на кафедре № 308 МАИ.

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

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

2. Задача составления расписания работы системы с учетом сложных ограничений и технологических особенностей.

3. Представление информационного процессы в виде графа состоящего из трех компонент G = (J,S,K), где J - множество задач обработки; S - множество информационных связей; К - множество, описывающие различные типы информационных связей. Построение графа вычислительного процесса как его абстрактой модели позволяет представить и проанализировать как общую структуру вычислительного процесса, так и связи между отдельными задачами, а также выявить формальные преобразования, приводящие к решению задачи планирования его выполнения.

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

5. Реализация алгоритма в виде программы для ЭВМ. С помощью программы проведено планирование работы различных систем, для которых получены допустимые расписания работы. Использование программы показало высокое быстродействие разработанного алгоритма.

Апробация работы. Основные результаты работы докладывались и получили одобрение на следующих научных конференциях и семинарах:

1. Международная конференция по автоматическому управлению Московского авиационного института и Пекинского аэрокосмического университета. Москва, 1993г.

2. XI международный научно-технического семинар "Современные технологии в задачах управления, автоматики и обработки информации". Алушта, 2002 г.

3. Международная научная конференция "Информационные технологии в естественных науках, экономике и образовании". Саратов - Энгельс 2002 г.

Публикации. Основные результаты диссертационных исследований опубликованы в 6 научных работах. В их числе 3 статьи в специализированных печатных изданиях [1, 2, 3] и 3 доклада на научных конференциях и семинарах [4, 5, 6].

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

Выводы:

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

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

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

2. В рамках предложенного подхода показана возможность сведения многостадийной системы обработки данных к одностадийной.

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

6. Разработанный метод и программа используются для планирования работы реальной системы, что подтверждается актом о внедрении ФГУП "НИИ точных приборов".

ЗАКЛЮЧЕНИЕ

В данной работе был предложен метод решения новой задачи теории расписаний, отличающейся большим количеством задач, наличием заданных директивных интервалов, наличием условий предшествования, т.е. начало выполнения некоторых задач возможно только после завершения информационно предшествующих им задач. Кроме того, существуют ограничения по объемам памяти средств обработки, и длительность выполнения некоторых задач зависит от времени окончания других задач (так называемые задачи поддержки). Созданный метод применим для планирования работы достаточно широкого круга систем при минимальной модификации. Показано его практическое применение для планирования работы ЛВС "Руслан", комплекса технических средств "Репер" и автоматизированной системы архивного хранения "Ретро". Быстродействие метода позволяет использовать его для решения задач оперативного планирования. Доказано необходимое условие существования расписания при использовании созданного метода. Разработанные принципы, метод, алгоритм и программное обеспечение носят общий характер и могут быть применены к любой сложной распределенной системе, для которой необходимо планирование работы. Например, планирование технологических операций на производстве, планирование учебных занятий и т.д.

1. Гусев И.О., Максимов Н.А., Склеймин Ю.Б., Фомин В.Г., Шароватов А.В. Оценка устойчивости средств автоматизированных информационно-управляющих комплексов в позиционном районе. В сб.: Ракетно-космическая техника. Серия 7, 1990г.

2. Склеймин Ю. Б. Метод решения задачи планирования работы в сложной неоднородной вычислительной сети с множественными ограничениями. Журнал "Информационные технологии" №2, Москва, 2002 г.

3. Склеймин Ю. Б. Алгоритм диспетчеризации работы наземной системы распределенной обработки данных с многофазным обслуживанием заявок. Журнал "Авиакосмическое приборостроение" №2, Москва, 2002 г.

4. Танаев B.C., Гордон B.C., Шафранский Я.М. Теория расписаний. Одностадийные системы.-М.:Наука, 1984.

5. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи, М.: Мир, 1982.

6. Ахыоджа Г.Х. Сетевые методы управления в проектировании и производстве. М.: Мир, 1979.

7. Сольвадор М. Календарное планирование и упорядочение работ. -М.:Мир, 1981г.

8. П.Смоляр Л.И. Оперативно-календарное планирование/модели и методы/.-М.:Экономика, 1979.

9. Барский А.Б. Параллельные процессы в вычислительных системах. -Планирование и организация. -М.:Радио и связь, 1990.

10. Левин В.И. Планирование выполнения частично упорядоченного множества работ. М: Известия РАН. Теория и системы управления. 2002г., № 2.

11. Левин В.И. Автоматная модель определения возможного времени проведения коллективных мероприятий. М: Известия РАН. Теория и системы управления. 1999г., № 3.

12. Бруно Д.Л., Грэхом Р.Л., Котляр В.Г. Теория расписаний и вычислительные машины. -М.: Наука, 1984.

13. Randow R. Integer Programming and Related Areas. A Classified Bibliography 1978 1981. - Berlin: Springer Verlag, 1982.

14. Сергиенко И.В. Математические модели и методы решения задач ' дискретной оптимизации. Киев.: Наукова думка, 1988.

15. Шафранский В.В. Математические модели и методы планирования развития отраслей промышленности. М: Наука, 1984.

16. Танаев В.Б. Теория расписаний. М.: Знание , 1988.

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

18. Чудаков А. Д., Фолевич Б. А. Автоматизированное оперативно-календарное планирование в гибких комплексах механообработки.-М.: Машиностроение, 1986.

19. Михалевич B.C., Кукса А.И. Методы последовательной оптимизации в дискретных сетевых задачах оптимального распределения ресурсов. М.: Наука, 1983.

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

21. Михалевич B.C., Трубин В.А., Н.З. Шор Оптимизационные задачи производственно-транспортного планирования: Модели, методы, алгоритмы. .- М.:Наука, 1986.

22. Левнер К.В., Гене Г.В. Дискретные оптимизационные задачи и эффективные приближенные алгоритмы.- М.:ЦЭМИ АН СССР, 1978.

23. Бабушкин А.И., Белов И.С. Оптимальные комбинации приоритетных правил составления расписаний. Автоматика и телемеханика №5,1986

24. Конвей В.В. и др. Теория расписаний. М.: Наука, 1975.

25. Подчасова Т.П. и др. Эвристические методы календарного планирования. Киев ,1986.

26. Визинг В.Г. О расписаниях, соблюдающих директивные сроки выполнения работ. -Кибернетика. 1985, №1.

27. Лебедев С.С., Фридман А.А. Новые исследования в дискретном программировании. В.сб.: Математический аппарат экономического моделирования. - М. :Наука.1988.

28. Алексеев О.Г. Комплексное применение методов дискретной оптимизации. М.: Наука , 1987.

29. Севастьянов С.В. Геометрия в теории расписаний . В сб.: Модели и методы оптимизации. Новосибирск.: Наука, 1988.

30. Ibaraki Т. Solvable classes of Discrete Dynamic Programming. Journal of Mathematical Analysis and Applications. 1973, № 43, стр. 642-693.