1pi=1wirisumwi(ci - pi -ri)

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

Рассмотрим задачу:

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

Требуется выполнить все работы, чтобы значение [math]\sum w_{i}(c_{i} - p_{i} - r_{i})[/math] было минимальным.

Описание алгоритма

Пусть [math]time[/math] — текущий момент времени.
Для каждого очередного значения [math]time[/math], которое изменяется от [math]0[/math] до времени окончания последний работы, будем:

1. Выбирать работу [math]j[/math] из множества невыполненных работ, у которой [math]r_{i} \le time[/math] и значение [math]w_{i}[/math] максимально.
2. Если мы смогли найти работу [math]j[/math], то выполняем её в момент времени [math]time[/math]
3. Увеличиваем [math]time[/math] на один.

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

Докажем, что алгоритм оптимален. Доказательство будем вести от противного.
Рассмотрим расписание [math]S_{1}[/math], полученное после выполнения нашего алгоритма, и оптимальное расписание [math]S_{2}[/math].
Возьмём первый момент времени [math]t_{1}[/math], когда расписания различаются. Пусть в этот момент времени в [math]S_{1}[/math], будет выполняться работа с весом [math]w_{1}[/math], а в [math]S_{2}[/math] — работа с весом [math]w_{2}[/math].
Это первый момент, в котором расписания отличаются, значит в [math]S_{2}[/math] работа с весом [math]w_{1}[/math] выполнится в момент времени [math]t_{2} \gt t_{1}[/math].
Поменяем местами работы с весами [math]w_{1}[/math] и [math]w_{2}[/math] в [math]S_{2}[/math] и полуим расписание [math]S_{3}[/math]. Это возможно, потому что время появления этих работ не меньше [math]t_{1}[/math].
При такой перестановке ответы на задачу для [math]S_{2}[/math] и [math]S_{3}[/math] будут отличаться на

[math](t_{1} - r_{2})w_{2} + (t_{2} - r_{1})w_{1} - ((t_{1} - r_{1})w_{1} + (t_{2} - r_{2})w_{2}) = t_{1}(w_{2} - w_{1}) + t_{2}(w_{1} - w_{2}) = (t_{1} - t_{2})(w_{2} - w_{1})[/math]

Первая скобка отрицательная: [math]t_{1} \lt t_{2}[/math]. Вторая скобка тоже отрицательная из того, что в [math]S_{1}[/math] работа с весом [math]w_1[/math] выполняется раньше, значит её вес должен быть больше [math]w_2[/math].
Итого имеем, что ответ для [math]S_{2}[/math] больше, чем ответ для [math]S_{3}[/math]. Следовательно расписание [math]S_2[/math] неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание [math]S_{1}[/math] отличается от оптимального. Следовательно мы доказали, что оно оптимальное.