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

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

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

Ряд стохастических моделей планирования допускают поступление заданий с течением времени в соответствии со стохастическим процессом. Обычно в этой формулировке используется модель многоклассовой сети массового обслуживания. Многоклассовые сети массового обслуживания служат полезными моделями для задач, в которых несколько типов ''деятельности'' конкурируют за ограниченное количество общих ресурсов. Они обобщают детерминированные задачи планирования набора заданий двумя способами: задания поступают ''с течением времени'', и каждое задание на каждом этапе имеет ''случайное'' время обработки. Задача оптимального управления в многоклассовой сети массового обслуживания заключается в поиске оптимального распределения доступных ресурсов между типами деятельности в течение времени. Неудивительно, что индексные политики являются оптимальными только для ограниченных версий этой общей модели. Важным примером является планирование многоклассовой односерверной системы с обратной связью: существует <math>N</math> типов заданий, задания типа <math>i</math> поступают в соответствии с пуассоновским процессом с частотой <math>\lambda_i</math>, требуют обслуживания в соответствии с распределением времени обслуживания <math>F_i(\cdot)</math> со средним временем обработки <math>s_i</math> и влекут за собой затраты на хранение в размере <math>c_i</math> в единицу времени. Задание типа <math>i</math> после обработки становится заданием типа <math>j</math> с вероятностью <math>p_{ij}</math> или выходит из системы с вероятностью <math>1 - \sum_j p_{ij}</math>. Цель состоит в том, чтобы найти политику планирования, которая минимизирует ожидаемую сумму затрат на хранение в стационарном состоянии. Климов [9] доказал оптимальность индексных политик для этой модели, а также для цели, в которой необходимо минимизировать общие дисконтированные затраты на хранение. Хотя оптимальность не выполняется при наличии нескольких параллельных машин, Глэйзбрук и Нино-Мора [7] показали, что это правило является асимптотически оптимальным. Для более общих моделей преобладающим подходом является использование аппроксимаций, таких как жидкостная аппроксимация [1] или диффузионное приближение диффузии [8].