An Analysis of fms scheduling problem : A beam search based algorithm and comparision of scheduling schemes

Abstract

ÖZET ESNEK ÜRETİM SİSTEMLERİNDE ÇİZELGELEME PROBLEMİNİN BİR ANALİZİ: IŞIN ARAMA TABANLI BİR ALGORİTMA VE ÇİZELGELEME METODLARININ KARŞILAŞTIRILMASI Süleyman Karabük Endüstri Mühendisliği Bölümü Yüksek Lisans Tez Yöneticisi: Yrd. Doç. İhsan Sabuncuoğlu Eylül, 1994 Literatürdeki Esnek Üretim Sistemleri (EÜS) çizelgeleme yaklaşımları her bir çizelgeleme noktasında verilen karar sayısına göre anında yönlendirme ve önce den çizelgeleme olmak üzere iki kategoriye ayrılabilir. Önceden çizelgeleme yak laşımı çizelgeleme kararlarının gerektiği zaman ve tek tek yapılmasini gerek tirir. Öte yandan, önceden çizelgeleme bütün çizelgeleme kararlarının bir kerede alınmasını öngörür. Literatürde hangi yaklaşımın üstün olduğu konusunda bir fikir birliği yoktur. Bu araştırmanın iki ana amacı vardır. Birincisi, anında yönlendirme ve önceden çizelgeleme yaklaşımlarının arasında olan ve her ikisinin olumlu taraflarım birleştiren yeni bir yaklaşım önermektir, ikincisi ise, önerilen yaklaşım ile diğerlerini değişik işletim çevrelerinde karşılaştırmasını yapmaktır. Bunun için, makinaların kısıtlı kuyruk kapasitesini, rota ve sıralama esnekliklerini gözönüne alarak makina ve otomatik güdümlü malzeme taşıtlarım çizelgeleyen bir algoritma geliştirilmiştir. Ayrıca değişik çizelgeleme yaklaşımlarının denenmesi için bir benzetim modeli de geliştirilmiştir. Anahtar sözcükler: Esnek Üretim Sistemleri, çizelgeleme, benzetim.

ABSTRACT AN ANALYSIS OF FMS SCHEDULING PROBLEM: A BEAM SEARCH BASED ALGORITHM AND COMPARISON OF SCHEDULING SCHEMES Süleyman Karabük M.S. in Industrial Engineering Supervisor: Assist. Prof. Disan Sabuncuoglu September, 1994 FMS scheduling procedures in the literature can be classified into on-line and off-line schemes according to the number of scheduling decisions made at a point in time. On line scheduling attempts to schedule operations one at a time when it is needed and off-line scheduling refers to scheduling operations of available jobs for the entire scheduling period. In the literature there is no unified argument for or against either of these scheduling schemes. This research has two main objectives: development of a new scheduling scheme called quasi on-line that makes a trade-off between on-line and off-line schemes and comparison of the proposed scheme with others under various experimental conditions. A new algorithm is proposed on which the quasi on line scheme is based. The proposed algorithm is a heuristic and utilizes a beam search technique. It considers finite buffer capacity, routing and sequence flexibilities and generates machine and AGV schedules for a given scheduling period. A simulation model is also developed to implement and test scheduling schemes. Keywords: Flexible Manufacturing Systems, scheduling, simulation. IV