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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство корректности)
Строка 1: Строка 1:
 
<tex dpi = "200">P \mid \mid \sum C_{i}</tex>
 
<tex dpi = "200">P \mid \mid \sum C_{i}</tex>
 
{{Задача
 
{{Задача
|definition = Дано <tex>n</tex> работ с заданными временами выполнения <tex>p_{i}</tex>.  И <tex>m</tex> параллельных станков с одинаковой скоростью выполнения работ.<br>Цель {{---}} составить такое расписание, чтобы суммарное время окончания всех работ было минимальным.
+
|definition = Дано <tex>n</tex> работ с заданными временами выполнения <tex>p_{i}</tex> и <tex>m</tex> параллельных станков с одинаковой скоростью выполнения работ.<br>Цель {{---}} составить такое расписание, чтобы суммарное время окончания всех работ было минимальным.
 
}}
 
}}
  

Версия 21:23, 4 июня 2016

[math]P \mid \mid \sum C_{i}[/math]

Задача:
Дано [math]n[/math] работ с заданными временами выполнения [math]p_{i}[/math] и [math]m[/math] параллельных станков с одинаковой скоростью выполнения работ.
Цель — составить такое расписание, чтобы суммарное время окончания всех работ было минимальным.


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

Идея

Пусть [math]p_{i}[/math] заданы в порядке невозрастания ([math]p_{0} \geqslant p_{1} \geqslant \ldots \geqslant p_{n-1} [/math]). Пусть теперь [math]b_{i} = \left\lceil\dfrac{i}{m}\right\rceil[/math]. Тогда в оптимальном расписании работа с номером [math]i[/math] будет выполнена на станке с номером [math]i \bmod m[/math], [math]b_{i}[/math]-ой с конца.

Псевдокод

Здесь предполагается что работы отсортирован в порядке неубывания времён выполнения.

list<int> schedule[m]  //Заведём список работ для каждого станка. Ответ будет храниться в нём.
    for i = 0 to n
        schedule[i mod m].push(i) //ставим работу с номером i на станок i mod m в конец.
//Заметим что расписание для каждого станка получилось перевёрнутым
//Поэтому развернём расписание для каждого станка.
for i = 0 to m schedule[i].reverse()

Ассимптотика

Так как нам понадобится сортировка для массива [math]p_{i}[/math], то итоговая ассимптотика будет [math]\mathcal{O}(n\log{n})[/math].

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

Докажем две леммы:

Лемма:
В оптимальном расписании на каждом станке работы выполняются в порядке неубывания времён выполнения.
Доказательство:
[math]\triangleright[/math]
Пусть это не так. Заметим что [math]\sum C_{i} = \sum p_{i} \cdot b_{i}[/math]. Следовательно каждая работа даёт вклад равный [math]p_{i} \cdot b_{i}[/math]. Тогда поменяем местами две работы которые нарушают порядок невозрастания. Заметим что [math]\sum C_{i}[/math] уменьшилась. Следовательно — оптимальное расписание не оптимально. Противоречие.
[math]\triangleleft[/math]
Лемма:
В оптимальном расписании количество выполненных работ на любых двух станках отличается не более чем на [math]1[/math].
Доказательство:
[math]\triangleright[/math]
Пусть это не так. Как было отмечено в предыдущей лемме, каждая работа даёт вклад в [math]\sum C_{i}[/math] равный [math]p_{i} \cdot b_{i}[/math]. Найдём два станка количество работ на которых отличается больше чем на [math]1[/math]. Пусть это станки [math]x[/math] и [math]y[/math]. Причём на стнаке [math]x[/math] выполняется больше работ. Тогда если отправить первую с начала работу со станка [math]x[/math] на станок [math]y[/math] то [math]\sum C_{i}[/math] уменьшится на разность количества работ на станках [math]x[/math] и [math]y[/math]. Следовательно — оптимальное расписание не оптимально. Противоречие.
[math]\triangleleft[/math]
Теорема:
Алгоритм [math]P \mid \mid \sum C_{i}[/math] строит оптимальное расписание.
Доказательство:
[math]\triangleright[/math]
Пусть это не так и оптимальное расписание отличается от расписания построенного алгоритмом. Заметим что расписание построенное алгоритмом удовлетворяет обеим леммам. Тогда можно воспользоваться одной из них чтобы улучшить оптимальное раписание. Следовательно — оптимальное расписание не оптимально. Противоречие.
[math]\triangleleft[/math]