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

Планирование связано с распределением ограниченных ресурсов (таких как машины или серверы) между конкурирующими объектами (такими как задания или клиенты) в течение определенного времени. Отличительной чертой задачи стохастического планирования является то, что некоторые релевантные данные моделируются как случайные переменные, распределения которых известны, тогда как фактические реализации – нет. Стохастические задачи планирования унаследовали несколько характеристик своих детерминированных аналогов. В частности, существует практически неограниченное количество типов задач в зависимости от машинной среды (одна машина, параллельные машины, мастерские, цеха поточного производства), характеристик обработки (с вытеснением или без вытеснения; пакетное планирование или поступление заданий с течением времени; сроки выполнения; крайние сроки) и целей (длительность выполнения, взвешенное время завершения, взвешенное время потока, взвешенное запаздывание). Кроме того, стохастические модели планирования имеют некоторые новые интересные особенности (или сложности):

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

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

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