Введение 2
1. Теоретические аспекты исследования задачи 4
1.1. Постановка задачи 4
1.2 Методы решения задачи минимизации взвешенного количества запаздывающих требований 5
2. Реализация программы 9
2.1. Реализация консольного интерфейса 9
2.2. Реализация программной части 14
3. Экспериментальное исследование 22
3.1. Описание экспериментов 22
3.2. Анализ экспериментов 23
Заключение 28
Список литературы 29
Приложение 1 31

Купить

Теория расписаний - это одна из областей исследования операций, связанная с упорядочиванием отдельных работ (операций) по времени и/или по выполнителям, то есть приборам.
Целью решения является разыскивание разрешимых расписаний, при которых были бы соблюдены все ограничения, или составление оптимального расписания по определенному критерию оптимальности.
Популярная работа Генри Гантта 1903г. (Gantt H.L.), который предложил то, что в современном мире именуют диаграммами Гантта, подтолкнула на введение предоставленного направления в науку.
Методы и алгоритмы решения задач теории расписании” используются для решения задач комбинаторной оптимизации. Начало действенного теоретического рассмотрения и изучения задач теории расписаний пришлось на 50-е годы 20-ого века, так же следует упомянуть о работах Джонсона, Джексона и Смита, а также монографии, которые внесли значимый вклад.
Одними из основополагающих проблем нововведенного направления являлись классифицирование задач и указание их сложности. Именно Грэхэмом было рекомендовано максимально сложившееся на данный момент классифицирование задач теории расписании”. Довольно глубокие исследования по задачам теории расписании” и их сложности показаны в работах Гэри и Джонсона, Ленстры и др., Лоулера и др., Танаева и др., Брукера и др.
Большая часть изученных задач теории расписании” представляют собой NP-трудные задачи. Независимо от этого, практика требует решения таких задач.
Так как задачи для одного прибора близко связаны с классическими задачами из других областей дискретной математики, им выделяется особенный интерес в теории расписании”. Так же следует упомянуть, что одноприборные задачи - это частные случаи и подзадачи более сложных практических задач.
Планирование проектов, организация транспортных потоков, управление производством, ресурсами в вычислительных системах и т.д. - именно в этих областях часто используются задачи теории расписании”.
Многообразие методов решения задач теории расписании, а также существенные объемы обработки данных делают значимым для настоящего момента вопрос составления быстрых и результативных алгоритмов. Данная работа направлена на исследование двух приближенных алгоритмов решения задачи теории расписаний - минимизации взвешенного количества запаздывающих требований.
Заключения, сделанные в выводе данной работы, говорят о результате сравнения двух приближенных алгоритмов решения.
Для данной задачи достаточные условия оптимальности получены В.С. Танаевым и В.С. Гордоном [3]. В случае одновременного поступления алгоритмы решения разработаны Moore J.M., Kise H., Ibaraki T. и Mine H. в [8]. В случае одновременного поступления при условии возможности нумерации требовании” одновременно по неубыванию продолжительностей и не возрастанию весов предложен алгоритм В.С. Гордоном и В.С. Танаевым [1]. Решение задачи в случае единичных весов получено Kise H. [5], Maxwell W.I. [7], Lawler E.L. [6], Sidney J.B. [9].
Ключевые цели работы:
1) Создание программного продукта, который даст возможность изучить задачу минимизации взвешенного количества запаздывающих требовании” с помощью двух приближенных алгоритмов решения задачи.
2) Изучение задачи минимизации взвешенного количества запаздывающих требовании, которое заключается в сравнении результатов двух приближенных алгоритмов решения задачи.

Купить