Modelování montážní linky Gejza Dohnal
1. Montážní linka S rozvojem hromadné výroby je velice těsně spojen rozvoj a automatizace výrobních a montážních linek. Tyto linky se od sebe obecně liší jednak topologií (uspořádáním pracovních stanic a pohybem výrobků mezi nimi), jednak okruhem činností, které linka vykonává. Společným prvkem je zpravidla transportní systém (dopravník, vozíky), propojující jednotlivé pracovní stanice. Montážní linka má jeden vstupní uzel, kterým vstupují základní prvky pro montáž, montážní jednotky. V průběhu montážního procesu jsou tyto jednotky doplňovány a upravovány tak, aby na konci linky vystupoval hotový výrobek. Jedna montážní linka obecně umožňuje montáž několika typů výrobků, které se od sebe mohou více či méně lišit. Podle toho, zda je linka určena pro jediný typ výrobků nebo pro několik typů zároveň, označujeme montážní linky jako a) linky s jednoduchým programem (single model assembly line, SMAL), na nichž jsou montovány pouze výrobky jediného typu b) linky se smíšeným programem (mixed model assembly line, MMAL), umožňující montáž několika typů výrobků bez nutnosti změny parametrů linky, přenastavení nástrojů či automatů c) linky s různými programy (multiple model assembly line), které vyžadují při změně typu montovaného výrobku změnu nastavení parametrů, výměnu nástrojů či přeprogramování automatů. Každý z uvedených typů montážních linek vyvolává poněkud jiný okruh problémů a metod k jejich řešení.
Obr. 1. Různé typy montážních linek podle skladby montovaných výrobků. Dalším základním prvkem montážní linky jsou pracovní stanice. Každá pracovní stanice zajišťuje několik operací (činností), při nichž je montážní jednotka doplňována o další komponenty, případně jiným způsobem zpracovávána (obráběna, povrchově upravována, seřizována, nastavována, …). Jedna pracovní stanice obvykle působí v určitém vymezeném prostoru, zahrnujícím část dráhy transportního systému, po předem vymezený čas. Některé typy montážních linek (linky typu U, U-shape assembly line) umožňují působení jedné pracovní stanice na dvou různých místech montážní linky (viz obr. 2), čímž může být zvýšena efektivita linky. Obr. 2. Dva typy montážních linek podle prostorového uspořádání: a) přímá, b) linka typu U. Pracovní stanice jsou zde vyznačeny čárkovaně, jednotlivé operace jako kroužky. Montážní operace v jednotlivých pracovních stanicích vyžadují plynulý přísun montovaných komponent. Tyto komponenty jsou soustřeďovány kolem transportního systému v průběžně doplňovaných zásobnících. V případě linek se smíšeným programem navíc tyto komponenty musejí být v zásobnících řazeny způsobem, odpovídajícím pořadí montovaných typů v transportním systému. Schéma takovéto montážní linky je na obr. 3.
Obr. 3. Montážní linka MMAL se třemi typy montovaných výrobků, třemi pracovními stanicemi, zásobníky komponent a sklady pro jednotlivé typy výrobků.
2. Řešené problémy S provozem montážních linek je spojena celá řada problémů, řešených pomocí matematických modelů a optimalizačních metod. 2.1. Problém vyvážení linky (balance problem) První skupina problémů, v literatuře označovaná jako SALBP (Simple Assembly Line Balancing Problem), řeší úlohu rozdělení montážních úkonů (operací) mezi pracovní stanice tak, aby byla zachována návaznost operací (podle předem daného schématu, grafu návazností) a nebyl překročen maximálně povolený čas montáže (délku cyklu) na každé stanici na straně jedné a tento čas byl co nejlépe využit na straně druhé. Tyto úlohy sledují některý z následujících cílů: - minimalizaci počtu pracovních stanic při zachování dané délky cyklu - minimalizaci délky cyklu (maximalizaci intenzity produkce) při daném počtu pracovních stanic - současnou minimalizaci délky cyklu a počtu stanic tak, aby byla minimální celková doba prodlevy (nečinnosti pracovních stanic, neefektivita linky)
Příklad: Montážní linka zahrnuje devět operací, jejichž délky (v časových jednotkách) a návaznosti ukazuje následující graf návazností (čísla v oválech označují číslo operace/délka operace). Linka obsahuje pět pracovních stanic S1, S2, S3, S4 a S5. 1/6 3/4
2/6 4/5
7/4 5/4
8/2
9/9
6/5
Jedním z možných řešení problému vyvážení této linky je následující rozdělení operací: S1={1,3}, S2={4,5}, S3={2,7}, S4={6,8}, S5={9}. Minimální délka cyklu je 10 časových jednotek. Obecnější úloha GALBP (General Assembly Line Balancing Problem) zahrnuje další omezení (například prostorové) a podmínky (paralelní stanice, seskupování operací, nekompatibilitu operací, specifitu pracovních stanic). Tyto úlohy a jejich řešení se liší podle konkrétních podmínek montážních linek, nicméně vždy se jedná o optimalizační úlohy. 2.2. Plánování produkce (production planning) a zásobovací strategie (supply policy) V případě linek typu MMAL (obr. 3) se objevují problémy s optimální strukturou produkce (posloupnost jednotlivých typů montovaných jednotek v čase) a problémy spojené se zajištěním dodávky komponent. První skupina úloh závisí na zvolené strategii „výroby na objednávku“ nebo „výroby na sklad“. Z matematického hlediska je zajímavější druhá skupina úloh, hledající optimílní strategie dodávky komponent do zásobníků montážní linky. Komponenty musejí být připraveny k montáži ve správném pořadí tak, aby nedocházelo k prodlevám a k přeplnění zásobníků komponentami určitých typů. 2.2. Optimalizace lidských zdrojů Zajímavý okruh úloh se týká stanovení optimálního počtu pracovníků a jejich specializace tak, aby při výpadku jednoho pracovníka nedošlo k ohrožení provozu linky. To souvisí s optimalizací nákladů na lidské zdroje (mzda, školení, zástupnost, doažitelnost, …)
3. Hledání kritických míst V následující kapitole se budu blíže zabývat jedním problémem, spojeným se spolehlivostí linky, s hledáním jejích kritických míst. Montážní linku lze v základním tvaru chápat jako tandemovou síť hromadné obsluhy, jejíž jednotlivé prvky jsou tvořeny systémy, které se v teorii hromadné obsluhy označují jako G/G/1/k. Předpokládejme, že linka je tvořena L pracovními stanicemi, mezi nimiž je vždy transportní subsystém. Jak pracovní stanice, tak i transportní subsystém, mají předřazený zásobník s konečnou kapacitou, v němž se mohou hromadit montážní jednotky, čekající na zpracování či na transport. U každé stanice může být navíc kontrolní stanice, která provádí výstupní kontrolu jakosti pro tuto pracovní stanici (obr. 4). pracovní stanice j
Zj
Wj
transportní subsystém j
Cj
Kj
Tj
transportní subsystém j+1
pracovní stanice j+1
Zj+1
Wj+1
Cj+1
Kj+1
Tj+1
Obr. 4. Model montážní linky s omezenými zásobníky a kontrolní stanicí: Zj – zásob-ník před j-tou stanicí, Wj – j-tá pracovní stanice, Cj – kontrola výstupu z j-té stani-ce, Kj – zásobník j-tého transportního subsystému, Tj – j-tý transportní subsystém Tento model předpokládá, že montážní jednotky vstupují do systému pracovní stanice j v časových intervalech, jejichž délka je obecně chápána jako náhodná veličina Aj s rozdělením pravděpodobnosti s distribuční funkcí Aj(t), j=1,…,L, přičemž na vstupu do montážní linky jsou tyto intervaly vzájemně stochasticky nezávislé. Doba montáže v pracovní stanici je opět náhodná veličina Bj, nezávislá na Aj s distribuční funkcí Bj(t) , j=1,…,L. Zavedeme nyní označení, týkající se charakteristik j-tého prvku montážní linky: Nechť λaj ,c aj - intenzita a variační koeficient vstupního proudu montážních jednotek do pracovní stanice j (je to zároveň intenzita a variační koeficient výstupu z prvku j-1)
λdj ,c dj
- intenzita a variační koeficient výstupního proudu
montážních jednotek z pracovní stanice j (intenzita a variační koeficient vstupu do kontrolního stanoviště j) b b λ j ,c j - intenzita a variační koeficient výstupního proudu z kontrolní
λcj ,c cj
stanice j (intenzita a variační koeficient vstupu do transportního subsystému j) - intenzita a variační koeficient výstupního proudu
µ j , µˆ j
z transportního subsystému j (je to zároveň intenzita a variační koeficient vstupu do prvku j+1 linky) - intenzita obsluhy pracovní stanice j a transportního
subsystému j n j ,m j - počet jednotek v zásobníku pracovní stanice j a transportního subsystému j N j , M j - kapacity zásobníku pracovní stanice j a transportního subsystému j
λa j ca j
W j
nj, Nj
pj
λd j
µj
cd j
λb j cb j
Vj mj, Mj
µˆ j
qj W j ,V j - doba čekání na zpracování v zásobníku pracovní stanice j a
pj
transportního subsystému j - pravděpodobnost nalezení neopravitelného výrobku kontrolní
qj
stanicí j - pravděpodobnost nalezení opravitelného výrobku kontrolní stanicí j
Označme dále d j , dˆ j - náklady na jednotku objemu zásobníku pracovní stanice j a transportního subsystému j α j , β j - přípustné pravděpodobnosti překročení kapacity zásobníku pracovní stanice j a transportního subsystému j Cílem optimalizační úlohy je potom nalézt minimum funkce L
∑ (d N j
j =1
za splnění podmínek
j
+ dˆj M j )
λc j cc j
P(n j = N j +1) ≤ α j , j =1,K,L, P(m j = M j +1) ≤ β j ,
j =1,K,L.
(1)
To znamená, že hledáme nejmenší „přípustné“ kapacity zásobníků, při kterých s předem danou pravděpodobností nedojde k přeplnění zásobníků a tím k zablokování linky. Prvek, který za těchto podmínek vyžaduje největší kapacitu zásobníků, je nejslabším článkem v lince (bottleneck). Mezi výstupní itenzitou λcL a vstupní intenzitou λaL platí následující vztah λcL λa = L ∏ j=1(1− α j )(1− β j )(1− p j ) Za předpokladu, že pravděpodobnosti přeplnění zásobníků jsou nulové, bude λa =
∏
λcL L j=1
(1− p j )
Optimalizační algoritmus potom může probíhat v následujících krocích: 1) Načti vstupní údaje o lince: L, λa ,c a , p j , q j , µ j , µˆ j , α j , β j . Polož
λ1a = λa ,c1a = c a .
2) Pro j=1,…,L postupně 2a) minimalizuj d j N j za podmínky P( n j = N j + 1) ≤ 2b) minimalizuj dˆ j M j za podmínky
αj
P(m j = M j +1) ≤ β j
3) Pro j=1,…,L spočti charakteristiky stanic (průměrný počet jednotek v zásobnících N j , M j , průměrné doby čekání W j ,V j , intenzitu provozu ρ . Hlavní problém spočívá v kroku 2. Pro výpočet pravděpodobností v (1) bychom potřebovali znát rozdělení pravděpodobnosti dob mezi vstupy jednotek do stanice j (= výstupy ze stanice j-1) a jejich stochastickou nezávislost. To však lze předpokládat pouze v případě systémů M/M/1/k. V obecném případě G/G/1/k jsou doby mezi výstupy ze systému závislé a jejich rozdělení pravděpodobnosti nelze „rozumným způsobem“ vyjádřit. Druhý problém lze obejít aproximací rozdělení doby mezi příchody a doby montáže rozděleními fázového typu PH(α,T) a PH(β,S). Rozdělení dob mezi výstupy je potom opět rozdělení fázového typu se známými parametry. Závislost dob mezi odchody v systému G/G/1 je
způsobena tím, že systém může být ve stavu, kdy čeká na příchod montážní jednotky. Pokud by nečekal, potom bude rozdělení dob mezi výstupy shodné s rozdělením dob montáže a tyto doby budou stochasticky nezávislé. V našem případě nás zajímá situace, kdy je systém blízko „přeplnění“, tedy má naplněný zásobník a čekání na příchod montážní jednotky nehrozí. V takovém případě můžeme závislost zanedbat a předpokládat, že doby mezi odchody jednotek ze stanice jsou nezávislé, neboli že doby mezi vstupy do následující stanice jsou nezávislé. Potom můžeme použít následující postup: Ad 2a) Minimalizace výrazu d j N j znamená nalezení nejmenšího Nj takového, že je ještě splněna uvedená podmínka. Splnění této podmínky lze převést na podmínku λaj − λdj ≤ α j. λaj
(2)
d K tomu je třeba spočítat hodnotu intenzity výstupního proudu λ j . d Obecně lze tuto hodnotu spočítat spolu s variačním koeficientem c j
z obecného vztahu pomocí derivací Laplace-Stieltjetsovy transformace F*(t) distribuční funkce F(t) dob mezi odchody:
[
]
λ = −[F *' (0)] , c = λ F *'' (0) − (F *' (0)) .1/ 2 . −1
2
(3) V některých případech lze vztah (3) nahradit analytickým výrazem, jak je tomu například při předpokladu rozdělení fázového typu (viz dále). Prakticky tento krok probíhá tak, že začneme od Nj = 1, pomocí (3) spočteme λdj ,c dj a zjistíme splnění podmínky (2). Není-li splněna, zvýšíme Nj o 1 a vše opakujeme, dokud nebude (2) splněno. Ad 2b) Po ukončení kroku 2a) spočteme λbj ,c bj ze vztahů
λbj = (1 − p j )λdj , cbj = [ p j + (1 − p j )(c dj ) 2 ]
1/ 2
c c a postupným výpočtem λ j , c j a zvyšováním hodnoty Mj od 1, dokud
nebude platit nerovnost analogická (3): λbj − λcj ≤ β j. λbj
Za předpokladu například useknutého normálního rozdělení doby montáže, rovnoměrného rozdělení a řady jiných, je velmi proble-
matické vyjádření distribuční funkce F(t) a její L-S transformace. Poněkud jednodušší situace je při použití rozdělení fázového typu. 4. Aproximace rozdělením fázového typu Definice: Náhodná veličina Y má rozdělení fázového typu (PH rozdělení) s reprezentací (α,T) řádu p, dá-li se interpretovat jako doba do absorpce Markovova procesu s p+1 stavy, z nichž stav (p+1) je absorpční, s počátečním rozdělením (α, α0) a maticí intenzit
⎛ T T0 ⎞ ⎟. ⎟ 0 0 ⎝ ⎠
přechodů ⎜⎜
Poznámka: Je-li matice T regulární, potom jsou stavy 1, …, p přechodné a veličina Y je s pravděpodobností 1 konečná (viz [1]). Charakteristiky PH rozdělení: Označme e vektor samých jedniček. (i)
Distribuční funkce náhodné veličiny Y má tvar
(ii)
Hustota pravděpodobnosti náhodné veličiny Y je rovna
(iii)
F ( y ) = 1 − α exp(Ty )e F (y) = 0
f ( y ) = α exp(Ty )T 0 e f (y) = 0
y≥0 y<0
Budeme-li interpretovat Y jako dobu do poruchy, potom intenzitu poruchy lze vyjádřit vztahem
r ( y) = (iv)
y≥0 y<0
f ( y) α exp(Ty )T 0 = 1 − F ( y) α exp(Ty )e
Je-li T regulární, potom Laplaceova transformace PH rozdělení má tvar ∞
∫e
− sy
F (dy ) = α ( sI − T) −1 T 0
0
(v)
Je-li T regulární, má náhodná veličina Y všechny momenty konečné a
mk = EX k = (− 1) k!αT − k e k
k ∈N
Lze ukázat, že množina rozdělení fázového typu je hustá v množině všech spojitých rozdělení na intervalu 0, ∞) . To znamená, že libo-
volné spojité rozdělení na 0, ∞) lze aproximovat libovolně přesně nějakým rozdělením fázového typu. Tato aproximace ovšem není jednoznačná a v některých případech může být konvergence k limitnímu rozdělení velmi pomalá. Nicméně, pro řadu obvyklých rozdělení lze tuto aproximaci nalézt poměrně dobře (viz [2]). 5. Závěr V případě montážní linky s ne-exponenciálními rozděleními doby montáže a dob mezi vstupy montážních jednotek do linky lze nalézt kritická místa pomocí algoritmu, naznačeného v kapitole 3. Tento algoritmus lze zjednodušit aproximací rozdělení doby montáže a doby mezi příchody jednotek do systému rozdělením fázového typu. Literatura
[1] Neuts, M. F. (1981). Matrix geometric solutions in stochastic models. Johns Hopkins University Press, Baltimore, MD [2] Johnson, M. A., Taaffe, M. R., The denseness of phase distributions. Research Memorandum No. 88-20, School of Industrial Engeneering, Purdue University [3] Asmussen, S., Olsson, M., Nerman, O., Fitting Phase-type Distributions via the EM Algorithm. Scandinavian Journal of Statistics 23 [4] Dohnal G., Meca M.: Fitting Distribution of Nonnegative Random Variable with PH-distribution. Workshop CTU 2002 [5] Dohnal G., Meca M.: Aproximace obecných systémů hromadné obsluhy pomocí EM algoritmu. ROBUST 2002, JČMF, 87-94 Adresa autora: Doc. RNDr. Gejza Dohnal, CSc., České vysoké učení technické v Praze, Fakulta strojní, Ústav technické matematiky, Karlovo nám. 13, 121 35 Praha 2 e-mail: gejza.
[email protected] Tato práce byla vytvořena za podpory projektu MŠMT 1M06047 - CQR
