Лекция: Модификации алгоритма распределения, основанные на идее

«критического пути»

4.3.1. Последовательная модификация алгоритма LPT при избирательности приборов.В ряде случаев, при избирательности приборов, строка матрицы загрузки имеет либо значение V(аi), либо бесконечно большое число. Таким образом, применение метода «критического пути» напрямую невозможно, так как он требует упорядо­чения строк матрицы загрузки в порядке убывания элементов строки, а почти в каждой строке присутствует бесконечный элемент. Следовательно, для решения задачи планирования для матриц загрузки такого вида предлагается три различные модификации метода, основанного на идее «критического пути».

Первая модификация:

все операторы, имеющие время аi > 0, но не равное бесконечности, записываются под тем же индексом в матрицу-строку A1[1,m], где т — чис­ло строк в матрице А;

элементы матрицы А1 упорядочиваются в порядке убывания, форми­руя список приоритетов;

строки матрицы А упорядочиваются в соответствии со списком при­оритетов;

решается задача распределения согласно минимаксному критерию.

Вторая модификация:

в каждой строке матрицы А ищется количество бесконечностей и за­писывается в матрицу-строку А1;

элементы матрицы А1 упорядочиваются в порядке убывания количе­ства бесконечностей, формируя список приоритетов;

строки матрицы А упорядочиваются в соответствии с получившимся

списком приоритетов;

решается задача распределения согласно минимаксному критерию.

Третья модификация:

в каждой строке матрицы А ищется количество бесконечностей и за­писывается в матрицу-строку А1;

элементы матрицы А1 упорядочиваются в порядке убывания количе­ства бесконечностей;

строки матрицы А упорядочиваются в соответствии с матрицей А1;

если строки матрицы А имеют одинаковое количество бесконечно­стей, то происходит упорядочение в порядке убывания элементов, отлич­ных от бесконечности;

решается задача распределения согласно минимаксному критерию.

4.3.2. Примеры использования модифицированных алгоритмов.Проиллюстрируем приведенные модификации алгоритма, основан­ного на идее «критического пути», на примере. Пусть исходная матрица имеет следующий вид:

Рассмотрим первую модификацию. Матрица А1 представляет собой соотношение A1= |4,3,19,4,8,17|. Модифицированная матрица имеет вид А1`=|19,17,8,4,4,3|, а упорядоченная матрица-

Решая задачу распределения, получаем следующее решение: на пер­вый прибор распределяются 3-е и 5-е задания, на второй прибор распреде­ляется 6-е задание, на третий прибор распределяются все оставшиеся зада­ния. Получившаяся загрузка приборов равна T1=27, Т2= 17, T3 = 11.

Рассмотрим вторую модификацию, где модифицированная матрица A1`=|8,4,19,17,3,4|, а упорядоченная матрица

Решая задачу распределения, получаем конечную загрузку приборов: T1=15, Т2= 19, T3 = 21.

Рассмотрим третью модификацию, где модифицированная матрица А1`=8,4,19,17,3,4|, а упорядоченная матрица

Решая задачу распределения, получаем конечную загрузку при­боров T1=19, Т2=19, Т3=17.

Попробуем решить эту задачу «в лоб», без всякого предварительного упорядочения. Получим следующее решение: Тх= 12, T2= 22, Т3= 21.

Как видно из результатов примера, наиболее перспективной моди­фикацией с точки зрения точности результата является третья.

Для определения, какая из модификаций точнее, был проведен вы­числительный эксперимент, результаты которого отражены в табл. 2.12-14.

Из [5] известно, что наиболее часто для вычислительных систем количество используемых приборов колеблется от двух до четырех, поэтому в таблицах приведены результаты для такого количества приборов. Кроме того, количество операторов, подлежащих распределению, последовательно увеличивается от 5 до 100 у.е., а время выполнения каждого оператора распределено по равномерному закону в интервале от 2 до 30.

Сравнение модификаций для двух приборов

Таблица 2.12

Сравнение модификаций для трех приборов

Таблица 2.13

Сравнение модификаций для четырех приборов

Таблица 2.14

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

Критериальная инвариантность алгоритма по критическому пути

Алгоритм составления расписаний «по критическому пути» (АКП) [1,2] предполагает превентивное конструирование упорядоченного списка работ, назначенных к выполнению. Его называют списком приоритетов, и при использовании АКП он составляется в порядке убывания длительностей работ где N- общее число назначенных к выполнению работ. Таким образом, список приоритетов для n работ, оставшихся к выполнению на произвольном s-м этапе обслуживания, где s=N-m-n+ 1,a m – количество обслуживающих приборов (устройств), имеет следующую структуру:

: >; (1)

В данной работе исследуется задача составления с помощью АКП расписания для выполнения совокупности независимых работ в однородной системе, т.е. время выполнения любой из N работ на любом из m приборов (устройств) считается одинаковым. Поэтому, если появляется освободившееся устройство, то из списка выбирается последняя невыполненная и готовая к выполнению работа, которая назначается к выполнению на этом свободном устройстве. Если свободны одновременно два или более приборов, то работа назначается на условно первое из них, затем на второе и т.д. Приоритет устройств, при этом, произволен в силу однородности системы и назначается пользователем или разработчиком.

Итак, пусть имеется текущее на момент формирования списка длительностей (1) распределенных между n приборами уже выполненных в данный момент работ

(2)

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

>; (3)

Для описанной ситуации обслуживания справедливо следующее, вытекающее из (1-3), свойство:

. (4)

Дальнейшая реализация АКП состоит в значении очередной (наибольшей из оставшихся не обслуженными) работы с длительностью из списка (1) такому прибору с загрузкой из списка (2), чтобы на этом s-м этапе обслуживания минимизировался выбранный для реализуемой продукции критерий. Из применяемых показателей оценки эффективности обслуживания очереди работ наибольшее признание и распространение получили описанные ниже три критерия [1,2]:

— минимаксный критерий или ММ-критерий, обеспечивающий минимальное общее время решений задачи;

— критерий равномерности загрузки, или РЗ-критерий, обеспечивающий максимальную равномерность использования обслуживающих ресурсов приборов [2];

— квадратичный критерий, или КВ-критерий, не имеющий прямого технологического смысла (имеется в виду технологии многоприборного выполнения работ), но косвенно связанный с предыдущими и удобный в применении [1].

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

Поскольку во многих технологиях обслуживания в различных ситуациях могут выступать на первый план различные критерии, интерес представляет оценка и использование АКП по каждому из введенных критериев:

1) При использовании ММ-критерия очевидно, что оптимум задачи этапа достигается на решении

,

поскольку при любом другом при > (вариант > решения не имеет). В приведенных выражениях j- индекс прибора в новом (s+1)-м распределении нумерации приборов перед обслуживанием (m-1)-й заявки;

2) При использовании РЗ-критерия результат оптимизации не столь очевиден. В связи с этим целесообразно сравнить результаты распределения для двух соседних по нумерации приборов: k-й и k+1-й, k, оценив их как вариацию функционала и имея в виду, что средняя длительность загрузки приборов при обоих новых распределениях одинакова. Действительно, при любом (s+1)-м назначении

. Тогда и, следовательно,

(5)

Из условия (5) индукцией с уменьшением k до 1 получается доказательство оптимальности АКП и по критерию равномерности загрузки.

3) Аналогично вариация функциональна КВ-критерия приводит к результату

(6)

что также позволяет применить индукцию с уменьшением k до 1, и из условия (6) получить доказательство оптимальности АКП по квадратичному критерию.

Таким образом, в данной работе получен чрезвычайно интересный и важный для критериальной оценки АКП результат, позволяющий при решении многокритериальных задач, включающих рассмотренные критерии, решать приближенным методом «критического пути» любую задачу только один раз по любому из критериев. При смене критериев результата оценки автоматически переносится на новую задачу, т.е. используется уже составленное расписание. Это экономит время разработчика и вычислительные ресурсы.

Самостоятельное значение имеет и доказанный факт пошаговой оптимальности АКП по наиболее важным критериям теории расписаний.