Введение 3
1. Цель работы 5
2. Постановка задачи 6
3. Алгоритмы 8
3.1. Алгоритм 1 (Процедура h 0) 8
3.2. Алгоритм 2 (Модифицированная процедура hO) 9
4. Описание работы проекта 11
5. Эксперименты 15
Заключение 19
Список использованной литературы 20
Приложение
Теория расписаний - это раздел исследования операций, в котором строятся и анализируются математические модели календарного планирования (т.е. упорядочивания во времени) различных целенаправленных действий с учетом целевой функции и различных ограничений [1].
Задача составления расписания встречается во многих сферах человеческой деятельности. Часто люди, сталкиваясь с проблемой составления расписаний, решают их на интуитивном уровне. Для решения бытовых вопросов применение интуитивного подхода оказывается достаточным, но перед обществом стоят и более сложные задачи. Развивающаяся стремительными темпами автоматизация производства и неуклонно увеличивающиеся его масштабы требуют разработки алгоритмов построения расписаний, в которых учтены различные ограничения.
Задачи теории расписаний, очевидно, связаны с построением расписаний, т.е. с упорядочиванием некоторых работ (операций) по времени и/или по исполнителям (приборам). При этом необходимо учитывать ограничения на последовательность выполнения требований, ограничения, связанные с приборами и т.п. Цель решения таких задач - построение допустимых расписаний, при котором все ограничения соблюдены, или, что является более сложным, - нахождение оптимального допустимого расписания по какому- либо критерию оптимальности. Например, построение оптимального расписания по быстродействию, расписания с минимальными финансовыми затратами и т.п.
Большинство задач теории расписаний являются NP-полными, то есть не существует псевдополиномиального алгоритма решения в предположении, что классы P и NP не совпадают. Поэтому разработка для NP-полных задач теории расписаний эффективных приближенных алгоритмов является актуальным.
Одна из известных задач теории расписаний - задача минимизации максимального временного смещения для одного прибора. Эта задача, как и большинство задач теории расписаний, является NP-полной в сильном смысле
[5].
В данной работе рассматривается частный случай этой задачи, когда требования можно перенумеровать одновременно по неубыванию директивных сроков и невозрастанию моментов поступления.
В данной работе был исследован алгоритм построения приближённого расписания для частного случая NP-полной задачи теории расписаний. Результаты экспериментов показали, что расписания, построенные данным алгоритмом и модифицированным алгоритмом без использования
вспомогательного расписания п{", совпадают.
Трудоемкость модифицированного алгоритма на порядок меньше трудоемкости самого алгоритма, который требует 0(п2Р) операций. Для построения расписаний п[ и и" используются результаты предыдущего шага, как в методах с использованием идеи динамического программирования, чего нельзя сказать о 7Г-", для его отыскания требуется 0(п) операций. В модифицированном алгоритме нет расписания п[", поэтому его трудоемкость на порядок ниже, т.е. 0(пР).
Алгоритм построения приближенного расписания является
вспомогательным в точном методе решения задачи. Следовательно, применение его модификации позволит уменьшить трудоемкость реализации точного метода на порядок.
