Графовые модели планирования. Алгоритм математического программирования

Модель процесса планирования можно представить в виде графа G = ( r , v_r , z, v_z , x_rz , v_x ),где:

r º { r _j } ( j =1…n ) – вершины графа, отображающие ресурсы (ПВМ) системы;
v_r º { v_{r j} } ( j =1…n ) –веса ресурсов,отображающие максимальное число заданий, которое может выполняться на каждом ресурсе;
z º { z _i } ( i =1…m ) – вершины графа, отображающие задания, поступающие на обработку в систему;
v_z º { v_{z i} } ( i =1…m ) – веса заданий, отображающие приоритеты заданий и число ресурсов, необходимое для выполнения каждого задания;

x_zr – ребра связи между заданиями и ресурсами, отображающие множество назначений заданий z на ресурсы r ;
v_x -веса ребер связи между ресурсами r и заданиями z , отображающие время выполнения i -гозадания на j-м ресурсе.

Задача оптимального планирования состоит в определении на графе G множества x_zr назначенийзаданий z на ресурсы r , обеспечивающих экстремальное (максимальное или минимальное) значение одного или нескольких критериев оптимальности, приведенных в разделе 10.1.

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

Алгоритм математического программирования. Рассмотрим алгоритм сведения задачи планирования к задаче математического программирования.

Пусть на вход вычислительной системы, состоящей из n_r ресурсов (элементарных машин) (ПВМ), поступает  m_z  заданий. Каждое  i-е  задание  является параллельной  программой  и требует для своего выполнения  n _{r i}   ресурсов,  где  1 £  n_ri <  n_r,  ( i = 1…m_z). При этом на каждой  j-й  ПВМ может обрабатываться не более, чем  m_zi  заданий  одновременно.

Задача оптимального планирования состоит в определении  матрицы x  оптимального распределения  заданий между  ресурсами,  элементы  x _{i j}  ( i = 1…m_z) ,  ( j = 1…n_r)  которой  определяются следующим образом:
- x_{i j}  = 1,  если   i-е  задание  назначается на выполнение  в  j-й  ПВМ;
- x_{i j}  = 0  - в противном случае.

Пусть  t _i  - заданное время выполнения  i-го  задания.  Тогда  обобщенная  нагрузка  на ресурсы  (т.е. суммарное время выполнения  всех  заданий)  равна   T_z  =  S t _i.  ( i = 1…m_z), а  среднее время  работы  каждого  ресурса   q _r = T_z/ n_r.

С учетом указанных величин задачу оптимального планирования процесса выполнения  m_z  заданий  на  n_r ресурсах  можно представить в виде следующей задачи математического программирования. 

Требуется определить значения элементов  x_ij матрицы xоптимального распределения  заданий между ресурсами, обеспечивающие равномерность нагрузки на ресурсы и минимальное суммарное время выполнения заданий в системе:
min  S S ( t _i - q _r  )² × x _{i j} ,   ( i = 1…n_z) ,    ( j = 1…n _r  )             при ограничениях:
- на число ресурсов  n _{r i},  необходимое для выполнения  i-го  задания: S  x _{i j}  = n _{r i}  ,  
- на число заданий m_zi , которое может одновременно обрабатываться  на  j-й ПВМ:S  x _{i j}  £  m_zj  .

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

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

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

Эвристические  алгоритмы  планирования. В условиях динамической  диспетчеризации вычислительного процесса и применения интеллектуальных ПВМ (раздел 5.6.2) используются так называемые эвристические (интуитивные) алгоритмы планирования. Основу этих алгоритмов составляют эвристики - совокупность эмпирических правил, основанных на неформальных соображениях, не имеющих теоретического обоснования. Использование эвристик позволяет существенно сокращать время решения задачи планирования по сравнению, например, с методами математического программирования и получать решение, близкое к оптимальному.

В качестве эвристических параметров алгоритма могут выступать:
- заданное время решения тех или иных задач;
- штраф за задержку решения задач;
- заданный срок окончания решения задач;
- степень загруженности (недогруженность или перегруженность) ресурсов и др.

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

При решении задачи планирования с использованием эвристического  подхода  все ресурсы системы разбиваются на несколько связных ресурсных подсистем. В каждой подсистеме  определяется так называемая  корневая ПВМ  с окрестностью  (локальной областью) L_r , которая включает номера ПВМ, расположенные от корневой ПВМ на расстоянии, не превышающем  заданного радиуса  r.

Разбиение ресурсов системы на локальные области позволяет существенно сократить время решения задачи планирования за счет выравнивания  нагрузки между ПВМ каждой подсистемы. Корневая ПВМ следит за нагрузкой ПВМ в своей локальной области  и при необходимости пересылает задачи в наименее загруженные ПВМ своей подсистемы. Кроме того, каждая перегруженная ПВМ может самостоятельно принимать решения по перемещению находящихся в ней задач в другие ПВМ своей подсистемы.