A hybrid flow shop scheduling problem in ink production

Abstract

Bu çalışmada, Esnek Akış Tipi (EAT) çizelgeleme problemi ve çözüm yöntemleri ile bunların mürekkep üreten bir fabrikadaki gerçek çizelgeleme problemi üzerindeki uygulaması ele alınmıştır. Makine yapısına, işlem özelliklerine ve amaç fonksiyonuna göre EAT çizelgeleme probleminin birçok varyasyonu vardır. Bu çalışmada fabrikadaki gerçek üretim sürecinin dikte ettiği özel bir varyasyon üzerinde durulmuştur. Buna göre modelde makine bloklama, sıra bağımlı hazırlık süreleri, sınırlı kuyruk ve makine uygunluğu kısıtları bulunmalıdır. Amaç fonksiyonu da en son bitirilen işin tamamlanma zamanını en küçük değerine düşürmektir. Bu problemi çözebilmek için bir Karmaşık Tam Sayılı Doğrusal Programlama modeli geliştirildi. Bu model kullanılarak küçük ölçekli problemlerin en iyi çözümleri gösterildi. Ancak EAT çizelgeleme problemlerinin NP-zor karmaşıklık sınıfında olduğu bilindiğinden, bu model orta ve büyük ölçekli problemleri çözmede yetersiz kalmaktadır. Bundan dolayı, genellikle sezgisel yöntemlerin kullanması gerekliliği ortaya çıkar. Bu çalışmada farklı sezgisel yöntemler üzerinde durulmuştur. İlk çizelgeyi üretmek için, En Kısa İşlem Süresi, En Uzun İşlem Süresi ve bunların varyasyonları olan farklı kurucu sezgiseller kullanıldı. İlk çizelgeyi geliştirmek için ise, Tabu Arama (TA) ve Benzetimli Tavlama (BT) meta sezgiselleri farklı kontrol parametreleri ile kullanıldı. Sezgisel yöntemlerin performansı, küçük ölçekli problemlerde, daha önce matematiksel model ile elde edilen en iyi çözümlerle karşılaştırılarak değerlendirildi. Son olarak, fabrikadaki gerçek çizelgeleme problem örnek alınarak, büyük ölçekli problemler oluşturuldu ve bunların sonuçları rapor edildi

This study concerns with Hybrid Flow Shop Scheduling (HFS) problem and its real world application in a factory that produces ink and related special paints. There are many variations of HFS depending on the machine environment, process (job) characteristics and objective function. This study focus on a special variation that includes the constraints of machine blocking, sequence-dependent setup times, limited buffers and machine eligibility and having an objective of minimizing makespan. This variation is imposed by the properties of real production system in the factory. An original MIP model has been formulated to get the optimal solutions for small scale instances of the problem. The outcomes have been reported for a set of test problems. However, since HFS problems are classified as NP-hard, mathematical models are incapable of solving medium and large instances of the problem which may be seen in real world applications. Therefore, it is necessary to study heuristic methods. Different construction heuristics are used to generate initial schedule such as Shortest Processing Time and Longest Processing Time and their variants. To improve the initial solution, Simulated Annealing and Tabu Search methods are utilized with different control parameters. The performances of the heuristics have been evaluated on small scale problems by comparing with the optimal solutions obtained with MIP model. Finally, large scale problems have been generated to imitate real scheduling problems in the factory and their solutions have been reported.