Спосіб рішення задачі планування паралельного розподілу задач в grid-системах

Реферат: Спосіб рішення задачі планування паралельного розподілу задач в GRID-системах вирішує задачу цілочисельного лінійного програмування з булевими змінними на основі рангового підходу та принципу оптимізації за напрямком. Введено правило відсікання неперспективних варіантів рішень по вибору мінімального значення довжини шляху в графі за вагою обмеження та сортування даних по убуванню значень коефіцієнтів в функціоналі. UA 92966 U (12) UA 92966 U UA 92966 U 5 Запропонована корисна модель належить до галузі кібернетики і обчислювальної техніки та може бути використана при вирішенні задач комбінаторної оптимізації на графах. Відомий "Спосіб послідовного призначення одиниць для наближеного рішення задачі про одномірний ранець", який вирішує задачу цілочисельного лінійного програмування з булевими змінними [1]:  n f x    c j x j  max , (1) j 1 при виконанні умов: n  ai j x j  b1 , (2) j 1   x j  0,1, i  1, j  1, n , (3) a1j  0 , (4) c j  0. В даному способі як початковий розглядається нульовий вектор, в якому змінним присвоюються одиничні значення за умови, що при побудові допустимого цілочисельного 0 рішення z призначаються одиничні значення у відповідності з послідовністю  j1   j2  ...  j n , 10 15 20 починаючи з найбільшого значення. Якщо для деякого  j k таке призначення виконати неможливо, тоді z0k  0 і переходять до номеру jk+1. Процес завершується після перегляду всіх j змінних або при порушенні умови (2). Призначення одиничних значень виконується у відповідності з послідовністю c j1  c j2  ... c j n . Недоліком відомого способу є те, що відносна похибка наближеного алгоритму для рішення задачі цілочисельного лінійного програмування з булевими змінними складає 20 %. Найбільш близьким до запропонованого технічного рішення, вибраний як прототип, є "Способ решения задачи целочисленного линейного программирования с булевыми переменными на основе рангового похода", який вирішує задачу цілочисельного лінійного програмування з булевими змінними на основі рангового підходу, та полягає у тому, що з   вершини s графа ΔD будується множина шляхів mr 1 , j  1, n першого рангу r, що задовольняє sj  r  властивості, і в множинах mr 1 визначаються шляхи максимальної довжини  sj  за вагою   sj     функціонала cj [2]. Для кожної вершини j визначається вага  j за правилом:    j  c j 1  c j  2  ... c n ,  n  0 ; j  1 n  1 . (5) ,    r   r  Виключаються шляхи  sj  , p  r , n у множині mr поточного рангу r, довжини якої dс  sj      sj         задовольняють нерівності:   25     r  (6) dc r  p  max dc  sp  , sp   c j      де  p  c p 1  c p  2  ... c n , та для вершини jn вага  j - дорівнює нулю;  r  dc  sj  - довжина шляху від вершини s до вершини ρ рангу r по вагах функціоналу.         Формується множина шляхів mr r 1 , p  r ,n наступного рангу, що задовольняє властивості sp (5), на базі множини шляхів mr попереднього рангу на основі рекурентного співвідношення: sj   r r 1  max r   j, p  p  r  1, n j  r , n j  p , (7) sp sj c  j 30 де r  j,p - шлях з вершини s графа ΔD у вершину р, що проходить через проміжну sj вершину j і який задовольняє правилам, тобто який одержується за рахунок приєднання до 1 UA 92966 U шляху r ребра (j, p), якщо таке з'єднання не суперечить правилу відсікання неперспективних sj варіантів рішень. 5 10 15 20 25 30  r  r 1 У визначених множинах mr r 1 виділяються щонайдовші шляхи   sj  .   sp     Якщо визначиться декілька шляхів максимальної довжини, то серед них вибирається шлях з меншим значенням довжини за вагою обмежень a1j. Перевіряється, чи вся множина шляхів наступного (r+1)-го рангу порожня. Якщо умова виконується, то в множинах виділяється шлях максимальної довжини і алгоритм закінчує роботу. Якщо умова не виконується, то перевіряється r=(n-1). У разі виконання рівності в множині виділяється шлях максимальної довжини і алгоритм закінчує роботу, інакше збільшується τ на 1 і виконується обчислення у відповідності до формул (5-7). Недоліком способу-прототипу є те, що відносна похибка наближеного алгоритму для рішення задачі цілочисельного лінійного програмування з булевими змінними на основі рангового підходу складає 12 %. В основу корисної моделі поставлена задача створити "Спосіб рішення задачі планування паралельного розподілу задач в GRID-системах", який дозволить зменшити відносну похибку алгоритму до 7 %. Поставлена задача вирішується за рахунок того, що у спосіб-прототип, додатково введено правило відсікання неперспективних варіантів рішеньна основі вибору мінімального значення довжини шляху в графі за вагою обмеження на основі принципу оптимізації за напрямком та сортування даних по убуванню значень коефіцієнтів в функціоналі. Технічний результат, який може бути отриманий при здійсненні корисної моделі полягає у зменшенні відносної похибки алгоритму рішення задачі цілочисельного лінійного програмування з булевими змінними на основі рангового підходу та принципу оптимізації за напрямком до 7 %. На фіг. 1 представлено граф ΔD. На фіг. 2 наведено приклад рішення задачі цілочисельного лінійного програмування з булевими змінними на основі рангового підходу та принципу оптимізації за напрямком. Запропонований "Спосіб рішення задачі планування паралельного розподілу задач в GRIDсистемах" ґрунтується на правилі відсікання неперспективних варіантів рішень по вибору мінімального значення довжини шляху в графі за вагою на основі принципу оптимізації за напрямком та сортуванні даних по убуванню значень коефіцієнтів в функціоналі. Суть способу полягає у наступному. Виконується сортування даних по убуванню значень коефіцієнтів в функціоналі: (8) c1  c 2  ... cn .   З вершини s графа ΔD будується множина шляхів mr , j  r , n sj 35 першого рангу r, що  r  задовольняє властивості, і визначаються в множинах mr шляхи максимальної довжини  sj    sj     за вагою функціонала cj. Для кожної вершинні визначається вага yj за правилом (5).    r   r  Виключаються шляхи  sp  , p  r ,n у множині mr поточного рангу r, довжини якої dc  sp      sj         задовольняють нерівності (6).   Формується множина шляхів mr r 1 p  r ,n наступного рангу, що задовольняє властивості sp (5), на базі множини шляхів 40 mr попереднього рангу на основі правила відсікання sj неперспективних варіантів рішень по вибору мінімального значення довжини шляху в графі за вагою обмеження на основі принципу оптимізації за напрямком:   r r 1  min r   j, p  p  r  1, n j  r , n j  p . (9) sp sj   j  r  r 1 У визначених множинах mr r 1 виділяються щонайдовші шляхи   sp  .   sp     Якщо визначиться декілька шляхів мінімальної довжини за вагою обмеження, то серед них вибирається шлях з найбільшим значенням довжини за вагою функціонала c1j. 2 UA 92966 U 5 10 Перевіряється, чи вся множина шляхів наступного (r+1)-го рангу порожня. Якщо умова виконується, то в множинах виділяється шлях максимальної довжини за вагою функціонала і алгоритм закінчує роботу. Якщо умова не виконується, то перевіряється r=(n-1). У разі виконання рівності в множині виділяється шлях максимальної довжини за вагою функціонала і алгоритм закінчує роботу, інакше збільшується τ на 1 і виконується обчислення у відповідності до формул (5-8). Джерела інформації: 1. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы: Учеб. пособие. - Изд. 2-е, испр. -М.: ФИЗМАТЛИТ, 2003. - 240 с. 2. Третьяк В.Ф., Голубничий Д.Ю., Огурцов В.В. Метод решения задачи целочисленного линейного программирования с булевыми переменными на основе рангового похода //Системи обробки інформації. Збірник наукових праць, 2009. - випуск 4 (78). С 152-155. ФОРМУЛА КОРИСНОЇ МОДЕЛІ 15 20 Спосіб рішення задачі планування паралельного розподілу задач в GRID-системах, який вирішує задачу цілочисельного лінійного програмування з булевими змінними на основі рангового підходу та принципу оптимізації за напрямком, який відрізняється тим, що введено правило відсікання неперспективних варіантів рішень по вибору мінімального значення довжини шляху в графі за вагою обмеження та сортування даних по убуванню значень коефіцієнтів в функціоналі. 3 UA 92966 U Комп’ютерна верстка Л. Литвиненко Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 4