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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 8: Строка 8:
 
==Алгоритм решения==
 
==Алгоритм решения==
 
Пусть <tex> i_1, i_2, ... i_r </tex> последовательность работ, выполняемых на станке с номером <tex> j </tex>. Тогда вклад этих работ в целевую функцию будет равен <tex> p_{i1}\frac{r}{s_j} + p_{i2}\frac{r-1}{s_j}+...+p_{ir}\frac{1}{s_j} </tex>. Отсюда видно, что сумма оптимальна, когда последовательность <tex> p_{ij} </tex> не убывает.
 
Пусть <tex> i_1, i_2, ... i_r </tex> последовательность работ, выполняемых на станке с номером <tex> j </tex>. Тогда вклад этих работ в целевую функцию будет равен <tex> p_{i1}\frac{r}{s_j} + p_{i2}\frac{r-1}{s_j}+...+p_{ir}\frac{1}{s_j} </tex>. Отсюда видно, что сумма оптимальна, когда последовательность <tex> p_{ij} </tex> не убывает.
Теперь введем неубывающую последовательность <tex> t_1, t_2 ... t_n </tex>, которая состоит из <tex> n </tex> маленьких элементов из множества <tex> \{\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} ... \}</tex>.
+
Теперь введем неубывающую последовательность <tex> t_1, t_2 ... t_n </tex>, которая состоит из <tex> n </tex> маленьких элементов из множества <tex> \{\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} ... \}</tex>. Если <tex> t_i = \frac{k}{s_j} </tex>, то на <tex> j-том </tex> станке
 +
 
 +
==Псевдокод==
 +
for i=1 to m do
 +
  Pj = f; wj=1/sj
 +
for i=1 to n do
 +
  Find the largest index j of wj = min po m (w);
 +
  pj = i+pj
 +
  wj = wj+1/pj

Версия 17:37, 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 i=1 to m do
 Pj = f; wj=1/sj
for i=1 to n do
 Find the largest index j of wj = min po m (w);
 pj = i+pj
 wj = wj+1/pj