Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 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 дает оптимальное решение рассматриваемой задачи.

 

Date: 2015-07-25; view: 973; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



mydocx.ru - 2015-2024 year. (0.005 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию