Montaj oran kısıtları ve renk kısıtlarını içeren araç sıralama problemi için sezgisel bir yaklaşım ve uygulama

thumbnail.default.placeholder
Tarih
2014-05-28
Yazarlar
Köksoy, Emek Gamze
Süreli Yayın başlığı
Süreli Yayın ISSN
Cilt Başlığı
Yayınevi
Fen Bilimleri Enstitüsü
Institute of Science And Technology
Özet
Bu çalışmada, montaj oran kısıtlarını ve renk kısıtlarını içeren araç sıralama problemi için üç aşamadan oluşan sezgisel bir yaklaşım önerilmiştir ve ROADEF finalistlerinin sonuçlarına göre değerlendirilmiştir. Birinci aşama araçların oran kısıtlarının ihlal sayısını minimum yapacak şekilde sıralanması için açgözlü algoritma tabanlı çeşitli seçim sezgiselleri içeren bir başlangıç algoritmasıdır. İkinci aşama oran kısıtı ihlal sayısının optimizasyonudur, araçların bulundukları dahil oldukları sıraların toplam ihlal sayısına göre yer değiştirilecek araç çiftlerinin karar verilmesine dayanır ve arama uzayını genişletmek için tavlama benzetimi yaklaşımı entegre edilmiştir. Bu aşamanın ikinci adımında Pareto prensibinden yararlanılarak en fazla ihlal sayısına sahip %20 aracın diğer araçlar ile yer değiştirilmesiyle %80 oranında iyileşme sağlanması amaçlanmıştır. Son aşama ise mevcut sıradaki araçların pozisyonları üzerinden renklerine göre ardışık araç grupları oluşturularak, bu araç gruplarının minimum renk ihlal sayısı oluşturacak başka pozisyonlara eklenmesidir. Sonuçlara bakıldığında önerilen başlangıç algoritmasının toplam sonuç üzerinde oldukça etkili olduğu görülmüştür. İkinci aşamanın ikinci adımının birinci adımdan sonra çalıştırıldığında etkisi olmamasına rağmen iki adım ayrı ayrı çalıştırıldığında birinci adımın sonuçlarına yakın sonuçlara çok daha kısa sürede ulaşılmaktadır. İyileştirmelerin %80'inin oran kısıtı optimizasyonunun birinci adımı ile sağlandığı ve renk optimizasyonu yaklaşımının da bazı veriler için ihlal sayısı iyileştirmelerin de etkili olduğu görülmüştür. Toplam sonuçlara bakıldığında genel olarak ilgili veriler için ROADEF finalistlerinin ulaştıkları sonuçların minimum ve maksimum değer aralıklarında sonuçlar elde edilmiştir.
In this study the car sequencing problem in which high priority ratio constraints are primary, color constraints are secondary is tackled. Heuristc approaches are proposed for this problem and evaluated according to results of ROADEF finalists. For optimization of ratio constraints, an initial algorithm based on greedy algorithm is used. After initial algorithm the main ratio constraint optimization algorithm is proposed. This algorithm has two stages. First one is related with swap of cars according to their number of regional violations which are total violations of sub-sequences in which the car is located in their positions. The second stage of this algorithm is related with Pareto principle. It is aimed to reduce %80 of total violation by swapping %20 cars which affect total violation at most with other cars. The last approach is related with color arrangement to recover color constraints violations. In this approach, cars are grouped according to their colors and batch size constraint after that new solutions are created by insertion of car groups. According to results, the effect of the initial algorithm to total result is seriously important. When the ratio constraint optimization second stage is run after first stage, it is not effective to recover violations, but when first stage and second stage are compared seperately, it is achieved close results to results of first stage in a shorter time by second stage. Although color optimization is proposed to minimize color violations, it is more effective for ratio constraint violations.
Açıklama
Tez (Yüksek Lisans) -- İstanbul Teknik Üniversitesi, Fen Bilimleri Enstitüsü, 2014
Thesis (M.Sc.) -- İstanbul Technical University, Institute of Science and Technology, 2014
Anahtar kelimeler
Araçlar, Algoritmalar, Vehicles, Algorithms
Alıntı