Изменения

Перейти к: навигация, поиск

1ripi1sumwc

1697 байт убрано, 00:14, 3 июня 2015
Нет описания правки
Перед решением основной задачи рассмотрим более простые.
==Просты задачи==
===Задача 1===
<tex dpi = "200"> 1 \mid p_i = 1\mid \sum C_i</tex>
Этот случай простейший. Для верного выполнения просто выставим работы по порядку, тогда ответом будет <tex>n</tex>, так как мы <tex>n</tex> раз сложим время выполнения одной работы, которое в нашем случае единица.
===Задача 2===
<tex dpi = "200"> 1 \mid p_i = 1\mid \sum w_i C_i</tex>
Входные данные для этой задачи: число работ <tex>n</tex> и вес каждой работы <tex>w_i</tex>
Для верного выполнения просто выставим работы по порядкуубывания весов, тогда ответом будет <tex> \sum_{i = 1}^n(w_iC_i)</tex>, так как мы <tex>n</tex> раз сложим время выполнения одной работы (которое в нашем случае единица) домноженное на вес этой работы.
===Задача 3===
<tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum f_i</tex>
{{Задача
<tex> t_i \leftarrow </tex> '''max'''<tex>(r_i, \ t_{i-1} - 1)</tex>
==Задача 4==
<tex dpi = "200"> 1 \mid r_j,p_j = p \mid \sum f_j</tex>
 
Вес всех работ <tex>w_i \geqslant 0</tex>
Для всех функций <tex>f_1, f_2, \ldots, f_n</tex> выполняются следующие свойства:
 
<tex>f_j</tex> неубывающая функция для <tex>j = 1, 2, \ldots, n</tex>
 
<tex>f_i - f_j</tex> неубывающая функция для <tex>i, j = 1, 2, \ldots, n</tex> при <tex>i < j </tex>
 
<tex>\sum w_i C_i</tex> являются функцией <tex>f_j(C_j)</tex>, так что по факту решаем задачу <tex>1 \mid r_j,p_j = p \mid \sum w_i C_i </tex>
 
'''Описание алгоритма'''
 
Пусть перед началом алгоритма работы пронумерованы в соответствии с свойствами для функций <tex>f_1, f_2, \ldots, f_n</tex>
 
Пояснение для псевдокода:
 
<tex>T</tex> это множество {<tex>r_j + lp \mid j = 1, 2, \ldots, n; l = 0, 1, \ldots, n-1 </tex>}
 
<tex>F_k'(s,e)</tex> это <tex>min(F_{k-1}(s,t_k)+F_{k-1}(t_k + p, e)+f_k(t_k + p) \mid t_k \in T, max(s, r_k) \leqslant t_k \leqslant e-p)</tex>
 
'''Псевдокод'''
 
'''for''' <tex> \forall s, e \in T \ with \ s \leqslant e</tex> '''do'''
<tex>F_0(s,e) \leftarrow 0</tex>
'''for''' <tex>k \leftarrow 1</tex> '''to''' <tex>n</tex> '''do'''
'''for''' <tex> \forall s, e \in T \ with \ s \leqslant e</tex> '''do'''
<tex>
F_k(s,e) \leftarrow
\begin{cases}
F_{k-1}(s,e) \ if\ r_k \notin [s - p,e);\\
F_k'(s,e) \ overwise;
\end{cases}
</tex>
'''Вычислить''' <tex>F_n($$ \min_{i=1}^n (r_i) $$, max_{t \in T}(t+p) )</tex>
==Описание алгоритма==
Пусть <tex>time</tex> {{---}} текущий момент времени.<br/>
'''while''' <tex> S \neq \varnothing </tex>
<tex> j \leftarrow null </tex>
'''if''' <tex> i \in S</tex> '''and''' <tex> r_{i} \leq leqslant \mathtt{time}</tex> '''and''' <tex>\max w_{i} </tex>
<tex> j \leftarrow i </tex>
'''if''' <tex>j \neq null </tex>
==Сложность алгоритма==
Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, [[Wikipedia:ru:Очередь с приоритетом (программирование)|очередь с приоритетами]]. Значит общее время работы алгоритма <tex>O((n + \max r_{i})\log n)</tex>
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 38 - 39
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 84 - 85
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 101 - 102
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]
Sergej Arkhipov
37
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/47287»

Навигация