T.C.

MARMARA ÜNİVERSİTESİ

SOSYAL BİLİMLER ENSTİTÜSÜ

İŞLETME ANABİLİM DALI

YÖNETİM VE ORGANİZASYON BİLİM DALI YÜKSEKLİSANSI

 

 

 

 

Kuyruk Modelleri

 

 

 

 

Ders : Karar Verme Teknikleri

Yöneten : Prof. Dr. Uğur Yozgat

Hazırlayanlar

Özlem Altınçekiç 99035

Murat Benlidayı 99029

İstanbul-2000

KUYRUK TEORİSİ

Şu durumları ele alalım,

  1. Bir süpermarkette ödeme kasaları önünde bekleyen müşteriler,
  2. Bir trafik ışığında bekleyen otomabiller,
  3. Bir berberde bekleyen müşteriler,
  4. Bir poliklinikte bekleyen hastalar,
  5. Bir havaalanında bekleyen uçak,
  6. Bir tamirci tarafından tamir edilecek arızalı araçlar,
  7. Bir sekreter tarafından yazılması beklenen yazılar,
  8. Bir bankamatikte bekleyen müşteriler.

Bu durumların müşterek sahip olduğu husus bekleme olayıdır. Bu gibi hizmetlere ve benzeri diğerlerine bekleme zorunluğu olmadan sahip olabilmek arzu edilir. Fakat bekleme yaşantının bir parçasıdır. Amaç minimize etmektir.

Bekleme olayı

Servis veya hizmet vasıtlarının çalışmasındaki rassallığın direkt bir sonucudur. Genele olarak müşterilerin gelişleri ve hizmet süreleri önceden bilinemez aksi takdirde servis vasıtalarının beklemeyi tamamen ortadan kaldıracak şekilde programlamak uygun olabilirdi. Bir servis vasıtasının (service facility) rassal şartlar altındaki operasyonunu incelemekteki amaç incelenmekte olan sistemin performansını ölçer bazı karekteristikler elde etmektir. Örneğin performansın mantıki bir ölçüsü bir müşterinin hizmet vermeden önce ne kadar bekleyeceğidir. Başka bir ölçü servis vasıtasının kullanılmadığı zaman yüzdesidir . Birinci sisteme müşteri açısından bakar, ikinci ölçü ise servis vasıtasını kullanılma derceseini değerlendirir. Müşterinin bekleme zamanı ne kadar fazla ise servis vasıtasının boş kalacağı zman yüzdesinin az olacağını veya bunun aksinin de doğru olacağını anlayabiliriz. Bu performans ölçüleri birbiriyle çelişen iki durum arasında makul bir denge kuracak servis hızını seçmek için kullanabilir. Bir kuyruk durumdaki belli başlı aktörler “Müşteri” ve “Servisçi ”.

1.Müşteri gelişleri

2.Müşteri hizmet süresi

Bir kuyruk modelinin temel elemanlarının şu faktöre mağdur olduğunu söyleyebiliriz.

  1. Gelişlerin dağılımı (ariables) (tek-toplu)

  2. Servis süresi dağılımları (tek-toplu)

  3. Servis vasıtasının tasarımı (seri, paralel, şebeke istasyonları)

  4. Servis disiplini (FIFO,LIFO, SIRO(service in random order)

  5. Kuyruk boyutu (sayısı-ölçüsü) (sonlu-sonsuz)

  6. Kaynak (müşteri yaratan) (sonlu-sonsuz)

  7. İnsan davranışı (kuyruk değiştirme, kuyruğu terketme)

Birleşik Gelişli Ve Gidişli Kuyruklar

Burada c tane paralele servisçiye sahip ve dolayısıyla c tane müşterinin aynı anda hizmet görebildiği kuyruk durumlarının göz önüne alıcağız. Aşağıda bu kuyruk sistemi şematik olarak gösterilmiştir.

servisçiler

Gelen müşteriler

kuyruk

sistem uzunluğu

Şekil 1.

Bu kuyruk sistemine paralel kuyruk sistemleri denir. Bunların karekteristiklerini özetlemeye uygun üniversal bir notasyon aşağıdaki formda standartlaştırılmıştır.

(a / b / c ) : ( d / e / f )

 

 

Burada bu harfler kuyruk modelinin temel elemanlarının yerlerini şöyle almaktadır.

a : gelişlerin dağılımı (distribution)

b : servis süresinin (veya gidişlerin dağılımı)

c : paralel servis sayısı (c=1,2,…,n)

d : Servis disiplini (LIFO,FIFO,SIRO)

e : sistemde müsaade edilen max. sayı (Sistem kapasitesi) (kuyuk + servistekiler)

f : kaynak sayısı (kapasitesi)

Bu standart notasyon geliş ve gidişlerin a ve b sembollerini de tekrar aşağıdaki kodlarla değiştirir.

M : poisson(veya Markovyan) geliş ve gidiş dağılımı ve eşdeğer olarak üssel gelişler arası sevis süresi dağılımı

D : sabist veya deterministik gelişler arası veya servis süresi

Ek : Gelişler veya servis süresinin Erlang veya Gamma dağılımı

GI :Gelişlerin veya geliş arası süresinin genel bağımısız dağılımı.

G: gidişlerin veya servis süresinin genel dağılımı.

Örnek

( M / D / 10) : ( GD / N / ¥ )

Burada poisson gelişleri, sabit servis süresine ve 10 tane servisçiye sahibiz. Servis disiplini genel disiplin yani ilk gelen önce. Sistem kapasitesinin maksimum N adet kabulü söz konusudur. Yani her gelen müşteri sisteme alınmaz . Müşteriyi meydana getiren kaynak kapasitesi ¥ ‘dur.

Örnek

( M / M / 1 ) : ( GD / ¥ / ¥ )

Kendall-Lee-Taha notasyon’u kuyruk sisteminin incelenmesinde geçici durumlar ile beraber devamlı hal durumları da söz konusudur. Biz devamlı hal şartlarındaki kuyruk problemlerini inceleyeceğiz, bu sebeple devamlı hal şartlarındaki kuyruk sistemlerinde aşağıdaki temel performans ölçüleri ile ilgileneceğiz.

 

Pn : Sistemde n tane müşteri olma olasılığı.

Ls : (length of system) Sistemdeki müşterilerin beklenen (ortalama) sayısı

Lq : (length of queu) Kuyruktaki müşterilerin beklenen sayısı

Ws : Sistemde umulan bekleme süresi ( kuyuk+servis)

Wq : Kuyruktaki umulan bekleme süresi

Tanımdan şunları çıkarabiliriz

¥ ¥

Ls = S n.Pn Lq = S n.Pn

n=0 n=c

Ls ile Ws arasında ve Lq ile Wq arasında kuvvetli bir bağlantı mevcuttur. Spesifik olarak l geliş hızı (arriable rate) verildiğinde şunları yazabiliriz.

Ls = l Ws Lq = l Wq

Bu eşitlikler gelişlerin veya servis süresinin dağılımını sınırlayan (tahditleyen) oldukça genel şartlar altında belli olurlar. Bununla beraber müşterilerin l hızına geldikleri fakat bütün gelişlerin sistemine dahil olmadıkları özel durumlarda bu eşitliklerin yanlızca gerçekten sisteme katılan müşterileri ihtiva edecek şekilde l ’yı yeniden tanımlayarak değiştirilmeleri gerekir.

Bu sebebten;

l eff : sisteme dahil olanlar için effektif geliş hızı (arriable rate) olmak üzere şunları yazabiliriz.

Ls = l eff * Ws Lq = l eff * Wq

l eff = b * l 0 < b < 1

Bunun anlamı ise sisteme gelenlerin yanlızca bir kısmının sisteme katılmalarıdır. Bununla beraber l eff’i Ls ve Lq cinsinden de belirleyebiliriz.

(sistemde beklenen(expected) ortalama bekleme zamanı) = ( Kuyrukta beklenen bekleme zamanı) + ( Beklenen servis süresi)

Ws = Wq + 1/m m = Servis Hızı

her iki tarafı l ile çarparsak 1/m = beklenen servis süresi

Ws * l = Wq * l + 1/m *l Ls = Lq + l /m

Ls- Lq = l /m Ls- Lq = l eff /m

l eff = m ( Ls –Lq )

Aşağıda geliştirilen kuyruk modellerinde Pn’nin bulunmasına çalışırız. Zira bu olasılıklarla performasın bütün temel ölçülerini aşağıdaki sırada bulabiliriz.

¥

Pn Ls = S n.Pn Ws = Ls / l Wq = Ws – 1/m Lq = m Wq

n=0

Örnek

Bir kuyruk sisteminde gelişlerin saatte 3 müşteri olarak geldiği ve servisin de saate 8 müşteri hızında olduğu biliniyor. Tek servisçili bir kuyruk durumu söz konusudur. Sistemdeki n müşterinin Pn olasılıkları şöyledir.

n

0

1

2

3

4

5

6

7

>=8

Pn

0.625

0.234

0.088

0.033

0.012

0.005

0.002

0.001

0

Bu durumda bu kuyuk sistemindeki performans ölçülerini hesaplayalım.

l = 3 müş./saat

m = 8 müş./saat

¥

Ls = S n.Pn = 0.P0 +1.P1+2.P3+…+8.P8

n=0

= 0*0.625+1*0.234+2*0.088+3*0.033+…+8*0

Ls = 6 müţ./saat

Ws= Ls / l = 0.6 / 3 = 0.2 saat

Wq = Ws – 1 / m = 0.2 – 1/ 8 = 0.075 saat

Lq = l * Wq = 3*0.075 = 0.225 müş.

Kuyruk Modellerinin Çeşitleri

Burada birleşik geliş ve gidişli bazı kuyruk modelleri incelenecektir. Her modelin karekteristikleri Kendall-Lee-Taha notasyonu cinsinden verilecektir. Servis disiplini olarak genel disiplin kullanılacaktır.

Model 1

( M / M / 1 ) : ( GD / ¥ / ¥ )

Bu modelde tek servisçi vardır. Sistemin veya kaynağın kapasitesi sınırsızdır. Gelişler l ve gidişler m hızıyla Poissondur. Bu modele ait formüller ispatları verilmeksizin şöyledir.

 

Pn = ( 1- r ) r = meşguliyet oranı 0 < r < 1

r = l / m < 1

Ls = r / ( 1 - r ) Lq = Ls - r

Ws = Ls / l Wq = Lq / l

Örnek

Bir otomobil yıkama servisinde arabaların ortalama saatte 5 ile Poisson dağılımına uymaktadır. Her otomobilin yıkanması farklı ise de ortalama 10 dakika ile üssel olmaktadır. Buna göre ilgili performans ölçülerini hesaplayalım.

l = 5 müş./saat

1/ m = 10 dak. / müş

m = 1/10 = 0.1 müş./dak = 6 müş. /saat

r = l / m = 5 / 6 = 0.83

Ls = r / (1-r ) = 0.83/ (1-0.83) = 5 müş.

Lq = r 2 / (1-r ) = 0.832 / (1- 0.83) = 4,17 müş.

Ws = 1/ (m * (1-r ))=1/6*(1/6) = 1 saat

Wq = r / m *(1-r ) = 5/6 saat

Burada park etme sorunu söz konusudur. Bu durumda gelen bir arabanın en azından zamanın %80’inde (%80 olasılıkla) park edebilecek şekilde yeterli park yerine ihtiyaç olması gerekiyor. O halde gelen bir arabanın park yeri bulabilmesi için burada bulunması gereken park yeri sayısı nedir.

n; sistemdeki sayıyı temsil ettiğinden bu şart bir olasılık ifadesi ile şöyle verilir.

P0+P1+P2+…+Ps >= 0.80

s : belirlemeye çalıştığımız belirli park yeri sayısıdır. Ancak bu s’ye dahil değildir.

(1-r )+(1-r )*r +(1-r )*r 2 +… +(1-r )*r s >= 0.80

(1-r )*(1+r +r 2+…+r s) = ( 1- r )* (1-r s +1)/(1-r ) = 1-r s+1 >= 0.80

r s+1 <= 0.20 her iki tarafında logoritmasını alırsak

(s+1)*log r <= log 0.2 1’den küçk olan sayıların log’u (-)’dir.

(s+1) >= log 0.2/ log (5/6)

s>= 7.8 @ 8

s>= 8 gelen arabalar için park yeri sayısı 8 veya daha fazla olmalıdır. Bu da sistem veya kuyruktaki arabaların sayısının (Lq) takriben iki misli olmak durumundadır.

Model 2

( M / M / 1 ) : ( GD / N / ¥ )

Bu model ile model 1 arasındaki tek fark sistemde müsaade edilen müşterilerin maksimum sayısının N olmasıdır. Bu durumda kuyruk uzunluğu N-1 dir. Bunun anlamı da, bir kere N müşteri sistemde olunca yeni gelen tüm müşteriler ya kuyruğa giremezler ya da bunların sisteme dahil olmasına müsade edilmez. Sonuç, servis vasıtasındaki efektif geliş hızı l eff’in kaynaktan gelişlerin yaratıldığı l değerinden daha az olmasıdır. Bu modele ait formüller şöyledir.

 

 

 

(1-r )*r n , r ¹ 1

(1-r N+1)

Pn =

1/(N+1) , r = 1

 

Burada r =l / m ‘nün önceki modelde olduğu gibi birden küçük olması gerekmez bunu sezgiyle çıkarabiliriz. Zira sistemde müsade edilen sayı gelişlerin ve gidişlerin nisbi veya bağıl değerleri kuyruk boyu ile (N-1) kontrol edilir. Yukarıda Pn’yi kullarak sistemde beklenen müşteri sayısı aşağıdaki gibi bulunur.

( r *[1-(N+1)* r N +N*r N+1 ] ) , r ¹ 1

(1-r ) (1 -r N+1 )

Ls=

N / 2 , r = 1

Lq, Ws, Wq ölçüleri de efektif geliş hızı l eff ‘i bulduktan sonra Ls’den elde edilir. Bir müşterinin sisteme dahil olmama olasılığı sistemde büyük N tane müşteri olma olasılığı Pn’ye eşit olduğundan sisteme katılan müşterilerin oranından

P{ n>N }= 1-Pn olması gerekir. Bundan sonra şunlar yazılabilir.

l eff = l *(1-Pn)

Wq = Lq / l eff

Lq = Ls - l eff / m

Ws = Wq + 1 / m

l eff = m * ( Ls-Lq) = l *(1-Pn)

Örnek

1.modele ait oto yıkama ortamını gözönüne alalım. Farzedelim ki bu servis ortamı toplam 5 arabalı park yerine sahiptir. Eğer park yerleri doluysa yeni gelen arabalar içeri giremezler bu durumda ilgili performans ölçülerinizi hesaplayalım, Bundan önce sınırlı park yeri sebebiyle ne kadar müşteri kaybedildiğini bulalım.

l = 5 müş. /saat

m = 6 müş. /saat

r = l / m = 5/6 =0.83

N=5+1=6

Burada bu sayı kaybedilen müşteri sayısı aslında l - l eff = l *Pn

n yerine N koyulabilir.

PN = P6 = (1- r ) * r N / (1- r N+1 ) = [(1-5/6)*(5/6)6 ] / (5/6)6 = 0.0744

l *Pn = 5 * 0.0744 = 0.387 araba/saat

Tahditle müşteriyi daha az bekletiriz. Farzedelim ki diğer performans ölçüleri hesaplanmış olsun.

Ls=

5/6*[1-(6+1)* (5/6)6 +6*(5/6)7 ]

(1-5/6)*(1- (5/6)7)

l eff = l *(1-Pn) = 5*(1-0.0744) = 4.613 müş./saat

Lq=2.29- 4.613/6 =1.521 oto

Ws=2.29 / 4.613 = 0.496 saat

Wq = 1.521 / 4.613 = 0.329 @ 0.33 saat

0.33+0.17 =0.5 saat (sistemde geçirilen saat)

O.5 saat kazanıldı, 3 müşteri kaybetmek pahasına.

Model 3

( M / M / c ) : ( GD / ¥ / ¥ )

Bu modelde gelişler l hızında meydana gelir ve maksimum müşteri aynı anda servis görebilir. Hem gelişler hem de gidişler poisson dağılımına göre meydana gelir. c adet servisçi kullanmanın nihai etkisi maksimum c tane müşterinin aynı anda servis görebilmelerine müsaade etmekle tek servisçili durumla kıyaslandığında servis hızını arttırmaktadır. Bu sebepten eğer sistemdeki müşterilerin sayısı n, en azından c’ye eşitse servis ortamındaki birleştirilmiş servis hızı cm ’dir. Diğer taraftan eğer n, c’den az ise (n<c) birleştirilmiş servis hızı nm olur. Zira n’den daha fazla servisçi meşgul değildir. (n<c) esnasında çok servisçili bir model kullanma servis hızının n ile değiştiği bir tek servisçi modeline eşttir. İspatları verilmeksizin bu modelin formülü şöyledir.

r n * P0 / n! , 0 £ n £ c

Pn =

r n * P0 / (c n-c *c!) , n>c

 

P0 = [ S r n / n! + r c / (c! (1- r /c)) ]-1

Lq = (r c+1)* P0 / (c-1)!(c-r )2

Wq= Lq / l

Ls = Lq + r

Ws = Ls / l = Wq: 1/m

 

 

Örnek

Küçük bir kasabaya 2 taksi firması tarafından hizmet veriliyor. Her bir firmanın ikişer adet teksisi vardır. Bunlar piyasayı eşit olarak paylaşmaktadır.Bu durum, her iki firmanın bürosuna müşterilerin saatte ortalama 10 adet gelişinden anlaşılır. Her taksi yolculuğu ortalama 11,5 dakika sürmektedir. Müşterilerin gelişi bir Poisson dağılımına uymaktadır. Buna karşın yolculuk süreleri üssel olmaktadır.Bu 2 firma daha sonra bir işadamı tarafından satın alınıyor. Bu kişinin ilk işi, müşterilere daha hızlı servis sağlamak ümidiyle bir tek büroya birleştirmek olmuştur. Buna uygun olup olmadığını ve performans ölçülerini belirleyelim.

l = 10 müş. /saat

1/m = 11,5 dak.

m =1/11,5*60=5,217 müş./saat

A firmasının,

r A = l A = 10 = 0,958 r A = r B %95,8 çok dolu bir kapasite

C*m A 2*5,217 Birleşik durumda l = 10+10 = 20 müş./saat

C= 2+2 = 4

r = l = 20 = 0,958

C C*m 4* 5,217

Her iki durumda da meşguliyet %’leri aynı olmaktadır ve oldukça yüksek bir değerdedir. Bu nedenle işadamının girişimini bu şekilde değerlendiremeyiz. Bu değerlendirmeyi her iki durum için kuyrukta bekleme zamanı veya sistemde bekleme zamanı değerleriyle kıyaslayabiliriz.

Ayrı durumda l = 10 müş. /saat, m = 5,217 müş./saat, C=2

r = l = 10 = 1,917 P0 = [ (1,917)0 + (1,917)1 + (1,917)2 ] -1 = 0,0212

m 5,217 0! 1! 2!(1- 1,917)

2

Lq = (r c+1)* P0 / (c-1)!(c-r )2 = (1,917) 3 * 0,0212/ 1!(2-1,917)2 = 21,68 müşteri

Wq= Lq / l = 21,68/10 = 2,168 saat kuyrukta bekleme süresi

Birleşik durumda, l =20 müş./saat, m = 5,217 müş./saat, C=4, r = 20/5,217 = 3,834

P0 = [ (3,834)0 + (3,834)1 + (3,834)2 + (3,834)3 + (3,834)4 ] -1 = 0,0042

0! 1! 2! 3! 4!(1- 3,834)

4

Lq = (r c+1)* P0 / (c-1)!(c-r )2 = (3,834) 5 * 0,0042/ 3!(4-3,834)2 = 21,05 müşteri

Wq= Lq / l = 21,05/20 = 1,05 » 1 saat kuyrukta bekleme süresi

Görüldüğü gibi birleşik durumda kuyrukta bekleme zamanı 1,05 saattir. Ayrıyken 2,16 saat olduğundan iki firmanın birleşmesi uygundur.

 

 

 

 

 

 

 

 

Model 4

( M / M / C ) : ( GD / N / ¥ ) C<N

Bu kuyruk durumu, sistemin kapasitesine N gibi bir sınır konulmuş olması nedeniyle farklılık gösterir. Burada maksimum kuyruk sayısı N-C’dir.

 

 

r n * P0 / n! , 0 £ n £ c

Pn =

r n * P0 / (c n-c *c!) , c < n £ N

c-1

P0 = n=0

c-1

n=0

Lq = (r c+1)* P0 / (c-1)!(c-r )2 [ 1-(r /c) N-C – (N-C)(r -C) N-C (1-r /C) ] , r /c¹ 1

P0 * r c (N-C)(N-C+1) / 2 C! , r /c=1

 

Ls = Lq + (C-C) = Lq + l eff /m C = Boş servisçilerin beklenen sayısı

c

C = S (c-n) pn l eff = l (1- Pn) = m (C-C)

n=0

(C-C) meşgul kanalların, yani servisçilerin beklenen sayısını göstermektedir. m (C-C) ise bir birim zaman başına servis veriliş veya hizmet edilmiş gerçek sayıyı, dolayısıyla da efektif geliş hızını temsil eder.

Bu modeldeki Pn ile ( M / M / C ) : ( GD / ¥ / ¥ ) modelindekinin arasındaki tek fark, P0 ‘ın ifadesinde meydana gelmektedir. Ayrıca burada kullanım faktörü p/c ‘nin 1’den az olması da gerekmez.

Örnek

Bir önceki birleştirilmiş taksi probleminde, her ne kadar patron beklenen bekleme zamanının çok olduğunu farkediyorsa da ilave taksiler almaya muktedir değildir. Uzun bekleme zamanının yarattığı problemi hafifletmek için taksi bürosuna, araba bekleyenlerin sayısı 16’yı aşınca yeni gelenlerin iptal edilmesi kararlaştırılmıştır. Bu durumda konulan tahditin etkisi ne olur? Bu kararı incelemek için 16 müşterilik bekleme listesine sahip olmanın N=16+4=20 tahditi konulmasını gerektirir. (Firmanın 4 taksisi var).

O halde kuyruk sistemi ( M / M / 4 ) : ( GD / 20/ ¥ ) şeklindedir.

l = 20 müş. /saat N=20

m = 5,217 müş./saat C=4

r = l = 20 = 3,8336 r /c=3,83/4=0,95 ¹ 1

m 5,217

 

P0 = [ (3,83)0 + (3,83)1 + (3,83)2 + (3,83)3 + (3,83)4[ 1-(3,83/4)] 17 ] -1 = 0! 1! 2! 3! 4! [ 1-(3,83/4)]

P0 =0,00753

Lq=0,00753 [ 3,835/3!(4-3,83)2] [ 1-(3,83/4)16-(20-4)(3,83/4)16(1-3,83/4)]

Lq=5,85 müţteri

Pn, n=N=20

P20 = (3,83)20/4!416 * 0,00753 = 0,03433

l eff =l (1- Pn)= 20(1-0,03433) 19,31 müş./saat

Wq= Lq/ l eff = 5,85/19,31 = 0,303 saat

Ws= Wq + 1/m = 0,303 +1/5,217 = 0,4946

Ls= Lq + l eff /m = 5,85+ 19,31/5,217 = 9,55 müşteri

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

YARARLANILAN KAYNAKLAR