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

Ряд стохастических моделей планирования допускают поступление заданий с течением времени в соответствии со стохастическим процессом. Обычно в этой формулировке используется модель многоклассовой сети массового обслуживания. Многоклассовые сети массового обслуживания служат полезными моделями для задач, в которых несколько типов ''деятельности'' конкурируют за ограниченное количество общих ''ресурсов''. Они обобщают детерминированные задачи планирования набора заданий двумя способами: задания поступают ''с течением времени'', и каждое задание на каждом этапе имеет ''случайное'' время обработки. Задача оптимального управления в многоклассовой сети массового обслуживания заключается в поиске оптимального распределения доступных ресурсов между типами деятельности в течение времени. Неудивительно, что индексные политики являются оптимальными только для ограниченных версий этой общей модели. Важным примером является планирование многоклассовой односерверной системы с обратной связью: существует <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].