Введение 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].
В данной работе рассматривается частный случай этой задачи, когда требования можно перенумеровать одновременно по неубыванию директивных сроков и невозрастанию моментов поступления.

Купить