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

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

Версия 19:15, 13 мая 2016

[math] O \mid p_{i,j} = 1 \mid \sum w_{i} U_{i} [/math]

Задача:
Дано [math]m[/math] одинаковых станков, которые работают параллельно, и [math]n[/math] работ, которые необходимо выполнить в произвольном порядке на всех станках. Любая работа на любом станке выполняется за единицу времени. Для каждой работы есть время окончания [math]d_i[/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] c наименьшим весом [math]w_{l}[/math] и заменим ее на работу [math]k+1[/math].

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

Псевдокод

Предполагаем, что перед началом выполнения алгоритма выполняется, что 1 \leqslant d_{1} \leqslant d_{2} \leqslant ... \leqslant d_{n}. Все работы, дедлайн которых равен 0, мы в любом случае выполнить без штрафа не успеем, поэтому их изначально можно отнести к просроченным. S — множество непросроченных работ, Check — функция, решающая задачу [math] O \mid p_{i,j} = 1, d_i \mid - [/math].


S =  [math]\varnothing[/math];
for i = 1 to n
   S = [math] S \cup \{i\} [/math];
   if not check(s) :
       найти такое [math]k[/math], что [math]w_{k} = \min \{ w_{j} \mid j \in S\}[/math];
       S = [math]S \setminus \{k\}[/math];

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

Время работы

См. также

Источники информации