Аннотация:
Рассматривается задача составления графика выполнения комплекса основных работ при условии, что в некоторые неопределенные моменты времени поступают заявки на выполнение дополнительных, более приоритетных работ. Если при выполнении основного задания поступает заявка на дополнительную работу, то выполнение этого задания завершается и должно быть начато заново в некоторый момент времени после окончания выполнения дополнительной работы. Все работы (основные и дополнительные) выполняются без прерываний. Предполагается, что при выполнении основного задания поступление более чем одной заявки на выполнение дополнительной работы маловероятно; такие случаи не рассматриваются. Кроме того, заявка на выполнение дополнительной работы может прийти только после завершения обслуживания предыдущей дополнительной заявки. Исследуются две формальные постановки задачи. В первой показателем эффективности является момент завершения комплекса основных работ, и задача заключается в его минимизации. Во второй постановке минимизируется вероятность коллизии, т.е. ситуации, когда заявка на выполнение дополнительной работы поступает в момент выполнения основного задания. Решение указанных задач основано на сведении их к бесконечным антагонистическим играм и дискретной аппроксимации последних конечными играми. Рассмотрены модельные примеры. Исследована также постановка с нефиксированными длительностями выполнения основных работ, линейно зависящими от объема выделенных им дополнительных ресурсов. В этом случае поиск допустимого расписания сводится к решению задачи линейного программирования.
Ключевые слова:
системы реального времени, планирование работ, коллизия, антагонистическая игра, невозобновляемые ресурсы, смешанная стратегия, оптимальная стратегия.
УДК:519.86
Поступила в редакцию: 14.04.2025 Исправленный вариант: 30.06.2025 Принята в печать: 16.07.2025
Полный текст:
PDF файл (1489 kB)