Лекция 10 (1121239), страница 2

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

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

Можно выдвинуть гипотезу, что не существует детерминированного полиномиального алгоритма A построения расписания по маршруту в графе G такого, что для (SW,,):SL:A(SL)=SP⁰, где SP⁰ – оптимальное расписание.

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

Локальная целевая функция на ребрах графа G

,

– разница во времени между минимальным временем завершения i-й работы и максимальным временем начала j-й работы.

• Если θ < 0, то j-я работа не может идти в расписании после i-й.

• В противном случае, чем меньше значение θ, тем меньше максимальный возможный промежуток в расписании между работами, соответствующими вершинам i и j, и тем больше значение локальной целевой функции.

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

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

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

Построим граф 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-я работа – чем меньше это число, тем раньше работу предпочтительно разместить;

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

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

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

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