» Montaj Hatti Dengeleme Icin Petri Agi Yaklasimi -1

Yayinlanma Zamani: 2011-12-26 17:09:00





BASİT MONTAJ HATTI DENGELEME PROBLEMİ ÇÖZÜMÜ İÇİN BİR PETRİ AĞI YAKLAŞIMI

DEÜ MÜHENDİSLİK FAKÜLTESİ
FEN ve MÜHENDİSLİK DERGİSİ
Cilt: 6 Sayı: 2 s. 1-15 Mayıs 2004
BASİT MONTAJ HATTI DENGELEME PROBLEMİ ÇÖZÜMÜ İÇİN BİR PETRİ AĞI YAKLAŞIMI
(A PETRI NET APPROACH FOR SOLVING
SIMPLE ASSEMBLY LINE BALANCING PROBLEM)
Özcan KILINÇCI

ÖZET / ABSTRACT
Montaj hattı dengeleme problemi bir atama problemidir. İş elemanları, hat üzerindeki iş istasyonlarına birbirleri arasındaki öncelik ilişkileri sağlanarak atanırlar. Hat  üzerinde sadece bir ürün işleniyorsa ve bu ürüne ait iş elemanlarının süreleri biliniyor ve sabit ise problem, basit montaj hattı dengeleme problemi olarak adlandırılır. Eğer hat üzerindeki iş istasyonu sayısı belli ise çevrim süresi azaltılmalıdır (BMHDP-1). BMHDP-1’i çözmek için Dal & Sınır algoritmaları, tabu araştırması, genetik algoritmalar vb. Araştırma tekniklerine dayalı sezgisel yöntemler geliştirilmektedir.

Bu makalede, bu problemin çözümü için yeni bir yaklaşım olarak Petri ağları sunulmuştur. Petri ağları,
kesikli olaylı sistemleri modelleyen, tasarlayan ve analiz eden bir tekniktir. Önerilen Petri ağlarına
dayalı algoritma özellikle ulaşılabilirlik analizini kullanır. Algoritma MATLAB 6.0’da kodlanmıştır.
Önerilen algoritmanın testi, Tonge’nin 70 iş elemanlı probleminde yapılmış, sonuçlar mevcut yedi
yöntemin sonuçları ile karşılaştırılmıştır. Algoritma, 13 çevrim süresinin 12’sinde en iyi sonuçları
vermiştir.
Assembly line balancing problem is an assignment problem. Tasks are assigned to work stations
on the line by providing the precedence relations between tasks. When the only one product is
produced on the line and its tasks have deterministic times, the problem is called simple assembly line
balancing problem (SALBP). If number of work stations on the line is fixed, then cycle time should be
reduced (SALBP-1). Heuristics based on branch and bound procedures, tabu search metaheuristics,
genetic approaches, and etc. have been developed to solve SALBP-1. In this article, Petri nets are
represented as a new approach to solve this problem. Petri nets are mathematical and graphical tool
to model, design, and analyze discrete event systems. Proposed algorithm based on Petri nets uses the
especially reachability analysis to determine available tasks and select task into them. Algorithm is
coded in MATLAB 6.0. Proposed algorithm is tested on Tonge’s 70-tasks problem, and then results
are compared with existing seven methods’ results. The algorithm gave best results for 12 of 13 cycle
times.
ANAHTAR KELİMELER / KEY WORDS
Montaj hattı dengeleme problemi, Petri ağları, Montaj üretim, Ulaşılabilirlik analizi
Assembly line balancing problem, Petri nets, Assembly production, Reachability analysis

1. GİRİŞ
Montaj hattı, yüksek üretkenlik ve otomasyon sağlayan bir yığın üretim sistemi çeşididir.
Bu avantajlarından yararlanmak için en önemli unsur, hat üzerindeki aynı işlem zamanına
sahip iş istasyon sayısını ya da çevrim süresini en küçüklemektir. Bu amaçla iş elemanları,
birbirleri ile öncelik ilişkilerine ve istasyon boş sürelerine göre iş istasyonlarına atanır. Bu
problem literatürde montaj hattı dengeleme problemi (MHDP) olarak adlandırılır. Eğer
montaj hattında, sadece bir ürüne ait işlemler yapılacaksa problem, tekli montaj hattı
dengeleme problemi adını alırken, birden fazla ürünün hat üzerindeki iş istasyonlarında
işlenmesi ile karmaşık montaj hattı dengeleme problemine dönüşür. İş istasyonlarına atanacak
iş elemanlarının işlem süreleri bilgisi de montaj hattı dengeleme problemini yeni sınıflara
ayırır. Eğer süreler biliniyorsa ve değişmiyorsa deterministik montaj hattı dengeleme
problemi, eğer süreler rasgele değişiyorsa stokastik montaj hattı dengeleme problemi
karşımıza çıkar. Deterministik süreli iş elemanlarına sahip tekli montaj hatlarındaki montaj
hattı dengeleme problemi, basit montaj hattı dengeleme problemi (BMHDP) olarak
tanımlanır. BMHDP’deki amaca göre 3 farklı durum söz konusudur. Eğer hat üzerindeki
çevrim süresi biliniyorsa (yada veriliyorsa), amaç montaj hattındaki iş istasyonu sayısını en
küçüklemektir. Bu durum birinci tip BMHDP’dir. Bilinen (yada verilen) iş istasyonu sayısına
göre çevrim süresi en küçüklenmeye çalışılıyorsa ikinci tip BMHDP geçerlidir (Baybars,
1986a). Montaj hattı çıktı oranının yüksek olması isteniyorsa BMHDP-1 ile ilgilenilir. Eğer
ürettim alanının hacimsel kısıtları söz konusuysa BMHDP-2 kullanılmalıdır. Son durumda, iş
istasyon sayısı ve çevrim süresi değiştirilerek montaj hattının etkinliği en büyüklenmeye
çalışılır (BMHDP-E). Hat etkinliği, hat üzerindeki iş istasyonlarının toplam sürelerinin ne
kadarının iş elemanları işlemlerine ayrıldığını gösteren bir performans ölçütüdür. Yüksek hat
etkinliği, iş istasyonlarındaki boş sürelerin az olduğunu gösterir. Eğer hat etkinliği %100 ise,
hat üzerindeki hiç bir iş istasyonunda boş süre söz konusu değildir.
Salveson tarafından 1955 yılında matematiksel olarak ifade edilmesine değin MHDP,
deneme yanılma ile çözülmekteydi. İzleyen yıllarda problemin doğrusal programlama, tam
sayı programlama vb. ile ifade edilmesi ile çalışmalar yoğunlaşmıştır. Fakat problemimin
boyutu büyüdükçe, yada bir başka deyişle hat üzerindeki iş elemanı sayısı arttıkça, çözüm
uzayı da büyüdüğünden matematiksel programlama ile optimum sonucu bulmak imkansız
hale gelmiştir. Bu aşamada optimum yada optimuma yakın sonuç üreten sezgisel yöntemler
geliştirilmiştir. Bu makalenin üzerinde yoğunlaştığı BMHDP-1 için de literatürde bir çok
sezgisel yöntem içeren çalışmalar bulunmaktadır. En çok bilinen yöntemlerden biri
Baybars’ın geliştirmiş olduğu LBHA-1’dir (Line Balancing Heuristic Algorithm-type 1)
(Baybars, 1986a). LBHA-1 problemin boyutunu küçülterek ve mümkünse problemi daha
küçük problemlere dönüştürerek, BMHDP-1’i basitleştirerek çözer. BMHDP-1 için sezgisel
yöntem geliştiren araştırmacıların yararlandığı metotlardan biri Dal ve sınır algoritmalarıdır.
Johnson tarafından geliştirilen FABLE (Fast Algorithm for Balancing Lines Effectively),
Nourie ve Venta’nın geliştirdiği OptPack, Hoffmann’ın yöntemi EUREKA, Scholl ve Klein
tarafından geliştirilen SALOME (Simple Assembly Line balancing Optimization MEthod) ve
Sprecher’in yöntemi AGSA (Adapted General Sequencing Algorithm) literatürde en çok
bilinen dal ve sınır algoritmalarına dayalı sezgisel çözüm yöntemleridir (Johnson, 1988;
Nourie ve Venta, 1991; Hoffmann, 1992; Scholl ve Klein, 1997; Sprecher, 1999). Genetik
Yaklaşım yöntemi, BMHDP-1’e sezgisel çözüm yöntemi geliştiren araştırmacılar için yeni bir
çalışma alanıdır. Rubinovitz ve Levitin , Kim vd., Bautista vd. ve Sabuncuoglu vd.
çalışmalarında genetik yaklaşımdan yaralanmışlardır (Rubinovitz ve Levitin, 1995; Kim vd.,
1996; Bautista vd., 2000; Sabuncuoğlu vd., 2001). Scholl ve Voss ve Chiang tabu araştırması
yöntemini kullanarak, BMHDP-1 için sezgisel yöntemler geliştirmişlerdir (Scholl ve Hoss, 1996; Chiang, 1998). Burada değinilen sezgisel yöntemler ve ilgili başka çalışmalar hakkında
daha fazla bilgi edinmek isteyen araştırmacılar, Baybars, Erel ve Sarin ve Kılınçcı’nın
çalışmalarından faydalanabilirler (Baybars, 1986b; Erel ve Sarin, 1998; Kılınçlı, 2003).
Bu çalışmada, BMHDP-1 için geliştirilen Petri ağları tabanlı yeni bir çözüm yöntemi
sunulacaktır. İzleyen bölümde Petri ağları ile ilgili genel bilgilere değinilecektir. Daha sonra
geliştirilen algoritma açıklanarak işleyişi örnek problem üzerinde verilecek, son olarak da
uygulama sonuçları sunulacaktır.
2. PETRİ AĞLARI
Bu bölümde özet olarak Petri ağları ile ilgili genel bilgilere değinilecektir. Özelikle
izleyen bölümde sunulacak olan algoritmada kullanılan özellikler ayrıntılı olarak verilecektir.
Petri ağları, Carl Adam Petri tarafından geliştirilen ve onun adıyla anılan, kesikli olaylı
sistemlerin modellenmesinde, analizinde ve tasarımında kullanılan grafiksel ve matematiksel
bir tekniktir. Petri ağları, eş zamanlı, eş zamansız, paralel, deterministik, stokastik, vb.
işlemlerin yer aldığı sistemlerle çalışma imkanı sağlar. Ayrıca modelde yer alan semboller
yardımıyla, sistemdeki olaylar için bir benzetim imkanı sağlar. Matematiksel bir araç olarak,
sistemin davranışlarını açıklayan durum denklemlerinin elde edilmesine, cebirsel sonuçların
bulunmasına ve diğer matematiksel modellerin geliştirilmesine yardımcı olur (Murata, 1989).
Temeli Carl Adam Petri’nin doktora çalışmasına dayanan Petri ağları, yazılım
sistemlerinden esnek imalat sistemlerine, endüstriyel kontrol sistemlerinden çok işlemcili
hafıza sistemlerine, veri akışı işleyen sistemlerden programlanabilir mantık kontrol
devrelerine kadar geniş bir uygulama alanına sahiptir. Benzer şekilde, eş zamanlı, eş
zamansız, paralel, vb. işlemler içeren üretim sistemlerinde de yaygın olarak kullanılmaktadır.
Üretim sistemlerindeki modelleme, sıralama, ölü noktaların kontrolü ve giderilmesi, kontrol
ve performans değerlendirme ile ilgili bir çok uygulama, Petri ağları ile yapılabilmektedir.
Montaj hatlı üretim sistemleri, özellikle sistemin modellenmesi, tasarımı ve kontrolü, hat
üzerindeki işlerin veya iş elemanlarının sıralanması açısından popüler bir uygulama alanıdır.
Teng ve Zhang, Ramaswamy vd., Adamou vd. ve Zha vd., Petri ağları ile üretim sisteminin
modellemesi ve kontrolü üzerinde çalışmışlardır (Teng ve Zhang, 1993; Ramaswamy vd.,
1997; Adamou vd., 1998; Zha vd., 1998). Cao ve Sanderson, McCarragher, D’Souza ve
Khator, Zimmermann ve Hommel, Yeung ve Moore, Zha ve Zha vd. Petri ağları ile robotlu
montaj hattı sistemlerini ve sistemdeki robotların işlemlerini modellemişlerdir (Cao ve
Sanderson, 1994; McCarragher, 1994; D’Souza ve Khator, 1997; Zimmermann ve Hommel,
1999; Yeung ve Moore, 2000; Zha, 2000; Zha vd., 2001). Montaj işlem planlarını ve işlem
sırasını belirlemek için Petri ağları, Thomas vd., Jeng vd., Yee ve Ventura ve Frey’in
çalışmalarında kullanılmıştır (Thomas vd., 1996; Jeng vd., 1999; Yee ve Ventura, 1999; Frey,
2000). Moore vd., Zussman ve Zhou, Zha ve Lim ve Tang vd. Petri ağları yardımıyla
montaj/demontaj işlem planlarını belirleyen yöntemler geliştirmişlerdir (Moore vd., 1998;
Moore vd., 2001; Zussman ve Zhou, 1999; Zha ve Lim, 2000; Tang vd., 2001). Burada
değinilen çalışmalar ve üretim sistemlerinde yapılan diğer Petri ağı çalışmaları hakkında bilgi
almak isteyen araştırmacılar Moore ve Gupta ve Kılınçcı’nın çalışmalarından yararlanabilir
(Moore ve Gupta, 1996; Kılınçlı, 2003). Yukarıda da değinildiği gibi, literatürdeki bir çok
Petri ağı çalışması montaj hattı sistemlerinin çeşitli problemlerine odaklansa da, Petri ağları
ile yapılmış bir montaj hattı dengeleme problemine rastlanılmamıştır.
Önerilen Petri ağ tabanlı algoritmayı açıklamadan önce, Petri ağlarla ilgili gerekli
bilgilerin verilmesi gerekmektedir. Bir Petri ağı dört bileşenden oluşur. Bunlar, grafiksel
gösterimde çember biçiminde ifade edilen konum (place), dikdörtgen kutu ya da çubuk
şeklinde gösterilen geçiş (transition), konum ve geçişi birbirine bağlayan yönlendirilmiş ok (arc), ve konumlar içinde nokta biçiminde gösterilen simge (token)’dir (Zurawski ve Zhou,
1994). Bir konum bir başka konuma, ya da bir geçiş bir başka geçişe doğrudan bağlı olamaz.
Geçiş ve konumu birbirine bağlayan oklar üzerindeki değerler, geçiş ve konum arasındaki
paralel bağlantı sayısını gösterir. Herhangi bir geçiş iki çeşit konuma sahiptir. Kendinden
önceki konumlar girdi konumu, kendinden sonraki konumlar çıktı konumu olarak adlandırılır.
Petri ağı bileşenleri Şekil 1’de gösterilmiştir.

Şekil 1. Petri ağı bileşenleri
Simgelerin hareketi, Petri ağları ile dinamik bir çalışma imkanı sağlar. Simgelerin
konumlar arasında hareket edebilmesi için, ilk anda yeterli sayıda simgenin gerekli konum
veya konumlara yerleştirilmesi gerekir. Başlangıç işaretlemesi, ilk anda hangi konumda ne
kadar simge olduğu bilgisini verir. Bu sağlandıktan sonra, simge konumlar arasında hareket
eder. Bunun için iki konum arasındaki geçişin oluşması gereklidir. Geçişin oluşmasından
önce de geçerlilik kuralının yerine gelmesi gerekir. Bir geçişin geçerli olması için, girdi
konumu ile geçiş arasındaki paralel ok sayısı kadar simgenin geçişe ait girdi konumunda yer
alması şarttır. Bu şart sağlandıktan sonra geçiş geçerli olur. Geçiş gerçekleştikten sonra, girdi
konumu ile geçiş arasındaki paralel ok sayısı kadar simge girdi konumundan silinir. Geçiş ile
çıktı konumu arasındaki paralel ok sayısı kadar simge çıktı konumuna yerleştirilir. Geçerlilik
kuralı ve oluşum kuralı ile ilgili gösterimler Şekil 2’de verilmiştir (Zurawski ve Zhou, 1994).
Petri ağları bazı özellikler taşır. Bunlardan literatürde en çok bilinenleri, ulaşılabilirlik
(reachability), canlılık (liveness), geri dönebilirlik (reversibility) ve sınırlandırılmışlık
(boundedness) özellikleridir. Canlılık özelliğinden, özellikle sistemlerin ölü noktalarının
belirlenmesinde yararlanılır. Geri dönebilirlik özelliği, belirli bir işlem yapıldıktan sonra,
sistemin işlem öncesi durumuna gelmesini sağlar. Sınırlandırılmışlık özelliği de, sistemdeki
kapasite sınırlamalarının modelde gösterilmesine imkan verir. Ulaşılabilirlik özelliği, sistemin
işleyişinin istenen konumlara gelip gelmediğini araştırır. Bu özelliğe dayalı olarak geliştirilen
ulaşılabilirlik analizi yardımıyla, sistemin başlangıç durumundan itibaren gelebileceği tüm
olası durumlar belirlenir. Bu çalışmada sunulacak algoritma, Petri ağlarının ulaşılabilirlik
analizinden yararlanmaktadır.

Şekil 2. (a) Geçiş t1 geçerli, (b) Geçerli geçiş t1 oluştu

Petri ağları ile ilgili bir başka bilinmesi gereken konu, ilişki (incidence) matrisidir. İlişki
matrisi, Petri ağı modelindeki konum ve geçişlerin bağlantı durumunu ve bağlantıyı sağlayan
okların ağırlık bilgilerini içeren bir tamsayı matrisidir. Matrisin kolon sayısı, modeldeki
konum sayısına, satır sayısı da modeldeki geçiş sayısına eşittir. İlişki matrisinde yer alan
hücrelerdeki sayılar, hücrenin yer aldığı satırdaki geçişle ilgili bilgiler içerir. Örneğin i. satır
ve j. kolondaki değer, i. geçiş ile ilgili bilgiler taşır. Buradaki değer, i. geçiş ile çıktı
konumları arasındaki paralel ok sayısının, i. geçiş ile girdi konumları arasındaki paralel ok
sayısının farkına eşittir. Bir başka deyişle, i. geçişin oluşması sonucunda, çıktı konumlarına
yerleştirilecek simge sayısından girdi konumlarından silinecek simge sayısının çıkarılması ile
bulunan değerdir. Ayrıca ilişki matrisi, simgelerin hareketi sonucu (ya da herhangi bir geçişin
geçerli olması sonucu) değişecek olan Petri ağı modelindeki simge durumunu belirlememize
imkan verir. Simge durumları, tek satır ve konum sayısı kadar kolona sahip bir vektörde
gösterilir. Her konumdaki simge sayısı ilgili kolonda belirtilir. Eğer mevcut duruma göre i.
geçiş geçerli olacaksa, geçişten sonra modelde oluşacak yeni simge durumu, mevcut simge
durumunu gösteren kolon vektör ile ilişki matrisinin i. satırının toplanmasıyla bulunur. Yeni
simge durumu, yeni geçiş imkanları sağlar. Böylece simgeler model üzerinde, konumlar
arasındaki hareketlerini sürdürürler.
Bu bölümde Petri ağları ile ilgili özet bilgiler sunulmuştur. Ayrıntılı bilgiye ulaşmak
isteyen araştırmacılar Murata, Zurawski ve Zhou, Desrochers ve Al-Jaar, Zhou ve
Venkatesh’in çalışmalarından yararlanabilir (Murata, 1989; Zurawski ve Zhou, 1994;
Desrochers ve Al-Jaar, 1995; Zhou ve Venkatesh, 1999). Bu bölümde verilen bilgiler ışığında
izleyen bölümde, BMHDP-1 için geliştirilen Petri ağ tabanlı algoritma sunulacaktır.
3. PETRİ AĞLARI İLE BMHDP-1’İN ÇÖZÜLMESİ
Geliştirilen algoritma açıklanmadan önce, Petri ağlarının BMHDP-1 çözümünde
kullanılmasının nedenlerini belirtmek gerekir. Petri ağları, paralel veya eşanlı olaylar içeren
ve grafiksel olarak bir akış diyagramı şeklinde gösterilebilen tüm sistemlerde
kullanılabilmektedir (Murata, 1989). Bir montaj hattı sistemi, paralel ve eşanlı işlemler
içermektedir. Ayrıca montaj hattında yapılacak işe ait iş elemanlarının öncelik ilişkisi, bir akış
diyagramı olarak gösterilebilir. Yine önceki bölümde de değinildiği gibi, simgelerin konumlar
arasındaki hareketi, dinamik çalışma imkanı sağlar. Bu dinamik çalışma da, iş
istasyonlarındaki boş sürelere ve öncelik ilişkilerine göre, iş istasyonlarına atanmaya aday iş
elemanlarının belirlenmesine ve içlerinden birinin seçimine olanak verir. Petri ağları
kullanarak geliştirilen algoritmanın temeli bu iki noktaya dayanmaktadır.
Algoritmayı uygulamadan önce, montaj hattının Petri ağı modeli oluşturulmalıdır. Petri
ağı modeli, montaj hattındaki iş elemanlarının öncelik ilişkilerini yansıtan bir modeldir. İş
elemanları, modeldeki geçişlerde tanımlanır. Dolayısıyla Petri ağı modelindeki geçiş sayısı,
problemdeki iş elemanı sayısına eşittir. Ayrıca iş elemanı sıra numarası ile modeldeki geçiş
sıra numarası aynı olmalıdır. Yani 3. iş elemanı 3. geçişte ifade edilmelidir. Böylece
algoritma sonucunun yorumlanması kolay olur. İlişki matrisi ve başlangıç simge durumunu
gösteren vektör, oluşturulan bu Petri ağı modelinden elde edilir. Geliştirilen algoritma
verilmeden önce, algoritmada kullanılan semboller açıklanacaktır.

Sonraki Konu :


Duyuru

Facebook sayfamiza üye olun


Duyuru
Sitemizde güncelleme çalismalari devam etmektedir.
Görüs ve önerilerinizi bizimle paylasabilirsiniz ! mail adresimiz : endustrimuhendisligi@hotmail.com