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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 12: Строка 12:
 
==Псевдокод==
 
==Псевдокод==
 
  for <tex>i</tex> = 1 to <tex>m</tex> do
 
  for <tex>i</tex> = 1 to <tex>m</tex> do
   <tex>\Pi_j = \empty </tex>
+
   <tex>\Pi_j = {\o} </tex>
 
   <tex>w_j = \frac{1}{s_j}</tex>
 
   <tex>w_j = \frac{1}{s_j}</tex>
 
  for <tex>i</tex> = 1 to <tex>n</tex> do
 
  for <tex>i</tex> = 1 to <tex>n</tex> do
 
   Find the largest index <tex> j </tex> of <tex>w_j</tex> = <tex>\min\limits_{l=1}^{m}{w_l}</tex>;
 
   Find the largest index <tex> j </tex> of <tex>w_j</tex> = <tex>\min\limits_{l=1}^{m}{w_l}</tex>;
   <tex>\Pi_j = i + \Pi_j </tex>
+
   <tex>\Pi_j = i \cup \Pi_j </tex>
 
   <tex>w_j = w_j + \frac{1}{s_j} </tex>
 
   <tex>w_j = w_j + \frac{1}{s_j} </tex>

Версия 17:58, 21 июня 2012


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

Есть несколько станков с разной скоростью выполнения работ и несколько работ с заданным временем выполнения.

Цель - составить такое расписание, чтобы суммарное время окончания всех работ было минимальным.

Алгоритм решения

Пусть [math] i_1, i_2, ... i_r [/math] последовательность работ, выполняемых на станке с номером [math] j [/math]. Тогда вклад этих работ в целевую функцию будет равен [math] p_{i1}\frac{r}{s_j} + p_{i2}\frac{r-1}{s_j}+...+p_{ir}\frac{1}{s_j} [/math]. Отсюда видно, что сумма оптимальна, когда последовательность [math] p_{ij} [/math] не убывает. Теперь введем неубывающую последовательность [math] t_1, t_2 ... t_n [/math], которая состоит из [math] n [/math] маленьких элементов из множества [math] \{\frac{1}{s_1}, \frac{1}{s_2} ... \frac{1}{s_m}, \frac{2}{s_1}, \frac{2}{s_2} ... \frac{2}{s_m}, \frac{3}{s_1} ... \}[/math]. Если [math] t_i = \frac{k}{s_j} [/math], то на [math] j[/math]-том станке

Псевдокод

for [math]i[/math] = 1 to [math]m[/math] do
  [math]\Pi_j = {\o} [/math]
  [math]w_j = \frac{1}{s_j}[/math]
for [math]i[/math] = 1 to [math]n[/math] do
  Find the largest index [math] j [/math] of [math]w_j[/math] = [math]\min\limits_{l=1}^{m}{w_l}[/math];
  [math]\Pi_j = i \cup \Pi_j [/math]
  [math]w_j = w_j + \frac{1}{s_j} [/math]