д) потери рабочего времени были минимальны.

Для оценки эффективности синхронизации пользуются коэффициентом использования рабочего времени:

η = Т /τR;

где: Т – суммарная трудоемкость сборки изделия, чел-ч.;

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

R – число работающих на конвейере.

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

Введем следующие обозначения:

i и j – индексы переходов;

i = 1,2,…m;

j = 1,2,…n;

отношение предшествования, заданных на множестве переходов (i,j – выполнение перехода i предшествует выполнению перехода j);

ti - трудоемкость i -го периода;

Р – положительное целое число (различным позициям соответствуют различные целые числа);

τ - такт конвейера, в большинстве случаев ti ≤τ для всех ί;

ѕ - порядковый номер операции или рабочего места, ѕ= 1,2,…Ѕ.

Введем также целочисленную переменную δīś:

δίš = 1, если ί-й переход закреплен за ś-м рабочим местом;

δίš = 0, если ί-й переход на ś-м рабочем месте не выполняется.

Целевой функцией или критерием оптимальности распределения переходов по операциям является минимум потерь рабочего времени, т.е.:

m

Σ (τ – Σti δis ) → min;

i=1 s

Но Σti δis = Ts , где Тs – трудоемкость S-й операции, а также ΣТS = Т, i=1  S=1

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

(τЅ- Т) → min;

т.е. синхронизация операций сводится к минимизации числа операций (рабочих мест):

Ѕ→min,

при следующих ограничениях, учитывающих требования пунктов:

S

а)* Σδis = 1 – каждый переход выполняется на одном рабочем месте;

S=1

m

б)* Σti δis ≤τ – не превышение продолжительностью каждой операции такта i=1ь конвейера;

S

в)* δjs ≤ Σδik - соблюдение условий предшествования для каждой пары i и j

k=1

при i j;

г)* ‌‌Рi - Pj‌δis + Pi – Pj‌δjs≤ ‌Pi - Pj‌ - условия выполнения операции в одной позиции. В самом деле, если δis=1 и δjs=1, т.е. переходы выполняются на одном рабочем месте, то данное условие соблюдается лишь при Рi = Рj , что означает выполнение переходов i и j в одной и той же позиции.

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

В рассматриваемом алгоритме решения поставленной задачи в качестве трудоемкости перехода берется величина:

ti = ti – ] ti/τ [,

где:] ti/τ [ – антье (целая часть числа).

4.5 Алгоритм методики формирования операций при их синхронизации

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

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

Подмножество переходов, которые можно включить на ν –м шаге в формируемую операцию, не нарушая условия предшествования, называется 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 выбирают переход в соответствии с некоторым приоритетным правилом. Наиболее распространены следующие правила выбора переходов:

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

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

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

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

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

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

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

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

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

4.6 Пример

Условие: синхронизировать операции техпроцесса сборки, представленного графом на рис.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).

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

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

Решение.

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

2.Заметим, что в начальный момент формирования первой операции только переход u1 является u-допустимым, т.е. Duo= {u1}. Т.к. коды позиционных ограничений для первой операции еще не установлены, определим сразу t-допустимое операцию перехода u1 , бывшего предшественником переходов u2 u3 ,u4 ,u5 делает их доступными для выполнения. По графеz1 находим Du1 = {u2 u3 u4 u5 }.

5.Значение второго кода позиционных ограничений Р пока не установлено, поэтому отбираем в Р-допустимое подмножество переходы, совместимые с u1 по первому коду, т.е.D1,p(1) = u2 , u3 . Переходы u4 ,u5 , имеющие код Р = 2, не являются р-допустимыми, т.к. в позиции с кодом Р = 1.

6. Определяем t-допустимое подмножество Dt(1) = u2 . Переход u3 не является t-допустимым, т.к. при его назначении в первую операцию вместе с уже назначенным переходом u1 суммарная продолжительность выполнения операции составит 11 мин, что превышает такт конвейера.

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

8. С помощью z2 находим Du(2)=u3 u4 u5 u6 , а затем D1,1(2)=u3 ; D(2)t =Ф. Формирование первой операции закончено: Ώ1 = u1, u2.

Аналогично формируется вторая операция. Из графы z2 следует, что Du(2)=u3u4u5u6 . Коды Р и Р для второй операции пока не установлены, поэтому определяем D(2)t= u3u4u5u6 .

Находим max t3t4t5t6 , выбираем u4 и фиксируем Р=2. По графе z3 определяем Du(3)=u3u5u6 , а затем D2,0(3)=u5u6 . Dt(3)=u5u6 , max t5t6 .

Выбираем u6 и замечаем, что P=2. Определяем Du(4)=u3u5u8 , D2,2(4)=u5 . Dt(4)=u5 и выбираем u5. Далее определяем Du(5)=u3u8 , D2,2(5)=Ф и Dt(5)=Ф. Формирование второй операции закончено, Ώ2= u4u5u6 .

Продолжив вычисления, определим Ώ3=u8 , Ώ4=u3u7 , Ώ5=u9u10 , Ώ6=u11 .

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

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12