Пусть имеется оптимальное расписание, в котором номера выполняе-
мых работ совпадают с порядковыми номерами работ. Тогда этому расписа-
нию будет соответствовать минимальное значение штрафа. Всякая переста-
новка в порядке выполнения двух или более работ уже не может привести
к уменьшению штрафа, поэтому, переставив местами работы с номерами k и
k+1, мы получим штраф не меньше.
Обозначим через l(i) время начала выполнения работы i.
С учетом представления штрафа это можно записать так
k-1 n
SUM c(i)*l(i) + c(k)*l(k) + c(k+1)*l(k+1) + SUM c(i)*l(i) <=
i=1 i=k+2
k-1 n
<= SUM c(i)*l(i) + c(k+1)*l'(k+1) + c(k)*l'(k) + SUM c(i)*l(i).
i=1 i=k+2
Здесь l'(k+1) и l'(k) - время начала выполнения соответственно
(k+1)-й и k-й работы после перестановки. Заметим, что k-я работа в
обоих расписаниях выполнятся после того, как будут выполнены предшест-
вующие k-1 работы, поэтому
l(k)=l'(k+1), l(k+1)=l(k)+t(k), l'(k)=l'(k+1)+t(k+1)=l(k)+t(k+1).
В результате получаем:
с(k)l(k) + c(k+1)(l(k)+t(k)) <= c(k+1)l(k) + c(k)(l(k)+t(k+1))
c(k+1)t(k) <= c(k)t(k+1)
t(k)/c(k) <= t(k+1)/c(k+1).
Алгоритм:
1) Для всех работ вычислить отношение t(i)/c(i);
2) Упорядочить работы по возрастанию этого отношения.