|
ключевым моментом в алгоритме генерации является поиск списка, из которого может быть произведен выбор оптимального плана. Очевидно, что алгоритм, используемый для генерации оптимального списка, является рекурсивной процедурой, которая начинается назначением списка индексов в порядке возрастания к задаче или задачам, которые выполняются последними вследствие ограничений предшествования в графе задач. Заметим, что множество последователей этих задач является пустым. Назначение производится «вверх по графу», т. е. в качестве кандидатов на присваивание индексов рассматриваются задачи, последователям которых уже был назначен индекс. Рассмотрение задач, таким образом, равнозначно разбиению их по признаку последнего предшествования, хотя задачи и не выполняются к моменту времени, который соответствует этому разбиению. Фактически изначально индексы могут присваиваться задачам в графе произвольно. Затем по алгоритму переназначаются индексы задач тем способом, который был описан выше. Задачи вносятся в список в порядке уменьшения индексов, начиная с последнего назначенного. Создается список. Оптимальный план формируется назначением готовых задач в этом списке свободным ресурсам. Данный алгоритм приведен на рисунке 2.1.8, где изображены граф задач с переназначенными индексами, результирующий список L* и оптимальный план. Оптимальные результаты для неприоритетных планов также были предложены Хью [12], что стало наиболее часто цитируемой ссылкой в работах по мультиресурсному планированию. Хью рассматривает две проблемы, связанные с задачами единичной длины: 1) определение минимума времени, необходимого для обработки графа задач при фиксированном числе ресурсов; 2) определение количества ресурсов, необходимых для обработки графа за заданное время. 53 |
оптимального плана, упорядочение задач в списке имеет первостепенное значение. Такими образом, ключевым моментом в алгоритме генерации является поиск списка, из; которого, может быть произведен выбор оптимального плана.. Очевидно, что алгоритм, используемый для. генерации оптимального списка, является рекурсивной процедурой, которая начинается назначением списка индексов в порядке возрастания к задаче или задачам, которые, выполняются последними вследствие ограничений предшествования в графе задач. Заметим, что множество последователей этих задач является пустым. Назначение производится «вверх по графу», т. е. в качестве кандидатов на присваивание индексов рассматриваются задачи,, последователям которых уже был назначен индекс. Рассмотрение задач, таким образом, равнозначно разбиению их по признаку; последнего предшествования,, хотя задачи7 и не выполняются к моменту времени, который соответствует этому разбиению. Фактически изначально индексы могут присваиваться задачам в графе произвольно. Затем по алгоритму переназначаются индексы задач тем способом, который был описан выше. Задачи вносятся в. список в порядке уменьшения индексов, начиная? с. последнего назначенного. Создается список. Оптимальный. план формируется назначением готовых задач в этом списке свободным; процессорам. Данный алгоритм: приведен на рис. 2.13, где изображены граф задач с переназначенными индексами, результирующий список L* и оптимальный план. Оптимальные результаты для неприоритетных планов также были предложены Хыо [6]что стало наиболее часто цитируемой ссылкой в. работах по мультипроцессорному планированию. Хью рассматривает две проблемы, связанные с задачами единичной длины: 1) определение минимума времени, необходимого -для, обработки графа задач при фиксированном числе процессоров; 59 |