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

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

Введение [ править ]

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

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

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

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

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

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

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

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

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

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

Проблемы с многоруким бандитом [ править ]

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

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

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

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

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

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

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

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

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

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

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

Ссылки [ править ]

↑ Перейти обратно: Перейти обратно: ^а ^б Цай, XQ; Ву, XY; Чжоу, X. (2014). Оптимальное стохастическое планирование . Спрингер США. стр. 49, стр. 95. ISBN 978-1-4899-7405-1 .
^ Нино-Мора, Дж. (2009). «Стохастическое планирование». Во Флудасе, К.; Пардалос, П. (ред.). Энциклопедия оптимизации . США: Спрингер. стр. 3818–3824. ISBN 978-0-387-74758-3 .
^ Смит, Уэйн Э. (1956). «Различные оптимизаторы для одностадийного производства». Ежеквартальный журнал военно-морских исследований по логистике . 3 (1–2): 59–66. дои : 10.1002/nav.3800030106 .
^ Роткопф, Майкл (1966). «Планирование со случайным временем обслуживания». Наука управления . 12 (9): 707–713. дои : 10.1287/mnsc.12.9.707 .
^ Вайс, Гидеон; Пинедо, Майкл (1980). «Планирование задач с экспоненциальным временем обслуживания на неидентичных процессорах для минимизации различных функций стоимости». Журнал прикладной вероятности . 17 (1): 187–202. дои : 10.2307/3212936 . JSTOR 3212936 . S2CID 34396501 .
^ Вебер, Ричард Р. (1982). «Планирование заданий со стохастической обработкой на параллельных машинах для минимизации времени изготовления или рабочего времени». Журнал прикладной вероятности . 19 (1): 167–182. дои : 10.2307/3213926 . JSTOR 3213926 . S2CID 9363363 .
^ Вебер, Ричард; Варайя, П.; Уолранд, Дж. (1986). «Планирование заданий со стохастически упорядоченным временем обработки на параллельных машинах для минимизации ожидаемого времени выполнения». Журнал прикладной вероятности . 23 (3): 841–847. дои : 10.2307/3214023 . JSTOR 3214023 . S2CID 9253615 .
^ Роббинс, Х. (1952). «Некоторые аспекты последовательного планирования экспериментов» (PDF) . Бюллетень Американского математического общества . 58 (5): 527–535. дои : 10.1090/s0002-9904-1952-09620-8 .
^ Гиттинс, Дж. К. (1979). «Бандитские процессы и индексы динамического размещения (с обсуждением)». Журнал Королевского статистического общества, серия B. 41 : 148–164. дои : 10.1111/j.2517-6161.1979.tb01068.x . S2CID 17724147 .
^ Гиттинс, Дж. К.; Джонс, Д. «Индекс динамического размещения для последовательного распределения экспериментов». В Гани, Дж.; и др. (ред.). Прогресс в статистике . Амстердам: Северная Голландия.
^ Гиттинс, Дж. К.; Глейзбрук, К.Д. (1977). «О байесовских моделях стохастического планирования». Журнал прикладной вероятности . 14 (3): 556–565. дои : 10.2307/3213458 . JSTOR 3213458 . S2CID 123637036 .
^ Уиттл, П. (1980). «Многорукие бандиты и индекс Гиттинса». Журнал Королевского статистического общества, серия B. 42 (2): 143–149. дои : 10.1111/j.2517-6161.1980.tb01111.x .
^ Уиттл, П. (1981). «Оружейные бандиты» . Анналы вероятности . 9 (2): 284–292. дои : 10.1214/aop/1176994469 .
^ Уиттл, П. (1988). «Беспокойные бандиты: Распределение активности в меняющемся мире». Журнал прикладной вероятности . 25 : 287–298. дои : 10.2307/3214163 . JSTOR 3214163 . S2CID 202109695 .
^ ван Ойен, член парламента; Панделис, Д.Г.; Тенекетзис, Д. (1992). «Оптимальность индексной политики для стохастического планирования со штрафом за переключение». Журнал прикладной вероятности . 29 (4): 957–966. дои : 10.2307/3214727 . JSTOR 3214727 . S2CID 7809829 .
^ Леви, Х.; Сиди, М. (1990). «Опросные системы: приложения, моделирование и оптимизация». Транзакции IEEE по коммуникациям . 38 (10): 1750–1760. дои : 10.1109/26.61446 .
^ Ли, СИ; Китанидис, ПК (1991). «Оптимальная оценка и планирование восстановления водоносных горизонтов с неполной информацией». Исследования водных ресурсов . 27 (9): 2203–2217. Бибкод : 1991WRR....27.2203L . дои : 10.1029/91wr01307 .
^ Гардони, П.; Рейншмидт, К.Ф.; Кумар, Р. (2007). «Вероятностная основа для байесовского адаптивного прогнозирования хода проекта» . Компьютерное гражданское и инфраструктурное проектирование . 22 (3): 182–196. дои : 10.1111/j.1467-8667.2007.00478.x . S2CID 205572781 .
^ Глейзбрук, К.Д.; Мальчики, Р.Дж. (1995). «Класс байесовских моделей для оптимального исследования». Журнал Королевского статистического общества, серия B. 57 (4): 705–720. дои : 10.1111/j.2517-6161.1995.tb02057.x .
^ Гейдж, А.; Мерфи, Р.Р. (2004). «Планирование датчиков в мобильных роботах с использованием неполной информации через Min-Conflict with Happiness». Транзакции IEEE о системах, человеке и кибернетике. Часть B: Кибернетика . 34 (1): 454–467. дои : 10.1109/tsmcb.2003.817048 . ПМИД 15369086 . S2CID 8405346 .
^ Чен, CYI; Дин, К.; Лин, БМТ (2004). «Краткий обзор планирования с учетом времени обработки, зависящего от времени». Европейский журнал операционных исследований . 152 : 1–13. дои : 10.1016/s0377-2217(02)00909-8 .
↑ Перейти обратно: Перейти обратно: ^а ^б ^с Цай, XQ; Ву, XY; Чжоу, X. (2009). «Стохастическое планирование с учетом повторяющихся пробоев с неполной информацией». Исследование операций . 57 (5): 1236–1249. дои : 10.1287/опре.1080.0660 .

[Cai_et_al._2014-1] Перейти обратно: Перейти обратно: ^а ^б Цай, XQ; Ву, XY; Чжоу, X. (2014). Оптимальное стохастическое планирование . Спрингер США. стр. 49, стр. 95. ISBN 978-1-4899-7405-1 .

[2] Нино-Мора, Дж. (2009). «Стохастическое планирование». Во Флудасе, К.; Пардалос, П. (ред.). Энциклопедия оптимизации . США: Спрингер. стр. 3818–3824. ISBN 978-0-387-74758-3 .

[3] Смит, Уэйн Э. (1956). «Различные оптимизаторы для одностадийного производства». Ежеквартальный журнал военно-морских исследований по логистике . 3 (1–2): 59–66. дои : 10.1002/nav.3800030106 .

[Rothkopf1966-4] Роткопф, Майкл (1966). «Планирование со случайным временем обслуживания». Наука управления . 12 (9): 707–713. дои : 10.1287/mnsc.12.9.707 .

[5] Вайс, Гидеон; Пинедо, Майкл (1980). «Планирование задач с экспоненциальным временем обслуживания на неидентичных процессорах для минимизации различных функций стоимости». Журнал прикладной вероятности . 17 (1): 187–202. дои : 10.2307/3212936 . JSTOR 3212936 . S2CID 34396501 .

[6] Вебер, Ричард Р. (1982). «Планирование заданий со стохастической обработкой на параллельных машинах для минимизации времени изготовления или рабочего времени». Журнал прикладной вероятности . 19 (1): 167–182. дои : 10.2307/3213926 . JSTOR 3213926 . S2CID 9363363 .

[7] Вебер, Ричард; Варайя, П.; Уолранд, Дж. (1986). «Планирование заданий со стохастически упорядоченным временем обработки на параллельных машинах для минимизации ожидаемого времени выполнения». Журнал прикладной вероятности . 23 (3): 841–847. дои : 10.2307/3214023 . JSTOR 3214023 . S2CID 9253615 .

[8] Роббинс, Х. (1952). «Некоторые аспекты последовательного планирования экспериментов» (PDF) . Бюллетень Американского математического общества . 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 . S2CID 17724147 .

[10] Гиттинс, Дж. К.; Джонс, Д. «Индекс динамического размещения для последовательного распределения экспериментов». В Гани, Дж.; и др. (ред.). Прогресс в статистике . Амстердам: Северная Голландия.

[11] Гиттинс, Дж. К.; Глейзбрук, К.Д. (1977). «О байесовских моделях стохастического планирования». Журнал прикладной вероятности . 14 (3): 556–565. дои : 10.2307/3213458 . JSTOR 3213458 . S2CID 123637036 .

[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 . JSTOR 3214163 . S2CID 202109695 .

[15] ван Ойен, член парламента; Панделис, Д.Г.; Тенекетзис, Д. (1992). «Оптимальность индексной политики для стохастического планирования со штрафом за переключение». Журнал прикладной вероятности . 29 (4): 957–966. дои : 10.2307/3214727 . JSTOR 3214727 . S2CID 7809829 .

[16] Леви, Х.; Сиди, М. (1990). «Опросные системы: приложения, моделирование и оптимизация». Транзакции IEEE по коммуникациям . 38 (10): 1750–1760. дои : 10.1109/26.61446 .

[17] Ли, СИ; Китанидис, ПК (1991). «Оптимальная оценка и планирование восстановления водоносных горизонтов с неполной информацией». Исследования водных ресурсов . 27 (9): 2203–2217. Бибкод : 1991WRR....27.2203L . дои : 10.1029/91wr01307 .

[18] Гардони, П.; Рейншмидт, К.Ф.; Кумар, Р. (2007). «Вероятностная основа для байесовского адаптивного прогнозирования хода проекта» . Компьютерное гражданское и инфраструктурное проектирование . 22 (3): 182–196. дои : 10.1111/j.1467-8667.2007.00478.x . S2CID 205572781 .

[19] Глейзбрук, К.Д.; Мальчики, Р.Дж. (1995). «Класс байесовских моделей для оптимального исследования». Журнал Королевского статистического общества, серия B. 57 (4): 705–720. дои : 10.1111/j.2517-6161.1995.tb02057.x .

[20] Гейдж, А.; Мерфи, Р.Р. (2004). «Планирование датчиков в мобильных роботах с использованием неполной информации через Min-Conflict with Happiness». Транзакции IEEE о системах, человеке и кибернетике. Часть B: Кибернетика . 34 (1): 454–467. дои : 10.1109/tsmcb.2003.817048 . ПМИД 15369086 . S2CID 8405346 .

[21] Чен, CYI; Дин, К.; Лин, БМТ (2004). «Краткий обзор планирования с учетом времени обработки, зависящего от времени». Европейский журнал операционных исследований . 152 : 1–13. дои : 10.1016/s0377-2217(02)00909-8 .

[Cai_et_al._2009-22] Перейти обратно: Перейти обратно: ^а ^б ^с Цай, XQ; Ву, XY; Чжоу, X. (2009). «Стохастическое планирование с учетом повторяющихся пробоев с неполной информацией». Исследование операций . 57 (5): 1236–1249. дои : 10.1287/опре.1080.0660 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]