4551
правка
Списочное планирование: различия между версиями
Перейти к навигации
Перейти к поиску
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 15: | Строка 15: | ||
Теорема 1. Коэффициент конкурентоспособности алгоритма LS составляет 2 | '''Теорема 1. Коэффициент конкурентоспособности алгоритма LS составляет <math>2 - \frac{1}{m}</math>.''' | ||
Доказательство. Рассмотрим расписание, созданное для заданной последовательности. Обозначим за <math>\ell</math> задание, определяющее продолжительность работы (т. е. последнее задание, назначенное машине i, имеющей максимальную нагрузку). Пусть L обозначает его размер, а X – общий размер всех остальных заданий, назначенных i. В момент, когда задание L было назначено i, это была машина с минимальной нагрузкой. Таким образом, нагрузка каждой машины составляет не менее X. Продолжительность работы оптимального расписания (т. е. расписания, которое минимизирует продолжительность этого периода) равна стоимости оптимального оффлайнового алгоритма и, таким образом, обозначается как OPT. Обозначим за P сумму всех размеров заданий в последовательности. | |||
Можно получить две следующие простые нижние границы для OPT. | |||
(1) <math>OPT \ge L</math> | |||
(2) <math>OPT \ge \frac{P}{m} \ge \frac{m \cdot X + L}{m} = X + \frac{L}{m}</math> | |||
OPT > | |||
Неравенство (1) вытекает из того факта, что {OPT} необходимо выполнить работу | Неравенство (1) вытекает из того факта, что {OPT} необходимо выполнить работу <math>\ell</math> и, таким образом, по крайней мере одна машина имеет нагрузку как минимум L. Первое неравенство в выражении (2) обусловлено тем, что по крайней мере одна машина получает по крайней мере часть <math>\frac{1}{m}</math> от совокупного размера заданий. Второе неравенство в (2) вытекает из приведенных выше соображений относительно нагрузки каждой машины. | ||
Это доказывает, что продолжительность работы алгоритма, X + L, может быть ограничена следующим образом | Это доказывает, что продолжительность работы алгоритма, X + L, может быть ограничена следующим образом: | ||
1X + L | |||
(3) <math>1X + L \le OPT + \frac{m - 1}{m} L \le OPT + \frac{m - 1}{m} OPT = (2 -\frac{1}{m} OPT)</math> | |||