авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 || 3 | 4 |

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ На правах рукописи ...»

-- [ Страница 2 ] --

Для базовых примеров массивов заявок кругового типа: натуральных ресурсных k j1 k j1, j1 0, 1,, k 1 (равные требования временного и квадратов процессорного ресурсов a j1 b j1 ), натуральных ресурсных прямоугольников горизонтальной формы k j1, k j1 1, j1 0, 1,, k 2 (преимущественные требования временного ресурса a j1 b j1 ), натуральных ресурсных прямоугольников вертикальной формы k j1 1, k j1, j1 0, 1,, k (преимущественные требования процессорного ресурса a j1 b j1 ) строятся объемлющие прямоугольники с вычислением ресурсных и эвристических мер.

Указанные построения и вычисления сопоставляются с имеющимися в литературе оптимальными построениями ресурсных оболочек. Делаются выводы о качестве предложенного эвристического полиномиального начально- кольцевого алгоритма.

2.3. Вершинно- кольцевой алгоритм Приведм и исследуем вершинно- кольцевой алгоритм диспетчирования линейными круговыми полиэдралями ресурсных прямоугольников k a j1, b j1, b j1, a j1, j1 [131,132].

j1 10. На начальном шаге вершинно- кольцевого алгоритма строим начальную ресурсную оболочку. Здесь последующие за максимальным элементы суперпозируются справа, сверху и вершинно- диагонально к основному элементу, соответственно (рисунок 2.18).

Y b2 b a2 a b0 b a0 a Y Рис.2.18. Начальная ресурсная оболочка 20. На втором шаге, в качестве максимального элемента принимается указанная оболочка. Вдоль правой стороны оболочки вертикально суперпозируются последующие грани до наилучшего приближения уровня оболочки с недостатком (операция динамического интегрирования ресурсных прямоугольников по вертикали). Затем, над верхней стороной оболочки вдоль горизонтали на упомянутом уровне суперпозируются последовательно оставшиеся элементы до наилучшего приближения с недостатком величины протяжнности оболочки (операция динамического интегрирования ресурсных прямоугольников по горизонтали). Наконец, вершинно- диагональным синтезом заполняем полученную новую ресурсную оболочку последующими гранями полиэдрали.

30. Введнный таким образом вершинно- кольцевой алгоритм повторяем до полного исчерпания ресурсных прямоугольников массива. Строится конечная ресурсная оболочка (рисунок 2.19).

Y2 a b a10 a b7 b8 b b b a7 a a b2 b b a a a b a b0 b b a0 a1 a Y Рис. 2.19. Конечная ресурсная оболочка В частности, для линейной полиэдрали натуральных ресурсных квадратов при k 32 соответствующие построения приведены на рисунке 2.20.

19 18 17 16 15 26 25 24 30 29 27 22 32 31 28 23 Рис. 2.20. Укладка круговой линейной полиэдрали ресурсных квадратов вершинно- кольцевым алгоритмом Сравним качество приведнного вершинно- кольцевого алгоритма с оптимальной укладкой в объемлющий прямоугольник минимальной площади, полученной в работах [66-68,70,71]. Приведм в таблице 2.8 результаты размещения вершинно- кольцевым и оптимальным алгоритмами для последовательности натуральных ресурсных квадратов k j1 k j1, j1 0, 1,, k 1. Здесь L- горизонтальное и H- вертикальное измерения объемлющего прямоугольника вершинно- кольцевого алгоритма, Lopt, H opt - соответствующие измерения оптимального алгоритма, - погрешность площади ресурсной оболочки в % относительно оптимального значения.

Таблица 2.8. Сравнение вершинно- кольцевого и оптимального алгоритмов,%,% Lopt, H opt Lopt, H opt L, H L, H k k 39 1 0 17 27, 53 1 1 1 23 57 2 0 18 22, 3 2 31 47 3 33,3 19 20, 5 4 3 5 61 76 65 54 34 4 20,0 20 21, 5 98 70 5 20,0 21 29, 5 12 38 9 11 74 66 39 6 31,3 22 27, 13 16 12 78 70 64 7 24,7 23 25, 11 19 14 14 15 82 75 56 8 26,7 24 24, 22 16 86 9 17,3 25 22, 15 20 43 94 25 10 23,5 26 25, 15 27 70 28 24 19 27 101 11 31,0 27 26, 106 12 25,5 28 24, 31 27 23 29 34 30 22 38 111 13 22,0 29 22, 117 39 14 28,1 30 22, 23 45 122 15 31,6 31 25, 45 37 23 55 49 40 16 29,6 32 18, 28 54 Заметим, что погрешность не превосходит 35%, что является подтверждением целесообразности использования предложенного вершинно кольцевого алгоритма при диспетчировании процессорно- временными ресурсами.

Эвристические меры ресурсных оболочек вершинно- кольцевого алгоритма приведены в таблице 2.9.

Таблица 2.9. Эвристические меры ресурсных оболочек вершинно кольцевого алгоритма Эвристическая k Эвристическая k Эвристическая k Эвристическая k мера мера мера мера 1 9 17 0,50 0,68 0,67 0, 2 10 18 0,70 0,68 0,65 0, 3 11 19 0,75 0,68 0,63 0, 4 12 20 0,72 0,66 0,63 0, 5 13 21 0,66 0,63 0,67 0, 6 14 22 0,76 0,67 0,65 0, 7 15 23 0,74 0,70 0,64 0, 8 16 24 0,71 0,68 0,63 0, Отметим, что эвристические меры ресурсных оболочек вершинно 0,26.

кольцевого алгоритма не превосходят значения Приведм параллельную версию вершинно- кольцевого алгоритма.

10. Линейную круговую полиэдраль ресурсных прямоугольников k a j1, b j1, разбиваем на четврки. В каждой четврке убывающих по j1 a j1, b j1 a j1 1, b j1 1, вложению ресурсных прямоугольников a j1 2, b j1 2 a j1 3, b j1 3 суперпозируем вдоль правой стороны a j1, b j1 - первый элемент a j1 1, b j1 1, вдоль начального элемента верхней стороны- второй элемент a j1 2, b j1 2 и вершинно- диагонально к начальному элементу суперпозируем третий элемент a j1 3, b j1 3.

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

b2 b a2 a3 b6 b a10 a a a b10 b b0 b b4 b a(14) a(15) b b b(14) b(15) a0 a1 a4 a5 a8 a9 b(12) b(13) a(12) a(13) Рис. 2.21. Линейная полиэдраль ресурсных оболочек Действительно, ресурсная оболочка рассмотренной четврки граней имеет a j1 a j1 1 b j1 b j1 2, параметры а следующая a j1 4 a j1 5 b j1 4 b j1 6. В силу свойства кругового типа исходной линейной полиэдрали, имеем вложение последующей ресурсной a j1 a j1 1 a j1 4 a j1 5, оболочки в предыдущую b j1 b j1 2 b j1 4 b j1 6 и горизонтальность формы a j1 a j1 1 b j1 b j1 2, т.к. a j1 b j1, a j1 1 b j1 1 b j1 2.

20. Полученную линейную полиэдраль мощности 2k 2 ресурсных оболочек также разбиваем на четврки. Кратное повторение данного алгоритма приводит к массиву новых ресурсных оболочек мощности 2k 4. Повторяем алгоритм до полного исчерпания массива (рисунок 2.22).

Y a10 a b10 b a(14) a(15) b b b(14) b(15) a8 a9 b(12) b(13) a(12) a(13) b2 b a2 a3 b6 b a a b0 b b4 b a0 a1 a4 a Y Рис. 2.22. Ресурсная оболочка параллельного вершинно- кольцевого алгоритма Проиллюстрируем работу параллельного вершинно- кольцевого алгоритма на линейной полиэдрали натуральных ресурсных квадратов k j1 k j1, j1 0, 1,, k 1. При k 16 локализация каждой из четврок приведена на рисунке 2.23.

14 13 12 16 2 8 Рис. 2.23. Ресурсные оболочки массива 16- ти натуральных ресурсных квадратов Последующая локализация полученных четырх ресурсных оболочек показана на рисунке 2.24.

2 8 4 14 13 12 16 Рис. 2.24. Ресурсная оболочка параллельного вершинно- кольцевого алгоритма Эвристическая мера ресурсной оболочки параллельного вершинно кольцевого алгоритма имеет значение 1 54 44 54 0,83.

2 1496 Видим, что соответствующая эвристическая мера последовательной версии вершинно- кольцевого алгоритма 0,68 (таблица 2.9), является лучше. Вместе с тем, число операций в параллельной версии меньше.

Таким образом, в настоящем параграфе предлагается и исследуется эвристический вершинно- кольцевой алгоритм диспетчирования массивами заявок кругового типа. Для базового примера массивов заявок кругового типа k j1 k j1, j1 0, 1,, k 1 строятся натуральных ресурсных квадратов объемлющие прямоугольники с вычислением ресурсных и эвристических мер.

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

2.4. Уровневый алгоритм Приведм и исследуем уровневый алгоритм диспетчированиями линейными круговыми полиэдралями ресурсных прямоугольников k a j1, b j1, b j1, a j1, j1 Определим величину [78, 132].

j1 k a j1 b j1, H которую назовм среднересурсной, и примем е за уровень j1 горизонтальной полосы 0 Y2 H.

10. На первом шаге вдоль линии Y1 0 вертикально суперпозируются q1 a j1, b j ресурсные прямоугольники до наилучшего приближения уровня j1 q1 b j1 H с недостатком (операция динамического интегрирования j1 ресурсных прямоугольников по вертикали). Здесь q1 - число ресурсных прямоугольников, суперпозированных в первом слое. Строится начальная ресурсная оболочка полученной совокупности ресурсных прямоугольников (рисунок 2.25).

Y b(1) a(1) b(0) a(0) Y Рис. 2.25. Начальная ресурсная оболочка 20. На втором шаге вдоль правой стороны достигнутой ресурсной оболочки Y1 a0 вертикально суперпозируются последующие ресурсные прямоугольники q1 q 2 a j1, b j1 до наилучшего приближения уровня с недостатком j1 q q1 q 2 b j1 H 0 (операция динамического интегрирования ресурсных j1 q прямоугольников по вертикали). Здесь q2 - число ресурсных прямоугольников, суперпозированных во втором слое. Строится новая ресурсная оболочка (рисунок 2.26).

Y b(4) a(4) b(1) b(3) a(1) a(3) b(0) b(2) a(2) a(0) Y Рис. 2.26. Первая ресурсная оболочка 30. На следующем шаге вдоль правой стороны достигнутой ресурсной оболочки Y1 a0 aq1 вертикально суперпозируются последующие ресурсные q1 q 2 q3 a j1, b j прямоугольники до наилучшего приближения уровня с j1 q1 q q1 q 2 q3 b j1 H недостатком (операция динамического интегрирования j1 q1 q ресурсных прямоугольников по вертикали). Здесь q3 - число ресурсных прямоугольников, суперпозированных в третьем слое.

40. Введнный таким образом уровневый алгоритм повторяем до полного исчерпания ресурсных прямоугольников массива. Строится конечная ресурсная оболочка (рисунок 2.27).

Y b(9) a(9) b(4) b(8) a(4) a(8) b(1) b(7) a(7) b(3) a(1) a(3) b(6) a(6) b(0) b(2) b(5) a(5) a(2) a(0) Y Рис. 2.27. Конечная ресурсная оболочка Обозначим через C- количество шагов уровневого алгоритма.

Горизонтальное измерение оболочки определяется как C L a0 aq1 aq1 q2 a q j, j Вертикальное измерение оболочки определяется как q1 q 2 q3 q1 1 q1 q 2 b j1, b j1, … b j1, H maxH1, H 2,, HC, H1 H2 H j1 q1 j1 q1 q j1 Параметры определены выше, число ресурсных qj q1, q2, q прямоугольников, суперпозированных на j - м шаге в вертикальном слое.

Приведм блок- схему уровневого алгоритма (рисунок 2.28). Введм следующие обозначения. a j, b j - параметры требований пользователей, k RA j, RB j - номера процессорного и количество заявок пользователей.

временного ресурсов, начиная с которых будет выделено a j, b j единиц соответствующего ресурса для j- ой заявки. AL- номер 1- го ресурса по оси Y1, одинаковый для всех прямоугольников соответствующей вертикальной полиэдрали, H V - уровень V- ой вертикальной полиэдрали. A, max H V параметры текущей оболочки соответственно по ресурсам 1- го, 2- го рода.

Начало Ввод a(j), b(j), j = 0,…,K- A = 0, j = 0, V = k a j b j H 1 j1 V = V+ AL = A A = A + a(j) S = 0, i = RA(j + i) = AL RB(j + i) = S i=i+ Нет j + i - 1 K- Да H(V) = S S = S + b(j + i - 1) SH Да Нет j=j+i- Вывод A, maxV(H) массив RA, RB Конец Рис.2.28. Блок- схема уровневого алгоритма Отметим, что количество операций работы уровневого алгоритма составляет k операций сложения и k операций сравнения, т.е. алгоритм является полиномиальным.

В частности, для линейной полиэдрали натуральных ресурсных квадратов при k 32 соответствующие построения приведены на рисунке 2.29.

30 27 20 100 25 21 16 32 29 26 22 17 Рис. 2.29. Укладка круговой линейной полиэдрали ресурсных квадратов уровневым алгоритмом Сравним качество приведнного уровневого алгоритма с оптимальной укладкой в объемлющий прямоугольник минимальной площади, полученной в работах Приведм в таблице 2.10 результаты размещения [66-68,70,71].

уровневым и оптимальным алгоритмами для последовательности натуральных ресурсных квадратов k j1 k j1, j1 0, 1,, k 1. Здесь L- горизонтальное и H- вертикальное измерения объемлющего прямоугольника уровневого алгоритма, Lopt, H opt - соответствующие измерения оптимального алгоритма, - погрешность площади ресурсной оболочки в % относительно оптимального значения.

Таблица 2.10. Сравнение уровневого и оптимального алгоритмов,%,% Lopt, H opt Lopt, H opt L, H L, H k k 52 42 39 1 0 17 21, 11 1 23 56 2 0 18 20, 2 3 31 47 3 0 19 26, 5 3 3 5 63 76 34 4 20,0 20 28, 5 7 69 5 28,3 21 28, 11 7 5 12 74 58 38 9 11 39 6 27,3 22 29, 14 9 80 17 11 64 7 21,4 23 21, 80 11 17 15 14 15 56 8 21,4 24 19, 85 9 19,0 25 21, 2117 15 20 90 75 43 96 10 23,5 26 15, 25 20 15 27 70 30 22 19 27 101 11 28,7 27 13, 34 26 108 12 32,5 28 22, 23 29 39 25 22 38 116 13 16,6 29 21, 123 14 16,3 30 19, 43 28 23 45 129 15 25,2 31 28, 44 36 23 55 136 16 23,8 32 18, 48 39 28 54 Заметим, что погрешность не превосходит 33%, что является подтверждением целесообразности использования предложенного уровневого алгоритма при диспетчировании процессорно- временными ресурсами.

Эвристические меры ресурсных оболочек уровневого алгоритма приведены в таблице 2.11.

Таблица 2.11. Эвристические меры ресурсных оболочек уровневого алгоритма Эвристическая Эвристическая Эвристическая Эвристическая k k k k мера мера мера мера 1 9 17 0,50 0,65 0,64 0, 2 10 18 0,70 0,68 0,63 0, 3 11 19 0,68 0,72 0,67 0, 4 12 20 0,72 0,73 0,69 0, 5 13 21 0,85 0,71 0,69 0, 6 14 22 0,83 0,70 0,70 0, 7 15 23 0,80 0,66 0,63 0, 8 16 24 0,63 0,65 0,62 0, Отметим, что эвристические меры ресурсных оболочек уровневого 0,35.

алгоритма не превосходят значения Для линейной круговой полиэдрали натуральных ресурсных k j1, k j1 1, j1 0, 1,, k прямоугольников горизонтальной формы при k 32 укладка уровневым алгоритмом по высоте приведена на рисунке 2.30.

10x 18x17 11x 23x 30x29 12x 19x 27x 13x 24x 14x 20x 31x 28x27 15x 25x24 21x20 16x15 7x 32x31 29x28 26x25 22x21 17x16 8x 9x Рис. 2.30. Укладка круговой линейной полиэдрали натуральных ресурсных прямоугольников горизонтальной формы уровневым алгоритмом по высоте Эвристические меры ресурсных оболочек уровневого алгоритма по высоте для натуральных ресурсных прямоугольников горизонтальной формы приведены в таблице 2.12.

Таблица 2.12. Эвристические меры ресурсных оболочек уровневого алгоритма по высоте для натуральных ресурсных прямоугольников горизонтальной формы Эвристическая k Эвристическая k Эвристическая k мера мера мера 18 23 0,66 0,65 0, 19 24 0,65 0,65 0, 20 25 0,70 0,64 0, 21 26 0,71 0,64 0, 22 27 0,64 0,65 0, Отметим, что эвристические меры ресурсных оболочек уровневого алгоритма по высоте для натуральных ресурсных прямоугольников 0,21.

горизонтальной формы не превосходят значения Наряду с уровневым алгоритмом по высоте, введм и исследуем уровневый алгоритм по протяжнности.

Для линейной круговой полиэдрали натуральных ресурсных k j1, k j1 1, j1 0, 1,, k прямоугольников горизонтальной формы при k 32 укладка уровневым алгоритмом по протяжнности приведена на рисунке 2.31.

10x9 9x8 8x7 7x 6 5 4 3 17x16 16x15 15x14 14x13 13x12 12x11 11x 22x21 21x20 20x19 19x18 18x 26x25 25x24 24x23 23x 29x28 28x27 27x 32x31 31x30 30x Рис. 2.31. Укладка круговой линейной полиэдрали натуральных ресурсных прямоугольников горизонтальной формы уровневым алгоритмом по протяжнности Эвристические меры ресурсных оболочек уровневого алгоритма по протяжнности для натуральных ресурсных прямоугольников горизонтальной формы приведены в таблице 2.13.

Таблица 2.13. Эвристические меры ресурсных оболочек уровневого алгоритма по протяжнности для натуральных ресурсных прямоугольников горизонтальной формы Эвристическая k Эвристическая k Эвристическая k мера мера мера 18 23 0,74 0,71 0, 19 24 0,70 0,74 0, 20 25 0,69 0,61 0, 21 26 0,69 0,61 0, 22 27 0,69 0,60 0, Отметим, что эвристические меры ресурсных оболочек уровневого алгоритма по протяжнности для натуральных ресурсных прямоугольников 0,24.

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

Рис.2.32. Эвристические меры ресурсных оболочек уровневых алгоритмов по высоте и по протяжнности для натуральных ресурсных прямоугольников горизонтальной формы Сравнение результатов не позволяет отдать предпочтение какому- либо из алгоритмов.

Для линейной круговой полиэдрали натуральных ресурсных k j1 1, k j1, j1 0, 1,, k 2 при прямоугольников вертикальной формы k 32 укладка уровневым алгоритмом по высоте приведена на рисунке 2.33.

10x 17x 22x 11x 29x 18x 26x27 12x 23x 13x 19x20 100 30x31 27x28 14x 24x25 20x21 15x16 7x 31x32 28x29 8x 25x26 21x 16x 9x Рис. 2.33. Укладка круговой линейной полиэдрали натуральных ресурсных прямоугольников вертикальной формы уровневым алгоритмом по высоте Эвристические меры ресурсных оболочек уровневого алгоритма по высоте для натуральных ресурсных прямоугольников вертикальной формы приведены в таблице 2.14.

Таблица 2.14. Эвристические меры ресурсных оболочек уровневого алгоритма по высоте для натуральных ресурсных прямоугольников вертикальной формы Эвристическая k Эвристическая k Эвристическая k мера мера мера 18 23 0,74 0,71 0, 19 24 0,70 0,74 0, 20 25 0,69 0,61 0, 21 26 0,69 0,61 0, 22 27 0,69 0,60 0, Отметим, что эвристические меры ресурсных оболочек уровневого алгоритма по высоте для натуральных ресурсных прямоугольников вертикальной 0,24.

формы не превосходят значения Исследуем уровневый алгоритм по протяжнности. Для линейной круговой полиэдрали натуральных ресурсных прямоугольников вертикальной формы k j1 1, k j1, j1 0, 1,, k 2 при k 32 укладка уровневым алгоритмом по протяжнности приведена на рисунке 2.34.

8x9 7x8 6 54 3 16x17 15x16 14x15 13x14 12x13 11x12 10x11 9x 21x22 20x21 19x20 18x19 17x 25x26 24x25 23x24 22x 28x29 27x28 26x 31x32 30x31 29x Рис. 2.34. Укладка круговой линейной полиэдрали натуральных ресурсных прямоугольников вертикальной формы уровневым алгоритмом по протяжнности Эвристические меры ресурсных оболочек уровневого алгоритма по протяжнности для натуральных ресурсных прямоугольников вертикальной формы приведены в таблица 2.15.

Таблица 2.15. Эвристические меры ресурсных оболочек уровневого алгоритма по протяженности для натуральных ресурсных прямоугольников вертикальной формы Эвристическая k Эвристическая k Эвристическая k мера мера мера 18 23 0,66 0,65 0, 19 24 0,65 0,65 0, 20 25 0,70 0,64 0, 21 26 0,71 0,64 0, 22 27 0,64 0,65 0, Отметим, что эвристические меры ресурсных оболочек уровневого алгоритма по протяжнности для натуральных ресурсных прямоугольников 0,21.

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

Рис. 2.35. Эвристические меры ресурсных оболочек уровневых алгоритмов по высоте и по протяжнности для натуральных ресурсных прямоугольников вертикальной формы Сравнение результатов не позволяет отдать предпочтение какому- либо из алгоритмов.

Для решения рамочной задачи рассмотрим версию уровневого алгоритма. С 0 Y1 a0 производим вертикальную этой целью, в начальной полосе q1 a j1, b j последовательную суперпозицию ресурсных прямоугольников j1 слева от линии Y1 a0 до наилучшего приближения с недостатком к высоте q1 b j1 M рамки (операция динамического интегрирования ресурсных j1 прямоугольников по вертикали) (рисунок 2.36). Здесь q1 - число ресурсных прямоугольников, суперпозированных в начальной полосе. Далее, строим линию Y1 a0 aq1 и слева от данной линии производим предыдущее построение по q1 q2 b j1 M отношению к оставшейся части массива (операция j1 q динамического интегрирования ресурсных прямоугольников по вертикали). Здесь q2 - число ресурсных прямоугольников следующей полосы. Циклическое повторение указанных действий приведт к исчерпанию массива и локализации последнего в полосу 0 Y2 M некоторой протяжнности, составленной из предыдущих отрезков 0, a0 a0, a0 aq1 Y2 M M aq a Y Рис. 2.36. Уровневый алгоритм рамочной задачи Вертикальные линейные полиэдрали, из которых составлена полоса 0 Y2 M, подлежащая рамочному ресурсному распределению по правилам координатности, аддитивности и цельности, обладают свойством убывания оснований ресурсных прямоугольников вдоль вертикальной координаты j2, a. Здесь a j1, j2 - основание полиэдральной грани в упомянутой полосе.

0, M Поэтому требуемому распределению по линейкам подлежат звенья Y2 0.

измерения горизонтальной линии Данная цель достигается последовательной суперпозицией с наилучшим приближением с недостатком протяжнности M 0 (операция динамического интегрирования ресурсных прямоугольников по горизонтали) посредством указанных измерительных элементов a j1, 0 - горизонтальных оснований ресурсных прямоугольников заявок пользователей.

Приведм и исследуем последовательно- координатный алгоритм диспетчеризации триодными полиэдралями ресурсных прямоугольников a j1 b j1, j2, j1, j2 0, k Z 1 при решении рамочной стадийной задачи на основе последовательного наилучшего приближения с недостатком по M M отношению к измерениям ресурсной рамки динамическим интегрированием.

q1 1 q1 a j1, a j1 M 0 Y 1. Строим первую полосу (операция j1 0 j1 динамического интегрирования ресурсных прямоугольников по горизонтали).

M M 20. Заполняем рамки гранями первой полосы наилучшим приближением вертикального измерения рамки. Для начальной рамки имеем p1 j1 1 p1 j1 j1 0, q1 1 Z, b j1, j2, b j1, j2 M 0 Y2 max (операция j1 j2 0 j2 динамического интегрирования ресурсных прямоугольников по вертикали).

Последующие рамки гранями первой полосы заполняются аналогично p 2 j1 b j1, j2 M 0 (операция динамического интегрирования ресурсных j 2 p1 j p 2 j1 j1 q1, q2 1 Z b j1, j2, прямоугольников по вертикали), Y2 max j 2 p1 j j и т.д.

30. Закончив распределение первой полосы, переходим ко второй, и далее, до полного исчерпания массива.

Таким образом, в настоящем параграфе предлагается и исследуется эвристический уровневый алгоритм диспетчирования массивами заявок кругового типа. Приводится блок- схема уровневого алгоритма распределения процессорно временных ресурсов. Устанавливается полиномиальная трудомкость предложенного уровневого алгоритма. Для базовых примеров массивов заявок кругового типа: натуральных ресурсных квадратов k j1 k j1, j1 0, 1,, k 1 (равные требования временного и процессорного ресурсов a j1 b j1 ), натуральных ресурсных прямоугольников горизонтальной формы k j1, k j1 1, j1 0, 1,, k 2 (преимущественные требования временного ресурса a j1 b j1 ), натуральных ресурсных прямоугольников k j1 1, k j1, j1 0, 1,, k 2 (преимущественные вертикальной формы a j1 b j1 ) требования процессорного ресурса строятся объемлющие прямоугольники с вычислением ресурсных и эвристических мер. Указанные построения и вычисления сопоставляются с имеющимися в литературе оптимальными построениями ресурсных оболочек. Делаются выводы о качестве предложенного эвристического полиномиального уровневого алгоритма.

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

2.5. Угловой алгоритм Приведм и исследуем угловой алгоритм диспетчирования линейными круговыми полиэдралями ресурсных прямоугольников k a j1, b j1, b j1, a j1, j1 Используем введнную [134].

j1 k a j1 b j1.

среднересурсную величину V j1 a0, b 10. На первом шаге максимальный ресурсный элемент помещаем в начало координат (рисунок 2.37).

Y V b(0) a(0) 0 Y V Рис. 2.37. Центральный угловой элемент первого шага Y2 Вдоль линии справа от этого элемента горизонтально q a j1, b j1 до последовательно суперпозируются ресурсные прямоугольники j1 q наилучшего приближения протяжнности с недостатком a0 a j1 V j1 (операция динамического интегрирования ресурсных прямоугольников по горизонтали). Здесь q1 - число ресурсных прямоугольников, суперпозированных горизонтально справа от центрального углового элемента первого шага a0, b0 (рисунок 2.38). Вдоль линии Y1 0 сверху над этим элементом вертикально последовательно суперпозируются ресурсные прямоугольники q1 q a j1, b j1 до наилучшего приближения уровня с недостатком j1 q1 q1 q b0 b j1 V 0 (операция динамического интегрирования ресурсных j1 q1 прямоугольников по вертикали). Здесь q2 - число ресурсных прямоугольников, суперпозированных вертикально сверху над центральным угловым элементом первого шага a0, b0 (рисунок 2.39).

Y2 Y V V b(4) a(4) b(3) a(3) b(1) b(1) b(0) b(0) b(2) b(2) a(2) a(2) a(0) a(1) a(0) a(1) 0 Y1 Y V V Рис. 2.38. Приближение Рис. 2.39. Приближение уровня с протяжнности с недостатком на недостатком на первом шаге первом шаге aq1 q2 1, bq1 q2 20. На втором шаге элемент вершинно диагонально синтезируется с центральным угловым элементом предыдущего a0, b шага (операция продольного динамического интегрирования ресурсных прямоугольников) (рисунок 2.40).

Y V b(4) a(4) b(3) b(5) a(3) a(5) b(1) b(0) b(2) a(2) a(0) a(1) 0 Y V Рис. 2.40. Вершинно- диагональный синтез центрального углового элемента второго шага Y2 b Вдоль линии справа от этого элемента горизонтально q1 q 2 1 q a j1, b j последовательно суперпозируются ресурсные прямоугольники j1 q1 q 2 до наилучшего приближения протяжнности с недостатком q1 q 2 1 q a0 aq1 q2 1 V 0 (операция динамического интегрирования a j j1 q1 q 2 ресурсных прямоугольников по горизонтали). Здесь q3 - число ресурсных прямоугольников, суперпозированных горизонтально справа от центрального aq1 q2 1, bq1 q2 углового элемента второго шага (рисунок 2.41).

Вдоль линии Y1 a0 сверху над этим элементом вертикально последовательно q1 q 2 1 q3 q a j1, b j1 до наилучшего суперпозируются ресурсные прямоугольники j1 q1 q 2 1 q3 q1 q 2 1 q3 q приближения уровня с недостатком b0 bq1 q2 1 b j1 V j1 q1 q2 1 q3 (операция динамического интегрирования ресурсных прямоугольников по вертикали). Здесь q4 - число ресурсных прямоугольников, суперпозированных вертикально сверху над центральным угловым элементом второго шага aq1 q2 1, bq1 q2 1 (рисунок 2.42).

Y2 Y V V b(4) b(4) b(7) a(4) a(4) a(7) b(3) b(3) b(5) b(5) b(6) b(6) a(3) a(5) a(6) a(3) a(5) a(6) b(1) b(1) b(0) b(0) b(2) b(2) a(2) a(2) a(0) a(1) a(0) a(1) 0 Y1 Y V V Рис. 2.41. Приближение протяжнности с Рис. 2.42. Приближение уровня с недостатком на втором шаге недостатком на втором шаге 30. На следующем шаге элемент aq1 q2 1 q3 q4 1, bq1 q2 1 q3 q4 1 вершинно- диагонально синтезируется с центральным угловым элементом предыдущего шага aq1 q2 1, bq1 q2 1 (операция продольного динамического интегрирования ресурсных прямоугольников) (рисунок 2.43).

Y V b(4) b(7) b(8) a(4) a(8) a(7) b(3) b(5) b(6) a(3) a(5) a(6) b(1) b(0) b(2) a(2) a(0) a(1) 0 Y V Рис. 2.43. Вершинно- диагональный синтез центральных угловых элементов a0 aq1 q2 1 aq1 q2 1 q3 q4 1 V Если или b0 bq1 q2 1 bq1 q2 1 q3 q4 1 V, то укладка углом завершается и переходим к п.40.

40. Определяем ресурсную оболочку полученной совокупности ресурсных прямоугольников (рисунок 2.44).

Y V b(4) b(7) b(8) a(4) a(8) a(7) b(3) b(5) b(6) a(3) a(5) a(6) b(1) b(0) b(2) a(2) a(0) a(1) 0 Y V Рис. 2.44. Ресурсная оболочка в пределах квадрата V V Горизонтальное измерение оболочки определяется как L maxL1, L2,, LC, где C- количество центральных угловых элементов- шагов укладки углом, q L1 a0 a j1, j1 q1 q 2 1 q L2 a0 aq1 q2 1, … a j j1 q1 q 2 Вертикальное измерение оболочки определяется как H maxH1, H 2,, HC, q1 q H1 b0 b j1, j1 q1 q1 q 2 1 q3 q H 2 b0 bq1 q2 1 … b j1, j1 q1 q 2 1 q3 Параметры q1, q2, q3, q4 определены выше.

50. Эта ресурсная оболочка принимается за начальную для укладки оставшихся элементов начально- кольцевым алгоритмом параграфа 2.2 (рисунки 2.45-2.46).

Y2 Y j1=13 j1=14 j1=15 j1=k-...

b(4) b(4) b(12) b(12) b(7) b(7) b(8) b(8) a(4) a(4) a(8) a(8) a(7) a(7) a(12) a(12) b(11) b(11) b(3) b(3) b(5) b(5) b(6) b(6) a(11) a(11) a(3) a(5) a(6) a(3) a(5) a(6) b(10) b(10) a(10) a(10) b(1) b(1) b(0) b(0) b(2) b(2) b(9) b(9) a(2) a(2) a(0) a(1) a(0) a(1) a(9) a(9) 0 Y1 Y Рис. 2.45. Укладка начально- Рис. 2.46. Укладка начально- кольцевым кольцевым алгоритмом справа алгоритмом сверху В итоге получаем конечную ресурсную оболочку углового алгоритма (рисунок 2.47).

Y j1=13 j1=14 j1=15 j1=k-...

b(4) b(12) b(7) b(8) a(4) a(8) a(7) a(12) b(11) b(3) b(5) b(6) a(11) a(3) a(5) a(6) b(10) a(10) b(1) b(0) b(2) b(9) a(2) a(0) a(1) a(9) Y Рис. 2.47. Конечная ресурсная оболочка углового алгоритма Приведм блок- схему углового алгоритма (рисунок 2.48). Введм следующие обозначения. a j, b j - параметры требований пользователей, k RA j, RB j - номера процессорного и количество заявок пользователей.

временного ресурсов, начиная с которых будет выделено a j, b j единиц соответствующего ресурса для j- ой заявки. AL- номер 1- го ресурса по оси Y1, одинаковый для всех прямоугольников соответствующей вертикальной полиэдрали, BL - номер 2- го ресурса по оси Y2, одинаковый для всех прямоугольников соответствующей горизонтальной полиэдрали. A, B- параметры центрального углового элемента текущего шага соответственно по ресурсам 1- го, 2- го рода. Выводится номер элемента j на котором укладка углом завершается.

Начало Ввод a(j), b(j), j = 0,…,K- K a j b j A = 0, B = 0, j = 0, V = 0, L j AL = A A = A + a(j) BL = B B = B + b(j) Нет AL and BL Да V = V+ S = 0, i = RA(j + i) = AL+S RB(j + i) = BL i=i+ Нет j + i - 1 K- Да D(V) = AL+S S = S + a(j + i - 1) Да AL+S L Нет j=j+i- BL = B S = 0, i = RA(j + i) = AL RB(j + i) = BL+S i=i+ Нет j + i - 1 K- Да H(V) = BL+S S = S + b(j + i - 1) Да BL+S L Нет j=j+i- max D(V), max H(V), j, массив RA, RB Конец Рис. 2.48. Блок- схема углового алгоритма Отметим, что количество операций работы углового алгоритма составляет k операций сложения и k операций сравнения, т.е. алгоритм является полиномиальным.

В частности, для линейной полиэдрали натуральных ресурсных квадратов при k 32 соответствующие построения приведены на рисунке 2.49.

14 13 12 11 10 9 8 765 4 3 2 22 25 24 29 27 32 31 Рис. 2.49. Укладка круговой линейной полиэдрали ресурсных квадратов угловым алгоритмом Сравним качество приведнного углового алгоритма с оптимальной укладкой в объемлющий прямоугольник минимальной площади, полученной в работах [66-68,70,71]. Приведм в таблице 2.16 результаты размещения угловым и оптимальным алгоритмами для последовательности натуральных ресурсных k j1 k j1, j1 0, 1,, k 1. Здесь L- горизонтальное и H квадратов вертикальное измерения объемлющего прямоугольника углового алгоритма, Lopt, H opt - соответствующие измерения оптимального алгоритма, - погрешность площади ресурсной оболочки в % относительно оптимального значения.

Таблица 2.16. Сравнение углового и оптимального алгоритмов,%,% Lopt, H opt Lopt, H opt L, H L, H k k 39 1 0,0 17 5243 24, 1 2 0,0 18 5746 22, 31 47 3 0,0 19 6257 41, 3 34 4 20,0 20 6661 39, 5 5 20,0 21 6766 32, 5 12 38 9 11 39 6 11,1 22 7667 33, 64 7 16,9 23 8071 30, 11 14 15 56 8 20,0 24 8475 27, 9 17,3 25 8880 26, 15 20 43 10 23,5 26 9284 24, 15 27 70 19 11 31,0 27 10088 26, 12 25,5 28 10692 25, 23 29 22 13 3430 22,0 29 11296 25, 14 3734 21,5 30 118100 24, 23 45 15 4337 25,8 31 121114 37, 23 55 16 4840 27,0 32 126119 30, 28 54 Заметим, что погрешность не превосходит что является 41,9%, подтверждением целесообразности использования предложенного углового алгоритма при диспетчировании процессорно- временными ресурсами.

Эвристические меры ресурсных оболочек углового алгоритма приведены в таблице 2.17.

Отметим, что эвристические меры ресурсных оболочек углового алгоритма 0,22.

не превосходят значения Таблица 2.17. Эвристические меры ресурсных оболочек углового алгоритма Эвристическая Эвристическая Эвристическая Эвристическая k k k k мера мера мера мера 1 0,50 9 0,68 17 0,65 25 0, 2 0,70 10 0,68 18 0,65 26 0, 3 0,68 11 0,68 19 0,72 27 0, 4 0,72 12 0,66 20 0,71 28 0, 5 0,66 13 0,63 21 0,67 29 0, 6 0,61 14 0,62 22 0,68 30 0, 7 0,68 15 0,66 23 0,67 31 0, 8 0,66 16 0,66 24 0,65 32 0, Для линейной круговой полиэдрали натуральных ресурсных k j1, k j1 1, j1 0, 1,, k прямоугольников горизонтальной формы при k 32 укладка угловым алгоритмом приведена на рисунке 2.50.

13x12 12x11 11x10 10x9 9x 8x7 7x6 6 4 3 24x 21x20 20x19 14x 28x27 15x 25x24 23x22 22x 16x 29x28 27x26 26x25 17x 18x 32x31 31x30 30x 19x Рис. 2.50. Укладка круговой линейной полиэдрали натуральных ресурсных прямоугольников горизонтальной формы угловым алгоритмом Эвристические меры ресурсных оболочек углового алгоритма для натуральных ресурсных прямоугольников горизонтальной формы приведены в таблице 2.18.

Таблица 2.18. Эвристические меры ресурсных оболочек углового алгоритма для натуральных ресурсных прямоугольников горизонтальной формы Эвристическая k Эвристическая k Эвристическая k мера мера мера 18 23 0,65 0,65 0, 19 24 0,66 0,65 0, 20 25 0,68 0,65 0, 21 26 0,68 0,64 0, 22 27 0,67 0,66 0, Отметим, что эвристические меры ресурсных оболочек углового алгоритма для натуральных ресурсных прямоугольников горизонтальной формы не 0,18.

превосходят значения Для линейной круговой полиэдрали натуральных ресурсных k j1 1, k j1, j1 0, 1,, k 2 при прямоугольников вертикальной формы k 32 укладка угловым алгоритмом приведена на рисунке 2.51.

17x18 16x17 15x16 14x15 13x14 12x13 11x12 10x11 9x 27x 23x24 22x23 18x 24x 19x 28x29 26x27 25x26 20x21 31x32 30x31 29x30 7x 21x 8x Рис. 2.51. Укладка круговой линейной полиэдрали натуральных ресурсных прямоугольников вертикальной формы угловым алгоритмом Эвристические меры ресурсных оболочек углового алгоритма для натуральных ресурсных прямоугольников вертикальной формы приведены в таблице 2.19.

Таблица 2.19. Эвристические меры ресурсных оболочек углового алгоритма для натуральных ресурсных прямоугольников вертикальной формы Эвристическая k Эвристическая k Эвристическая k мера мера мера 18 23 0,68 0,67 0, 19 24 0,71 0,65 0, 20 25 0,71 0,65 0, 21 26 0,70 0,63 0, 22 27 0,68 0,62 0, Отметим, что эвристические меры ресурсных оболочек углового алгоритма для натуральных ресурсных прямоугольников вертикальной формы не 0,21.

превосходят значения Таким образом, в настоящем параграфе предлагается и исследуется эвристический угловой алгоритм диспетчирования массивами заявок кругового типа. Приводится блок- схема углового алгоритма распределения процессорно временных ресурсов. Устанавливается полиномиальная трудомкость предложенного углового алгоритма. Для базовых примеров массивов заявок кругового типа: натуральных ресурсных квадратов k j1 k j1, j1 0, 1,, k 1 (равные требования временного и процессорного ресурсов a j1 b j1 ), натуральных ресурсных прямоугольников горизонтальной формы k j1, k j1 1, j1 0, 1,, k 2 (преимущественные требования временного ресурса a j1 b j1 ), натуральных ресурсных прямоугольников вертикальной формы k j1 1, k j1, j1 0, 1,, k 2 (преимущественные требования процессорного ресурса a j1 b j1 ) строятся объемлющие прямоугольники с вычислением ресурсных и эвристических мер. Указанные построения и вычисления сопоставляются с имеющимися в литературе оптимальными построениями ресурсных оболочек. Делаются выводы о качестве предложенного эвристического полиномиального углового алгоритма.

2.6. Алгоритм последовательных приближений Приведм и исследуем алгоритм последовательных приближений диспетчирования линейными круговыми полиэдралями ресурсных k a j1, b j1, b j1, a j1, j1 [135].

прямоугольников j1 10. На первом шаге определяем номер грани q1, делящей исходную полиэдраль на две части по соотношению равенства суммарных уровней q1 1 k b j1 2 b j1 0.

Y1 Вдоль линии вертикально суперпозируются j1 0 j1 q1 a j1, b j1, вдоль линии Y1 a0 вертикально ресурсные прямоугольники j1 k a j1, b j1 (рисунок 2.52).

суперпозируются ресурсные прямоугольники j1 q Y b(q1-1) 26x25 b(k-1) 13x a(k-1) a(q1-1)...

...

32x b(0) b(q1) 23x a(0) a(q1) 0 Y Рис. 2.52. Ресурсная оболочка первого шага Вычисляем эвристическую меру получаемой ресурсной оболочки с измерениями a0 aq1 - по горизонтали, H maxH1, H 2 - по вертикали, где q1 1 k b j1, b j1.

H1 H j1 0 j1 q 20. На втором шаге определяем номера граней q1, q2, делящие исходную полиэдраль на три части по соотношению равенства суммарных уровней q1 1 q2 1 k 1 k b j1 3 b j1 0, b j1 3 b j1 0.

Вдоль линии Y1 0 вертикально j1 0 j1 0 j1 q1 j1 q1 a j1, b j1, суперпозируются ресурсные прямоугольники вдоль линии j1 Y1 a0 вертикально суперпозируются ресурсные прямоугольники q 2 a j1, b j1 и вдоль линии Y1 a0 aq1 вертикально суперпозируются j1 q k a j1, b j1 (рисунок 2.53).

ресурсные прямоугольники j1 q Y b(k-1) 13x b(q1-1) 28x27 b(q2-1) 22x21 a(k-1) a(q2-1) a(q1-1)...

...

...

b(0) 32x31 b(q1) 27x26 b(q2) 21x a(q1) a(0) a(q2) Y Рис. 2.53. Ресурсная оболочка второго шага Вычисляем эвристическую меру получаемой ресурсной оболочки с a0 aq1 aq2 - по горизонтали, H maxH1, H 2, H3- по измерениями q1 1 q 2 1 k b j1, b j1, b j1.

H1 H2 H вертикали, где Сравниваем j1 0 j1 q1 j1 q эвристические меры настоящего и предыдущего шага. Если эвристическая мера стала больше, то предыдущее значение принимается за окончательный результат.

Иначе выполняем следующий шаг.

30. На третьем шаге определяем номера граней q1, q2, q3, делящие исходную полиэдраль на четыре части по соотношению равенства суммарных уровней q3 q1 1 q 2 k 1 k 1 k b j1 4 b j1 0, b j1 4 b j1 0, b j1 4 b j1 0.

1 1 Вдоль j1 0 j1 0 j1 q1 j1 0 j1 q 2 j1 Y1 линии вертикально суперпозируются ресурсные прямоугольники q1 a j1, b j1, вдоль линии Y1 a0 вертикально суперпозируются ресурсные j1 q 2 a j1, b j1, вдоль линии Y1 a0 aq1 вертикально прямоугольники j1 q q3 a j1, b j суперпозируются ресурсные прямоугольники и вдоль линии j1 q Y1 a0 aq1 aq2 вертикально суперпозируются ресурсные прямоугольники k a j1, b j1 (рисунок 2.54).

j1 q Y 26x b(q2-1) 20x b(q3-1) b(k-1) 13x b(q1-1) 30x a(q3-1) a(k-1) a(q2-1) a(q1-1)...

...

...

...

b(0) 32x31 b(q1) 29x28 b(q2) 23x22 19x18 b(q3) a(q1) a(0) a(q2) a(q3) Y Рис. 2.54. Ресурсная оболочка третьего шага Вычисляем эвристическую меру получаемой ресурсной оболочки с a0 aq1 aq2 aq3 измерениями по горизонтали, q1 1 q 2 b j1, b j1, H maxH1, H 2, H3, H 4 - H1 H по вертикали, где j1 0 j1 q q3 1 k b j1, b j1.

H3 H4 Сравниваем эвристические меры настоящего и j1 q 2 j1 q предыдущего шага. Если эвристическая мера стала больше, то предыдущее значение принимается за окончательный результат. Иначе выполняем следующий шаг.

Проиллюстрируем алгоритм последовательных приближений на линейной k k j1 k j1.

полиэдрали натуральных ресурсных квадратов j1 На первом шаге соотношение равенства суммарных уровней принимает вид q 1 k q k 1 k H q k j1 k j1, или j1 j1.

j1 0 j1 q j1 k q 1 j1 Высота каждой полиэдрали должна равняться половине суммы высот всех k q k q 1 k k 1.

ресурсных квадратов Решая квадратное уравнение, k k получаем q 2 2k 1q 0, 2k 1 2k 12 4 k k 1 2k 1 k 12 k q1, 2.

2 65 В частности, при k 32 имеем q1, 2 q 10. Построения первого шага приведены на рисунке 2.55.

24 25 275 Рис. 2.55. Первый шаг алгоритма последовательных приближений Эвристическая мера объемлющего ресурсного прямоугольника первого шага равна 2,78. Построения второго шага приведены на рисунке 2.56.

19 27 21 23 32 Рис. 2.56. Второй шаг алгоритма последовательных приближений Эвристическая мера объемлющего ресурсного прямоугольника второго шага равна 1,07. Так как эвристическая мера уменьшилась, то переходим к следующему шагу. Построения третьего шага приведены на рисунке 2.57.

17 24 18 29 19 30 20 140 32 28 Рис. 2.57. Третий шаг алгоритма последовательных приближений Эвристическая мера объемлющего ресурсного прямоугольника третьего шага равна 0,68. Так как эвристическая мера уменьшилась, то переходим к следующему шагу. Построения четвртого шага приведены на рисунке 2.58.

21 26 22 16 17 115 31 32 29 25 20 Рис. 2.58. Четвртый шаг алгоритма последовательных приближений Эвристическая мера объемлющего ресурсного прямоугольника четвртого шага равна 0,60. Так как эвристическая мера уменьшилась, то переходим к следующему шагу. Построения пятого шага приведены на рисунке 2.59.

23 30 19 27 24 20 98 31 28 25 32 29 26 22 18 Рис. 2.59. Пятый шаг алгоритма последовательных приближений Эвристическая мера объемлющего ресурсного прямоугольника пятого шага равна 0,67. Так как эвристическая мера увеличилась, то результат предыдущего шага считаем наилучшим. Таким образом, эвристическая мера алгоритма последовательных приближений при упорядочивании 32- х натуральных ресурсных квадратов имеет значение 0,60.

Сравним качество приведнного алгоритма последовательных приближений с оптимальной укладкой в объемлющий прямоугольник минимальной площади, полученной в работах [66-68,70,71]. Приведм в таблице 2.20 результаты размещения алгоритмом последовательных приближений и оптимальным алгоритмами для последовательности натуральных ресурсных квадратов k j1 k j1, j1 0, 1,, k 1. Здесь L- горизонтальное и H- вертикальное измерения объемлющего прямоугольника алгоритма последовательных приближений, Lopt, H opt - соответствующие измерения оптимального алгоритма, - погрешность площади ресурсной оболочки в % относительно оптимального значения.

Таблица 2.20. Сравнение алгоритма последовательных приближений и оптимального алгоритма,%,% Lopt, H opt Lopt, H opt L, H L, H k k 39 1 11 0,0 17 5242 21, 1 2 32 0,0 18 5646 20, 31 47 3 53 0,0 19 5754 23, 3 34 4 76 20,0 20 6157 20, 5 5 89 20,0 21 6566 28, 5 12 38 9 11 39 6 1011 11,1 22 6670 20, 64 7 1215 16,9 23 7074 19, 11 14 15 56 8 1815 28,6 24 7478 17, 9 2117 19,0 25 9172 18, 15 20 43 10 2321 19,3 26 9675 15, 15 27 70 19 11 2624 21,6 27 10178 13, 12 2928 21,7 28 10691 24, 23 29 22 13 3925 16,6 29 10798 22, 14 3239 20,6 30 112102 20, 23 45 15 3542 16,2 31 117106 23, 23 55 27 16 3846 15,6 32 120115 20, Заметим, что погрешность не превосходит что является 28,6%, подтверждением целесообразности использования предложенного алгоритма последовательных приближений при диспетчировании процессорно- временными ресурсами.

Эвристические меры ресурсных оболочек алгоритма последовательных приближений приведены в таблице 2.21.

Таблица 2.21. Эвристические меры ресурсных оболочек алгоритма последовательных приближений Эвристическая k Эвристическая k Эвристическая k Эвристическая k мера мера мера мера 1 0,50 9 0,65 17 0,64 25 0, 2 0,70 10 0,63 18 0,63 26 0, 3 0,68 11 0,62 19 0,62 27 0, 4 0,72 12 0,63 20 0,61 28 0, 5 0,66 13 0,71 21 0,65 29 0, 6 0,61 14 0,64 22 0,61 30 0, 7 0,68 15 0,61 23 0,60 31 0, 8 0,68 16 0,61 24 0,59 32 0, Отметим, что эвристические меры ресурсных оболочек алгоритма 0,22.

последовательных приближений не превосходят значения Введм и исследуем также алгоритм последовательных приближений с параллельной структурой.

10. На первом шаге по соотношению равенства суммарных уровней q1 1 k b j1 b j1 0 определяем номер грани q1, делящей исходную полиэдраль.

j1 0 j1 q Вдоль линии Y1 0 вертикально суперпозируются ресурсные прямоугольники q1 a j1, b j1, вдоль линии Y1 a0 вертикально суперпозируются ресурсные j1 k a j1, b j1 (рисунок 2.60).

прямоугольники j1 q Y b(q1-1) 26x25 b(k-1) 13x a(k-1) a(q1-1)...

...

32x b(0) b(q1) 23x a(0) a(q1) 0 Y Рис. 2.60. Ресурсная оболочка первого шага Вычисляем эвристическую меру получаемой ресурсной оболочки с измерениями a0 aq1 - по горизонтали, H maxH1, H 2 - по вертикали, где q1 1 k b j1, H 2 b j1.

H j1 0 j1 q 20. На втором шаге для каждой из двух вертикальных полиэдралей предыдущего шага производим аналогичные действия. А именно, по q 2 1 q1 b j1 b j1 соотношению равенства суммарных уровней определяем j1 0 j1 q номер грани q2, делящей первую вертикальную полиэдраль первого шага q1 a j1, b j1. По соотношению равенства суммарных уровней j1 q3 1 k b j1 b j1 0 определяем номер грани q3, делящей вторую вертикальную j1 q1 j1 q k a j1, b j1.

полиэдраль первого шага j1 q Y1 Вдоль линии вертикально суперпозируются ресурсные q2 a j1, b j1, Y1 a прямоугольники вдоль линии вертикально j1 q1 a j1, b j1, суперпозируются ресурсные прямоугольники вдоль линии j1 q Y1 a0 aq2 вертикально суперпозируются ресурсные прямоугольники q3 a j1, b j1 Y1 a0 aq2 aq и вдоль линии вертикально j1 q k a j1, b j1 (рисунок 2.61).

суперпозируются ресурсные прямоугольники j1 q Y b(q1-1) 26x25 b(k-1) 13x 20x19 a(k-1) b(q3-1) b(q2-1) a(q1-1) 30x a(q2-1) a(q3-1)...

...

...

...

b(0) 32x31 b(q2) 29x28 b(q1) 23x22 19x18 b(q3) a(q2) a(0) a(q1) a(q3) Y Рис. 2.61. Ресурсная оболочка второго шага Вычисляем эвристическую меру получаемой ресурсной оболочки с a0 aq2 aq1 aq3 измерениями по горизонтали, q 2 1 q1 b j1, b j1, H maxH1, H 2, H3, H 4 - H1 H по вертикали, где j1 q j1 q3 1 k b j1, b j1.

H3 H4 Сравниваем эвристические меры настоящего и j1 q1 j1 q предыдущего шага. Если эвристическая мера стала больше, то предыдущее значение принимается за окончательный результат. Иначе выполняем следующий шаг.

30. На третьем шаге для каждой из четырх вертикальных полиэдралей предыдущего шага производим аналогичные действия. А именно, по q 4 1 q 2 b j1 b j1 соотношению равенства суммарных уровней определяем j1 0 j1 q номер грани q4, делящей первую вертикальную полиэдраль предыдущего шага q 2 a j1, b j1. По соотношению равенства суммарных уровней j1 q5 1 q1 b j1 b j1 0 определяем номер грани q5, делящей вторую вертикальную j1 q 2 j1 q q1 a j1, b j1.

полиэдраль предыдущего шага По соотношению равенства j1 q q6 1 q3 b j1 b j1 суммарных уровней определяем номер грани q6, делящей j1 q1 j1 q q3 a j1, b j1.

третью вертикальную полиэдраль предыдущего шага По j1 q q7 1 k b j1 b j1 соотношению равенства суммарных уровней определяем j1 q3 j1 q номер грани q7, делящей четвртую вертикальную полиэдраль предыдущего шага k a j1, b j1.

j1 q Y1 Вдоль линии вертикально суперпозируются ресурсные q 4 a j1, b j1, Y1 a прямоугольники вдоль линии вертикально j1 q 2 a j1, b j1, суперпозируются ресурсные прямоугольники вдоль линии j1 q Y1 a0 aq4 вертикально суперпозируются ресурсные прямоугольники q5 a j1, b j1, Y1 a0 aq4 aq вдоль линии вертикально j1 q q1 a j1, b j1, суперпозируются ресурсные прямоугольники вдоль линии j1 q Y1 a0 aq4 aq2 aq5 вертикально суперпозируются ресурсные q6 a j1, b j1, прямоугольники вдоль линии j1 q Y1 a0 aq4 aq2 aq5 aq1 вертикально суперпозируются ресурсные q3 a j1, b j1, прямоугольники вдоль линии j1 q Y1 a0 aq4 aq2 aq5 aq1 aq6 вертикально суперпозируются q7 a j1, b j ресурсные прямоугольники и вдоль линии j1 q Y1 a0 aq4 aq2 aq5 aq1 aq6 aq3 вертикально суперпозируются k a j1, b j1 (рисунок 2.62).

ресурсные прямоугольники j1 q Y q3-1 q - 20x19 15x b(q4-1) 31x30 b(q2-1) b(q1-1) 13x 30x29 26x25 k- b(q5-1) 27x a(q1-1) 21x q6- a(q4-1) a(q2-1) a(q5-1)...............

...

......

b(q4) b(0) 32x31 30x30 b(q2) b(q5) 29x28 26x26 23x22 20x20 19x q1 q6 q3 q 14x a(0) a(q4) a(q2) a(q5) Y Рис. 2.62. Ресурсная оболочка третьего шага Вычисляем эвристическую меру получаемой ресурсной оболочки с a0 aq4 aq2 aq5 aq1 aq6 aq3 aq7 измерениями по H maxH1, H 2, H3, H 4, H5, H 6, H 7, H8- по вертикали, горизонтали, где q5 1 q6 q 4 1 q 2 1 q1 b j1, b j1, b j1, b j1, b j1, H1 H2 H3 H4 H j1 0 j1 q 4 j1 q 2 j1 q5 j1 q q3 1 q7 1 k b j1, H 7 b j1, H 8 b j1.

H6 Сравниваем эвристические меры j1 q6 j1 q3 j1 q настоящего и предыдущего шага. Если эвристическая мера стала больше, то предыдущее значение принимается за окончательный результат. Иначе выполняем следующий шаг.

Обратим внимание, что вначале ресурсная оболочка вытянута по вертикали и эвристическая мера велика (сказывается влияние величины асимметрии). С каждым шагом ресурсная оболочка вс более принимает горизонтальную форму и на каком- то шаге станет вытянутой по горизонтали вновь со значительной эвристической мерой. Следовательно, на каком- то промежуточном шаге достигается наименьшее значение эвристической меры.

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

Проиллюстрируем алгоритм последовательных приближений с параллельной структурой на линейной полиэдрали натуральных ресурсных квадратов при k 32. Построения первого шага совпадают с соответствующими построениями первого шага алгоритма последовательных приближений на рис.4 с эвристической мерой объемлющего ресурсного прямоугольника первого шага соответственно равной 2,78. Построения второго шага приведены на рисунке 2.63.

23 29 24 150 19 31 32 27 Рис. 2.63. Второй шаг упорядочивания ресурсных квадратов Эвристическая мера объемлющего ресурсного прямоугольника второго шага равна 0,76. Так как эвристическая мера уменьшилась, то переходим к следующему шагу. Построения третьего шага приведены на рисунке 2.64.

23 31 12 87 26 24 21 32 30 27 25 22 19 15 Рис. 2.64. Третий шаг упорядочивания ресурсных квадратов Эвристическая мера объемлющего ресурсного прямоугольника третьего шага равна 1,06. Так как эвристическая мера увеличилась, то результат предыдущего шага считаем наилучшим. Таким образом, эвристическая мера алгоритма последовательных приближений с параллельной структурой при упорядочивании 32- х натуральных ресурсных квадратов имеет значение 0,76.


Сравним качество приведнного алгоритма последовательных приближений с параллельной структурой с оптимальной укладкой в объемлющий прямоугольник минимальной площади, полученной в работах [66-68,70,71].

Приведм в таблице 2.22 результаты размещения алгоритмом последовательных приближений с параллельной структурой и оптимальным алгоритмами для последовательности натуральных ресурсных квадратов k j1 k j1, j1 0, 1,, k 1. Здесь L- горизонтальное и H- вертикальное измерения объемлющего прямоугольника алгоритма последовательных приближений с параллельной структурой, Lopt, H opt - соответствующие измерения оптимального алгоритма, - погрешность площади ресурсной оболочки в % относительно оптимального значения.

Таблица 2.22. Сравнение алгоритма последовательных приближений с параллельной структурой и оптимального алгоритма,%,% Lopt, H opt Lopt, H opt L, H L, H k k 39 11 1 0,0 17 21, 1 23 2 32 0,0 18 20, 31 47 3 53 0,0 19 23, 3 34 4 76 20,0 20 20, 5 5 89 20,0 21 24, 5 12 38 9 11 39 6 1011 11,1 22 20, 64 7 1215 16,9 23 19, 11 14 15 56 8 1321 30,0 24 17, 9 1524 20,0 25 28, 15 20 43 10 1728 17,5 26 24, 15 27 70 19 27 11 3421 39,2 27 20, 12 3523 20,7 28 17, 23 29 22 38 13 3925 16,6 29 17, 14 4328 16,3 30 16, 23 45 15 4536 28,1 31 26, 23 55 27 16 4939 26,4 32 96150 25, Заметим, что погрешность не превосходит 39,2%, что является подтверждением целесообразности использования предложенного алгоритма последовательных приближений с параллельной структурой при диспетчировании процессорно- временными ресурсами.

Эвристические меры ресурсных оболочек алгоритма последовательных приближений с параллельной структурой приведены в таблице 2.23.

Таблица 2.23. Эвристические меры ресурсных оболочек алгоритма последовательных приближений с параллельной структурой Эвристическая k Эвристическая k Эвристическая k Эвристическая k мера мера мера мера 1 0,50 9 0,77 17 0,64 25 0, 2 0,70 10 0,78 18 0,63 26 0, 3 0,68 11 0,87 19 0,62 27 0, 4 0,72 12 0,73 20 0,61 28 0, 5 0,66 13 0,71 21 0,63 29 0, 6 0,61 14 0,70 22 0,61 30 0, 7 0,68 15 0,69 23 0,60 31 0, 8 0,83 16 0,67 24 0,59 32 0, Отметим, что эвристические меры ресурсных оболочек алгоритма последовательных приближений с параллельной структурой не превосходят 0,37.

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

Рис. 2.65. Сравнение погрешностей алгоритмов последовательных приближений Графики эвристической меры ресурсных оболочек обоих версий разработанных алгоритмов для натуральных ресурсных квадратов показаны на рисунке 2.66.

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

Для линейной круговой полиэдрали натуральных ресурсных k j1, k j1 1, j1 0, 1,, k прямоугольников горизонтальной формы при k 32 приведм соответствующие построения алгоритмом последовательных приближений по высоте с параллельной структурой. Построения первого шага показаны на рисунке 2.67.

7x 24x23 8x 9x 10x 25x 11x 12x 26x25 13x 14x 27x26 15x 16x 28x 253 17x 18x 29x 19x 30x29 20x 21x 31x 22x 32x 23x Рис. 2.67. Первый шаг алгоритма последовательных приближений по высоте для ресурсных прямоугольников горизонтальной формы Эвристическая мера объемлющего ресурсного прямоугольника первого шага равна 2,43. Построения второго шага приведены на рисунке 2.68.

17x 24x23 18x17 29x28 7x 8x 19x 25x24 9x 10x 30x29 20x19 11x 133 26x 12x 21x 13x 31x 27x 14x 22x 15x 32x31 28x27 23x22 16x Рис. 2.68. Второй шаг алгоритма последовательных приближений по высоте для ресурсных прямоугольников горизонтальной формы Эвристическая мера объемлющего ресурсного прямоугольника второго шага равна 0,66. Так как эвристическая мера уменьшилась, то переходим к следующему шагу. Построения третьего шага приведены на рисунке 2.69.

17x 24x23 12x 21x20 13x 31x30 18x 29x28 27x26 25x 72 7x 14x 22x21 8x 19x 9x 15x 32x31 30x29 28x27 10x 26x25 23x22 20x19 16x15 11x Рис. 2.69. Третий шаг алгоритма последовательных приближений по высоте для ресурсных прямоугольников горизонтальной формы Эвристическая мера объемлющего ресурсного прямоугольника третьего шага равна 1,21. Так как эвристическая мера увеличилась, то результат предыдущего шага считаем наилучшим. Таким образом, эвристическая мера алгоритма последовательных приближений по высоте с параллельной структурой при упорядочивании линейной круговой полиэдрали 32- х натуральных ресурсных прямоугольников горизонтальной формы имеет значение 0,66.

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

Таблица 2.24. Эвристические меры ресурсных оболочек алгоритма последовательных приближений по высоте для прямоугольников горизонтальной формы Эвристическая k Эвристическая k Эвристическая k мера мера мера 18 0,66 23 0,61 28 0, 19 0,65 24 0,60 29 0, 20 0,63 25 0,59 30 0, 21 0,61 26 0,64 31 0, 22 0,63 27 0,64 32 0, Отметим, что эвристические меры ресурсных оболочек алгоритма последовательных приближений по высоте с параллельной структурой для 0,16.

прямоугольников горизонтальной формы не превосходят значения Исследуем алгоритм последовательных приближений по протяжнности с параллельной структурой. Для линейной круговой полиэдрали натуральных k j1, k j1 1, ресурсных прямоугольников горизонтальной формы j1 0, 1,, k 2 при k 32 приведм соответствующие построения алгоритмом последовательных приближений по протяжнности с параллельной структурой.

Построения первого шага показаны на рисунке 2.70.

23x22 22x21 21x20 20x19 19x18 18x17 17x16 16x15 15x14 14x13 13x12 12x11 11x10 10x9 9x 8x7 7x6 6 5 4 3 32x31 31x30 30x29 29x28 28x27 27x26 26x25 25x24 24x Рис. 2.70. Первый шаг алгоритма последовательных приближений по протяжнности для ресурсных прямоугольников горизонтальной формы Эвристическая мера объемлющего ресурсного прямоугольника первого шага равна 2,93. Построения второго шага приведены на рисунке 2.71.

16x15 15x14 14x13 13x12 12x11 11x10 10x9 9x 8x7 7x6 6 5 4 3 23x22 22x21 21x20 20x19 19x18 18x17 17x 95 28x27 27x26 26x25 25x24 24x 32x31 31x30 30x29 29x Рис. 2.71. Второй шаг алгоритма последовательных приближений по протяжнности для ресурсных прямоугольников горизонтальной формы Эвристическая мера объемлющего ресурсного прямоугольника второго шага равна 0,7. Так как эвристическая мера уменьшилась, то переходим к следующему шагу. Построения третьего шага приведены на рисунке 2.72.

11x10 10x9 9x8 8x 7x6 6 5 4 3 16x15 15x14 14x13 13x12 12x 20x19 19x18 18x17 17x 23x22 22x21 21x 26x25 25x24 24x 28x27 27x 30x29 29x 32x31 31x Рис. 2.72. Третий шаг алгоритма последовательных приближений по протяжнности для ресурсных прямоугольников горизонтальной формы Эвристическая мера объемлющего ресурсного прямоугольника третьего шага равна 1,10. Так как эвристическая мера увеличилась, то результат предыдущего шага считаем наилучшим. Таким образом, эвристическая мера алгоритма последовательных приближений по протяжнности с параллельной структурой при упорядочивании линейной круговой полиэдрали 32- х натуральных ресурсных прямоугольников горизонтальной формы имеет значение 0,7.

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

Таблица 2.25. Эвристические меры ресурсных оболочек алгоритма последовательных приближений по протяжнности для прямоугольников горизонтальной формы Эвристическая k Эвристическая k Эвристическая k мера мера мера 18 0,63 23 0,61 28 0, 19 0,63 24 0,60 29 0, 20 0,61 25 0,67 30 0, 21 0,65 26 0,67 31 0, 22 0,63 27 0,65 32 0, Отметим, что эвристические меры ресурсных оболочек алгоритма последовательных приближений по протяжнности с параллельной структурой 0,2.

для прямоугольников горизонтальной формы не превосходят значения Для линейной круговой полиэдрали натуральных ресурсных k j1 1, k j1, j1 0, 1,, k 2 при прямоугольников вертикальной формы k 32 приведм соответствующие построения алгоритмом последовательных приближений по высоте с параллельной структурой. Построения первого шага показаны на рисунке 2.73.

7x 23x 8x 9x 24x25 10x 11x 12x 25x 13x 26x27 14x 15x 275 27x 16x 17x 28x 18x 29x30 19x 20x 30x 21x 31x 22x Рис. 2.73. Первый шаг алгоритма последовательных приближений по высоте для ресурсных прямоугольников вертикальной формы Эвристическая мера объемлющего ресурсного прямоугольника первого шага равна 2,93. Построения второго шага приведены на рисунке 2.74.

16x17 23x24 17x18 28x29 7x 18x19 8x 24x 9x 29x30 19x20 10x 140 25x26 11x 20x21 12x 30x 26x27 13x 21x 14x 31x32 27x28 22x23 15x Рис. 2.74. Второй шаг алгоритма последовательных приближений по высоте для ресурсных прямоугольников вертикальной формы Эвристическая мера объемлющего ресурсного прямоугольника второго шага равна 0,7. Так как эвристическая мера уменьшилась, то переходим к следующему шагу. Построения третьего шага приведены на рисунке 2.75.

16x 23x24 11x12 20x21 12x 17x 30x31 28x29 26x27 24x25 13x 75 21x22 7x 18x 8x 14x 31x32 29x30 9x 27x28 25x26 22x23 19x 15x16 10x Рис. 2.75. Третий шаг алгоритма последовательных приближений по высоте для ресурсных прямоугольников вертикальной формы Эвристическая мера объемлющего ресурсного прямоугольника третьего шага равна 1,10. Так как эвристическая мера увеличилась, то результат предыдущего шага считаем наилучшим. Таким образом, эвристическая мера алгоритма последовательных приближений по высоте с параллельной структурой при упорядочивании линейной круговой полиэдрали 32- х натуральных ресурсных прямоугольников вертикальной формы имеет значение 0,7.


Эвристические меры ресурсных оболочек алгоритма последовательных приближений по высоте с параллельной структурой для натуральных ресурсных прямоугольников вертикальной формы приведены в таблице 2.26.

Таблица 2.26. Эвристические меры ресурсных оболочек алгоритма последовательных приближений по высоте для прямоугольников вертикальной формы Эвристическая k Эвристическая k Эвристическая k мера мера мера 18 0,63 23 0,61 28 0, 19 0,63 24 0,60 29 0, 20 0,61 25 0,67 30 0, 21 0,65 26 0,67 31 0, 22 0,63 27 0,65 32 0, Отметим, что эвристические меры ресурсных оболочек алгоритма последовательных приближений по высоте с параллельной структурой для 0,2.

прямоугольников вертикальной формы не превосходят значения Исследуем алгоритм последовательных приближений по протяжнности с параллельной структурой. Для линейной круговой полиэдрали натуральных k j1 1, k j1, ресурсных прямоугольников вертикальной формы j1 0, 1,, k 2 при k 32 приведм соответствующие построения алгоритмом последовательных приближений по протяжнности с параллельной структурой.

Построения первого шага показаны на рисунке 2.76.

22x23 21x22 20x21 19x20 18x19 17x18 16x17 15x16 14x15 13x14 12x13 11x12 10x11 9x 8x9 7x8 6 54 3 31x32 30x31 29x30 28x29 27x28 26x27 25x26 24x25 23x Рис. 2.76. Первый шаг алгоритма последовательных приближений по протяжнности для ресурсных прямоугольников вертикальной формы Эвристическая мера объемлющего ресурсного прямоугольника первого шага равна 2,43. Построения второго шага приведены на рисунке 2.77.

15x16 14x15 13x14 12x13 11x12 10x11 9x 8x9 7x8 6 54 3 22x23 21x22 20x21 19x20 18x19 17x18 16x 31x32 30x31 29x30 28x 27x28 26x27 25x26 24x25 23x Рис. 2.77. Второй шаг алгоритма последовательных приближений по протяжнности для ресурсных прямоугольников вертикальной формы Эвристическая мера объемлющего ресурсного прямоугольника второго шага равна 0,66. Так как эвристическая мера уменьшилась, то переходим к следующему шагу. Построения третьего шага приведены на рисунке 2.78.

10x11 9x10 8x 7x8 6 54 3 15x16 14x15 13x14 12x13 11x 19x20 18x19 17x18 16x 22x23 21x22 20x 31x32 30x 29x30 28x 27x28 26x 25x26 24x25 23x Рис. 2.78. Третий шаг алгоритма последовательных приближений по протяжнности для ресурсных прямоугольников вертикальной формы Эвристическая мера объемлющего ресурсного прямоугольника третьего шага равна 1,21. Так как эвристическая мера увеличилась, то результат предыдущего шага считаем наилучшим. Таким образом, эвристическая мера алгоритма последовательных приближений по протяжнности с параллельной структурой при упорядочивании линейной круговой полиэдрали 32- х натуральных ресурсных прямоугольников вертикальной формы имеет значение 0,66.

Эвристические меры ресурсных оболочек алгоритма последовательных приближений по протяжнности с параллельной структурой для натуральных ресурсных прямоугольников вертикальной формы приведены в таблице 2.27.

Отметим, что эвристические меры ресурсных оболочек алгоритма последовательных приближений по протяжнности с параллельной структурой 0,16.

для прямоугольников вертикальной формы не превосходят значения Таблица 2.27. Эвристические меры ресурсных оболочек алгоритма последовательных приближений по протяжнности для прямоугольников вертикальной формы Эвристическая k Эвристическая k Эвристическая k мера мера мера 18 0,66 23 0,61 28 0, 19 0,65 24 0,60 29 0, 20 0,63 25 0,59 30 0, 21 0,61 26 0,64 31 0, 22 0,63 27 0,64 32 0, Таким образом, в настоящем параграфе предлагается и исследуется эвристический алгоритм последовательных приближений диспетчирования массивами заявок кругового типа. Устанавливается полиномиальная трудомкость предложенного алгоритма последовательных приближений. Для базовых примеров массивов заявок кругового типа: натуральных ресурсных k j1 k j1, j1 0, 1,, k 1 (равные требования временного и квадратов процессорного ресурсов a j1 b j1 ), натуральных ресурсных прямоугольников горизонтальной формы k j1, k j1 1, j1 0, 1,, k 2 (преимущественные требования временного ресурса a j1 b j1 ), натуральных ресурсных прямоугольников вертикальной формы k j1 1, k j1, j1 0, 1,, k (преимущественные требования процессорного ресурса a j1 b j1 ) строятся объемлющие прямоугольники с вычислением ресурсных и эвристических мер.

Указанные построения и вычисления сопоставляются с имеющимися в литературе оптимальными построениями ресурсных оболочек. Делаются выводы о качестве предложенного эвристического полиномиального алгоритма последовательных приближений.

2.7. Сравнительный анализ полиномиальных алгоритмов диспетчирования Проведм сравнительный анализ разработанных и исследованных полиномиальных алгоритмов диспетчирования линейными круговыми полиэдралями [78]. Графики погрешностей по сравнению с оптимальным алгоритмом для натуральных ресурсных квадратов приведены на рисунке 2.79.

Рис. 2.79. Сравнение полиномиальных алгоритмов Как было показано ранее, погрешность начально- кольцевого алгоритма не превосходит 31%, погрешность уровневого алгоритма не превосходит 33%, погрешность углового алгоритма не превосходит 42%, погрешность алгоритма последовательных приближений не превосходит 29% и погрешность однородного алгоритма не превосходит 21%.

Оптимальная укладка в объемлющий квадрат минимальной площади получена в работах [67,70]. Сравнение эвристических мер ресурсных оболочек оптимальной укладки в объемлющий прямоугольник и квадрат минимальной площади дано на рисунке 2.80.

Рис. 2.80. Эвристические меры ресурсных оболочек оптимальных алгоритмов укладки в прямоугольник и квадрат Графики эвристической меры ресурсных оболочек разработанных и исследованных полиномиальных алгоритмов диспетчирования линейными круговыми полиэдралями для натуральных ресурсных квадратов показаны на рисунке 2.81.

Рис. 2.81. Эвристические меры ресурсных оболочек полиномиальных алгоритмов диспетчирования линейными круговыми полиэдралями Графики эвристической меры ресурсных оболочек разработанных и исследованных алгоритмов: начально- кольцевого, углового, уровневого, алгоритма последовательных приближений для натуральных ресурсных прямоугольников горизонтальной формы приведены на рисунке 2.82, для вертикальной формы- на рисунке 2.83.

Рис. 2.82. Эвристические меры ресурсных оболочек полиномиальных алгоритмов диспетчирования ресурсными прямоугольниками горизонтальной формы Рис. 2.83. Эвристические меры ресурсных оболочек полиномиальных алгоритмов диспетчирования ресурсными прямоугольниками вертикальной формы Таким образом, полиномиальные алгоритмы распределения процессорно временных ресурсов: начально- кольцевой, уровневый, угловой и последовательных приближений могут быть рекомендованы для использования в диспетчерах Grid- систем.

Рассмотрим вопрос определения прогнозных значений параметров квадратной ресурсной рамки, в которую может быть локализован массив заявок k max b j1 a j1 b j кругового типа. В случае, когда максимальная 0 j1 k 1 j1 высота ресурсного прямоугольника меньше среднересурсной величины граней и k max a j1 Ak a j1 максимальная длина основания меньше 0 j1 k 1 j1 среднересурсной величины оснований линейной полиэдрали, параметры k a j1 b j1. В случае, когда квадратной ресурсной рамки имеют величину j1 k max b j1 a j1 b j1 максимальная высота ресурсного прямоугольника 0 j1 k 1 j1 max a j1 Ak, параметры меньше среднересурсной величины граней и 0 j1 k k 1 k a j1 b j1 a j1.

квадратной ресурсной рамки имеют величину j1 0 j1 Значение определяется в результате статистического моделирования.

В качестве базового примера линейной круговой полиэдрали с ограничением на максимальную высоту и максимальную длину основания j1 j1, j1 1, 2,, k.

ресурсных прямоугольников, исследуем массив k k k k j j1 j Действительно,. Соответственно, j1 1 j1 k k 1 k 1 k k 1 k j1 k. Следовательно,. Видим, что max 1 j1 k 2 k 2 при k 3 и ограничение на максимальную высоту выполняется. Покажем, что также выполняется ограничение на максимальную длину основания. Сумма длин Ak оснований ресурсных прямоугольников определяется выражением k k Ak j1 j1 k k j1 k k 1 xdx k 2. Соответственно, k k j1 1 j1 1 Ak k Ak при k 3. Для квадратной ресурсной рамки с k,и k k, значение и % погрешности относительно величиной стороны для 2 j1 j1, j1 1, 2,, k, в случае локализации начально- кольцевым массива алгоритмом, приведены в таблице 2.28.

Таблица 2.28. Значение и % погрешности для массива j1 j1, j1 1, 2,, k k % k % k k 2 10 7 1 12,5 22 16 3 15, 11 8 1 11,1 23 17 3 15, 12 8 2 20,0 24 17 3 15, 13 9 3 25,0 25 18 4 18, 14 10 3 23,1 26 19 3 13, 15 11 2 15,4 27 19 3 13, 16 12 2 14,3 28 20 2 9, 17 12 3 20,0 29 21 2 8, 18 13 2 13,3 30 21 3 12, 19 14 1 6,7 31 22 3 12, 20 14 1 6,7 32 23 3 11, 21 15 1 6, Видим, что погрешность не превосходит 25%, что можно считать приемлемым прогнозом.

В качестве базового примера линейной круговой полиэдрали с ограничением на максимальную высоту и максимальной длиной основания больше среднересурсной величины оснований линейной полиэдрали рассмотрим массив натуральных ресурсных квадратов k j1 k j1, j1 0, 1,, k 1.

Действительно, сумма длин оснований натуральных ресурсных квадратов k k k 1 k Ak k j1 j Ak определяется выражением.

j1 0 j1 k k 1 k Соответственно, как показано выше,. Видим, что 2 max k j1 k и k Ak при k 2.

0 j1 k Покажем, что ограничение на максимальную высоту выполняется. А k k 1 2k k 1 k k j1 j именно,. Следовательно, j1 0 j1 k k 1 2k 1 k2 k при k 2.

,и k 3 3 k2 k Для квадратной ресурсной рамки с величиной стороны в случае 3 локализации начально- кольцевым алгоритмом (таблица 2.4) прогноз оказывается точным.

Значение и % погрешности превышения величины стороны ресурсной k j1 k j1, j1 0, 1,, k 1, в случае локализации рамки для массива начально- кольцевым алгоритмом, приведены в таблице 2.29, из которой видно, что погрешность не превосходит 15%.

Таблица 2.29. Значение и % погрешности для массива k j1 k j1, j1 0, 1,, k k % k % 3 k k k2 k 2 3 9 17 7 2 9,1 21 58 15 4 5, 10 20 7 2 8,0 22 62 16 5 6, 11 22 8 2 7,1 23 66 17 6 7, 12 25 9 3 9,7 24 70 17 6 7, 13 29 10 5 14,7 25 74 18 7 8, 14 32 10 5 13,5 26 79 19 7 7, 15 35 11 3 7,0 27 83 19 3 3, 16 39 12 3 6,3 28 88 20 3 2, 17 42 12 2 3,8 29 92 21 3 2, 18 46 13 2 3,5 30 97 22 3 2, 19 50 14 3 4,9 31 102 22 3 2, 20 54 14 3 4,6 32 107 23 4 3, Рассмотрим линейную круговую полиэдраль натуральных ресурсных k j1, k j1 1, j1 0, 1,, k 2 с прямоугольников горизонтальной формы ограничением на максимальную высоту и максимальной длиной основания больше среднересурсной величины оснований линейной полиэдрали.

Действительно, сумма длин оснований натуральных ресурсных прямоугольников Ak горизонтальной формы определяется выражением k k k 2 k Ak k j1 j1 2 1. Соответственно, как показано выше, j1 0 j1 k k 1 k k j1 k и k Ak при k 2. Покажем, 1. Видим, что max 0 j1 k 2 что ограничение на максимальную высоту выполняется. А именно, k 2 k 2 k k k j1 k j1 1 k j1 k j1 j12 j j1 0 j1 0 j1 2 j1.

k k 1 2k 1 k k 1 1.

3 k k 1 2k k2 k при k 2.

,и k Следовательно, 3 3 k2 k Для квадратной ресурсной рамки с величиной стороны в случае 3 локализации начально- кольцевым алгоритмом параграфа 2.2 прогноз также оказывается точным. Значение и % погрешности превышения величины k j1, k j1 1, j1 0, 1,, k 2, в стороны ресурсной рамки для массива случае локализации начально- кольцевым алгоритмом, приведены в таблице 2.30, из которой видно, что погрешность не превосходит 6%.

Таблица 2.30. Значение и % погрешности для массива k j1, k j1 1, j1 0, 1,, k k % 3 k k 18 44 13 0 0, 19 48 14 1 1, 20 52 14 1 1, 21 55 15 1 1, 22 60 16 3 4, 23 64 17 4 5, 24 68 17 4 4, 25 72 18 5 5, 26 76 19 5 5, 27 81 19 1 1, 28 85 20 0 0, 29 90 21 1 0, 30 95 22 1 0, 31 100 22 1 0, 32 104 23 1 0, Для линейной круговой полиэдрали натуральных ресурсных k j1 1, k j1, j1 0, 1,, k прямоугольников вертикальной формы прогноз также оказывается точным. Значение и % погрешности превышения величины стороны ресурсной рамки в случае локализации начально- кольцевым алгоритмом параграфа 2.2, приведены в таблице 2.31, из которой видно, что погрешность не превосходит 11%.

Таблица 2.31. Значение и % погрешности для массива k j1 1, k j1, j1 0, 1,, k k % 3 k k 18 44 12 4 7, 19 48 13 4 7, 20 52 14 5 8, 21 55 14 4 6, 22 60 15 6 8, 23 64 16 7 9, 24 68 17 8 10, 25 72 17 8 9, 26 76 18 9 10, 27 81 19 9 9, 28 85 19 5 5, 29 90 20 5 4, 30 95 21 6 5, 31 100 22 6 5, 32 104 22 5 4, Видим, что прогноз значений параметров квадратной ресурсной рамки, в которую может быть локализован массив заявок кругового типа оказался точным для массивов натуральных ресурсных квадратов, натуральных ресурсных прямоугольников горизонтальной формы, натуральных ресурсных прямоугольников вертикальной формы.

Таким образом, в настоящем параграфе приводится сравнительный анализ полиномиальных алгоритмов распределения процессорно- временных ресурсов для массивов заявок кругового квадратичного типа. Делается вывод о целесообразности предложенных алгоритмов при диспетчировании в Grid системах.

2.8. Выводы 1. Предложены, разработаны и исследованы полиномиальные алгоритмы диспетчирования, адаптированные к массивам заявок кругового квадратичного типа.

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

3. Проведн сравнительный анализ разработанных полиномиальных алгоритмов диспетчирования линейными круговыми полиэдралями:

начально- кольцевого, уровневого, углового, последовательных приближений.

Глава 3. Массивы заявок гиперболического типа 3.1. Центрально- кольцевой алгоритм Приведм и исследуем центрально- кольцевой алгоритм диспетчирования линейными гиперболическими полиэдралями ресурсных прямоугольников k a j1, b j1, b j1, a j1, j1 [129].

j1 Предыдущие построения начально- кольцевой локализации переходят в центрально- кольцевую локализацию. При этом, роль максимального, начального ресурсного элемента линейной круговой полиэдрали переходит к центральному a j, b j * * элементу минимальной асимметрии измерений 1 b j1 a j1 min b j1 a j1. Данный ресурсный элемент делит массив на * * j j1 j1 больших высот и меньших * предшествующие элементы с номерами оснований и последующие элементы с j1 j1 противоположного свойства.

* 10. Центральный ресурсный элемент принимаем в качестве начальной оболочки (рисунок 3.1).

Y b(7) a(7) 0 Y Рис. 3.1. Начальная ресурсная оболочка 20. На втором шаге вдоль правой стороны оболочки Y1 a j1 вертикально * суперпозируются последующие по отношению к центральному ресурсные j1 q * a j1, b j прямоугольники до наилучшего приближения уровня оболочки j1 j1 * * b j1 b j1* j1 q * с недостатком (операция динамического интегрирования j1 j1 ресурсных прямоугольников по вертикали). Здесь q1 - число ресурсных прямоугольников, суперпозированных в вертикальном слое. Строится новая ресурсная оболочка полученной совокупности ресурсных прямоугольников (рисунок 3.2).

Y b(7) b(8) a(7) a(8) 0 Y Рис. 3.2. Первая ресурсная оболочка 30. Над верхней стороной достигнутой оболочки вдоль горизонтали на упомянутом уровне Y2 b j * суперпозируются последовательно элементы, j1 q * a j1, b j1, предшествующие по отношению к центральному до j1 j1 * наилучшего приближения с недостатком величины протяжнности оболочки * a j1 a j1* a j1* q1 j1 q * (операция динамического интегрирования j1 j1 ресурсных прямоугольников по горизонтали). Здесь q2 - число ресурсных прямоугольников, суперпозированных в горизонтальном слое. Строится новая ресурсная оболочка полученной совокупности ресурсных прямоугольников (рисунок 3.3).

Y b(5) b(6) a(6) a(5) b(7) b(8) a(7) a(8) 0 Y Рис. 3.3. Вторая ресурсная оболочка 40. На следующем шаге вновь вдоль правой стороны достигнутой оболочки Y1 a j1 a j1 q * * вертикально суперпозируются последующие ресурсные j1 q1 q * a j1, b j1 до наилучшего приближения уровня оболочки прямоугольники j1 j1 q1 * b j1 b j1* b j1* q2 j1 q1 q * с недостатком (операция динамического j1 j1 q1 * интегрирования ресурсных прямоугольников по вертикали). Здесь q3 - число ресурсных прямоугольников, суперпозированных в вертикальном слое. Строится новая ресурсная оболочка (рисунок 3.4).

Y b(5) b(6) b(10) a(6) a(5) a(10) b(7) b(8) b(9) a(7) a(8) a(9) Y Рис. 3.4. Третья ресурсная оболочка 50. Далее, над верхней стороной достигнутой оболочки вдоль горизонтали Y2 b j1 b j1 q * * суперпозируются последовательно элементы, j1 q2 q * a j1, b j1, предшествующие по отношению к центральному до j1 j1 q2 * наилучшего приближения с недостатком величины протяжнности оболочки a j1 a j1* a j1* q1 a j1* q1 q3 j1 q2 q * (операция динамического j1 j1 q2 * интегрирования ресурсных прямоугольников по горизонтали). Здесь q4 - число ресурсных прямоугольников, суперпозированных в горизонтальном слое.

60. Введнный таким образом алгоритм центрально- кольцевой локализации повторяем до полного исчерпания ресурсных прямоугольников массива (рисунок 3.5).

Y b(0) b(1) b(2) b(4) b(3) a(4) a(3) a(2) a(1) a(0) b(5) b(6) b(10) a(6) a(5) a(10) b(7) b(8) b(9) a(7) a(8) a(9) Y Рис. 3.5. Конечная ресурсная оболочка Отметим, что количество операций работы центрально- кольцевого алгоритма составляет k операций сложения и k операций сравнения, т.е. алгоритм является полиномиальным.

В частности, для линейной полиэдрали гиперболических ресурсных прямоугольников с центральным элементом минимальной асимметрии k j1 3k j1, k k k j1 1, 2,, k k при соответствующие 2 2 построения приведены на рисунке 3.6.

31x 32x 33x 34x 50x 35x 36x 37x 46x 49x 38x 39x 43x37 45x 48x 40x40 41x39 42x38 44x36 47x Рис. 3.6. Укладка гиперболической линейной полиэдрали ресурсных прямоугольников центрально- кольцевым алгоритмом Эвристические меры ресурсных оболочек центрально- кольцевого алгоритма для этой последовательности гиперболических ресурсных прямоугольников с центральным элементом минимальной асимметрии приведены в таблице 3.1.

Таблица 3.1. Эвристические меры ресурсных оболочек центрально- кольцевого алгоритма Ресурсная Эвристическая Ресурсная Эвристическая k k оболочка мера оболочка мера 10 8966 0,82 16 178142 0, 11 9773 0,73 17 188151 0, 12 10679 0,67 18 199159 0, 13 114117 0,78 19 209168 0, 14 123125 0,72 20 220176 0, 15 167134 0, Отметим, что эвристические меры ресурсных оболочек центрально 0,39.

кольцевого алгоритма не превосходят значения Таким образом, в настоящем параграфе предлагается и исследуется эвристический центрально- кольцевой алгоритм диспетчирования массивами заявок гиперболического типа. Устанавливается полиномиальная трудомкость предложенного центрально- кольцевого алгоритма. Для базового примера массива k j1 3k j1, заявок гиперболического типа ресурсных прямоугольников k k k j1 1, 2,, k строятся объемлющие прямоугольники с вычислением 2 2 эвристических мер. Делаются выводы о качестве предложенного эвристического полиномиального центрально- кольцевого алгоритма.

3.2. Уровневый алгоритм по высоте и протяжнности В полиномиальном алгоритме параграфа 3.1 существенную роль играл центральный элемент минимальной асимметрии измерений, находящийся внутри линейной гиперболической полиэдрали. В случае линейных гиперболических k a j1, b j1, b j1, a j1, j полиэдралей ресурсных прямоугольников j1 горизонтальной формы такой элемент является начальным (рисунок 3.7), а для линейных гиперболических полиэдралей ресурсных прямоугольников вертикальной формы такой элемент минимальной асимметрии измерений является конечным (рисунок 3.8).



Pages:     | 1 || 3 | 4 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.