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

• Автор: Красный, Дмитрий Георгиевич
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Ростов-на-Дону
• Количество страниц: 189 с. : ил.

ВВЕДЕНИЕ.

1. ПАРАЛЛЕЛЬНЫЕ РАСПРЕДЕЛИТЕЛЬНЫЕ ЗАДАЧИ ТЕОРИИ РАСПИСАНИЙ И МЕТОДЫ ИХ РЕШЕНИЯ.

1.1. Распределительные злдлчи теории расписаний и области их применения .

1.1.1. История возникновения и применения.

1.1.2. Распределение заданий в вычислительных системах

1.1.3. Структура и технология решения распределительных задач

1.2. Основные термины и концептуальная модель задач теории расписаний

1.3. Математическое описание неоднородной распределительной задачи .

1.3.1. Теоретикомножественная составляющая распределительной задачи

1.3.2. Критериальнооценочная составляющая распределительной задачи

1.3.3. Оптимизационная составляющая распределительной задачи

1.3.4. Понятие среды решения распределительной задачи и ее характеристики.
1.4. АНАЛИЗ СУЩЕСТВУЮЩИХ МЕТОДОВ РЕШЕНИЯ РАСПРЕДЕЛИТЕЛЬНЫХ ЗАДАЧ
1.4.1. Детерминированные методы точного решения распределительных задач
1.4.2. Списочные методы точного решения распределительных задач.
1.4.3. Комбинаторный подход решения распределительных задач.
1.4.4. Эвристические и вероятностные методы.
1.5. Выводы но первой главе.
2. СПИСОЧНОМОДИФИЦИРОВАННЫЙ АЛГОРИТМ ТОЧНОГО РЕШЕНИЯ НЕОДНОРОДНОЙ РАСПРЕДЕЛИТЕЛЬНОЙ ЗАДАЧИ
2.1. СПИСОЧНОМОДИФИКАЦИРОВАИПЫЙ АЛГОРИТМ АЛЕКСЕЕВА.
2.1.1. Общая характеристика алгоритма Алексеева.
2.1.2. Списочная модификация алгоритма Алексеева для распределительной задачи с количественной неоднородностью.
2.1.3. Списочная модификация алгоритма Алексеева для распределительной задачи с качественной неоднородностью.
2.2. СРАВНИТЕЛЬНЫЙ АНАЛИЗ СТРУКТУРЫ РЕШЕНИЯ НЕОДНОРОДНЫХ РАСПРЕДЕЛИТЕЛЬНЫХ ЗАДАЧ КЛАССИЧЕСКИМ И СПИСОЧНОМОДИФИЦИРОВАННЫМИ
алгоритмами Алексеева
2.2.1. Решение распределительной задачи с количественной неоднородностью
2.2.2. Решение распределительной задачи с качественной неоднородностью
2.3. Имитационное исследование применения СМ АА для точного решения
НЕОДНОРОДНЫХ РАСПРЕДЕЛИТЕЛЬНЫХ ЗАДАЧ.
2.3.1. Организация вычислительного эксперимента.
2.3.2. Исследование свойств СМАА при решении распределительных задач с количественной неоднородностью.
2.3.3. Исследование свойств СМ А А КК и К при решении распределительных задач с качественной неоднородностью.
2.4. ВЫВОДЫ НО ВТОРОЙ ГЛАВЕ
3. ИССЛЕДОВАНИЕ РЕШЕНИЯ НЕОДНОРОДНОЙ РАСПРЕДЕЛИТЕЛЬНОЙ ЗАДАЧИ ПРИБЛИЖЕННЫМИ МЕТОДАМИ.
3.1. Приближенное решение неоднородной распределительной задачи
3.1.1. Приближенное решение и алгоритмы.
3.1.2. Показательная распределительная задача с количественной неоднородностью
3.1.3. Решение неоднородной распределительной задачи алгоритмом ПлотниковаЗверева .
3.2. Модификация списочного алгоритма Алексеева для приближенного РЕШЕНИЯ НЕОДНОРОДНОЙ РАСПРЕДЕЛИТЕЛЬНОЙ ЗАДАЧИ.
3.2.1. Списочномодифицированный алгоритм Алексеева без возвратов.
3.2.2. Решение неоднородной распределительной задачи СМАА без возвратов.
3.2.3. Исследование точности решения СМАА без возвратов
3.2.4. Исследование зависимости относительного улучшения точности СМ АА без
возвратов в сравнении с алгоритмом ПЗ от изменения параметров задачи
3.3. Применение эволюционногенетической модели для решения
неоднородной распределительной задачи
3.3.1. Возможность решения неоднородной распределительной задачи генетическим алгоритмом.
3.3.2. Исследование ЭГА при решении неоднородной распределительной задачи.
3.3.3. Описание перспективной области значений параметров ЭГА
3.3.4. Решение неоднородной распределительной задачи ЭГА.
3.4. Имитационное моделирование приближенного решения неоднородных
распределительных задач.
3.4.1. Организация вы числительного эксперимента.
3.4.2. Результаты вычислительного эксперимента.
3.5. Выводы по третьей главе.
4. ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ РЕШЕНИЯ НЕОДНОРОДНЫХ РАСПРЕДЕЛИТЕЛЬНЫХ ЗАДАЧ.
4.1. Вычислительный эксперимент и ребования к программному
ОБЕСПЕЧЕНИЮ
4.1.1. Требования к программному обеспечению
4.1.2. Концептуальная схема функционирования программного обеспечения
4.1.3. Объектноориентированная модель реализации ПО
4.2. СТРУКТУРА ХРАНЕНИЯ ДАННЫХ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ.
4.2.1. Использование базы данных
4.2.2. Концептуальная модель объекта хранения и функциональные зависимости
4.2.3. Реляционные выражения и таблицы базы данных
4.3. Интерфейс взаимодействия с пользователем.
4.4. выводы по четвертой главе
ЗАКЛЮЧЕНИЕ.
СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ


Генри Гантта , предложившего формы представления расписаний, названные диаграммами Гантта. Они встречаются во многих работах по теории расписаний. В связи с бурным развитием автоматизации производства с х годов го века в данном направлении прикладной математики началось активное теоретическое исследование задач теории расписаний, с появления работ Джексона и Джонсона ,. Одним из направлений теории расписаний, получившее широкое распространение, является исследование классических распределительных задач. В данном направлении теории расписаний основное внимание уделяется вопросам, связанным с построением иаилучших календарных планов расписаний исполнения конечного множества требований, последовательнопараллельно обслуживаемых детерминированными системами одного или нескольких устройств. В связи с этим стало актуальным разработка и исследование математических методов, позволяющих решать распределительные задачи. Классические распределительные задачи теории расписаний являются схематичными теоретическими моделями многих задач, встречающихся на практике, и имеют не только большое теоретическое значение, но и получили практическое применение в различных видах целенаправленной деятельности человека. К примеру, при подготовке и проведении Олимпийских игр г. Барселоне, необходимо было организовать более мероприятий за дней. Для этого применялась система поддержки решений 8иССЕ8Б , разработанная в университете г. Однако, непосредственное применение средств вычислительной техники для одновременного выполнения многих программ или функциональных операторов, в свою очередь, связано с постановкой задач распределения заданий между процессорами вычислительной системы ,. Вычислительной системой ВС называется совокупность вычислительных средств, включающих не менее двух ЭВМ или процессоров с автоматическим обменом информации между ними по системам связи. ВС предназначены для автоматической обработки информации в соответствии с заданными алгоритмами. Вычислительные машины в системе могут быть неравноценны. Одни из них выполняют вычисления, предусмотренные алгоритмами решаемых задач, такие машины называются основными. Другие, которые предназначаются для выполнения операций вводавывода, редактирования и контроля работы ВС, называются вспомогательными периферийными . Увеличение производительности вычислительных средств можно обеспечить различными способами. Повышение вычислительной мощности ЭВМ за счет применения быстродействующих элементов ограничено. Быстродействие определяется переходными процессами, протекающими в элементах, длительность которых не может быть меньше величины, определяемой физическими свойствами материалов, конструкцией и технологией изготовления. Значительно повысить производительность ЭВМ путем совмещения операций не удается, так как невозможно освободить ЭВМ от большого числа подготовительных операций, необходимых для реализации алгоритма. Использование нескольких ЭВМ влечет повышение вычислительной мощности, но не позволяет сократить время выполнения набора функциональных операторов, вследствие чего приводит к неэффективному использованию вычислительных средств при обслуживании случайного потока заданий. Результата от объединения нескольких ЭВМ в единую систему вычислений можно добиться, если сделать это с применением методов динамического распределения, которые рассматриваются при решении распределительных задач теории расписаний. Для более эффективного использования многомашинного или многопроцессорного вычислительного комплекса рекомендуется также проектировать ВС на базе двухчетырех обрабатывающих узлов, т. Ввиду того, что при проектировании ВС с большим числом устройств обработки информационных потоков резко возрастает время простоя каждого устройства обработки в сравнении с системой базирующейся на двухчетырех вычислительных блоках . Другой способ увеличения производительности заключается в подготовке вычислительного процесса в комплексе данные плюс вычислительная система их обработки . Данный способ заключается в создании плана вычислений, т. ЭВМ их обработки.