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

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

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

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

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

Множество корректных расписаний (т.е. множество S в задаче (1.1.)) определим набором ограничений:

Задача:

известна в теории расписаний как задача о выборе максимального числа совместимых заявок и является NP–трудной.

Для частной задачи:

известен оптимальный жадный алгоритм сложности O(n∙log n) [Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2000.].

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

Задача для схемы с подциклами

s₁

f₁

s₂

f₂

s₃

f₃

φ₁

φ₁

φ₁

...

φ₂

φ₂

φ₂

0

2*T

T

3*T

число работ в цепочке

цепочка работ

резерв для сдвига

расписания

1. в каждом подцикле может находиться не более 1 цепочки работ и работы в цепочке следуют друг за другом без пауз;

2. время выполнения работ не должно пересекать границы подцикла;

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

4. в конце подцикла должен быть зарезервирован интервал времени, длительность которого не меньше, чем заданная доля длительности подцикла;

5. число работ в цепочке не должно превышать заданного значения;

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

Задача для схемы без подциклов

1. число работ в цепочке не должно превышать заданного значения;

2. суммарная длительность выполнения работ цепочки не должна превышать заданного значения;

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

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

Задача построения статико-динамических расписаний

Пусть задано множество работ:

SW={a_i=<s_i,f_i,t_i,p_i>|i[1..n]}, где

• [s_i,f_i) – директивный интервал;

• t_i – время выполнения работы;

• p_i – номер раздела работы;

•  и , определяющие, временные затраты на переключение контекста между окнами и резерв свободного времени внутри каждого окна.

Требуется построить расписание, представляющее собой набор окон:

SP={w_i=<S_i,F_i,SW_i>|i[1..m]}, где

• S_i – время открытия окна;

• F_i – время закрытия окна;

• SW_i={aⁱ_j}SW – множество работ, выполняемых внутри окна.

Ограничения корректности расписания:

1. (i,j)[1..m],ij:SW_iSW_j= – множества работ, размещенных внутри разных окон, не пересекаются;

2. i[1..n],j[1..m],a_iSW_j:s_iS_j<F_jf_i – временной интервал окна лежит внутри директивных интервалов работ, выполняющихся в окне;

3. (i,j)[1..n],k[1..m],a_i,a_jSW_k:p_i=p_j – разделы работ, размещенных внутри одного окна, совпадают;

4. (i,j)[1..m],i<j:S_jF_i+ – окна не пересекаются и между любыми двумя соседними окнами есть промежуток не короче времени, необходимого на переключение контекста;

5. – суммарное время выполнения всех работ из одного окна с учетом резерва времени не больше, чем длина окна.

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

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

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

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