Задача

Вернемся к ситуации с одним ресурсом и набором из n заявок на его использова- ние в течение интервала времени. Будем считать, что ресурс доступен, начиная с времени 5. Однако в отличие от предыдущей задачи заявки становятся более гибкими — вместо начального и конечного времени заявка содержит предельное время d.
и непрерывный интервал времени длиной t , а начинаться она может в любое время до своего предельного времени. Каждой принятой заявке должен быть выделен интервал времени длиной t., и разным заявкам должны назначаться неперекрывающиеся интервалы.

Существуют разные объективные функции, к оптимизации которых можно было бы стремиться в такой ситуации, и некоторые из них по вычислительной сложности существенно превосходят другие. Здесь мы рассмотрим очень есте- ственную цель, которая может оптимизироваться жадным алгоритмом. Допустим, мы намерены удовлетворить каждую заявку, но некоторые заявки могут быть отложены на более позднее время. Таким образом, начиная с общего начального времени s, каждой заявке i выделяется интервал времени t.; обозначим этот ин- тервал [s(i), f (i)], гдеf(i) = s(i) + t. Однако в отличие от предыдущей задачи этот алгоритм должен определить начальное время (а следовательно, и конечное время) для каждого интервала.

Заявка i будет называться задержанной, если она не успевает завершиться к предельному времени, то есть если f (i) > d.. Задержка такой заявки i определяется по формуле l. = f (i) - d. Будем считать, что если заявка не является просроченной, то l = 0. Целью новой задачи оптимизации будет планирование всех заявок с не- перекрывающимися интервалами, обеспечивающее минимизацию максимальной задержки L = max. lЭта задача естественным образом встречается при планиро- вании вычислительных заданий, которые должны выполняться на одном компью- тере, поэтому мы будем называть заявки «заданиями».

На рис. 4.5 изображен пример с тремя заданиями: первое имеет длину tl = 1 c предельным временем d1 = 2, у второго t2 = 2 и d2 = 4, и у третьего t3 = 3 и d3 = 6. Нетрудно убедиться в том, что при планировании заданий в порядке 1, 2, 3 макси- мальная задержка равна 0.


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

Еще по теме Задача:

  1. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  2. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  3. Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
  4. ЗАДАЧА
  5. ЗАДАЧА: РЕШЕНИЕ
  6. Основные задачи.
  7. в) Задачи
  8. в) Задачи
  9. ПСИХОАНАЛИЗ: ЗАДАЧА
  10. ЗАДАЧА ДВИГАТЕЛЬНАЯ
  11. Основные задачи
  12. Правило решаемой психологической задачи.
  13. Задачи и упражнения
  14. Терапевтическая задача