В рассматриваемом алгоритме сборочные операции формируются последовательно, начиная с первой.

На каждом шаге в формируемую операцию включается только один переход. Из множество переходов отбираются такие, которые на очередном шаге не имеют предшественников (предположим, что их предшественники уже включены в предыдущие или формируемую операцию).

Подмножество переходов, которые можно включить на ν –м шаге в формируемую операцию, не нарушая условия предшествования, называется u -допустимым подмножеством и обозначаются D_u .

Пусть формируемая операция s должна выполняться в позиции Р. Тогда из u -допустимого подмножества следует отобрать переходы, имеющие позиционный код Р. Они образуют р – допускаемое подмножество (обозначаемое D_p), которое, как правило, содержит меньшее число переходов, чем u-допустимое подмножество, за счет наложения позиционных ограничений.

Третье налагаемое условие – не превышение продолжительностью операции такта конвейера – еще более ограничивает число переходов, которые на ν-м шаге можно включить в s.

Отбирая из числа р – допустимых переходы, удовлетворяющие условию:

t_i ≤ τ- T_s^ν-1;

получим, наконец, t –допустимое подмножество D_t. Здесь:

t_i – трудоемкость i –го перехода;

τ - такт конвейера;

T₃^ν-1 суммарная трудоемкость переходов, уже назначенных в s к моменту ν.

Так последовательно отбирая u –допустимые, р - допустимые и t – допустимые подмножества, на каждом ν –м шаге будем иметь совокупность переходов, которые в момент ν можно назначить в операцию s.

При этом возможны три ситуации:

1. На ν-м шаге t – допустимые подмножества является пустым (D_t =Ф), т.е. к моменту ν переходы, удовлетворяющие всем трем условиям, отсутствуют. В этом случае формирование операции s закончено, и переходят к формированию следующей операции (s +1)-й.

2. На ν-м шаге t -допустимое подмножество содержит один переход. Тогда он назначался в операцию s, и переходят к (ν+1)-му шагу ее формирования.

3. На ν-м шаге t – допустимое подмножество содержит несколько переходов.

4. В этом случае из D_t выбирают переход в соответствии с некоторым приоритетным правилом. Наиболее распространены следующие правила выбора переходов:

- равновероятный выбор;

- выбор перехода с минимальной длительностью выполнения;

- выбор перехода с максимальной длительностью выполнения;

- выбор перехода, для которого максимальна или минимальна длительность выполнения всех следующих за ним переходов;

- выбор перехода, для которого максимально число всех следующих за ним переходов;

- выбор перехода, для которого максимально отношение длительности выполнения всех следующих за ним переходов к длительности его выполнения;

- рандомизированный, но не равновероятный выбор: переход выбирается с заранее заданной вероятностью по одному из вышеуказанных правил, т.е. каждое правило имеет свой «вес».

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

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

Пример

Условие: синхронизировать операции техпроцесса сборки, представленного графом на рис.1 и таблицей исходных данных, при такте конвейера τ=10 мин.

Особенности задачи:

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

Ограничения второй группы (Р) также не допускают выполнения на одном рабочем месте переходов с разными ненулевыми кодами, но при этом переходы с кодами Р=0 совместимы с любыми другими (по группе Р), например: код 1 – левая сторона конвейера; код 2 – правая сторона конвейера; код 0 – возможность выполнения перехода на любой стороне конвейера.

Т.о. каждому переходу приписана пара кодов (Р,Р) и наличие позиционных ограничений равносильно требованию: любая операция может содержать только те переходы, которые имеют одинаковые пары кодов.

Совмещение переходов, например: u₁ ,u_{2 ,}u₃ ; имеющих пары кодов (1,0),(1,1) и (1,0)не нарушает позиционных ограничений, также как и объединение в какой-то другой операции переходов u₄ ,u₆ ,u₁₁ (пары кодов 2,0; 2,2; 2,0). Нельзя объединять в одну операцию такие переходы, как u₆ , u₇ ; u₂ ,u₇ ; подмножество. Оно также включает только переход u₁ , т.е. D_t^o = u₁ .

3. Назначаем переход u₁ в первую операцию и фиксируем, что Р=1, ибо u₁ приписана пара кодов (1,0).

4. Заполним графу z₁ таблицы 2, имея в виду, что назначение в первую т.к. запрещено совмещение пар кодов 2,2 и 1,2, а также 1,1 и 1,2.

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

Решение.

1. Заполним графу z_o таблицы u-допустимых подмножеств, для чего против каждого перехода проставим количество предшественников, которое он имеет в начальный момент формирования первой операции.

2.Заметим, что в начальный момент формирования первой операции только переход u₁ является u-допустимым, т.е. D_u^o= {u₁}. Т.к. коды позиционных ограничений для первой операции еще не установлены, определим сразу t-допустимое операцию перехода u₁ , бывшего предшественником переходов u₂ u₃ ,u_{4 ,}u₅ делает их доступными для выполнения. По графеz₁ находим D_u¹ = {u₂ u₃ u₄ u₅ }.

5.Значение второго кода позиционных ограничений Р пока не установлено, поэтому отбираем в Р-допустимое подмножество переходы, совместимые с u₁ по первому коду, т.е.D_1,p⁽¹⁾ = u₂ , u₃ . Переходы u₄ ,u₅ , имеющие код Р = 2, не являются р-допустимыми, т.к. в позиции с кодом Р = 1.

6. Определяем t-допустимое подмножество D_t⁽¹⁾ = u₂ . Переход u₃ не является t-допустимым, т.к. при его назначении в первую операцию вместе с уже назначенным переходом u₁ суммарная продолжительность выполнения операции составит 11 мин, что превышает такт конвейера.

7. Назначаем в первую операцию u₂ и устанавливаем, что P = 1. Следовательно, теперь в первую очередь можно включать только переходы, имеющие коды позиционных ограничений 1,0 или 1,1 , а код 1,2 является запрещенным.

8. С помощью z₂ находим D_u⁽²⁾=u₃ u₄ u₅ u₆ , а затем D_1,1⁽²⁾=u₃ ; D⁽²⁾_t =Ф. Формирование первой операции закончено: Ώ₁ = u₁, u₂.

Аналогично формируется вторая операция. Из графы z₂ следует, что D_u⁽²⁾=u₃u₄u₅u₆ . Коды Р и Р для второй операции пока не установлены, поэтому определяем D⁽²⁾_t= u₃u₄u₅u₆ .

Находим max t₃t₄t₅t₆ , выбираем u₄ и фиксируем Р=2. По графе z₃ определяем D_u⁽³⁾=u₃u₅u₆ , а затем D_2,0⁽³⁾=u₅u₆ . D_t⁽³⁾=u₅u₆ , max t₅t₆ .

Выбираем u₆ и замечаем, что P=2. Определяем D_u⁽⁴⁾=u₃u₅u₈ , D_2,2⁽⁴⁾=u₅ . D_t⁽⁴⁾=u₅ и выбираем u₅. Далее определяем D_u⁽⁵⁾=u₃u₈ , D_2,2⁽⁵⁾=Ф и D_t⁽⁵⁾=Ф. Формирование второй операции закончено, Ώ₂= u₄u₅u₆ .

Продолжив вычисления, определим Ώ₃=u₈ , Ώ₄=u₃u₇ , Ώ₅=u₉u₁₀ , Ώ₆=u₁₁ .

Коэффициент использования рабочего времени 0,83.

Рис.4.1. Граф технологической последовательности сборки изделия

Табл.4.2.

Исходные данные к расчету

Табл.4.3.

Таблица u -допустимых подмножеств

	Z0	Z1	Z2	Z3	Z4	Z5	Z6	Z7	Z8	Z9	Z10	Z11
u1	0
u2	1	0
u3	1	0	0	0	0	0	0
u4	1	0	0
u5	1	0	0	0	0
u6	1	1	0	0
u7	3	3	3	2	2	1	1	0
u8	1	1	1	1	0	0
u9	1	1	1	1	1	1	1	1	0
u10	1	1	1	1	1	1	0	0	0	0
u11	2	2	2	2	2	2	2	2	2	1	0

Табл.4.1.