http://npc-news.ru/

Оптимальная диаграмма совмещения потоков работ

Производя сортировку работ в соответствии с алгоритмом Джонсона, находим оптималь­ный порядок выполнения работ. Для данного упорядочения работ Т = 27.

Задача для упорядочения ра­бот на трёх пунктах сводится, при определённых условиях, к задаче для двух пунктов путем объединения соответствующих работ, выполняемые в пунктах А и В или пунктах В и С: соответствующие длительности работ при этом складываются. Класс задач, к которым применим ал­горитм Джонсона, таким образом, ограничен. В случаях, когда ?7 > 3 для решения используют, как правило, эвристические или приближенные методы.

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

2.1.3. Системы с многофазным циклическим обслу­живанием. Периодические расписания наилучшим образом подходят для планирования многократного выполнения ком­плекса работ или операций [9]. Пусть выполнение работ произ­водится в соответствии с некоторой последовательностью работ (далее — алгоритмом) А, содержащей т работ (операций), среди которых могут быть одинаковые:

Запись (2.1) показывает, что на к-й фазе выполняется опера­ция djk. Алгоритм (2.1) назовем локальным алгоритмом (ЛА) обработки цифровой информации.

Пусть модель системы представлена набором Q элементов (исполнительных ресурсов, рабочих мест), настраиваемых на выполнение операций из набора элементов I типов,

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

Теорема. Алгоритм 1 строит периодическое расписа­ние с максимальным совмещением циклов.

Определение. Совмещение назовем равномерным с ша­гом Т, если Т{ = const = Т.

При равномерном совмещении шаг равен периоду цикличе­ского расписания и минимальное Т может быть найдено как

Из Алгоритма 1 непосредственно вытекает следующее важное следствие.

Следствие. Если А* и А* — два варианта закрепления ПЭ за фазами ЛА, то t(A\) = t(J4*), если Н(А\) = Я(Л*); t(A*) — среднее время получения результата в расписании с максималь­ным совмещением

Рассмотрим задачу оптимизации закрепления элементов. Пусть R = {Д*}, г = 1,…, г — множество всех вариантов закреп­ления за фазами вычислительного алгоритма (2.1), т.е. множе­ство ОЛА.

В серии экспериментальных статистических исследований различных ОЛА вероятность Pij выполнения утверждения:

составляет в среднем более 0,8. Этот факт позволяет с большой достоверностью использовать данное утверждение в качестве одного из косвенных критериев качества периодических распи­саний ЛА.

Задача оптимального закрепления элементов заключается в нахождении такого ОЛА, для которого

t(A*) = min{t(A*)                                        (2.5)

Так как закрепление элементов каждого типа производится

независимо, то можно выделить множества вариантов закреп-

Можно показать, что задача (2.5) эквивалентна задаче мини­мального покрытия таблицы вариантов. Для её решения предло­жен эффективный алгоритм закрепления элементов за фазами ЛА, использующий эвристическое правило: вариант закрепле­ния элемента i-ro типа с характеристикой Нц лучше или эквива­лентен варианту с Н-Г). если выполняется условие \Н^\ — \Нц \ —

— \Hi2\Hn \ ^ 0-

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


Комментарии закрыты.