Расписания для одного ресурса.

Рассмотрим постановку следующей простой задачи. Пусть имеются п независимых операций (работ), каждая из которых характеризуется временем U (і = 1,2... п) выполнения в системе. Необходи

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

прохождения работ через систему.

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

Если заданы дополнительно приоритеты щ {г = 1,2,...,п) работ (чем приоритетней работа, тем больше величина щ), то оптимальное решение задачи соответствует упорядочению работ по принципу

Рассмотрим теперь задачу оптимального прохождения взаимозависимых работ через систему. Пусть длительность выполнения к-й работы равна, Д. Если fc-я работа выполняется первой, то для подготовки системы, находящейся в исходном состоянии, к обслуживанию требуется Да- времени. Если работа j выполняется непосредственно после г-й, то для перенастройки системы требуется время tij. Если к-я работа выполняется последней, то требуется До времени для возврата системы в исходное состояние. Необходимо найти такую последовательность выполнения работ, при которой минимизируется общее время их прохождения через систему. Поскольку суммарное время выполнения

время, необходимое на перенастройку системы.

Эта задача имеет следующую графическую интерпретацию. Рассмотрим полный ориентированный граф (X,U)7 где X =

= {0, 1...... п} —множество вершин, U — множество дуг. Каждой

дуге (i,j) припишем число (вес) Uj, называемое также длиной дуги. Нулевая вершина здесь соответствует начальному и конечному состоянию системы. Требуется найти такой контур, проходящий через каждую вершину только один раз, которому соответствует наименьшая длина, равная сумме длин его дуг. Задачу можно решить, используя все перестановки п задач. Для каждой перестановки вычисляется длина пути на графе. Этот алгоритм решения задачи называется исчерпывающим и имеет экспоненциальную сложность. Однако существуют алгоритмы с меньшей сложностью, которые дают хорошие, хотя не обязательно оптимальные решения. Таким алгоритмом является,

например алгоритм GTS [8], который осуществляет поиск на графе, выбирая на каждом шаге дугу с минимальным весом. Алгоритм имеет квадратичную сложность 0(п2).

2.1.1.