Atölye tipi çizelgeleme için uzman-tabu arama modeli

Abstract

Bu tezde genel iş-atölyesi çizelgeleme probleminin çözüm kalitesinin iyileştirilmesi incelenmiştir. Bu amaçla genel olarak kesin çözüm arayan analitik yöntemler; yaklaşık çözüm arayan basit sezgisel yöntemler, çeşitli yapay zeka teknikleri, ve komşuluk aramasına dayalı yerel ve zeki arama yöntemleri analiz edilerek iki aşmalı bir çizelgeleme modeli tasarlanmıştır. Amaçlanan çizelgeleme modelinin ilk aşamasında, uzman sistem yöntembilimi kullanılarak iyi bir başlangıç çizelgesi elde edilmektedir. Bunun için, 24 kuraldan oluşan bir çizelgeleme bilgi tabanı oluşturulmuştur. Uzman sistem bu bilgi tabanından, atölye İş yükü ve iş teslim tarihi verisini kullanarak önce atölye sistem durumunu ve başarı ölçütünü belirlemekte, sonra bir çizelgeleme kuralı önermektedir. îkinci aşamada, uzman sistem tarafindan üretilen başlangıç çizelgesi, aynı basan ölçütü altında, tabu arama yöntemiyle iyileştirilmektedir. Tabu arama yöntemi mevcut bir çözümün komşularını artımlı arayarak ve aramanın hikayesini hafızasında tutarak, çözüm uzayındaki daha iyi çözümleri bulabilme yeteneği gösteren zeki bir arama yordamıdır. Bu çalışmada zeki aramanın gereklerini yeterince yerine getirebilen bir tabu arama çizelgecisi tasarlamak için, başta komşuluk yapılan, tabu listesi,seçkin çözümler listesi, aspirasyon ölçütü, yoğunlaşma ve çeşitlendirme taktikleri ile artım ve durdurma düzenekleri olmak üzere, çeşitli taktik ve parametreler üzerinde deneyler yapılmıştır. Bu deneylerde literatürde yer alan ve en iyi veya alt sınır çözümleri bilinen 38 test problemi kullanılmıştır. Sonra atölye yükü ve iş teslim tarihi açısından 9 farklı sistem durumu içeren bir deney düzeneği oluşturulmuş ve bunun üzerinde amaçlanan çizelgeleme modeli test edilmiştir. Son olarak, uzman sistemin basit öncelik kurallanna göre daha iyi olduğu, tabu arama yönteminin uzman sistemle üretilen başlangıç çizelgelerini iyileştirdiği, uzman sistemin basit öncelik kurallanna göre daha iyi bir başlangıç çizelgecisi olduğu gibi bazı önemli sonuçlar bulunmuş ve uzman-tabu arama çizelgeleme modelinin olurluluğu istatistikİ olarak gösterilmiştir. Amaçlanan çizelgeleme modelin tabu arama modülünde henüz geliştirilebilecek bazı unsurlar olması nedeniyle modelin gelecekte iyileştirilmesi mümkündür. Aynca tabu arama tekniğinin esnek yapısı nedeniyle hem çizelgeleme probleminin her türüne hem de diğer eniyileme problemlerine rahatlıkla uygulanabilir olması nedeniyle, bu tekniğin gelecekte önemli uygulamalannın olacağı vurgulanmaktadır.Anahtar Kelimeler : üretim çizelgeleme, uzman sistemler, tabu arama

The aim of this thesis is to develop a scheduling model using the intelligent pronlem solving approaches for deterministic job-shop scheduling. To do this, first of all the properties of the problem were examined and the current solution approaches in literature reviewed. The literature review revealed that the scheduling model must contain the approaches using the intelligent problem solving methodology with the ability to explore the search space widely. Thus, expert systems and tabu search issues are dealt with in more detail. The target scheduling system predicts that an expert system module is will produce an initial solution which will then be improved by a tabu search module. The reason why the scheduling system contains expert systems is that they can produce solutions different from the classic methods and can manage the multi-criteria in scheduling environment. Similarly, tabu search has the ability to provide the search facilities which are more comprehensive and more effective. The scheduling system was developed step by step. In the first phase, in order to prodece an initial solution, a prototype of the expert system which has a knowledge base managing the simple priority dispatching rules was developed. In the second phase, a tabu search framework was built and some of their important parameters' values were fixed by using some benchmark problems. In the final phase, an experimental design taking in the consideration the combination of different values of shop load and job due dates yeilded nine system states. For ech system state thirty test problems were generated. The test problems produced were solved by three methods. These are several simple priority dispatching rules, the expert system prototype, and the tabu search module with initial expert system solution. Next, the results obtained from each method were statistically analised and and interpred. The experimetal results indicated that the solutions of the tabu search method numerically are 1 6.74% better than that of the simple priority dispatching rules and only approximately 5% worse than that of the optimal. This showed that the expert systems are superior to the simple priority dispatching rules and that the tabu search method with initial expert system solution produces near-optimal solutions. Consequently, the feasibility of the target scheduling system has been statistically proven.Keywords : production scheduling, expert systems, tabu search