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

• Склеймин, Юрий Борисович
• кандидат технических наук
• 2004

Оглавление диссертации кандидат технических наук Склеймин, Юрий Борисович

Введение

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

ЗАКЛЮЧЕНИЕ

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

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

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.