1pi1sumwu

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

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

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]. Примерами таких структур данных, например, являются двоичная куча и красно-черное дерево.