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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Описание алгоритма)
(Псевдокод)
(не показана 21 промежуточная версия этого же участника)
Строка 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>Цель {{---}} составить такое расписание, чтобы суммарное время окончания всех работ было минимальным.
 
}}
 
}}
  
 
== Описание алгоритма ==
 
== Описание алгоритма ==
 
=== Идея ===
 
=== Идея ===
Пусть <tex>p_{i}</tex> заданы в порядке невозрастания (<tex>p_{1}  \geqslant p_{2} \geqslant \ldots \geqslant p_{n} </tex>). Пусть теперь <tex>b_{k} = \dfrac{k}{m}</tex>. Тогда в оптимальном расписании работа с номером <tex>i</tex> будет выполнена на станке <tex>i \bmod m</tex>, <tex>b_{i}</tex>-ой с конца.
+
Пусть <tex>p_{i}</tex> заданы в порядке невозрастания (<tex>p_{0}  \geqslant p_{1} \geqslant \ldots \geqslant p_{n-1} </tex>). Пусть теперь <tex>b_{i} = \left\lceil\dfrac{i}{m}\right\rceil</tex>. Тогда в оптимальном расписании работа с номером <tex>i</tex> будет выполнена на станке с номером <tex>i \bmod m</tex>, <tex>b_{i}</tex>-ой с конца.
  
 
=== Псевдокод ===
 
=== Псевдокод ===
 +
Итоговым расписанием будет массив  <tex>\mathtt{schedule}</tex>  где в  <tex>\mathtt{schedule[i][j]}</tex>  храниться номер работы которую надо исполнить на станке номер <tex>i</tex>, <tex>j</tex>-ой по счёту.
  
  list<int> schedule[m] <font color=green> //Заведём список работ для каждого станка. Ответ будет храниться в нём.</font>
+
  '''function''' getSchedule(p : '''int'''[n]): '''list'''<'''int'''>[m]
    '''for''' i = 0 '''to''' n
+
  '''Pair'''<'''int''','''int'''> jobs[n]
        schedule[i mod m].push(i) <font color=green>//ставим работу с номером i на станок i mod m в конец.</font><br>
+
  '''for''' i = 0 '''to''' n
    <font color=green>//Заметим что расписание для каждого станка получилось перевёрнутым<br>   //Поэтому развернём расписание для каждого станка.</font>
+
    jobs[i] = <tex>\langle</tex>p[i], i<tex>\rangle</tex> <font color=green>// Создаём пары для востановления номера работы после сортировки.</font>
    '''for''' i = 0 '''to''' m
+
  sort(jobs) <font color=green>// Cортируем массив в порядке уменьшения p[i].</font><br>
        schedule[i].reverse()
+
  '''list'''<'''int'''> schedule[m] <font color=green> // Заведём список работ для каждого станка. Ответ будет храниться в нём.</font>
 +
  '''for''' i = 0 '''to''' n
 +
    schedule[i mod m].pushFront(jobs[i].second) <font color=green>// Cтавим i-ую в порядке уменьшения p[i] работу на станок i mod m в конец.</font><br>
 +
   '''return''' schedule
  
 
=== Ассимптотика ===
 
=== Ассимптотика ===
Так как нам понадобится сортировка для массива <tex>p_{i}</tex>, то итоговая ассимптотика будет <tex>\mathcal{O}(n\log{n})</tex>.
+
Так как нам понадобится [[Быстрая сортировка | сортировка]] для массива <tex>p_{i}</tex>, то итоговая ассимптотика будет <tex>\mathcal{O}(n\log{n})</tex>.
 +
 
 +
== Доказательство корректности ==
 +
Докажем две леммы:
 +
{{Лемма
 +
|id=lemma1
 +
|statement= В оптимальном расписании на каждом станке работы выполняются в порядке неубывания времён выполнения.
 +
|proof= Пусть это не так. Заметим что <tex>\sum\limits_{i=0}^{n-1} C_{i} = \sum\limits_{i=0}^{n-1} p_{i} \cdot b_{i}</tex>. Следовательно каждая работа даёт вклад равный <tex>p_{i} \cdot b_{i}</tex>. Тогда поменяем местами две работы которые нарушают порядок невозрастания. Заметим что <tex>\sum\limits_{i=0}^{n-1} C_{i}</tex> уменьшилась. Следовательно {{---}} оптимальное расписание не оптимально. Противоречие.}}
 +
 
 +
{{Лемма
 +
|id=lemma2
 +
|statement= В оптимальном расписании количество выполненных работ на любых двух станках отличается не более чем на <tex>1</tex>.
 +
|proof= Пусть это не так. Как было отмечено в предыдущей лемме, каждая работа даёт вклад в <tex>\sum\limits_{i=0}^{n-1} C_{i}</tex> равный <tex>p_{i} \cdot b_{i}</tex>. Найдём два станка количество работ на которых отличается больше чем на <tex>1</tex>. Пусть это станки <tex>x</tex> и <tex>y</tex>. Причём на стнаке <tex>x</tex> выполняется больше работ. Тогда если отправить первую с начала работу со станка <tex>x</tex> на станок <tex>y</tex> то  <tex>\sum\limits_{i=0}^{n-1} C_{i}</tex> уменьшится на разность количества работ на станках <tex>x</tex> и <tex>y</tex>. Следовательно {{---}} оптимальное расписание не оптимально. Противоречие.}}
 +
 
 +
{{Теорема
 +
|id=theorem1
 +
|statement= Алгоритм <tex>P \mid \mid \sum C_{i}</tex> строит оптимальное расписание.
 +
|proof= Пусть это не так и оптимальное расписание отличается от расписания построенного алгоритмом. Заметим что расписание построенное алгоритмом удовлетворяет обеим леммам. Тогда можно воспользоваться одной из них чтобы улучшить оптимальное раписание. Следовательно {{---}} оптимальное расписание не оптимально. Противоречие. }}
 +
 
 +
== См. также ==
 +
* [[Pintreepi1Lmax|<tex>P \mid intree, p_{i} = 1 \mid L_{max}</tex>]]
 +
* [[PpmtnriLmax|<tex>P \mid pmtn, r_i \mid L_{max}</tex>]]
 +
* [[Ppi1sumwu|<tex>P \mid p_i=1 \mid \sum w_i U_i</tex>]]
 +
== Источники информации ==
 +
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 22
 +
 
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Теория расписаний]]

Версия 22:15, 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]-ой с конца.

Псевдокод

Итоговым расписанием будет массив [math]\mathtt{schedule}[/math] где в [math]\mathtt{schedule[i][j]}[/math] храниться номер работы которую надо исполнить на станке номер [math]i[/math], [math]j[/math]-ой по счёту.

function getSchedule(p : int[n]): list<int>[m]
  Pair<int,int> jobs[n]
  for i = 0 to n
    jobs[i] = [math]\langle[/math]p[i], i[math]\rangle[/math] // Создаём пары для востановления номера работы после сортировки.
  sort(jobs) // Cортируем массив в порядке уменьшения p[i].
list<int> schedule[m] // Заведём список работ для каждого станка. Ответ будет храниться в нём. for i = 0 to n schedule[i mod m].pushFront(jobs[i].second) // Cтавим i-ую в порядке уменьшения p[i] работу на станок i mod m в конец.
return schedule

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

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

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

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

Лемма:
В оптимальном расписании на каждом станке работы выполняются в порядке неубывания времён выполнения.
Доказательство:
[math]\triangleright[/math]
Пусть это не так. Заметим что [math]\sum\limits_{i=0}^{n-1} C_{i} = \sum\limits_{i=0}^{n-1} p_{i} \cdot b_{i}[/math]. Следовательно каждая работа даёт вклад равный [math]p_{i} \cdot b_{i}[/math]. Тогда поменяем местами две работы которые нарушают порядок невозрастания. Заметим что [math]\sum\limits_{i=0}^{n-1} C_{i}[/math] уменьшилась. Следовательно — оптимальное расписание не оптимально. Противоречие.
[math]\triangleleft[/math]
Лемма:
В оптимальном расписании количество выполненных работ на любых двух станках отличается не более чем на [math]1[/math].
Доказательство:
[math]\triangleright[/math]
Пусть это не так. Как было отмечено в предыдущей лемме, каждая работа даёт вклад в [math]\sum\limits_{i=0}^{n-1} 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\limits_{i=0}^{n-1} 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]

См. также

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

  • P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 22