Стохастическое планирование: различия между версиями

Рассмотрим одну машину, которая обрабатывает n заданий, причем (случайное) время обработки задания i задается распределением Fj(-), среднее значение которого равно pi. Правило WSEPT (первым обрабатывается задание с наименьшим взвешенным ожидаемым временем обработки – Weighted Shortest Expected Processing Time) упорядочивает задания в порядке убывания величины wi/pi. Смит [ ] доказал, что правило WSEPT минимизирует сумму взвешенных времен завершения, когда каждое время обработки является детерминированными. Роткопф [11] обобщил этот результат и доказал следующую теорему:

Теорема 1. Правило WSEPT минимизирует ожидаемую сумму взвешенных времен завершения в классе всех динамических политик без вытеснения (и, следовательно, также в классе всех статических политик без вытеснения).

Если вытеснение допускается, правило WSEPT не является оптимальным. Впрочем, Севчик [ ] показал, как присвоить каждому заданию в каждый момент времени «индекс» таким образом, чтобы планирование задания с наибольшим индексом в каждый момент времени было оптимальным. Такие политики, называемые индексными политиками, были всесторонне изучены, поскольку они (относительно) просты с точки зрения реализации и анализа. Оптимальность индексных политик зачастую может быть доказана при некоторых допущениях о распределении времени обработки. Например, Вебер, Варайя и Уолранд [14] доказали следующий результат для планирования n заданий на m идентичных параллельных машинах:

Теорема 2. Правило SEPT минимизирует ожидаемую сумму времени выполнения в классе всех динамических политик без вытеснения, если распределение времени обработки заданий упорядочено стохастически.

Для той же задачи, но с целью минимизации общей длительности выполнения Бруно, Дауни и Фредриксон [ ] доказали оптимальность правила LEPT (первым обрабатывается задание с самым длинным ожидаемым временем обработки) при условии, что все задания имеют экспоненциально распределенное время обработки.

Одним из наиболее значительных достижений в области стохастического планирования является доказательство оптимальности индексных политик для задачи о многоруком бандите и ее многочисленных вариантов, первоначально предложенное Гиттинсом и Джонсом [5, 6]. В экземпляре задачи о бандите имеется N проектов, каждый из которых находится в одном из возможного конечного числа состояний. В каждый (дискретный) момент времени можно попробовать реализовать любой из проектов, что приводит к случайному вознаграждению; проект, который был опробован, претерпевает (марковский) переход состояния, в то время как другие проекты остаются замороженными и не меняют состояния. Цель лица, принимающего решение, заключается в определении оптимального способа опробования проектов, позволяющего максимизировать совокупное дисконтированное вознаграждение. Конечно, эту задачу можно решить как большую стохастическую динамическую программу, но такой подход не раскрывает какой-либо структуры и, кроме того, непрактичен с точки зрения вычислений, за исключением очень небольших задач. (Кроме того, если пространство состояний любого проекта является счетным или бесконечным, неясно, как можно точно решить полученную динамическую программу!) Замечательным результатом работы Гиттинса и Джонса [ ] является оптимальность индексных политик: каждому состоянию каждого проекта можно сопоставить индекс, так что в любой момент времени оптимальной является попытка реализации проекта с наибольшим индексом. Первоначальное доказательство Гиттинса и Джонса [ ] впоследствии было упрощено многими авторами; кроме того, появилось несколько альтернативных доказательств, основанных на различных методах, что привело к гораздо лучшему пониманию класса задач, для которых индексные политики являются оптимальными [2, 4, 6, 10, 17]

Хотя индексные политики просты с точки зрения реализации и анализа, они часто не являются оптимальными для многих задач. Поэтому естественно исследовать разрыв между оптимальной индексной политикой (или естественной эвристикой) и оптимальной политикой. Например, правило WSEPT является естественной эвристикой для задачи планирования заданий на идентичных параллельных машинах с целью минимизации ожидаемой суммы взвешенных времен завершения. Однако правило WSEPT не обязательно является оптимальным. Вайс [16] показал, что при умеренных и разумных допущениях ожидаемое количество случаев, когда правило WSEPT отличается от оптимального решения, ограничено сверху постоянной величиной, не зависящей от количества заданий. Таким образом, правило WSEPT является асимптотически оптимальным. В качестве другого примера аналогичного результата Уиттл [18] обобщил модель многорукого бандита, чтобы учесть переходы состояний в проектах, которые не были активированы, что привело к появлению модели «беспокойного бандита». Для этой модели Уиттл [18] предложил индексную политику, асимптотическая оптимальность которой была установлена Вебером и Вайсом [15].

Ряд стохастических моделей планирования допускают поступление заданий с течением времени в соответствии со стохастическим процессом. Обычно в этой формулировке используется модель многоклассовой сети массового обслуживания. Многоклассовые сети массового обслуживания служат полезными моделями для задач, в которых несколько типов деятельности конкурируют за ограниченное количество общих ресурсов. Они обобщают детерминированные задачи планирования набора заданий двумя способами: задания поступают с течением времени, и каждое задание на каждом этапе имеет случайное время обработки. Задача оптимального управления в многоклассовой сети массового обслуживания заключается в поиске оптимального распределения доступных ресурсов между типами деятельности в течение времени. Неудивительно, что индексные политики являются оптимальными только для ограниченных версий этой общей модели. Важным примером является планирование многоклассовой односерверной системы с обратной связью: существует N типов заданий, задания типа i поступают в соответствии с пуассоновским процессом с частотой A,, требуют обслуживания в соответствии с распределением времени обслуживания F,(-) со средним временем обработки si и влекут за собой затраты на хранение в размере ci в единицу времени. Задание типа i после обработки становится заданием типа j с вероятностью pij или выходит из системы с вероятностью 1 - Pj pij. Цель состоит в том, чтобы найти политику планирования, которая минимизирует ожидаемую сумму затрат на хранение в стационарном состоянии. Климов [ ] доказал оптимальность индексных политик для этой модели, а также для цели, в которой необходимо минимизировать общие дисконтированные затраты на хранение. Хотя оптимальность не выполняется при наличии нескольких параллельных машин, Глэйзбрук и Нино-Мора [7] показали, что это правило является асимптотически оптимальным. Для более общих моделей преобладающим подходом является использование аппроксимаций, таких как жидкостная аппроксимация [1] или диффузионное приближение диффузии [8].