Лекции All in One (1121240), страница 9

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 9)

Значение данной функции вычисляется алгоритмом, строящим расписание по маршруту.

Второй способ сведения задачи построения статико-динамического расписания к задаче нахождения на графе маршрута

Построим граф G’=<N’,A’>,

N’={n_i⁺,n_i^–|i[1..n]}{O} – множество вершин; вершина n_i⁺ соответствует размещению работы без закрытия текущего окна, n_i^– – размещению работы с закрытием окна. Вершина О является началом всех маршрутов.

A’={(n_i⁺,n_j^–),(n_i⁺,n_j⁺),(n_i^–,n_j^–)|i,j[1..n],ij}{(O,n_i⁺), (O,n_i^–)|i[1..n]} – множество ребер. Вершины, соответствующие одной работе, ребрами не связаны.

Алгоритм построения расписания по заданной последовательности работ полностью аналогичен предыдущему, за исключением того, что в п.4 при размещении работы, соответствующей вершине n_j^– текущее окно закрывается принудительно.

Если SP⁰ корректное оптимальное расписание для множества работ SW, то существует такая последовательность вершин SL, что модифицированный алгоритм построит по ней корректное оптимальное расписание.

Построенное расписание будет совпадать с расписанием SP⁰

• по количеству размещенных в нем работ,

• по количеству окон,

• по множеству работ выполняемых внутри каждого окна,

но может отличаться по времени открытия и закрытия окон.

Алгоритм построения расписания обменов по каналу с централизованным управлением (схема с подциклами)

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

Дано:

• Множество работ, которые должны выполняться на системе . Для каждой работы заданы - время выполнения, - директивный интервал выполнения и выполняется условие ;

• Дополнительные ограничения на корректность расписания ;

• Вектор значений технологических требований .

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

Здесь k - порядковый номер j-ой работы в расписании,

- время начала выполнения j-ой работы в расписании ,

- время завершения выполнения j-ой работы.

Множество корректных расписаний определим набором ограничений:

1. Построение муравьями путей в графе.

2. Применение алгоритма размещения работ в расписание, на вход которому подаются последовательности вершин, построенные муравьиным алгоритмом.

3. Вычисление целевой функции.

4. Обновление количества феромона на ребрах графа.

5. Если условие останова не выполнено, переход к п.1.

Сопоставим каждой работе из J вершину r_i.

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

Получим полносвязный ориентированный граф

• – множество вершин,

• – множество ребер (между любыми двумя вершинами есть два ориентированных ребра).

Утверждение. Каждому пути в графе G соответствует ровно одно расписание и для одного и того же расписания может существовать более одного пути, по которому его можно построить.

Локальные эвристические функции на ребрах графа:

1. – чем ýже директивный интервал работы, тем раньше её предпочтительно разместить;

2. , - чем ýже директивный интервал работы и чем больше времени нужно на её выполнение, тем раньше её предпочтительно разместить;

3. , где NS – количество подциклов, в которые может быть размещена j-я работа – чем меньше это число, тем раньше работу предпочтительно разместить;

Сравнение алгоритмов на классе исходных данных А.

Сравнение алгоритмов на классе исходных данных Б.

Характеристики

Список файлов лекций