Késleltetett összeszerelı üzemek logisztikával integrált termelésirányításának matematikai modellje és fázis algoritmusai

GUBÁN ÁKOS1, DR. CSELÉNYI JÓZSEF2

Késleltetett összeszerelı üzemek logisztikával integrált termelésirányításának matematikai modellje és fázis algoritmusai

1. A rendszer általános leírása Egy adott diszkrét terméket gyártó üzem külsı megrendelés vezérelt rendszerének irányítása egy összetett feladat, melyet bonyolít, az hogy a gyártósorok nem homogének, valamint a megrendelések idıben elosztva érkeznek ismeretlen gyakorisággal. Ezért szükség lehet egy megrendelés után a termelési és raktározási folyamatok átütemezésére. Így a rendszer kétszintő lesz: statikus és dinamikus. A statikus modell egy rögzített megrendelés halmazhoz rendel egy gyártási ütemtervet, mely tartalmazza az alkatrész megrendelést, beszállítást, raktározást, összeszerelést, és a készáru-raktározást. A cél az összköltség minimalizálása a kiszállítási határidık betartása mellett. A továbbiakban feltételezzük, hogy két raktár lesz, egy alkatrész- és egy készáruraktár, és tárolókapacitásuk felülrıl nem korlátos. A dinamikus rendszer a statikus rendszer fölé épül úgy, hogy egy megrendelés beérkezésekor újraszámítást végez a mőveleti soron kívül lévı megrendelési tételekre. Ezért fontos, hogy a statikus algoritmus futási ideje alacsony legyen. A modell öt logikai szintet tartalmaz (1. ábra). Részei: beszállítók, alkatrészraktár, szerelısorok, készáruraktár, és felhasználók. A felhasználók felıl egy megadott ∆T középtávú idıre (negyedév, hónap, néhány hét) vonatkozó megrendeléseket tároljuk, és minden megrendelésrıl nyilvántartjuk, az igényelt termé1 2

BGF Pénzügyi és Számviteli Fıiskolai Kar Salgótarjáni Intézet, fıiskolai adjunktus. Miskolci Egyetem Anyagmozgatási és Logisztikai Tanszék, tanszékvezetı egyetemi tanár.

226

GUBÁN Á., CSELÉNYI J.: KÉSLELTETETT ÖSSZESZERELİ ÜZEMEK LOGISZTIKÁVAL...

keket, ezek mennyiségét, valamint teljesítési idejüket. Mivel a termékek száma korlátos ezért ezek az adatok mátrixokkal egyszerően leírhatók. A statikus rendszer mőködését a megrendelések vezérlik, a megrendelések ismeretében elindul egy visszafelé haladó ütemezési eljárás, mely meghatározza az összeszereléshez szükséges alkatrészek mennyiségét, a szerelısorok kiosztását, a sorozat nagyságokat. Ezek ismeretében történik az alkatrész-beszállítás ütemezése. Mindkét esetben költségszámítás történik. Az nyilvánvaló, hogy a két költség összege – bármennyire is minimálisak – nem feltétlen lesz optimális, mivel a második költség függ az elsı költség ütemtervétıl. Ezért szükség van harmadik lépésre is, egy finomhangolására, ami egy érzékenységvizsgálat. A megfelelı paraméterek módosítása hogyan hat a modellre.

1. ábra A rendszer váza A cél: megrendelésfüggıen olyan ütemtervet kialakítani, mely optimális szinten tartja az összköltséget. Egyszerősítések, melyek az alkalmazhatóságot nem szőkíti le: a beszállítók egymástól függetlenül szállítanak az alkatrészraktárba, és egy adott alkatrészt egy beszállító szállít, egy beszállító akár több terméket is szállíthat. A beszerzési egységköltség nem függ a mennyiségtıl. A tárolás egy egységes alkatrészraktárban történik a kiszállítás a szerelısorok felé csak ebbıl a raktárból történik. Bármely alkatrész bármely szerelısor felé szállítható. A késztermékek a készáru-raktárba kerülnek be, és a felhasználók felé is csak innen

227

BUDAPESTI GAZDASÁGI FİISKOLA – MAGYAR TUDOMÁNY NAPJA, 2001

történhet kiszállításuk. A szerelısorokon a termékek sorozatban készülnek, a sorozatszám rögzített és nem bontható. A gyártási költségek a gyártósorokon eltérıek, a beszerzési egységköltség nem függ a mennyiségtıl. A készáruraktár tárolókapacitására nem teszünk fel korlátot, és a készáruk kiszállítási költsége a felhasználókat terheli.

2. A feladat szétbontása Mint fent említettük, a statikus feladatot három fázisra bontjuk szét. A Beszerzés-Alkatrészraktározás-Szerelés-Készáruraktározás-Kiszállítás ötös határozza meg a feladat részköltségeit (1. ábra). Az I. fázisra vonatkozó költségrészek: Szerelés-Készáruraktározás. A fázis feladata a megrendelésekben szereplı késztermékekre gyártósoronként olyan gyártási programot adni, melyben az átállási-, gyártási és készáru raktározási költségek minimálisak. A fázis eredménye egy program és az alkatrészraktár készleteinek idıbeli mennyisége. A II. fázis feladata a Beszerzés-Alkatrészraktározás költség vizsgálata. A megadott alkatrész rendelkezésre álláshoz az alkatrész megrendelésekre, beszállításokra és raktározásra ad megfelelı ütemterv készítése. Eredménye egy költségérték. A III. fázis a finomhangolás: vizsgáljuk, hogyan alakul az elsı és második fázis költsége a paraméterek megfelelı változtatásával. A hangolás természetesen egy érzékenység vizsgálaton keresztül valósul meg. A jelen cikkben az I. fázis vizsgálatát végezzük el.

3. Az I. fázis A fázist a megrendelések vezérlik, az ismert megrendelések kiszállítási idıpontjait tekintjük a módszer kiindulási adatainak. Olyan gyártási sorrendet (gyártósoronként) határozunk meg, amely teljesíti a kényszert és a gyártási-, átállási-, termékraktározási költségek és a szerelısorok kihasználatlanságából származó veszteség összköltsége minimális lesz. A feladatban kezdetben a kényszerek nem sérülhetnek. Feltételezzük, hogy az egységes alkatrész raktárban minden alkatrész a szükséges idıre rendelkezésre áll (II. fázis). Az alapadatok az eljárás elindítása elıtt ismertek.

3.1. Az I. fázisban használt alapadatok A[ν,i] B[ν,µ] Tτ[ν,i] TP[k,ν] TC[k,ν] KP[k,ν] KC[k,ν] KS[k] KST [ν] ahol:

228

az i-edik megrendelésben a ν-edik termékbıl megrendelt mennyiség; a ν-edik termékbe a µ alkatrészbıl beépülı darabszám; az i-edik megrendelés ν-edik termékének relatív kiszállítási idıpontja; a k-adik szerelısoron ν-edik termékének átfutási ideje; a k-adik szerelısoron ν-edik termékének átállási ideje; a k-adik szerelısoron ν-edik termékének gyártási költsége; a k-adik szerelısoron ν-edik termékének átállási költsége; a k-adik szerelısor egységnyi idıre esı állási költsége; ν-edik terméknek egységnyi idı alatti tárolási költsége,


ν∈[1;νm] a termékazonosító, i∈[1;in] a megrendelés azonosító, k∈[1;kl] a szerelısor azonosító, µ∈[1;µj] alkatrész azonosító; υ,i,k,µ∈N+

3.2. Az I. fázis eredményadatai TR[ν;i]:

az i-edik megrendelés ν-edik termék utolsó darabjának elkészülési idıpontja fp(µ,t): alkatrész igényfüggvény, alkatrészenként a 0 ≤ t ≤ ∆T idıintervallum alatt. TST[ν;i] = Tτ[ν;i] – TR[ν;i] (≥0): i-edik megrendelés ν-edik termék raktározási ideje.

3.3. Az I. fázis általános algoritmusa A kiszállítási idıpontok Tτ[ν;i] ismeretében számítsuk ki minden együttesen megrendelt azonos termékekre teljes gyártási idıt, minden egyes sorra!

TT

k ,i ,ν

= Aν ,i ⋅ T P

k ,ν

Létrehozunk a termékekre egy egységes kielégítési sort, egyetlen virtuális gyártósort feltételezve. A sorban a termékeket a kiszállítási idejük szerint sorrendbe rendezzük: ν1 ,ν 2 ,ν 31 ,K ,ν n a termékek sorrendje azáltal, hogy Tiτ ,ν ≤ Tiτ ,ν ≤ Tiτ ,ν ≤ K ≤ Tiτ ,ν 1

1

2

2

3

3

n

n

ahol a ν1 az i1 megrendeléshez, a ν2 az i2 megrendeléshez, … , a νn az in megrendeléshez tartozó termék. A kialakított sorrend felhasználásával osszuk ki a termékeket a valódi gyártósorokhoz! Jelöljük egy gyártósor felszabadulásának relatív idıpontját τk-val (k = 1,…kl.). (τk:= 0). Illetve a k-adik gyártósorhoz tartozó terméksorozat: sk := NUL, és a gyártósor kiosztási láncot pedig c := NUL szimbolizálja. A kiosztás: a ν1 terméket rendeljük ahhoz a sorhoz (k1), amelyiken a gyártása a legkisebb költséget igényli, és a gyártás határidın belül befejezıdik:

{

k = min Aυi ⋅ K kpυ + δ ⋅ K kpυ

}

τ

τ k + T k ,i ,ν + δ ⋅ T k ,ν ,i ≤ Tν ,i τ k := τ k + TkTυi + δTkCυi T

C

valamint a gyártósorhoz tartozó terméksor: sk := sk ⊕ (υ , i ) ; c := c ⊕ k ahol δ jelzi, hogy történt-e szerelısor átállítás, és a ⊕ jel pedig a láncképzés mőveletét szimbolizálja. A ν2 terméket a maradék sorok közül ahhoz rendeljük, amelyiken a gyártása a legkisebb költséget igényli (k2) és teljesíti a kényszerfeltételt. A további termék együttesekhez azon gyártósorok közül választunk, amelyiken még lehetséges a kiszállítási idıig való teljesítés, és amelyiken a legkisebb költséggel tudjuk gyártani. Amennyiben egy termékhez bármely hozzárendelés sérti a kényszert, az eljárás egy termékkel visszalép úgy, hogy a közvetlen elıtte

229


lévı termékhez azt a legjobb sort rendeljük, amely teljesíti a kényszert és a költség a legkisebb. A visszaléptetésekhez az alábbi láncmőveleteket kell elvégezni: sk := sk ⊕ (υ , i ) , c := c ⊕ k Azaz az utolsó elemeket leválasztjuk a sorokról, és jelezzük, hogy ez a gyártósor már nem használható fel. Majd újra indítjuk a kiosztást ettıl az elemtıl kezdıdıen. Ha ez sem jó, akkor további visszalépésre van szükség. Az algoritmus nem lesz polinomiális lépésszámú, mivel az elemszám mérete nem nagy, valós idıben megoldást ad. Amint sikerült egy kezdeti lehetséges sk, c kiosztás kapnunk, meghatározzuk a költségeket. A sorokon kialakult termék sorrendek: 1. gyártósor: ν11 ,ν12 ,K ,ν1l1 és a megrendelés azonosítók: i11 , i12 ,K , i1l1

M km

gyártósor:

ν km 1 ,ν km 2 ,K ,ν kmlkm és

a

megrendelés

azonosítók:

ikm 1 , ikm 2 ,K , ikml km

2.ábra Kezdeti kiosztás Az algoritmus kiosztása eljárása a gyártósor kihasználatlanságot az idı intervallum végére helyezi, mértéke: TkKih = max Tυτi − υ ,i

lk

∑ TkiT

m =1

kmν km

A kiszámításra kerülı költségek: átállási költség egy soron: K kC = teljes átállási-költség: K

C

=

∑

lk

∑ K kCν

m =1 K kC ;

; km

k

szerelési költség egy soron: K kP = teljes gyártási-költség: K P =

∑ k

230

lk

∑ K kPν

m =1 K kP ;

km

⋅ Aν km ikm ;

.


a k-adik soron a ν kj sorszámú termék gyártás kezdés idıpontja: TνB = k, j

a ν kj termék tárolási ideje és költsége: TνST = Tντ − kj kj STT

Kν

kj

ST

= Tν

kj

ST

⋅ Kν

kj

⋅ Aν

kj ,ikj

j −1

∑ TνT

m =1

;

km

j

∑ TνT

m =1

,

km

;

a teljes tárolási költség: K ÖST =

km lk

∑∑ KνSTT ; kj

k =1 j =1

kihasználatlanságból eredı költségek: K

KIH

=

lk

∑ K kS ⋅ TkKIH

k =1

és a teljes költség: K1 = KC + KP + KÖST + KKIH. A K1 költség egy lehetséges költségérteket ad, ami egyáltalán nem biztos, hogy optimális lesz. Ezért olyan eljárásokat keresni kell, amelyek javítanak a költségértéken, és optimum közelébe viszi az összköltséget.

3.4. A megoldás javításának elsı lépése Nyilván a megoldás javítására több lehetıség kínálkozik, többek között termékek átrendezése, vagy az azonos típusú, de különbözı megrendelésekhez tartozó termékek gyártásának összevonása (csökken az átállási költség és idı), valamint javító megoldásnak tőnik a teljesítés idıbeli csúsztatása a lehetséges határidın belül (raktározási költség csökkentése). A megoldást elıször összevonással javítjuk, majd az így kapott lehetıségek közül a legjobbat kiválasztva, csúsztatással próbáljuk meg még tovább javítani a költségértéket. 3.4.1. Az összevonások Az összevonásokat a kezdeti virtuális gyártósoron hajtjuk végre. A megoldás során, virtuális a soron az azonos termékek összevonását végezzük el. Minden esetben csak két azonos terméket vonunk össze. Az összevonás után a teljesítés idıpontja: ) TT = TT + TT l

l

p

type(νl) = type(νk)

∑ (ThT + δThC ) ≤ Thτ ; h ∈ [l + 1,K, p − 1] i

h =1

231


3. ábra Összevonások Az összevonások után az elızı eljárást alkalmazva, szétosztjuk – amennyiben lehetséges – a gyártósorokhoz az így kialakult termékeket. Ha a kiszámított költségfüggvény kisebb értéket ad, mint a korábbi újabb összevonást végzünk, a különbözı lehetıségek segítségével. Az nyilvánvaló, hogy, ha túl távoli elemeket vonunk össze, akkor a késztermék raktározási költséget nagy mértében megnövelhetjük. A pár összevonások lehetıségének száma: n (n − 1) 0≤σ ≤ 2 továbbá az összes lehetıség az együttes párösszevonásokra: ) σ = 2σ ami már aránylag kis n érték mellett is nagyon nagy szám lehet. A megoldás során célszerő figyelembe venni a BELLMAN-féle optimalitási tétel [3] megfogalmazását. Így az összevonások sorozata optimumot ad, ha minden lépésben javítást adunk. Az összevonásokat mindig a sor elejérıl kezdve indítjuk el, ha σ nem túl nagy (azaz σ ≤ n), akkor minden esetet célszerő figyelembe venni. Ellenkezı esetben egy módosított Branch and Bound eljárást alkalmazunk. 3.4.2. Idıbeli csúsztatás Amennyiben rendelkezünk egy lehetséges megoldással az összevonások után, akkor a kihasználatlansági helyeket helyezzük el gyártósoronként úgy, hogy a kényszer feltétel ne sérüljön meg, és a költségfüggvény értéke csökkenjen. Ezzel a megoldással a költségfüggvény raktározási költségkomponensét tudjuk csökkenteni. A csúsztatást gyártósoronként egymásután végezzük el, és minden esetben külön-külön hatáselemzést végzünk. Az eljárás gondolatmenete a következı: vegyük egy gyártósor sorához tartozó utolsó terméket! A gyártáskezdési idıpontot toljuk el az idıintervallumon mindaddig az idıhatárig, míg a kényszerfeltétel nem sérül. Mivel a gyártás végpontját a lehetséges határig kitoltuk, ezért a raktározási idıtartamot csökkentettük, így a költség is csökken. Ezután vegyük a közvetlen a sorban elıtte lévı terméket és erre is végezzük el a csúsztatást, majd a többi termékre hasonlóan. Ha minden termékre elvégeztük, biztos hogy egy lehetséges megoldást kaptunk. Már egy csúsztatás esetén is csökken a raktározási

232


költség. Folytassuk ugyanezt az eljárást a következı gyártósoron. Az eljárás elvi mőködését a 4. ábra mutatja be egy gyártósorra.

4. ábra Idıbeli csúsztatás elvi mőködése Az elsı fázis így egy optimum közeli megoldást biztosít a K1 költségre. A továbbiakban az alkatrészraktár kezelésére, és kiszolgálására kell eljárást adni, ez a második fázis feladat lesz. A csúsztatás algoritmusát az 5. ábra vázolja.

4. A II. fázis vázlatos ismertetése A fázis elindítása csak az elsı fázis algoritmusának, és eredményeinek ismeretében lehetséges. A második fázis az elsıtıl megkapja az alkatrész raktár – minden idıpontra meghatározott – minimális készleteit alkatrészekre lebontva. Ehhez kell a beszállítást megszervezni úgy, hogy most a kényszerfeltétel a minimális igény kielégítése lesz. A megoldás során ismertnek tételezzük fel a beszállítási útvonalakat, jármő típusokat, minimálisan szállítható mennyiségeket, szállítási 233


fajlagos költségeket, továbbá az együttszállítható alkatrészeket. Továbbá, rögzítetnek tételezzük fel a beszállító felé elindított megrendelés és a beszállítás között eltelt idıt. A beszállítás ütemezését úgy kell megoldani, hogy a szállítási és alkatrész-raktározási költségek minimálisak legyenek a megadott elsı fázisbeli ütemezéshez (K2). A feladat méretébıl adódóan, ebben a fázisban nagyobb szerepet kapnak a heurisztikák. A beszállítás ütemezéséhez a genetikus algoritmus nyújt segítséget. A fázis vizsgálati körébe tartozik a jármőindításhoz szükséges feltételek, kihasználtság stb.

5. ábra A csúsztatás algoritmusa

5. Következtetés A késleltetett összeszerelı üzemek megrendelés vezérelt gyártásütemezési problémáját több fázisra kell bontani. Minden fázis igényli az egzakt matematikai megoldásokat, de néhány esetben a feladat méretébıl adódóan heurisztikákat és szimulációs módszereket kell alkalmazni. A modell felépítése során fontos feladat az elkészült modellek hatékonyságvizsgálata. Mivel eltérı körülmények között eltérı módon viselkedhetnek az eljárások. A jelen cikkben nem részletezett második és harmadik fázis kidolgozása teljesen hasonlóan történik mint az elsı fázisé,

234


azaz minden eljárás és modell a költségfüggvényeken alapul és ennek minimumát vagy minimum közeli értékét keressük. egy megadott idıkorláton belül. A feladat végsı célja a teljes dinamikus rendszermodell felépítése és részletes futás- és környezeti elemzése.

Irodalom [1] SÁRKÖZI, F.: Mesterséges neurális hálózatok, mint GIS függvények. [2] FISCHMAN, G. S.: Monte Carlo: Concepts, Algorithms, and Applications, Springer, Berlin, 1997. [3] TÓTH, T.: Tervezési elvek, modellek és módszerek a számítógéppel integrált gyártásban, Miskolci Egyetemi Kiadó 1998. [4] GUBÁN, M.: Szállítási feladat, PSZF, 1997. [5] DAVIS L.: Handbook of Genetic Algorithms, Van Nonstrand Reinhold 1991. [6] SCHWEFEL, H. P.: Numerische Optimierung von Computer-Modellen mittels Evolutionsstrategie, Birkhäuser Verlag, Basel, 1977. [7] HUIRONG MENG, SHAOKUI YANG: Reliability Assement for Compound Carrier of Planetary Gearbox by ANN-MC Method Ten World Congress on the Theory of Machine and Mechanisms, Oulu, Finland, June 20-24, 1999. [8] GUBAN, A.: The Genetic Algorithm and Application of Gas EMES’99 Meeting Felix-Spa May 27-29 1999.

235

Késleltetett összeszerelı üzemek logisztikával integrált termelésirányításának matematikai modellje és fázis algoritmusai

Recommend Documents