Стохастическое планирование
Ключевые слова и синонимы
Определение последовательности (Sequencing); формирование очереди (Queueing)
Постановка задачи
Планирование связано с распределением ограниченных ресурсов (таких как машины или серверы) между конкурирующими объектами (такими как задания или клиенты) в течение определенного времени. Отличительной чертой задачи стохастического планирования является то, что некоторые релевантные данные моделируются как случайные переменные, распределения которых известны, тогда как фактические реализации – нет. Стохастические задачи планирования унаследовали несколько характеристик своих детерминированных аналогов. В частности, существует практически неограниченное количество типов задач в зависимости от машинной среды (одна машина, параллельные машины, мастерские, цеха поточного производства), характеристик обработки (с вытеснением или без вытеснения; пакетное планирование или поступление заданий с течением времени; сроки выполнения; крайние сроки) и целей (длительность выполнения, взвешенное время завершения, взвешенное время потока, взвешенное запаздывание). Кроме того, стохастические модели планирования имеют некоторые новые интересные особенности (или сложности):
• Планировщик может делать выводы об оставшемся времени обработки задания, используя информацию о прошедшем времени обработки; вопрос о том, может ли планировщик использовать эту информацию, решается разработчиком модели.
• Многие алгоритмы планирования принимают решения, сравнивая время обработки заданий. Если задания имеют детерминированное время обработки, это не представляет никаких проблем, так как существует только один способ их сравнения. Если же время обработки является случайной величиной, сравнение этих величин становится сложной задачей. Существует много способов сравнения пар случайных переменных, и некоторые из них являются лишь отношениями частичного порядка. Таким образом, любой алгоритм, который работает путем сравнения времени обработки, теперь должен указывать конкретный порядок, используемый для сравнения случайных переменных (и для определения того, что делать, если две случайные переменные несопоставимы в рамках указанного порядка).
Эти соображения приводят к понятию политики планирования, которая определяет, как следует распределять ограниченные ресурсы между конкурирующими видами деятельности в зависимости от состояния системы в любой момент времени. Состояние системы включает в себя такую информацию, как ранее выполненные задания, время, прошедшее с момента начала выполнения текущих заданий, реализации случайных дат запуска и сроков выполнения (если таковые имеются), а также любую другую информацию, которую можно вывести на основе наблюдаемой до настоящего момента истории. Политика, которая позволяет использовать всю эту информацию, называется динамической, тогда как политика, не позволяющая использовать какую-либо информацию о состоянии, является статической.
При любой политике целевая функция для стохастической модели планирования, работающей в соответствии с этой политикой, обычно является случайной величиной. Таким образом, сравнение двух политик влечет за собой сравнение связанных с ними случайных величин, поэтому необходимо уточнять, в каком смысле эти случайные величины сравниваются. Обычным подходом является поиск решения, которое оптимизирует ожидаемое значение целевой функции (которое имеет преимущество, так как является полным порядком); реже используются другие упорядочения, такие как стохастическое упорядочение или упорядочение по отношению правдоподобия.
Основные результаты
Рассмотрим одну машину, которая обрабатывает 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].
Применение
Стохастические модели планирования применимы во многих ситуациях, в первую очередь в компьютерных и коммуникационных сетях, колл-центрах, логистике и транспортировке, а также в производственных системах [4, 10].
См. также
Литература
1. Avram, F., Bertsimas, D., Ricard, M.: Fluid models of sequencing problems in open queueing networks: an optimal control approach. In: Kelly, F.P., Williams, R.J. (eds.) Stochastic Networks. Proceedings of the International Mathematics Association, vol. 71, pp. 199-234. Springer, New York (1995)
2. Bertsimas, D., Nino-Mora, J.: Conservation laws, extended polymatroids and multiarmed bandit problems: polyhedral approaches to indexable systems. Math. Oper. Res. 21(2), 257-306(1996)
3. Bruno, J., Downey, P., Frederickson, G.N.: Sequencing tasks with exponential service times to minimize the expected flow time or makespan. J. ACM 28,100-113(1981)
4. Dacre, M., Glazebrook, K., Nino-Mora, J.: The achievable region approach to the optimal control of stochastic systems. J. R. Stat. Soc. Series B 61 (4), 747-791 (1999)
5. Gittins, J.C.,Jones, D.M.: A dynamic allocation index for the sequential design experiments. In: Gani, J., Sarkadu, K., Vince, I. (eds.) Progress in Statistics. European Meeting of Statisticians I, pp. 241-266. North Holland, Amsterdam (1974)
6. Gittins, J.C.: Bandit processes and dynamic allocation indices. J. R. Stat. Soc. Series B, 41 (2), 148-177 (1979)
7. Glazebrook, K., Nino-Mora, J.: Parallel scheduling of multiclass M/M/m queues: approximate and heavy-traffic optimization of achievable performance. Oper. Res. 49(4), 609-623 (2001)
8. Harrison, J.M.: Brownian models of queueing networks with heterogenous customer populations. In: Fleming, W., Lions, P.L. (eds.) Stochastic Differential Systems, Stochastic Control Theory and Applications. Proceedings of the International Mathematics Association, pp. 147-186. Springer, New York (1988)
9. Klimov, G.P.: Time-sharing service systems I. Theory Probab. Appl. 19, 532-551 (1974)
10. Pinedo, M.: Scheduling: Theory, Algorithms and Systems, 2nd ed. Prentice Hall, Englewood Cliffs (2002)
11. Rothkopf, M.: Scheduling with Random Service Times. Manag. Sci. 12,707-713 (1966)
12. Sevcik, K.C.: Scheduling for minimum total loss using service time distributions. J. ACM 21,66-75 (1974)
13. Smith, W.E.: Various optimizers for single-stage production. Nav. Res. Logist. Quart. 3, 59-66 (1956)
14. Weber, R.R., Varaiya, P., Walrand, J.: Scheduling jobs with stochastically ordered processing times on parallel machines to minimize expected flow time. J. Appl. Probab. 23, 841-847 (1986)
15. Weber, R.R., Weiss, G.: On an index policy for restless bandits. J. Appl. Probab. 27,637-648 (1990)
16. Weiss, G.: Turnpike optimality of Smith's rule in parallel machine stochastic scheduling. Math. Oper. Res. 17, 255-270 (1992)
17. Whittle, P.: Multiarmed bandit and the Gittins index. J. R. Stat. Soc. Series B 42,143-149 (1980)
18. Whittle, P.: Restless bandits: Activity allocation in a changing world. In: Gani, J. (ed.) A Celebration of Applied Probability. J Appl. Probab. 25A, 287-298 (1988)