Tek makine gecikme problemi için yeni bir nöro-baskın kural

Abstract

ÖZET Anahtar Kelimeler: Tek Makina Çizelgeleme, Toplam Ağırlıklı Gecikme, Yapay Sinir Ağı, Nöro-Baskın Kural. Günümüzde, yüksek miktarda üretim yapan işletmelerin karşılaştığı endüstriyel problemlerin başında işlerin sıralanması ve çizelgelenmesinde yaşanan zorluklar gelmektedir. Binlerce parçanın makinalar üzerindeki işlem sıralarım maliyet perspektifi göz önüne alınarak dinamik olarak belirlemek oldukça büyük zaman almaktadır.Bu tez çalışmasında, tek makina problemleri için toplam ağırlıklı gecikmeyi minimize eden bir nöro-baskın kural (NBK) sunulmaktadır. Nöro-baskın kuralı elde etmek için, Geriye Yayınımlı Yapay Sinir Ağı (BPANN) kullanılmıştır. Çalışmada 3 farklı tipte tek makina toplam ağırlıklı gecikme problemi incelenmiştir. Birinci tip problem hazırlık zamanı olmaksızın sadece işlem zamanı, teslim zamanı ve ağırlık (gecikme maliyeti) parametrelerinden oluşan basit tek makina problemidir. İkinci tip problem, birinci tip problemde olmayan hazırlık zamanı parametresini içermektedir. Üçüncü tip problem ise hazırlık zamanı olmaksızın çift teslim zamanı problemidir. Birinci tip problem için yapay sinir ağı (YSA) 49,000 eğitme verisi ile eğitilmiş ve 441,000 test verisiyle de test edilmiştir. İkinci tip problem için YSA 39,200 veri ile eğitilmiş ve 352,800 veri ile test edilmiştir. Üçüncü tip problem için YSA 24,500 veri ile eğitilmiş ve 220,500 veri ile test edilmiştir. Üç YSA için de eğitme ve test sonuçlan oldukça yüksek seviyededir. Önerilen nöro-baskın kural, lokal optimallik için yeterli bir koşul sunmaktadır. Bu da, herhangi bir sıranın nöro- baskın kuralı bozması halinde, bozulmayı sağlayan işlerin toplam ağırlıklı gecikme kriterine göre yer değiştirmesini sağlamaktadır. Önerilen nöro-baskın kural, rasgele üretilmiş bir takım problemler için çeşitli sezgiseller ile karşılaştırılmaktadır. Sayısal sonuçlarımız gösteriyor ki, nöro-baskın kural tüm çalıştırmalarda öncelik kurallarından daha etkin olmaktadır. Sonuç olarak, nöro-baskın kural üst ve alt sınırları iyileştirebilmektedir. viii

A NEW NEURO-DOMINANCE RULE FOR SINGLE MACHINE TARDINESS PROBLEM SUMMARY Keywords: Single Machine Scheduling, Total Weighted Tardiness, Artificial Neural Network, Neuro-Dominance Rule. Today, sequencing and scheduling of the work tasks is rising as the prior handicap for the companies that is dealing with massive amount of production. It takes a very long time to determine the operation sequence of thousands of parts dynamically, considering the cost perspective. In this thesis work, a neuro-dominance rule (NDR) presented that minimize total weighted tardiness for single machine problems. Backpropagation Artificial Neural Network (BPANN) has been used to obtain the neuro-dominance rule. It is examined single machine total weighted tardiness problem of three different types in this study. The first problem is the problem which has developed by only processing time, due date and weighted parameters without release time on simple single machine problem. The second problem contains the release time parameter which isn't included in the first problem. The third problem is the double due date problem without release time. For the first problem, the artificial neural network (ANN) is trained with 49,000 training data and it is tested with 441,000 test data. For the second problem, ANN is trained with 39,200 data and tested with 352,800 data. For the third problem, ANN is trained with 24,500 data and tested with 220,500 data. The training and test results are also quite high for the three ANN. The proposed neuro-dominance rule provides a sufficient condition for local optimality. It has been provide mat if any sequence violates the neuro-dominance rule then violating jobs are switched according to the total weighted tardiness criterion. The proposed neuro-dominance rule is compared to a number of heuristics for a set of randomly generated problems. Our computational results indicate that the neuro-dominance rule dominates the heuristics in all runs. Therefore, the neuro- dominance rule can improve the upper and lower bounds. IX