Автор: Пользователь скрыл имя, 10 Марта 2012 в 11:00, курсовая работа
Теория расписаний является важным разделом исследования дискретных экстремальных задач. Задачи теории расписаний состоят в оптимальном распределении имеющихся ресурсов для выполнения требований за определенный промежуток времени. Под ресурсами могут пониматься машины, станки, учебные помещения, приборы и тому подобное, под требованиями — выполняемые работы, программы, школьные занятия, грузоперевозки и многое другое.
Одно из допустимых решений имеет вид:
Рисунок 5 Диаграмма Гантта для примера 2
1.4 Величины, используемые как критерии оценки расписаний
Рассмотрим величины, используемые в дальнейшем как критерии оценки расписаний, и соотношения между ними.
Сначала разделим исходные и искомые величины задачи. Первые определяются спецификой решаемой задачи, вторые являются результатом составления расписания. Чтобы подчеркнуть эту разницу, при обозначении этих величин используются строчные латинские буквы, а при обозначении искомых - прописные. Например: и .
Постановка задачи в теории расписаний начинается с описания системы машин и множества работ. Для простейшего процесса обслуживания система машин полностью описывается их числом. Пусть система состоит из m машин, занумеруем их 1,2,..., m. Занумеруем также работы числами от 1 до n, и пусть
- момент готовности (момент появления или момент поступления) работы. Эта величина представляет собой момент поступления i-й работы в систему из некоторого внешнего источника. есть минимально возможное время начала первой из операций работы i, i=1,..., n;
- плановый (директивный) срок. Эта величина представляет собой момент, к которому i-я работа должна быть выполнена. Иными словами, представляет собой директивное время окончания операции, заданное некоторыми внешними по отношении к рассматриваемой системе причинами.
Допустимая длительность прохождения работы в системе равна . Достаточно задать две из трех величин ,,. Теоретически безразлично какие две из них заданы, а какая находится из приведенного соотношения, поэтому для каждой работы все они считаются заданными.
Работа i состоит из операций. Для каждой операции задается набор следующих величин:
, ,
, ,
. .
. .
. .
, ,
где - номер машины, на которой выполняется операция j,
- длительность выполнения операции, т.е. длина интервала времени,
требуемого машиной для выполнения операции j.
общая длительность всех операций работы i (длительность работы).
может быть как постоянной, так и случайной величиной (в последнем случае до окончания операции ее длительность может быть только оценена). Тем не менее в этом случае для обозначения длительности операций испльзуются строчные буквы, поскольку предполагается, что она совершенно не зависит от расписания.
Наконец, предположим, что включает в себя все настройки машины, предшествующие выполнению операции, и все переналадки ее после выполнения операции. Подобное предположение равносильно тому, что длительности настройки машины не зависят от последовательности операций, то есть время, необходимое для подготовки машины к выполнению некоторой операции, не зависит от того, какую операцию последней выполнила машина. В большинстве случаев подобные предположения являются хорошим приближением к действительности и значительно упрощают математическую модель. Однако существуют случаи, когда такие предположения невозможны и нужно учитывать точные длительности настроек и возможную их зависимость от порядка выполнения операций.
Лист