1pi1sumwu — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
(Время работы)
Строка 34: Строка 34:
 
== Доказательство корректности ==
 
== Доказательство корректности ==
 
== Время работы ==
 
== Время работы ==
 +
Время работы алгоритма зависит от того, насколько быстро мы будем добавлять и удалять работы из множества <tex> S </tex>, а также как быстро мы будем искать работу с минимальным <tex> w_{i} </tex>. Если в качестве множества <tex> S </tex> использовать структуру данных, умеющую выполнять данные операции за <tex> O(\log n) </tex>, то время работы всего алгоритма будет составлять <tex> O(n\log n) </tex>. Примерами таких структур данных, например, являются [[Двоичная куча | двоичная куча]] и [[Красно-черное дерево | красно-черное дерево]].
 +
 
== Литература ==
 
== Литература ==
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Теория расписаний]]
 
[[Категория: Теория расписаний]]

Версия 23:46, 10 июня 2013

Эта статья находится в разработке!


Постановка задачи

1) Дано [math] n [/math] работ и [math] 1 [/math] станок.

2) Для каждой работы известны её дедлайн [math] d_{i} [/math] и вес [math] w_{i} [/math]. Время выполнения всех работ [math] p_i [/math] равно [math] 1 [/math].

Требуется минимизировать [math]\sum w_{i} U_{i}[/math], то есть суммарный вес всех просроченных работ.

Алгоритм

Идея алгоритма состоит в том, чтобы на шаге [math] k [/math] строить оптимальное расписание для первых [math] k [/math] работ с наименьшими дедлайнами.

Будем считать, что работы отсортированны в порядке неуменьшения их дедлайнов. Пусть мы уже рассмотрели первые [math] k [/math] работ, тогда множество [math] S_{k} [/math] содержит только те работы, которые мы успеваем выполнить в порядке неуменьшения их дедлайнов при оптимальном составлении расписания . Рассмотрим работу [math] k + 1 [/math]. Если мы успеваем выполнить данную работу до ее дедлайна, то добавим ее во множество [math] S_{k} [/math], тем самым получив [math] S_{k + 1} [/math]. Если же [math] k + 1 [/math] работу выполнить до дедлайна мы не успеваем, то найдем в [math] S_{k} [/math] работу [math] l [/math] с наименьшим весом [math] w_{l} [/math] и заменим ее на работу [math] k + 1 [/math].

Таким образом, рассмотрев все работы, мы получим [math] S_{n} [/math] — множество работ, которые мы успеваем выполнить до наступления их дедлайнов, причем вес просроченных работ будет наименьшим. От порядка выполнения просроченных работ ничего не зависит, поэтому расположить в расписании их можно произвольным образом.

Псевдокод

Предполагаем, что перед началом выполнения алгоритма выполняется, что [math] 1 \leqslant d_{1} \leqslant d_{2} \leqslant ... \leqslant d_{n} [/math]. Все работы, дедлайн которых равен [math] 0 [/math], мы в любом случае выполнить без штрафа не успеем, поэтому их изначально можно отнести к просроченным.

[math] S [/math] — множество непросроченных работ, [math] t [/math] — текущее время.

[math] t = 1; [/math]
[math] S =  \varnothing; [/math]
for [math] i = 1 [/math] to [math] n [/math]
    [math] S = S \cup i ;[/math]
    if [math] d_{i}  \geqslant t [/math]     
        [math] t = t + 1; [/math]
    else
        [math] k = j : (w_{j} = \min \limits_{l \in S} w_{l}); [/math]
        [math] S = S \setminus k; [/math]

Доказательство корректности

Время работы

Время работы алгоритма зависит от того, насколько быстро мы будем добавлять и удалять работы из множества [math] S [/math], а также как быстро мы будем искать работу с минимальным [math] w_{i} [/math]. Если в качестве множества [math] S [/math] использовать структуру данных, умеющую выполнять данные операции за [math] O(\log n) [/math], то время работы всего алгоритма будет составлять [math] O(n\log n) [/math]. Примерами таких структур данных, например, являются двоичная куча и красно-черное дерево.

Литература