Стохастическое планирование - Stochastic scheduling

Стохастическое планирование заботы планирование проблемы, связанные со случайными атрибутами, такими как случайное время обработки, случайные сроки выполнения, случайные веса и стохастические поломки машины. Основные приложения возникают в производственных системах, компьютерных системах, системах связи, логистике и транспорте, машинном обучении и т. Д.

Введение

Целью задач стохастического планирования могут быть обычные задачи, такие как минимизация общего времени потока, сковорода, или общая стоимость опозданий из-за несоблюдения сроков; или могут быть нерегулярные цели, такие как минимизация затрат на досрочное и несвоевременное завершение работ, или общие затраты на планирование задач при вероятном наступлении катастрофического события, такого как сильный тайфун.^[1]

На производительность таких систем, оцениваемую с помощью регулярного или нерегулярного измерения производительности, может значительно повлиять политика планирования, принятая для определения приоритетов доступа заданий к ресурсам с течением времени. Целью стохастического планирования является определение политик планирования, которые могут оптимизировать цель.

Проблемы стохастического планирования можно разделить на три основных типа: проблемы, касающиеся планирования пакета стохастических заданий, многорукий бандит проблемы и проблемы, связанные с планированием систем массового обслуживания^[2]. Эти три типа обычно предполагают наличие полной информации в том смысле, что распределения вероятностей задействованных случайных величин известны заранее. Когда такие распределения не определены полностью и существует несколько конкурирующих распределений для моделирования интересующих случайных величин, проблема называется неполной информацией. В Байесовский метод был применен для обработки задач стохастического планирования с неполной информацией.

Планирование пакета стохастических заданий

В этом классе моделей фиксированная партия ${\displaystyle n}$ задания со случайным временем обработки, распределение которых известно, должны выполняться набором ${\displaystyle m}$ машины для оптимизации заданной производительности.

Самая простая модель в этом классе - это задача упорядочивания набора ${\displaystyle n}$ работы на одной машине, чтобы минимизировать ожидаемое взвешенное время потока. Время обработки задания - это независимые случайные величины с общим распределением ${\displaystyle G_{i}(\cdot )}$ со средним ${\displaystyle p_{i}}$ для работы ${\displaystyle i}$. Допустимые политики должны быть непредвиденными (решения по планированию основаны на истории системы до настоящего времени включительно) и неупреждающими (обработка задания должна продолжаться непрерывно до завершения после запуска).

Позволять ${\displaystyle w_{i}\geq 0}$ обозначают норму затрат, понесенных за единицу времени в системе для работы ${\displaystyle i}$, и разреши ${\displaystyle {\tilde {C}}_{i}}$ обозначают время его случайного завершения. Позволять ${\displaystyle \Pi }$ обозначим класс всех допустимых политик, и пусть ${\displaystyle E_{\pi }[\cdot ]}$ обозначают ожидания в соответствии с политикой ${\displaystyle \pi \in \Pi }$. Проблема может быть сформулирована как

$${\displaystyle \min _{\pi \in \Pi }w_{1}E_{\pi }[{\tilde {C}}_{1}]+\cdots +w_{n}E_{\pi }[{\tilde {C}}_{n}].}$$

Оптимальное решение в частном детерминированном случае дается правилом Смита кратчайшего взвешенного времени обработки:^[3] упорядочить задания в порядке невозрастания индекса приоритета ${\displaystyle w_{i}p_{i}}$. Естественное расширение правила Смита также оптимально для приведенной выше стохастической модели.^[4]

В общем, правило, которое назначает более высокий приоритет заданиям с более коротким ожидаемым временем обработки, оптимально для целевого времени потока при следующих предположениях: когда все распределения времени обработки задания являются экспоненциальными;^[5] когда все задания имеют общее общее распределение времени обработки с неубывающей функцией степени опасности;^[6] и когда распределение времени обработки заданий является стохастическим.^[7]

Проблемы с многоруким бандитом

Многорукий бандит модели образуют особый тип оптимального распределения ресурсов (обычно работающий с распределением времени), в котором количество машин или процессоров должно быть выделено для обслуживания набора конкурирующих проектов (называемых «руками»). В типичной структуре система состоит из одной машины и набора стохастически независимых проектов, которые будут вносить случайные вознаграждения непрерывно или в определенные дискретные моменты времени, когда они обслуживаются. Цель состоит в том, чтобы максимизировать ожидаемое общее дисконтированное вознаграждение по всем динамически изменяемым политикам.^[1]

Первая версия многобандитных задач была сформулирована Роббинсом (1952) в области последовательных планов.^[8] С тех пор за два десятилетия не было значительного прогресса, пока Гиттинс и его сотрудники не добились знаменитых исследовательских достижений в Gittins (1979),^[9] Гиттинс и Джонс (1974),^[10] Гиттинс и Глейзбрук (1977),^[11] и Уиттл (1980)^[12] при марковских и полумарковских настройках. В этой ранней модели каждое плечо моделируется марковским или полумарковским процессом, в котором временные точки перехода между состояниями являются эпохами принятия решений. Машина может в каждую эпоху выбрать руку для обслуживания с вознаграждением, представленным как функция текущего состояния обрабатываемой руки, и решение характеризуется индексами распределения, присвоенными каждому состоянию, которое зависит только от состояний рук. Поэтому эти индексы известны как индексы Гиттинса, а оптимальные политики обычно называются Индекс Гиттинса политики, благодаря его авторитетному вкладу.

Вскоре после основополагающей статьи Гиттинса расширение проблемы ветвящегося бандита для моделирования случайных прибытий (также известное как проблема открытого бандита или бандита с захватом руки) было исследовано Уиттлом (1981).^[13] Другие расширения включают модели неугомонного бандита, сформулированные Уиттлом (1988),^[14] в которой каждая рука беспокойно развивается в соответствии с двумя различными механизмами (режим ожидания и режим занятости), а модели с затратами / задержками переключения, предложенные Van Oyen et al. (1992),^[15] которые показали, что никакая индексная политика не является оптимальной, когда переключение между вооружениями влечет за собой расходы / задержки.

Планирование систем массового обслуживания

Модели этого класса связаны с проблемами проектирования оптимальных дисциплин обслуживания в системах массового обслуживания, где задания, которые должны быть выполнены, поступают в случайные эпохи с течением времени, вместо того, чтобы быть доступными в начале. Основным классом моделей в этом контексте являются мультиклассовые сети массового обслуживания (MQN), широко применяемые в качестве универсальных моделей компьютерных коммуникаций и производственных систем.

Простейшие типы MQN включают в себя планирование нескольких классов заданий на одном сервере. Подобно двум категориям моделей, обсуждавшимся ранее, простые правила индекса приоритета оказались оптимальными для множества таких моделей.

Более общие модели MQN включают такие функции, как время переключения для смены службы с одного класса работы на другой (Леви и Сиди, 1990),^[16] или несколько станций обработки, которые обеспечивают обслуживание соответствующих неперекрывающихся подмножеств классов заданий. Из-за сложности таких моделей исследователи стремились разработать относительно простые эвристические политики, обеспечивающие производительность, близкую к оптимальной.

Стохастическое планирование с неполной информацией

Большинство исследований стохастических моделей планирования в значительной степени основывались на предположении о полной информации в том смысле, что распределения вероятностей задействованных случайных величин, таких как время обработки и время работы / простоя машины, полностью определены априори. .

Однако бывают обстоятельства, при которых информация доступна лишь частично. Примеры планирования с неполной информацией можно найти в разделе «Очистка окружающей среды»,^[17] управление проектом,^[18] разведка нефти,^[19] планирование датчиков в мобильных роботах,^[20] и моделирование времени цикла,^[21] среди многих других.

В результате неполной информации может существовать несколько конкурирующих распределений для моделирования интересующих случайных величин. Эффективный подход разработан Cai et al. (2009),^[22] для решения этой проблемы на основе обновления байесовской информации. Он идентифицирует каждое конкурирующее распределение по реализации случайной величины, например ${\displaystyle \Theta }$. Первоначально, ${\displaystyle \Theta }$ имеет предварительное распределение, основанное на исторической информации или предположениях (что может быть неинформативным, если историческая информация недоступна). Информация о ${\displaystyle \Theta }$ может быть обновлен после наблюдения реализации случайных величин. Ключевой проблемой при принятии решений является то, как использовать обновленную информацию для уточнения и улучшения решений. Когда политика планирования статична в том смысле, что она не меняется с течением времени, определяются оптимальные последовательности, чтобы минимизировать ожидаемое дисконтированное вознаграждение и стохастически минимизировать количество запоздалых заданий при обычном экспоненциальном сроке выполнения.^[22] Когда политика планирования является динамической в ​​том смысле, что она может вносить корректировки в процессе на основе актуальной информации, разрабатывается апостериорный индекс Гиттинса, чтобы найти оптимальную политику, которая минимизирует ожидаемое дисконтированное вознаграждение в классе динамических политик.^[22]

использованная литература

1. Cai, X.Q .; Wu, X.Y .; Чжоу, X. (2014). Оптимальное стохастическое планирование. Springer США. С. 49, с.95. ISBN  978-1-4899-7405-1.
2. Нино-Мора, Дж. (2009). «Стохастическое планирование». In Floudas, C .; Pardalos, P. (ред.). Энциклопедия оптимизации. США: Springer. С. 3818–3824. ISBN  978-0-387-74758-3.
3. Смит, Уэйн Э. (1956). «Различные оптимизаторы для одноступенчатого производства». Ежеквартально по военно-морской логистике. 3: 59–66. Дои:10.1002 / nav.3800030106.
4. Роткопф, Майкл (1966). «Планирование с произвольным временем обслуживания». Наука управления. 12 (9): 707–713. Дои:10.1287 / mnsc.12.9.707.
5. Вайс, Гидеон; Пинедо, Майкл (1980). «Планирование задач с экспоненциальным временем обслуживания на неидентичных процессорах для минимизации различных функций затрат». Журнал прикладной теории вероятностей. 17 (1): 187–202. Дои:10.2307/3212936.
6. Вебер, Ричард Р. (1982). «Планирование заданий с требованиями к стохастической обработке на параллельных машинах для минимизации времени изготовления или рабочего времени». Журнал прикладной теории вероятностей. 19 (1): 167–182. Дои:10.2307/3213926.
7. Вебер, Ричард; Varaiya, P .; Вальранд, Дж. (1986). «Планирование заданий со стохастически упорядоченным временем обработки на параллельных машинах для минимизации ожидаемого времени обработки». Журнал прикладной теории вероятностей. 23 (3): 841–847. Дои:10.2307/3214023.
8. Роббинс, Х. (1952). «Некоторые аспекты последовательного планирования экспериментов». Бюллетень Американского математического общества. 58 (5): 527–535. Дои:10.1090 / s0002-9904-1952-09620-8.
9. Гиттинс, Дж. К. (1979). «Бандитские процессы и индексы динамического размещения (с обсуждением)». Журнал Королевского статистического общества, серия B. 41: 148–164. Дои:10.1111 / j.2517-6161.1979.tb01068.x.
10. Gittins, J.C .; Джонс, Д. "Индекс динамического размещения для последовательного размещения экспериментов". В Gani, J .; и другие. (ред.). Прогресс в статистике. Амстердам: Северная Голландия.
11. Gittins, J.C .; Глейзбрук, К. (1977). «О байесовских моделях в стохастическом планировании». Журнал прикладной теории вероятностей. 14: 556–565. Дои:10.2307/3213458.
12. Уиттл, П. (1980). «Многорукие бандиты и индекс Гиттинса». Журнал Королевского статистического общества, серия B. 42 (2): 143–149. Дои:10.1111 / j.2517-6161.1980.tb01111.x.
13. Уиттл, П. (1981). «Оружейные бандиты». Анналы вероятности. 9 (2): 284–292. Дои:10.1214 / aop / 1176994469.
14. Уиттл, П. (1988). «Беспокойные бандиты: распределение активности в меняющемся мире». Журнал прикладной теории вероятностей. 25: 287–298. Дои:10.2307/3214163.
15. van Oyen, M.P .; Pandelis, D.G .; Тенекетзис, Д. (1992). «Оптимальность индексных политик для стохастического планирования со штрафом за переключение». Журнал прикладной теории вероятностей. 29 (4): 957–966. Дои:10.2307/3214727.
16. Levy, H .; Сиди, М. (1990). «Системы опроса: приложения, моделирование и оптимизация». Транзакции IEEE по коммуникациям. 38 (10): 1750–1760. Дои:10.1109/26.61446.
17. Lee, S.I .; Китанидис, П. (1991). «Оптимальная оценка и планирование восстановления водоносного горизонта с неполной информацией». Исследование водных ресурсов. 27: 2203–2217. Дои:10.1029 / 91wr01307.
18. Gardoni, P .; Reinschmidt, K. F .; Кумар, Р. (2007). «Вероятностная основа для байесовского адаптивного прогнозирования хода проекта». Компьютерное проектирование строительства и инфраструктуры. 22: 182–196. Дои:10.1111 / j.1467-8667.2007.00478.x.
19. Glazebrook, K.D .; Мальчики, Р.Дж. (1995). «Класс байесовских моделей для оптимального исследования». Журнал Королевского статистического общества, серия B. 57: 705–720. Дои:10.1111 / j.2517-6161.1995.tb02057.x.
20. Gage, A .; Мерфи, Р.Р. (2004). «Сенсорное планирование в мобильных роботах с использованием неполной информации через Min-Conflict with Happiness». Транзакции IEEE по системам, человеку и кибернетике - Часть B: Кибернетика. 34: 454–467. Дои:10.1109 / tsmcb.2003.817048.
21. Chen, C.Y.I .; Ding, Q .; Lin, B.M.T. (2004). «Краткий обзор планирования с временем обработки, зависящим от времени». Европейский журнал операционных исследований. 152: 1–13. Дои:10.1016 / s0377-2217 (02) 00909-8.
22. Cai, X.Q .; Wu, X.Y .; Чжоу, X. (2009). «Стохастическое календарное планирование с учетом повторных поломок с неполной информацией». Исследование операций. 57 (5): 1236–1249. Дои:10.1287 / opre.1080.0660.