В рассматриваемом алгоритме сборочные операции формируются последовательно, начиная с первой.
На каждом шаге в формируемую операцию включается только один переход. Из множество переходов отбираются такие, которые на очередном шаге не имеют предшественников (предположим, что их предшественники уже включены в предыдущие или формируемую операцию).
Подмножество переходов, которые можно включить на ν –м шаге в формируемую операцию, не нарушая условия предшествования, называется u -допустимым подмножеством и обозначаются Du .
Пусть формируемая операция s должна выполняться в позиции Р. Тогда из u -допустимого подмножества следует отобрать переходы, имеющие позиционный код Р. Они образуют р – допускаемое подмножество (обозначаемое Dp), которое, как правило, содержит меньшее число переходов, чем u-допустимое подмножество, за счет наложения позиционных ограничений.
Третье налагаемое условие – не превышение продолжительностью операции такта конвейера – еще более ограничивает число переходов, которые на ν-м шаге можно включить в s.
Отбирая из числа р – допустимых переходы, удовлетворяющие условию:
ti ≤ τ- Tsν-1;
получим, наконец, t –допустимое подмножество Dt. Здесь:
ti – трудоемкость i –го перехода;
τ - такт конвейера;
T3ν-1 суммарная трудоемкость переходов, уже назначенных в s к моменту ν.
Так последовательно отбирая u –допустимые, р - допустимые и t – допустимые подмножества, на каждом ν –м шаге будем иметь совокупность переходов, которые в момент ν можно назначить в операцию s.
При этом возможны три ситуации:
1. На ν-м шаге t – допустимые подмножества является пустым (Dt =Ф), т.е. к моменту ν переходы, удовлетворяющие всем трем условиям, отсутствуют. В этом случае формирование операции s закончено, и переходят к формированию следующей операции (s +1)-й.
2. На ν-м шаге t -допустимое подмножество содержит один переход. Тогда он назначался в операцию s, и переходят к (ν+1)-му шагу ее формирования.
3. На ν-м шаге t – допустимое подмножество содержит несколько переходов.
4. В этом случае из Dt выбирают переход в соответствии с некоторым приоритетным правилом. Наиболее распространены следующие правила выбора переходов:
- равновероятный выбор;
- выбор перехода с минимальной длительностью выполнения;
- выбор перехода с максимальной длительностью выполнения;
- выбор перехода, для которого максимальна или минимальна длительность выполнения всех следующих за ним переходов;
- выбор перехода, для которого максимально число всех следующих за ним переходов;
- выбор перехода, для которого максимально отношение длительности выполнения всех следующих за ним переходов к длительности его выполнения;
- рандомизированный, но не равновероятный выбор: переход выбирается с заранее заданной вероятностью по одному из вышеуказанных правил, т.е. каждое правило имеет свой «вес».
При наличии двух и более переходов, имеющих одинаковую степень приоритета, выбирается переход с меньшим порядковым номером.
Использование различных приоритетных правил приводят, вообще говоря, к разным решениям задачи синхронизации операций. Однако нельзя указать какое – либо одно универсальное правило, приходящее всегда к наилучшему решению. Результат, полученный при использовании того или иного правила, зависят от особенностей техпроцесса, операции которого синхронизируются.
Пример
Условие: синхронизировать операции техпроцесса сборки, представленного графом на рис.1 и таблицей исходных данных, при такте конвейера τ=10 мин.
Особенности задачи:
В данном примере имеется две группы позиционных ограничений. Первая группа (Р) характеризует переходы, которые нельзя выполнять на одном рабочем месте, если они имеют разные коды, например, ограничения по профессии исполнителя: код 1 – слесарь-сборщик, код 2 – сварщик.
Ограничения второй группы (Р) также не допускают выполнения на одном рабочем месте переходов с разными ненулевыми кодами, но при этом переходы с кодами Р=0 совместимы с любыми другими (по группе Р), например: код 1 – левая сторона конвейера; код 2 – правая сторона конвейера; код 0 – возможность выполнения перехода на любой стороне конвейера.
Т.о. каждому переходу приписана пара кодов (Р,Р) и наличие позиционных ограничений равносильно требованию: любая операция может содержать только те переходы, которые имеют одинаковые пары кодов.
Совмещение переходов, например: u1 ,u2 ,u3 ; имеющих пары кодов (1,0),(1,1) и (1,0)не нарушает позиционных ограничений, также как и объединение в какой-то другой операции переходов u4 ,u6 ,u11 (пары кодов 2,0; 2,2; 2,0). Нельзя объединять в одну операцию такие переходы, как u6 , u7 ; u2 ,u7 ; подмножество. Оно также включает только переход u1 , т.е. Dto = u1 .
3. Назначаем переход u1 в первую операцию и фиксируем, что Р=1, ибо u1 приписана пара кодов (1,0).