QSumCi — различия между версиями
| Строка 7: | Строка 7: | ||
==Алгоритм решения== | ==Алгоритм решения== | ||
| − | Пусть <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> 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> не убывает. |
Версия 16:51, 21 июня 2012
Постановка задачи
Есть несколько станков с разной скоростью выполнения работ и несколько работ с заданным временем выполнения.
Цель - составить такое расписание, чтобы суммарное время окончания всех работ было минимальным.
Алгоритм решения
Пусть последовательность работ, выполняемых на станке с номером . Тогда вклад этих работ в целевую функцию будет равен . Отсюда видно, что сумма оптимальна, когда последовательность не убывает.
