Интервальное планирование

Рассмотрим очень простую задачу планирования. Имеется некий ресурс — аудито- рия, суперкомпьютер, электронный микроскоп и т. д.; множество людей обращает- ся с заявками на использование ресурса в течение периода времени.
Заявка имеет вид: «Можно ли зарезервировать ресурс, начиная с времени 5 и до времени f?» Будем считать, что ресурс в любой момент времени может использоваться только одним человеком. Планировщик выбирает подмножество заявок, отклоняя все остальные, чтобы принятые заявки не перекрывались по времени. Целью плани- рования является максимизация количества принятых заявок.

Более формальная постановка: имеется n заявок с номерами 1, ..., n; в каждой заявке i указывается начальное время s. и конечное времяf. Естественно, s. < f для всех i . Две заявки i и j называются совместимыми, если запрашиваемые интервалы не перекрываются, то есть заявка i приходится либо на более ранний интервал времени, чем у j (f < s.), либо на более поздний интервал времени, чем у j (f < s). В более общем смысле подмножество A заявок называется совместимым, если все пары запросов i, j A, i Φ j являются совместимыми. Целью алгоритма является выбор совместимого подмножества заявок максимально возможного размера.

Пример задачи интервального планирования представлен на рис. 1.4. На диа- грамме представлено одно совместимое множество размера 4, и оно является самым большим совместимым множеством.

Вскоре мы увидим, что эта задача может быть решена с применением очень естественного алгоритма, который упорядочивает множество заявок по некоторой эвристике, а затем «жадно» обрабатывает их за один проход, выбирая совмести-

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

Рис. 1.4. Пример задачи интервального планирования


<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Интервальное планирование:

  1. 4.2.3. Интервальная шкала
  2. Интервальная шкала
  3. Планирование телепередач
  4. Планирование, а не планы
  5. 11. КРИМИНАЛИСТИЧЕСКИЕ ВЕРСИИ И ПЛАНИРОВАНИЕ РАССЛЕДОВАНИЯ
  6. § 2. ПЛАНИРОВАНИЕ И СОДЕРЖАНИЕ НАБЛЮДЕНИЯ
  7. 10.2. Планирование и организация следственных действий
  8. 5.4. Планирование упражнений
  9. Искусство планирования спонтанного
  10. 5.9. Планирование социальных контактов
  11. 5.2.9. Планирование сроков достижения уже определённой цели
  12. Статья 437. Планирование, подготовка, развязывание и ведение агрессивной войны
  13. 11.3. Понятие и основные принципы планирования расследования в зависимости от исходной информации (следственной ситуации)
  14. Вопросы для самопроверки
  15. Программирование телевизионного вещания