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

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

Вступление

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рекомендации