Analyzing and evaluating priority rules for job shop scheduling problems


Thesis Type: Postgraduate

Institution Of The Thesis: Marmara University, Faculty of Engineering, Industrial Engineering, Turkey

Approval Date: 2004

Thesis Language: English

Student: MUSTAFA BATUHAN AYHAN

Supervisor: SEROL BULKAN

Abstract:

ATÖLYE TİPİ ÇİZELGELEME PROBLEMLERİ İÇİN ÖNCELİK KURALLARININ ANALİZ EDİLMESİ VE DEĞERLENDİRİLMESİ Atölye tipi çizelgeleme problemleri genel çizelgeleme sistemlerinin en zor ve en çok çalışılan alanlarından biridir. Bu problemler genel olarak, NP-zordur. Ve birçok çözüm teknikleri bu problemlerin optimal çözümlerini bulmakta başarısız kalır. Aslında bazı atölye tipi çizelgeleme problemleri vardır ki hala optimal çözümlerine ulaşılamamıştır. Bu problemleri çözmek için bazı komşuluk arama metotları olmasına rağmen, bu metotların etkinliği, kullanılan olanaklı başlangıç çözümlere dayanır. Genel olarak, öncelik kuralları bu metotlar için daha iyi olanaklı başlangıç çözümleri sağlar. Bu çalışma, öncelik kurallarının farklı atölye tipi çizelgeleme problemlerinde farklı performans kriterlerini göz önüne alan bir analiz ve değerlendirmeye odaklanmıştır. İlk olarak, genel çizelgeleme sistemleri için etraflıca bir analiz gerçekleştirilmiştir. Bu genel analizi takiben, atölye tipi üretim sistemlerinin ön tanımları ve sınıflandırmaları anlatılmıştır. Sonra, çeşitli önemli performans kriterleri araştırılmıştır. Daha sonra, en umut verici ve son zamanlarda geliştirilen öncelik kuralları listelenmiş ve açıklanmıştır. Bu kuralları, seçilen atölye tipi çizelgeleme problemlerine uygulamak için bir kıyaslama aracı geliştirilmiştir. Bu araç analizin önemli bir parçasıdır, çünkü analizin önemli bileşenlerini tedarik etmektedir. Rastgele atanan 'gerekli bitme zaman' etkisini azaltmak için program 5 defa çalıştırılmıştır. Analiz kısmında daha anlamlı bilgilere ulaşmak için, bu aracın çıktıları kendi amacımız doğrultusunda yönlendirilmiştir. Bu bilgilerle öncelik kuralları farklı problemler üzerinde değerlendirilmiştir. Kısaca, bu araştırmada, 6 farklı performans kriterine göre 35 farklı öncelik kuralı, 82 atölye tipi çizelgeleme probleminde analiz edilmiştir. Sonuçta ortaya çıkan yorumlar Eşli t Test analizleri kullanılarak değerlendirilmiştir. 6 farklı performans kriteri için farklı problem tiplerinde en iyi sonucu veren kurallar bulunmuştur. Temmuz, 2004 M. Batuhan AYHAN ABSTRACT ANALYZING AND EVALUATING PRIORITY RULES FOR JOB SHOP SCHEDULING PROBLEMS Job shop scheduling problems are one of the most difficult and studied fields of general scheduling systems. These problems are generally NP-Hard and most of the solution techniques fail to find optimal solutions. In fact there are some job shop scheduling problems, which cannot be still solved to achieve the optimal solutions. Although there are some neighborhood searching methods to solve these problems, the effectiveness of these methods rely on the initial feasible solutions, they implement. In general, priority rules provide better initial feasible solutions for these methods. This study is focused on the analysis and evaluation of the priority rules over different job shop scheduling problems regarding different performance criteria. Firstly, a comprehensive analysis of general shop scheduling systems is performed. Following this general analysis, the preliminary definitions and classifications of job shop scheduling systems have been explained. Then various important performance criteria have been explored. Afterwards, the most promising and recently developed priority rules have been listed and explicated. A comparison tool is developed to implement these rules to selected job shop scheduling problems. This tool is an important part of this analysis, since it supplies important components for the analysis. In order to reduce the effect of random due date assignments, program was run for 5 times. In the analysis part outputs of this tool have been manipulated to achieve more meaningful information. With this information, priority rules have been evaluated over different problems. Briefly, in this research, 35 different priority rules are analyzed over 82 job shop scheduling problems according to 6 different performance criteria. Consequently, the resulting comments are evaluated by using paired t test analysis. Best resulting rules have been found out for different types of problems with regarding 6 different performance criteria. July, 2004 M. Batuhan AYHAN