Rozvrhování montážních systémů 24. dubna 2023 1 Montážní linka s flexibilním časem 2 Montážní linka s fixním časem Montážní linka Job shop každá úloha má jednoznačnou identitu výroba na objednávku, malý objem výroby potenciálně komplikovaná cesta systémem velmi obtížný problém Montážní linka (flexible assembly system) limitovaný počet odlišných typů výrobků specifikováno vyráběné množství každého typu systém pro manipulaci s materiálem startovní čas úlohy je funkcí času dokončení na předchozím stroji limitovaný počet úloh čekajících ve frontě mezi stroji masová produkce ještě obtížnější problém Hana Rudová, FI MU: Rozvrhování montážních systémů 2 24. dubna 2023 Montážní linka s flexibilním časem (unpaced assembly system) Několik strojů zapojených sériově (flow system) Flexibilní čas stroj může strávit tolik času na úloze, kolik je třeba Blokování následující stroj je plný a úloha na něj nemůže být přesunuta Fronty mezi stroji? bez újmy na obecnosti lze uvažovat fronty nulové délky frontu délky n lze simulovat n stroji, na kterých je doba provádění úlohy nulová ⇒ budeme uvažovat fronty nulové délky Limitovaný počet odlišných typů výrobků Specifikováno vyráběné množství každého typu Cíl: maximalizace výkonu výkon opět definován kritickým strojem Hana Rudová, FI MU: Rozvrhování montážních systémů 3 24. dubna 2023 Příklad: výroba kopírek Různé typy kopírek montované na jedné lince Odlišné modely mají obvykle společný základ Odlišnost v rámci komponent automatický podavač ano/ne, rozdílné optiky, . . . Odlišnost typů vede k odlišným dobám výroby na jednotlivých strojích Hana Rudová, FI MU: Rozvrhování montážních systémů 4 24. dubna 2023 Cyklické rozvrhy Rozvrhy jsou často cyklické nebo periodické daná množina úloh rozvrhována v určitém pořadí jsou obsaženy všechny typy výrobků některé typy zde mohou být vícekrát druhá identická množina rozvrhována, atd. Nevhodné pokud jsou dlouhé nastavovací doby pak se vyplatí dlouhé běhy výrobku jednoho typu Praktické pokud nevýznamná nastavovací doba nízké skladovací náklady snadné na implementaci nicméně: acyklický rozvrh může dávat maximální výkon V praxi cyklické rozvrhy s malými odchylkami závislými na aktuálních objednávkách Hana Rudová, FI MU: Rozvrhování montážních systémů 5 24. dubna 2023 Minimální podílová množina (minimum part set) Předpokládejme l typů výrobků Nk požadovaný počet výrobků typu k z největší společný dělitel Potom N∗ = N1 z , . . . , Nl z je nejmenší množina se „správnými” proporcemi minimální podílová množina (MPS, minimum part set) Uvažujme úlohy v MPS jako n úloh: n = 1 z l k=1 Nk pij jako dříve cyklický rozvrh je rozvrh určen seřazením úloh v MPS maximalizace výkonu = minimalizace doby cyklu Hana Rudová, FI MU: Rozvrhování montážních systémů 6 24. dubna 2023 Příklad: MPS Systém se 4 stroji Tři odlišné typy výrobku, které musí být vyráběny ve stejném množství, tj. N∗ = (1, 1, 1) Doby provádění Úlohy 1 2 3 p1j 0 1 0 p2j 0 0 0 ← fronta mezi strojem 1 a 3 p3j 1 0 1 p4j 1 1 0 Hana Rudová, FI MU: Rozvrhování montážních systémů 7 24. dubna 2023 Příklad: posloupnost v MPS 1,2,3 Úlohy 1 2 3 p1j 0 1 0 p2j 0 0 0 p3j 1 0 1 p4j 1 1 0 1 1 3 3 1 1 1 1 1 3 3 1 1 1 32 2 2 2 22 2 0 1 2 3 5 4 6 7 doba cyklu=3 1 2 3 4 stroje 8 Hana Rudová, FI MU: Rozvrhování montážních systémů 8 24. dubna 2023 Příklad: posloupnost v MPS 1,3,2 Úlohy 1 2 3 p1j 0 1 0 p2j 0 0 0 p3j 1 0 1 p4j 1 1 0 1 1 12 2 2 3 3 2 1 1 2 1 3 1 3 2 1 0 1 2 4 5 6 doba cyklu=2 3 4 stroje 2 1 3 Hana Rudová, FI MU: Rozvrhování montážních systémů 9 24. dubna 2023 Minimalizace doby cyklu Heuristika padnoucího profilu (profile fitting heuristic, PF) Vyber první úlohu j1 výběr libovolné úlohy nebo výběr úlohy s nejdelší celkovou dobou provádění Úloha generuje profil Xi,j1 = i h=1 ph,j1 předpokládáme, že úloha j1 poběží bez blokování ⇒ Xi,j1 čas odchodu: čas, kdy úloha j1 opustí stroj i Hana Rudová, FI MU: Rozvrhování montážních systémů 10 24. dubna 2023 PF: určení následující úlohy Spočítej pro každou možnou úlohu dobu, kterou stroje čekají dobu, kdy je úloha blokována spočítej čas odchodu pro kandidáta na druhou pozici (j2), např. pro úlohu c (j1: úloha na první pozici) X1,j2 = max(X1,j1 + p1c, X2,j1 ) Xi,j2 = max(Xi−1,j2 + pic, Xi+1,j1 ) i = 2, . . . , m − 1 Xm,j2 = Xm−1,j2 + pmc Hana Rudová, FI MU: Rozvrhování montážních systémů 11 24. dubna 2023 PF: určení následující úlohy Spočítej pro každou možnou úlohu dobu, kterou stroje čekají dobu, kdy je úloha blokována spočítej čas odchodu pro kandidáta na druhou pozici (j2), např. pro úlohu c X1,j2 = max(X1,j1 + p1c, X2,j1 ) Xi,j2 = max(Xi−1,j2 + pic, Xi+1,j1 ) i = 2, . . . , m − 1 Xm,j2 = Xm−1,j2 + pmc neproduktivní doba na stroji i, pokud je c na druhé pozici: Xi,j2 − Xi,j1 − pic celková neproduktivní doba (přes všechny stroje) pro c: m i=1 (Xi,j2 − Xi,j1 − pic) úloha s nejmenší neproduktivní dobou vybrána na druhou pozici (pro další pozice opakuj totéž) ... myšlenka padnoucího profilu Hana Rudová, FI MU: Rozvrhování montážních systémů 12 24. dubna 2023 Diskuse PF heuristika se chová v praxi dobře stále platí, že při použití heuristiky PF nehrají roli nastavovací doby Zjemnění: neproduktivní doby nejsou stejně špatné na všech strojích uvažuj kritický stroj použití vah v součtu Hana Rudová, FI MU: Rozvrhování montážních systémů 13 24. dubna 2023 Montážní linka s fixním časem Popis modelu transportér, který se posunuje konstantní rychlostí výrobky, které se vyrábí se posunují mezi stroji pevnou rychlostí jednotková doba cyklu: určena jako doba mezi dvěma po sobě jdoucími úlohami na lince každý stroj má danou kapacitu a omezení cíl: uspořádat úlohy tak, aby nebyly stroje přetíženy a byla minimalizována cena za nastavení Příklad: výroba automobilu rozdílné modely vyráběné na stejné lince auta mají odlišné barvy a vybavení vyráběná auta uspořádána tak, aby byla minimalizována cena za nastavení a stroje na lince byly rovnoměrně vytíženy Hana Rudová, FI MU: Rozvrhování montážních systémů 14 24. dubna 2023 Skupiny a distribuce Atributy a charakteristiky každé úlohy barva, vybavení, . . . Cena za změny při výrobě vytváření skupin výrobků, které mají vybrané atributy stejné např. barva auta Časově náročné operace distribuuj úlohy, které obsahují tyto operace operace omezující kapacitu (index kritičnosti) operace s vyšším indexem jsou kritičtější např. instalace posuvné střechy př. čtyřikrát časově náročnější, 10% aut má posuvnou střechu, tj. index kritičnosti = 4/10 sekce linky pro instalaci posuvné střechy musí být vytížena alespoň čtyřikrát méně než sekce pro automobily bez posuvné střechy, jinak nebude dostatek času na instalaci posuvné střechy Hana Rudová, FI MU: Rozvrhování montážních systémů 15 24. dubna 2023 Kritéria Minimalizace celkové ceny na nastavení Splnění termínů dokončení pro výrobky na objednávku celkové nezáporné vážené zpoždění opakování: Tj = max(Cj − dj , 0) Distribuce operací omezujících kapacitu ψi (l) značí penalizaci, pokud stroj musí vyrábět dva výrobky, které jsou l pozic od sebe Pravidelné tempo spotřeby materiálu Hana Rudová, FI MU: Rozvrhování montážních systémů 16 24. dubna 2023 Heuristika seskupování a distribuce (grouping and spacing) 1 Urči celkový počet úloh, které mají být rozvrhovány vyšší počet úloh na rozvrhování umožní nižší cenu, ale snadněji dojde k narušení rozvrhu typicky jeden den až týden 2 Seskup úlohy obsahující operace s vysokými cenami za nastavení 3 Uspořádej skupiny podle nastavovacích cen a termínů objednávky 4 Distribuuj úlohy v rámci skupiny tak, aby byly brány v úvahu operace omezující kapacitu nejkritičtější operace distribuovány co nejlépe co nejdříve a zohledni přitom termíny objednávky Hana Rudová, FI MU: Rozvrhování montážních systémů 17 24. dubna 2023 Jednoduchý matematický model 1 stroj, n úloh Každá úloha: pj = 1, dj (mohou být nekonečné), wj , b atributů aj1, . . . , ajb 1. atribut reprezentuje barvu 2. atribut je 1, pokud má úloha posuvnou střechu, jinak je 0 . . . Jestliže úloha j následována úlohou k a aj1 = ak1, pak je nutná cena na nastavení cjk cjk je funkcí aj1 a ak1 Jestliže aj2 = ak2 = 1, pak je nutná penalizace ψ2(l) pokud jsou úlohy j a k od sebe vzdáleny l pozic Jestliže je úloha dokončena po termínu dokončení, uvažujeme vážené nezáporné zpoždění Cíl: minimalizovat celkovou cenu včetně ceny za nastavení ceny za distribuci ceny za zpoždění Hana Rudová, FI MU: Rozvrhování montážních systémů 18 24. dubna 2023 Příklad: heuristika seskupování a distribuce (zadání) 1 stroj, 10 úloh, pj = 1 Atributy úlohy j: aj1 a aj2 Cena za nastavení s využitím aj1 pro úlohu j: dvě po sobě jdoucí úlohy mají aj1 = ak1, pak cjk = |aj1 − ak1| aj2 = ak2 = 1 a mezi j a k je (l − 1) úloh, pak ψ2(l) = max(3 − l, 0) úlohy těsně po sobě (0 = l − 1), pak je penalizace max(3 − 1, 0) = 2 jedna úloha mezi nimi (1 = l − 1), pak je penalizace max(3 − 2, 0) = 1 více než jedna úloha mezi nimi (s), pak je penalizace max(3 − s, 0) = 0 Některé úlohy mají konečné termíny dokončení, pokud překročeny, pak wj Tj brána v úvahu Úlohy 1 2 3 4 5 6 7 8 9 10 aj1 1 1 1 3 3 3 5 5 5 5 aj2 0 1 1 0 1 1 1 0 0 0 dj ∞ 2 ∞ ∞ ∞ ∞ 6 ∞ ∞ ∞ wj 0 4 0 0 0 0 4 0 0 0 Hana Rudová, FI MU: Rozvrhování montážních systémů 19 24. dubna 2023 Příklad: heuristika seskupování a distribuce (řešení) 3 skupiny dle aj1 Skupina A: úlohy 1,2,3 skupina B: úlohy 4,5,6 skupina C: úlohy 7,8,9,10 Nejlepší pořadí skupin vzhledem k ceně za nastavení A, B, C nebo C, B, A Ale úloha 7 nebo 2 by nebyla dokončena včas a cena za zpoždění vysoká ⇒ výběr pořadí A, C, B Úlohy s atributem 2 nutno distribuovat, optimální posloupnosti minimalizující penalizaci ψ2 A: 2,1,3 atributy 1 0 1 C: 8,7,9,10 atributy 0 1 0 0 B: 5,4,6 atributy 1 0 1 cena 3 (první-třetí=1, třetí-pátý=1, osmý-desátý=1) Celková cena: 6+3+0=9 (cena za nastavení+cena za distribuci+cena za zpoždění) Hana Rudová, FI MU: Rozvrhování montážních systémů 20 24. dubna 2023 Shrnutí Montážní linka s flexibilním časem př. výroba kopírek cyklické rozvrhy heuristika padnoucího profilu PF Montážní linka s fixním časem př. výroba automobilů heuristika seskupování a distribuce Hana Rudová, FI MU: Rozvrhování montážních systémů 21 24. dubna 2023