Seminarski Rad Slobodan Radicev - Redovi Cekanja

REDOVI ÈEKANJA – teorija i praktièna primena

Slobodan Radièev, 87/07 Fakultet tehnièkih nauka, Departman za industrijsko inženjerstvo i menadžment, [email protected]

Prof. dr Mila Stojakoviã Apstrakt Ovaj rad se fokusira na teoriju redova èekanja (Queuing theory) i njenom praktiènom primenom, za koju je korišãen raèunarski program WinQSB 1.0 for Windows. Program WinQSB je razvio Yih-Long Chang, a objavila kompanija Wiley. U uvodnom delu rada je opisana osnova i problematika teorije redova èekanja. Akcenat rada je stavljen na pronalaženje optimalnog rešenja za broj uslužnih mesta jednog kompleksnog problema. Takoðe, kao uvod u rešavanje kompleksnog problema je dat primer rešavanja jednog jednostavnog problema. Na kraju je prikazano kako je uz pomoã adekvatnog softvera i adekvatnog hardwera za rešeavanje kompleksnih problema potrebno samo nekoliko minuta. Kljuène reèi: Redovi èekanja, simulacija, optimalno rešenje

Novi Sad, jul 2009.

1

Sadržaj Sadržaj ..................................................................................................... 2 Teorija o èekanju u redovima ................................................................... 3 Notacije èekanja u redovima i jednostavan primer ................................... 5 Jednostavan M/M/1 primer ................................................................... 6 Brži radnici ili više radnika?.............................................................. 8 Proširenje primera: M/M/M1 i M/M/2 sa troškovima ...................... 10 Generalno èekanje u redovima............................................................ 14 Zakljuèak ............................................................................................... 21

2

Teorija o èekanju u redovima1 Teorija o èekanju u redovima se bavi problemima èekanja u redu (ili èekanja). Kao tipièni primeri mogu se navesti:  Banke i supermarketi – èekanje na uslugu  Kompjuteri –èekanje na odgovor  Otkazivanja – èekanje da nešto otkaže, tj.prestane da obavlja svoj posao, npr. deo mašine  Javni prevoz – èekanje voza ili autobusa Kao što nam je poznato, èekanje u redovima je uobièajeno svakodnevno iskustvo. Redovi se stvaraju zato što su izvori ogranièeni. Zapravo, ima ekonomskog smisla što redovi postoje. Na primer, koliko bi kasa u supermarketima bilo potrebno da bi se izbeglo èekanje u redovima? Koliko bi autobusa ili vozova bilo potrebno da bi se izbegli i/ili eliminisali redovi? U dizajniranju sistema za èekanje moramo imati za cilj ravnotežu izmeðu usluživanja mušterija (kratki redovi koji podrazumevaju puno uslužnih radnika) i ekonomskih obzira (bez prevelikog broja uslužnih radnika). U suštini, svi sistemi èekanja mogu se razložiti na individualne pod-sisteme koji se sastoje od entiteta koji èekaju na neku aktivnost. Uglavnom možemo govoriti o tom individualnom pod-sistemu kao o sistemu u kojem mušterije èekaju na uslugu. Da bismo analizirali taj pod-sistem potrebne su nam informacije u vezi sa:  Procesom dolaska o Naèin na koji mušterije dolaze, npr. pojedinaèno ili u grupama (dolasci u turama ili gomilama) o Naèin na koji se dolasci distribuiraju u toku vremena (npr. najverovatnije vreme distribucije izmeðu sukcesicnih dolazaka (distribucija vremena izmeðu dolazaka) o Postoji li konaèan broj mušterija ili (efektivno) neogranièen broj Najprostiji proces dolaska je onaj gde imamo potpuno regularne dolaske (npr. isti konstantni vremenski interval izmeðu sukcesivnih dolazaka). Poisonov tok dolazaka odgovara nasumiènim dolascima. U Poisonovom toku sukcesivne mušterije dolaze u intervalima koji su nezavisno i eksponencijalno distribuirani. Posionov tok je bitan jer je prigodan matematièki model za mnoge sisteme èekanja u stvarnom životu i opisuje ga samo jedan parametar – proseèna stopa dolazaka. Ostali bitni procesi dolaska su ugovoreni dolasci; dolasci u turama; i vremenski zavisne stope dolazaka (npr. stopa dolazaka varira u zavisnosti od doba dana).  Servisnim mehanizmom: o Opis izvora neophodnih za poèetak usluge o Koliko dugo traje obavljanje usluge (distribucija vremena usluge) o Broj dostupnog uslužnog osoblja (u daljem tekstu:radnika) o Da li je osoblje u serijama (svaki radnik ima poseban red) ili u paralelama (jedan red za sve radnike) o Da li je dozvoljeno preskakanje (radnik može da zaustavi usluživanje mušterije da bi se posvetio drugoj „hitnijoj“ mušteriji. 1

Korišãen materijal sa web sajta: http://people.brunel.ac.uk/

3

Uobièajena je pretpostavka da su vremena za izvršenje usluge prema mušterijama nezavisna i da ne zavise od procesa dolaska. Još jedna ustaljena pretpostavka o vremenima potrebnim za usluge je da se ona eksponencijalno distribuiraju. 

Karakteristikama reda: o Kako, iz cele grupe mušterija koje èekaju na uslugu, biramo sledeãu koja ãe biti uslužena (npr. PDPI 2 (prvi doðe - prvi izaðe), takoðe poznat i pod imenom PDPU3(prvi došao – prvi uslužen); PDPZ4(poslednji doðe – prvi ode); nasumièno) (to se èesto naziva i disciplinom reda) o Da li imamo:  Nepridruživanje (mušterije odluèuju da se ne pridruže redu ukoliko je suviše dugaèak)  Odustajanje (mušterije napuštaju red ukoliko su èekale suviše dugo na uslugu)  Upadanje (mušterije menjaju redove ukoliko smatraju da ãe na taj naèin biti ranije usluženi)  Red konaènog kapaciteta ili (efektivno) red neogranièenog kapaciteta Promena u disciplini reda (pravilu na osnovu kog biramo koja mušterija ãe sledeãa biti uslužena) èesto može da smanji zagušenje. Uglavnom disciplina reda koja „bira mušteriju sa najkraãim vremenom usluge“ daje kao rezultat najmanju vrednost za (proseèno) vreme koje mušteija provede èekajuãi u redu.

Tu treba primetiti da je od situacija kada se èeka u redu neodvojiva ideja o nesigurnosti što se tièe, na primer, vremena izmeðu dolazaka i vremena usluge. To znaèi da su nam potrebne verovatnoãe i statistike da bi analizirali situacije sa èekanjima u redu. Što se tièe analize èekanja u redovima, tipovi pitanja za koja smo zainteresovani uglavnom se tièu mera koje se primenjuju u radu sistema. U sklopu takvih pitanja mogu se naãi i sledeãa:  Koliko dugo mušterija pretpostavlja da ãe èekati u redu pre nego je usluže, i koliko dugo ãe morati da èeka pre nego se izvrši usluga?  Kolika je verovatnoãa da ãe mušterija èekati duže nego što je predviðeni vremenski interval, pre nego budu usluženi?  Kolika je proseèna dužina reda?  Kolika je verovatnoãa da ãe red preãi odreðenu dužinu?  Kakva je oèekivana iskorišãenost radnika i oèekivani vremenski period tokom kog èe biti potpuno okupiran (prisetite se da nas osoblje košta novca tako da je neophodno da ih držimo zauzetima). Zapravo, ako možemo da pripišemo troškove faktorima kao što su vreme koje mušterija provde èekajuãi i dokolica osoblja, tada možemo da istražimo kako da dizajniramo sistem sa minimalnim ukupnim troškovima.

2

Termin u engleskom jeziku je FIFO (first-in first-out) FCFS (first-come first served) 4 LIFO (last-in first-out) 3

4

Postoje pitanja na koja je neophodno naãi odgovor da bi menadžment mogao da oceni alternative u pokušaju da kontroliše/poboljša situaciju. Neki od problema koji su u praksi èesto istraživani su:  Da li vredi ulagati napor u smanjenje vremena usluživanja?  Koliki broj radnika na usluživanju treba zaposliti?  Da li bi trebalo uvesti neke prioritete za odreðene tipove mušterija?  Da li je prostor u kome mušterije èekaju adekvatan? Da bi se dobili odgovori na prethodno postavljena pitanja postoje dva osnovna pristupa:  

Analitièke metode teorije èekanja (na osnovu formule); i Simulacija (na osnovu kompjutera).

Razlog zašto postoje dva pristupa(umesto samo jednog) je taj što su analitièke metode odgovarajuãe za relativno proste sisteme èekanja. Kompleksni sistemi èekanja se skoro uvek analiziraju koristeãi simulaciju (više tehnièki poznata kao simulacija diskretnog dogaðaja). Prosti sistemi èekanja koji se mogu dotaãi pomoãu teorije èekanja u redovima u suštini:  Sastoje se od samo jednog reda; povezani sistemi u kojima muštrije prelaze iz jednog reda u drugi ne mogu se razmotriti kroz teoriju èekanja.  Imaju dobro definisane distribucije za procese dolaska i usluživanja (npr. standardne statistièke distribucije kao što su Poisonova ili Normalna); sistemi gde se te distribucije dobijaju iz posmatranih podataka, ili su vremenski zavisne, teško se analiziraju pomoãu teorije èekanja. Prvi problem teorije èekanja u redovima je istražio Erlang 1908.godine koji je posmatrao kolika kolièina telefonske razmene je neophodna da bi se održala razumna vrednost broja telefonskih poziva koji nisu dobijeni jer je razmena bila zauzeta (izgubljeni pozivi). U okviru deset godina razvio je (složenu) formulu za rešavanje problema.

Notacije èekanja u redovima i jednostavan primer Uobièajeno je da se koriste sledeãi simboli:  Lamda kao proseèan broj dolazaka za odreðeni vremenski period, npr.proseèna stopa dolazaka  µ kao proseèan broj mušterija usluženih u datom vremenskom periodu, npr. proseèna stopa usluženih Posotji standardni notacioni sistem koji svrstava sisteme èekanja u redu pod A/B/C/D/E, gde:  A predstavlja verovatnoãu distribucije za proces dolaska  B predstavlja verovetnoãu distribucije za proces usluživanja  C prdstavlja broj kanala(radnika)  D predstavlja maksimalani dozvoljeni broj mušterija u sistemu èekanja(onih koje èekaju ili koje su bile uslužene)

5



E predstavlja ukupni maksimalni broj mušterija

Uobièajene opcije za A i B su:  M za Poisonovu distribuciju dolazaka (eksponencijalna distribucija izmeðu dolazaka), ili eksponencijalna distribucija vremena kod usluživanja  D za determinisanu ili stalnu vrednost  G za generalnu distribuciju (ali sa poznatim prosekom i varijacijama) Ukoliko D i E nisu specifikovani, podrazumeva se da su neogranièeni. Na primer, sistem èekanja M/M/1, najprostiji sistem èekanja, ima Poisonovu distribuciju dolazaka, eksponencijalnu vremensku distribuciju i jedan kanal (jednog uslužnog radnika). Treba primetiti da prilikom korišãenja takvih notacija uvek se pretpostavlja da postoji samo jedan red (linija èekanja), i da se mušterije kreãu iz tog jednog reda prema radnicima.

Jednostavan M/M/1 primer Pretpostavimo da imamo jednog radnika na usluživanju i da mušterije pristižu u radnju po Poisonovoj distribuciji dolazaka po proseènoj stopi za koju je lamda=0,5 po minutu, što znaèi u proseku se jedna mušterija pojavi svake 1/lamda=1/0,5=2 minuta. To nagoveštava da vremena izmeðu dolazaka imaju eksponencijalnu distribuciju sa proseènim vremenom izmeðu dolazaka od 2 minuta. Radnik ima eksponencijalno vreme usluživanja sa proseènom stopom usluživanja od 4 mušterije po minutu, odnosno, stopa usluživanja je µ=4 mušterije po minutu. Tako što imamo Poisonovu stopu dolazaka/vreme eksponencijalne usluge/jednog radnika, imamo i M/M/1 red u terminima standardne notacije. Možemo analizirati takvo èekanje koristeãi program WinQSB. Unošne informacije su prikazane ispod na slici 1 i tabeli 1.

Slika 1.

6

Tabela 2

A pri èemu bi izlazna informacija bila sledeãa (Tabela 2.):

Tabela 2.

Prva linija izlazne informacije kazuje nam da rezultati potièu od formule. Za taj vrlo jednostavni sistem èekanja postoje taène formule koje nam pružaju statistike iznad svake pretpostavke da je sistem dostigao stanje mirovanja – odnosno, da je sistem bio korišãen dovoljno dugo da bi došao do neke uravnotežene pozicije. Naravno, sistemi u stvarnom životu teško da ikad dostignu takvo stanje mirovanja. Jednostavno reèeno, život prosto nije takav. Meðutim, uprkos tome, te jednostavne

7

formule èekanja u redu mogu nam pružiti pogled u to kako bi sistem mogao vrlo brzo da poène da se ponaša. Raèunaru je trebao deliã sekunde da proizvede izlaznu informaciju koju smo videli. Jedan faktor koji bi trebalo primetiti je intenzitet saobraãaja =(stopa dolaska)/Stopa odlaska), gde je stopa dolaska=broj dolazaka po jedinici vremena , a stopa odlaska = broj odlazaka po jedinici vremena. Intenzitet saobraãaja je mera zagušenja sistema. Ukoliko je blizu nule, postoji vrlo malo èekanja u redovima i generalno, kako se poveãava intenzitet saobraãaja (do blizu 1 ili èak i više od 1), iznos èekanja se poveãava. Za sistem koji smo prethodno naveli, pretpostavili smo da je stopa dolaska 0,5 a da je stopa odlaska 4, tako da je intenzitet saobraãaja 0,5/4 = 0,125.

Brži radnici ili više radnika? Razmotrite situaciju koju smo prethodno naveli – šta biste više voleli:  Jednog radnika koji radi duplo brže, ili  Dva radnika koji rade po originalnoj stopi? Jednostavan odgovor je da to možemo analizirati uz pomoã raèunarskog programa. Za prvu situaciju jedan radnik koji radi dvostruko brže od ostalih odgovara stopi usluga od µ=8 mušterija po minutu. Izlazna informacija za takvu situaciju prikazana je ispod u tabeli 3.

Tabela 3.

8

Za dva radnika koja rade po originalnoj stopi izlazna informacija je data dole (Tabela 4. i Tabela 5.). Treba obratiti pažnju da je ta situacija M/M/2 sistem èekanja. Takoðe treba primetiti da raèunarski program pretpostavlja da ta dva radnika dobijaju mušterije iz istog reda (pre nego da svaki od njih ima svoj zaseban red).

Tabela 4.

Tabela 5.

Uporedite dve izlazne informacije iznad – koju opciju preferirate? Neke navedene cifre su identiène. Izvlaèenjem cifara koje su razlièite dobijamo podatke koje si prikazani u Tabeli 6.:

9

Proseèno vreme u sistemu(èekanje i usluživanje) Proseèno vreme u redu Verovatnoãa neophodnosti èekanja u redu

Dvostruko brži radnik

Dva radnika, originalna stopa

0,1333

0,2510

0,0083

0,0010

6,25%

0,7353%

Tabela 6.

Iz priloženog se može videti da sa jednim radnikom koji radi dvostruko brže mušterije u proseku manje provedu vremena u sistemu, ali moraju da èekaju duže na uslugu i takoðe postoji veãa verovatnoãa da ãe morati da èekaju u redu.

Proširenje primera: M/M/M1 i M/M/2 sa troškovima Sada ãemo proširiti primere koji smo prethodno imali tako što ãemo sada pomožiti stopu dolaska mušterija sa faktorom 6 (tj. mušterije dolaze 6 puta brže nego u prethodnom primeru). Takoðe ãemo uneti kapacitet reda (prostor za èekanje) sa vrednošãu 2 – tj. ako su svi radnici okupirani i dve mušterije èekaju, kada se nova mušterija pojavi, onda ãe oni otiãi – ta pojava je poznata kao nepridruživanje. Takoðe ãemo dodati podatak o troškovima koji se tièe radnika i mušterija:  Svaki minut tokom koga je radnik besposlen košta nas 0,5 evra  Svaki minut tokom koga mušterija èeka na radnika košta nas 1 evro  Svaka mušterija koja se nije pridružila redu (ode a da nije uslužena), košta nas 5 evra Paket ulaznih informacija je prikazan dole u tabeli 7.

Tabela 7.

10

Pri èemu bi izlazna informacija bila sledeãa (Tabela 8.):

Tabela 8.

Obratite pažnju da, kao što navedene informacije pokazuju, to je M/M/1/3 sistem jer imamo jednog radnika a maksimalni broj mušterija koji može biti u sistemu (bilo da se uslužuje ili ja na èekanju) je 3 (jedan se uslužuje, dva èekaju). Kljuèna stvar je da, pošto smo ubacili podatke o troškovima, imamo cifru koja predstavlja ukupne troškove operacije tog sistema, tj. 3,0114 po minutu (u stanju mirovanja). Pretpostavimo sada situaciju kada bismo imali dva radnika umesto jednog – da li bi troškovi bili manji ili veãi? Prost odgovor glasi da bi nam to mogao reãi program. To je M/M/2/4 sistem èekanja jer imamo dva radnika i ukupan broj mušterija u sistemu od 4 (dve se uslužuju, dve èekaju u redu na uslugu). Takoðe program pretpostavlja da se ta dva radnika snabdevaju mušterijama iz istog reda (pre nego da svaki od njih ima svoj zaseban red). Paket ulaznih informacija je prikazan dole u tabeli 9.

11

Tabela 9.

Pri èemu bi izlazna informacija bila sledeãa (Tabela 10.):

Tabela 10.

Tako da možemo videti da postoji primetna ušteda troškova po minutu kada postoje dva radnika umesto jednog. Zapravo, program može automatski da izvši analizu za nas da vidimo koliko trošak varira u zavisnosti od broja radnika. To se može videti dole na slici 2 i tabeli 11 i grafiku 1.

12

Slika 2.

Tabela 11.

Grafik 1.

13

Generalno èekanje u redovima Ekran prikazan dole (Slika 3. i Tabela 12.) pokazuje moguãe ulazne parametre u paketu u sluèaju generalnog modela èekanja u redu (tj. da nije M/M/r sistem).

Slika 3.

Tabela 12.

14

Tu imamo i broj moguãih izbora za distribuciju vremena usluga i distribuciju vremena izmeðu dolazaka. U stvari, program prepoznaje nekih 15 razlièitih distribucija. Druge stavke koje su gore pomenute su:  Koeficijent pritiska usluge – pokazuje kako radnici ubrzaju usluživanje kada je sistem prometan, odnosno kada su svi radnici zauzeti, stopa usluge se poveãava. Ako je taj koeficijenat s i imamo r radnika sa stopom usluge µ onda se stopa usluge menja iz µ u (n/r)sµ kada postoji n mušterija u sistemu i n≥r.  Koeficijent obeshrabrenog dolaska – pokazuje kako je dolazak mušterija obeshrabren kada je sistem prometan,tj. Kada su svi radnici zauzeti stopa usluga se poveãava. Ako je taj koeficijent s i imamo r radnika sa stopom dolaska lamda tada se stopa dolazaka menja iz lamde u (r/(n+1))slamda kada postoji n mušterija u sistemu i n ≥r.  Distribucija velièine gomile ili glavnine – mušterije mogu doãi zajedno (u gomilama, ili glavninama) i to pokazuje distribuciju velièine kod takvih gomila. Kao primer analize koja se može uraditi kao primer problema navodimo sledeãe (Tabela 13.):

Tabela 13.

Rešavanjem problema dobijamo (Slika 4.):

15

Slika 4.

Slika 4. prikazuje da ne postoji nijedna formula za evaluaciju situacije koju smo postavili. Mozemo probati da procenimo situaciju koristeãi približnu formulu, ili pomoãu Monte Karlo simulacije. Ukoliko odabaremo približni pristup dobijamo podatke prikazane u tabeli 14.:

Tabela 14.

Problem je taj što su ti približni rezultati èista besmislica (tj. nisu dobra približna vrednost). Na primer, proseèan iznos broja mušterija u redu je -2,9813, verovatnoãa 16

da su svi radnici besposleni -320% itd. Dok u ovom konkretnom sluèaju je oèigledno da približnost ne važi, za druge probleme možda nije tako oèigledno da sistem približnih vrednosti ne vredi. Ako prihvatimo Monte Karlo simulaciju, dobiãemo ovakav ekran (Slika 5 i Slika 6..):

Slika 5.

Slika 6.

Ono što ãe se desiti ovde je to da ãe kompjuter konstruisati model sistema koji smo specifikovali i interno generisati dolaske mušterija, vremena usluga, itd. i skupiti 17

statistièke podatke o tome kako sistem funkcioniše. Kao što je specifikovano gore, to ãe obavljati taj proces za 1000 vremenskih jedinica (u ovom sluèaju, sati). Fraza „Monte Karlo“ proizilazi iz dobro poznatog kockarskog grada na Mediteranu u Monaku. Kao u ruletu, dobijamo nasumiène brojeve kao kad zavrtimo rulet, tako da u Monte Krlo simulaciji koristimo nasumiène brojke koje je generisao kompjuter. Rezultati su prikazani ispod (Tabela 15.).

Tabela 15.

Ti rezultati izgledaju mnogo razumniji nego oni koji su dobijeni metodom približnih vrednosti. Meðutim, jedan faktor koji bi trebalo razmotriti je vreme simulacije koje je specifikovano – tu iznosi 1000 sati. Da bismo sakupili što taènije informacije o ponašanju sistema, mogli bismo poželeti da simuliramo duže vreme. Rezultati simulacije koja je i 10 i 100 puta duža prikazana je u tabelama ispod (Tabela 16 i Tabela 17.).

18

Tabela 16.

19

Tabela 17.

Kao što je oèigledno, što duže simuliramo, sve više imamo poverenja u statistike/verovatnoãe koje smo dobili. Kao i ranije, možemo da istražimo kako bi se sistem mogao ponašati sa više radnika. Simuliranjem 1000 sati (da bi smanjili sveukupno prošlo vreme koje se zahteva), i posmatranjem samo sveukupnog troška sistema po satu (stavka 22 u izlaznom podatku iznad), dolazimo do sledeãih rezulatata (Tabela 18.):

20

Broj radnika Ukupni trošak sistema 1 4452 2 3314 3 2221 4 1614 5 1257 6 992 7 832 8 754 9 718 10 772 11 833 12 902 Tabela 18.

Prema tome, broj radnika koji se povezuje sa minimalnim troškom sistema je 9.

Zakljuèak U radu je istaknuta prednost primene raèunarskog programa WinQBS u rešavanju konkretnih problema iz svakodnevnog života. U radu je prikazano da se primenom WinQBS softwear može doãi do optimalnog rešenja odnosno broja radnika koji ãe biti najefektivniji odnosno najekonomièniji za posmatrani posao. Upotrebom programa se eliminiše velika doza subjektivnosti u procesu iznalaženja rešenja i donošenja odluke, a kontinualnom pripremom bi se konstantno popravljale i unapreðivale performanse subjekata koji ih koriste.

21