Задачи теории расписаний. Классификация задач, способы представления

Задача теории расписаний считается заданной, если определены

1) подлежащие выполнению работы и операции;

2) количество и типы машин, выполняющих операцию;

3) порядок прохождения машин;

4) критерии оценки расписаний.

В зависимости от характера поступления работ различают два вида задач: статические и динамические. В статических задачах в свободную систему одновременно поступает определенное число работ. После этого новые работы не поступают и расписание составляется для вполне определенного и известного заранее числа работ. В динамических задачах работы поступают в систему в некоторые моменты времени, которые можно предсказать только в статистическом смысле. Поэтому моменты будущих поступлений не определены. Упорядочение в динамических и статических задачах требует различных методов решения.

Порядок выполнения машинами операций одной работы определяет, является ли система машин:

а) конвейерной;

б) со случайным порядком выполнения работ;

в) системой произвольного типа.

В конвейерной системе последовательность прохождения машин одинакова для каждой из работ. Согласно принятой терминологии это означает, что существует такая нумерация машин, что для одной и той же работы номер машины, выполняющей операцию X, меньше номера машины, выполняющей операцию Y, если X предшествует Y.

В системе со случайным порядком выполнения работ машинами любая операция может выполняться любой машиной, т.е. все машины являются идентичными.

В системах произвольного типа каждая операция может выполняться какой-либо определенной машиной.

Для классификации задач теории расписаний в дальнейшем используется запись А/В/С/D, где

· А характеризует процесс поступления работ. Для динамических задач А представляет собой функцию распределения времени между поступлениями. Для статических задач А соответствует числу одновременно поступивших работ, если по этому поводу ничего специально не оговорено. Если на месте А стоит n то это означает произвольное, но конечное число работ в статическом случае.

· В характеризует число машин в системе. Если на месте В стоит m то это означает произвольное число машин.

· С характеризует порядок (дисциплину) выполнения работ машинами. Если на месте С находится F, то это соответствует конвейерной системе; если R - то случайной, и если G - произвольной. Для системы, состоящей из одной машины, указанные дисциплины теряют смысл и поэтому для такой системы третий параметр опускается.

· D характеризует оценку (критерий) расписания.

Пример употребления указанных обозначений: запись означает, что требуется упорядочить n работ для выполнения их в конвейерной системе, состоящей из двух машин, так, чтобы минимизировать максимальную длительность прохождения работы (джонсоновская задача составления расписания).

Общая задача теории расписаний записывается так: - упорядочить работ в произвольной системе из машин так, чтобы минимизировать максимальную длительность прохождения работы.

32.Задачи теории расписаний. Одноприборные задачи ТР. Минимизация суммарного запаздывания.

33.Задачи теории расписаний. n-приборные задачи ТР. Постановка задачи, ограничения