Ekonomik lot çizelgeleme probleminde sezgisel algoritmalarınkıyaslamalı bir çalışması

Ekonomik lot çizelgeleme probleminde sezgisel algoritmaların kıyaslamalı bir çalışması endüstriyel ürünler , Ekonomik lot çizelgeleme probleminde sezgisel algoritmaların kıyaslamalı bir çalışması mühendislik formülleri sanayi malzemeleri , Ekonomik lot çizelgeleme probleminde sezgisel algoritmaların kıyaslamalı bir çalışması endüstriyel valf motor Ekonomik lot çizelgeleme probleminde sezgisel algoritmaların kıyaslamalı bir çalışması bakım malzemeleri ve arıza giderme yöntemleriBu yazı A comparative study of heuristic algorithms on Economic
Lot Scheduling Problem isimli Asif S. Raza, Ali Akgunduz 'ün çalışmasının kısa bir özetidir.


Ekonomik lot çizelgeleme problemleri genellikle deterministik olmayan zor çözülebilen polinom problemleri olarak görülmüştür.Araştırmacılar sezgisel yaklaşımların etkinliğinin gelişimi üzerinde odaklanmıştır.Bu çalışmada yazarlar zaman-değişimi lot ölçek yaklaşımını göz önüne alıyorlar.Kesin çözüm algoritmalarının bir hesaplanabilir çalışması sunuluyor.Bu algoritmalar şunlardır: Dobson’ın sezgiseli,melez genetik algoritma,komşu arama sezgiselleri,tabu arama ve simule edilmiş tavlama algoritması.

Ekonomik lot çizelgeleme problemi toplam maliyeti minimize etmek için verilmiş tek bir üretim bölümü üzerinde birkaç farklı ürünlerin üretim atamalarıyla ilgilenir.Ekonomik lot çizelgeleme probleminin özellikleri ise şöyledir:

1.Makinada bir seferde sadece bir ürün üretilebilir
2.Her ürün deterministik ve kısıtlı talep ve üretim oranlarına sahiptir.
3.Kurulum maliyeti ve zamanları üretim serisinden bağımsızdır.
4.Üretim bölümünün, planlama anlayışı boyunca öngörülmüş talebi karşılayabileyeceği farz edilir.
5.Stok tutma maliyeti,stok miktarıyla doğru orantılıdır.[Maxwell,1964]

Dobson’ın Ekonomik lot çizelgeleme problemi modeli

1.Ürünlerin birbirleri üzerinde öncelikleri yoktur.
2.Geri dönen siparişlere izin verilmez
3.Üretim bölümünün hatalı serbest ve daima kusursuz kaliteli ürünler üretebilmesi farz edilir.
The data for the problem is:
i ürün indeksi
m ürünlerin toplam sayısı
pi parçanın üretim oranı i, 8i ¼ 1; 2; . . . ; m
di parçanın talep oranı i, 8i ¼ 1; 2; . . . ; m
hi stok tutma maliyeti ( $ per unit per day), 8i ¼ 1; 2; . . . ; m
Ai kurulum maliyeti ($) 8i ¼ 1; 2; . . . ; m
si ürün için kurulum zamanı i. (days) 8i ¼ 1; 2; . . . ; m
T ürün çevriminin aralığı
K 1 _
Pmi
¼1
di
pi


Tabu Arama Algoritması

Tümleşik optimizasyon problemlerinin çözümü için tekrarlı sezgisel bir yöntemdir.Yerel aramanın genelleştirilmiş bir halidir.Her bir adımda geçerli çözümün yerel komşuları açıklanır ve böylece aday çözümlerin bir sayısı üretilir.En iyi aday çözüm aramadaki gelecek iterasyon için komşuların elenmesindendir.Farklı yerel arama geçerli komşularda gelişmiş çözüm bulunamayınca sona erer.Tabu arama yeniler şimdiki çözümden daha kötü olsa bile yeni çözümler keşfetmeye devam eder.Çevrimi engellemek için tabu listesinde en son ziyaret edilen çözüme uyan bilgi kaydedilir.[Glover,1990]

Tabu Kısıtlaması

Önceden ziyaret edilmiş çözümlere çevrimde geri gitmekten kaçınmak için bir kontrol mantığıdır.Bu alternatif çözümlerin seçilmiş özelliklerinde hareket edilerek başarılır.Tabu listesinde çözümün özellikleri kaydedilir.

Melez Genetik Algoritması

Bir genetik algoritma doğal seçilimlerin ve genetiklerin mekanizması üzerinde stokastik arama algoritma tabanlıdır.Algoritma popülasyon olarak adlandırılan rasgele çözümlerin bir setiyle başlar.Popülasyonda her birey probleme mümkün çözüm olan bir kromozom olarak kimliklendirilir.Kromozomlar başarılı iterasyonlar üzerinden evrim geçirir.Her bir nesil boyunca kromozomlar yeteneklerin bazı ölçüleri kullanılarak evrimleşir.Algoritma karmaşık ve geniş arama uzayına sahip olan problemler için uygun yapılandırılmıştır.Genetik algoritmanın bir problemi çözebilmesi için bazı temel bileşenleri şunlardır.1.çözüm temsil edilebilir ve başlatılabilir olmalı 2.amaç ve uygunluk fonksiyonu 3.yeniden üretim,çaprazlama ve mutasyon 4.uygunluk ölçeği

Simüle Edilmiş Tavlama Algoritması

Tümleşik optimizasyon problemleri için etkin bir yoldur.Tipik bir simulasyonlu tavlama algoritması uygulaması bir çekirdek çözüm,cooling schedule,onaylanmış olasılıklı fonksiyon ve durdurma kriterine gerek duyar.

Bu algoritma 3 tane önemli konu vardır

1.Cooling schedule 2.Markov zincir uzunluğu 3.onaylanmış olasılık fonksiyonu

Cooling Schedule

3 parametre içerir bunlar 1.ilk sıcaklık 2.sıcaklık kayıp kuralı 3.Son sıcaklık

Markov Zincir uzunluğu üretilmiş çözümlerin rasgele bir sayısını tarif eder.


Bu çalışmada yazarlar Simulasyonlu tavlanmış algoritma ile bir istatiksel çalışma yapıyorlar.Bu çalışmanın tabloları orijinal haliyle aşağıdaki gibidir.

Genetik algoritma hariç bütün sezgisel yöntemlerin çözümlerini yazarlar Matlab programını kullanarak yapmışlar.Genetik algoritmayla kıyaslama için [Moon,2002] de belirtilen yöntemi kullanmışlar.Çalışmalar intel pentium 4 2.40 ghz işlemcili 256 mb ram li bilgisayarda test edilmiştir.

Çalışmada kullanılan referanslar

Aarts, E. H. L., & Laarhoven, P. J. N. V. (1985). Statistical cooling: A general approach to combinatorial optimization problem. Philips
Journal of Research, 40, 193–226.
Allen, S. J. (1990). Production rate planning for two products sharing a single process facility: A real world case study. Production and
Inventory Management, 31, 24–29.
Aytug, H., Khouja, M., & Vergara, F. E. (2003). Use of genetic algorithm to solve production and operations management problems: A
review. Interantional Journal of Production Research, 41, 3955–4009.
Ben-daya, M., & Al-Fawzan, M. (1998). A tabu search approach for the flow shop scheduling problem. European Journal of Operational
Research, 109(1), 88–95.
Bomberger, E. E. (1966). A dynamic programming approach to a lot size scheduling problem. Management Science, 12, 778–784.
Delporte, C., & Thomas, L. (1978). Lot sizing and sequencing for N products on one facility. Management Science, 23, 1070–1079.
Dobson, G. (1987). The economic lot-scheduling problem: Achieving feasibility using time-varying lot sizes. Operations Research, 35,
764–771.
Dobson, G. (1992). The cyclic lot scheduling problem with sequence-dependent setups. Operations Research, 40, 736–749.
Doll, C. L., & Whybark, D. C. (1973). An iterative procedure for the single-machine multi-product lot scheduling problem. Management
Science, 20, 50–55.
Eglese, R. W. (1990). Simulated annealing: A tool for operational research. European Journal of Operational Research, 46, 271–281.
Eilon, S. (1959). Economic batch-size determination for multi-product scheduling. Operations Research, 10, 217–227.
Elmaghraby, S. (1978). The economic lot scheduling problem (ELSP): Review and extension. Management Science, 24, 587–598.
Faaland, B. H., Schmitt, T. G., & Arreola-Risa, A. (2004). Economic lot scheduling with lost sales and setup times. IIE Transactions, 36,
629–640.
Feldmann, M., & Biskup, D. (2003). Single-machine scheduling for minimizing earliness and tardiness penalties by meta-heuristic
approaches. Computers & Industrial Engineering, 44, 307–323.
Forrest, S. (1985). Documentation for PRISONERS DILEMMA and NORMS programs that Use the Genetic Algorithm. Ann Arbor:
University of Michigan.
French, S. (1982). Sequencing and Scheduling: An Introduction to the Mathematics of the Job-Shop. Ellis Horwood Limited.
Gaafar, L. (2006). Applying genetic algorithms to dynamic lot sizing with batch ordering. Computers & Industrial Engineering, 51,
433–444.
Gallego, G. (1990). An extension to the class of easy economic lot scheduling problem easy?. IIE Transactions 22, 189–190.
Gallego, G. (1993). Reduced production rates in the economic lot scheduling problem. International Journal of Production Research, 31,
1035–1046.
Gallego, G., & Roundy, R. (1992). The economic lot scheduling problem with finite backorder costs. Naval Research Logistics, 39,
729–739.
Gallego, G., & Shaw, X. (1997). Complexity of the ELSP with general cyclic schedules. IIE Transactions, 29, 109–113.
Gellego, G., & Moon, I. (1992). The effect of externalizing setups in the economic lot scheduling problem. Operations Research, 40,
614–619.
Giri, B. C., Moon, I., & Yun, W. Y. (2003). Scheduling economic lot sizes in detriorating production systems. Naval Research Logistics,
50, 650–661.
Glover, F. (1989). Tabu Search – Part I. OSAR Journal on Computing, 1, 190–206.
Glover, F. (1990). Tabu Search – Part II. OSAR Journal on Computing, 2, 4–32.
Glover, F., Glover, F. W., & Laguna, M. (1998). Tabu Search. Kluwer Academic Publishers.
Hanssmann, F. (1962). Operations Research in Production Planning and Control. New York: John Wiley.
Hsu, W. (1983). On the general feasibility test for scheduling lot sizes for several products on one machine. Management Science, 29,
93–105.