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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм)
(Псевдокод)
Строка 15: Строка 15:
  
 
== Псевдокод ==
 
== Псевдокод ==
 +
Предполагаем, что перед началом выполнения алгоритма выполняется, что <tex> 1 \leqslant d_{1} \leqslant d_{2} \leqslant ... \leqslant d_{n} </tex>. Все работы, дедлайн которых равен <tex> 0 </tex>, мы в любом случае выполнить без штрафа не успеем, поэтому эти работы изначально можно отнести к просроченным.
 +
 +
<tex> S </tex> {{---}} множество непросроченных работ, <tex> t </tex> {{---}} текущее время.
 +
 +
 +
<tex> t = 1; </tex>
 +
<tex> S =  \varnothing; </tex>
 +
'''for''' <tex> i = 1 </tex> '''to''' <tex> n </tex>
 +
    <tex> S = S \cup i ;</tex>
 +
    '''if''' <tex> d_{i}  \geqslant t </tex>   
 +
        <tex> t = t + 1; </tex>
 +
    '''else'''
 +
        <tex> k = j : (\min \limits_{j \in S} w_{j}) </tex>
 +
        <tex> S = S \setminus k; </tex>
 +
 
== Доказательство корректности ==
 
== Доказательство корректности ==
 
== Время работы ==
 
== Время работы ==

Версия 02:43, 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 : (\min \limits_{j \in S} w_{j}) [/math]
        [math] S = S \setminus k; [/math]

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

Время работы

Литература