Временное планирование и составление расписаний

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

Definition

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

Scope

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

Core questions

• Как представляются длительные действия и условия их начала и окончания?
• Как моделируются временные ограничения между событиями и проверяется их согласованность?
• Как распределяются ограниченные ресурсы между параллельными действиями?
• Как объединяются или разделяются планирование (принятие решения о том, какие действия) и составление расписания (принятие решения о том, когда)?

Key concepts

• длительные действия
• параллелизм и перекрытие
• временные ограничения
• простая временная задача
• интервальная алгебра Аллена
• ресурсные ограничения
• составление расписания
• сроки и время выполнения

Key theories

Сети временных ограничений

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

Интервальная алгебра для качественного времени

Интервальная алгебра Аллена описывает возможные качественные отношения между временными интервалами (до, во время, перекрывается и т. д.) и поддерживает рассуждения о временных знаниях, когда точное время неизвестно.

Интеграция планирования с составлением расписания

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

Clinical relevance

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

History

Качественное временное рассуждение было формализовано интервальной алгеброй Аллена (1983), а количественные сети временных ограничений — Дехтером, Мейри и Перлом (1991). Эти основы, наряду с моделями длительных действий, добавленными в PDDL в начале 2000-х годов, позволили использовать временные планировщики в таких приложениях, как автономное управление космическими аппаратами.

Key figures

• James F. Allen
• Rina Dechter
• Judea Pearl
• Itay Meiri
• Nicola Muscettola

Seminal works

• dechter1991
• allen1983

Frequently asked questions

В чем разница между планированием и составлением расписания?

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

Что такое простая временная задача?

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