Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Алгоритм SPT
В системах оперативной обработки в качестве основного критерия эффективности используется среднее время обслуживания заявок. Нетрудно видеть, что в случае, когда времена решения задач априори известны, минимальное среднее время ответа дает алгоритм SPT (Shortest-processing-task-first), назначающий задачи на решение в порядке убывания времени решения ti, т.е. t1Јt2Ј...ЈtL. При этом время ответа ui для задачи zi есть
ti - собственно время решения и среднее время ответа есть
Покажем, что u* действительно минимальное значение среднего времени обслуживания. Для того чтобы показать, что u* действительно минимально среди u для всех перестановок, достаточно показать, что применение к произвольной перестановке (a1,...,aL) любой парной транспозиции, меняющей местами элементы ak и al, где talЈ tak и l>k, может лишь уменьшить исходное значение u, соответствующее перестановке (a1,...,aL), где ai - номер задачи, назначаемой на решение i-й по порядку, i=I,L. Действительно, пусть задачи с номерами ak и al поменялись местами. Тогда для полученной перестановки среднее время обслуживания равно
так как l>k, а talЈ tak. Следовательно, перемещение вперед задачи с меньшим временем решения приводит к уменьшению среднего времени обслуживания. В перестановке (1,...,L) при условии, что t1Ј...ЈtL, нельзя сделать ни одной такой улучшающей транспозиции, а потому u* есть минимальное среднее время обслуживания и алгоритм SPT дает оптимальное решение рассматриваемой задачи.
|