Введение 3
1. Цель работы 5
2. Постановка задачи 6
3. Описание алгоритма 7
4. Описание работы проекта 9
5. Примеры 12
5.1 Примеры экспериментов 15
6. Анализ экспериментов 27
Заключение 35
Список использованной литературы 36
Приложение
Купить

Теория расписаний - это раздел исследования операций, в котором строятся и анализируются математические модели кaлендарного плaнировaния (т.е. упорядочивания во времени) различных целенаправленных действий с учетом целевой функции и различных ограничений [1]
Задачи теории расписаний, очевидно, связаны с построением расписаний, т.е. с упорядочиванием каких-либо операций (требований) повремени и/или по исполнителям (приборам). При этом необходимо принимать во внимание ограничения на порядок реализации требований,
ограничения, связанные с исполнителями и т.п. Целью решения этих задач,является построение допустимых расписаний, при котором учтены все ограничения,или, что является более сложным, - построение оптимального расписания по какому-либо критерию оптимальности.
Качество обучения студентов в вузах и, конечно же, результативность использования возможностей профессорско-преподавательского состава зависят в некоторой части от степени подготовки учебного процесса. Одной из важнейших частей учебного процесса является расписание занятий - организовывает ритм работы, оказывает влияние на творческую отдачу преподавателей, поэтому имеется возможность рассматривать его как причину оптимизации расходования не безграничных трудовых ресурсов - преподавательского состава. Или же та самая электронная очередь в банке, которая распределяет поток клиентов по их требованиям. В этой модели присутствуют моменты поступления, продолжительности и ожидаемые сроки окончания обслуживания требований. Здесь ограниченным ресурсом является время, которое так же нуждается в оптимизации. С этими и многими другими, более сложными моделями обслуживания определенных требований ежедневно сталкивается человечество. Этим и обусловлена актуальность исследования в области теории расписаний.
Большая часть задач теории расписаний является NP-полными. Вследствие этого, и разработка эффeктивных приближeнных алгоритмов для NP-полных задач тeории расписаний являeтся актуальным. [2]
Одной из известных задач теории расписаний является задача минимизации суммарного штрафа. Эта задача, как и большинство задач теории расписаний, относится к классу NP- полных в сильном смысле задач.

Купить