Resource constrained parallel machine scheduling problems with machine eligibility restrictions: Mathematical and constraint programming based approaches

Abstract

Bu tezdeki araştırmada, elektrik malzemeleri üreten bir firmanın plastik-enjeksiyon bölümündeki gerçek çizelgeleme probleminden motive olunmuş ve iş-makine elverişliliği altındaki ek kaynak kısıtlı üç adet paralel makine çizelgeleme problemi analiz edilmiştir. Ele alınan ilk problem tüm işlerin işlem sürelerini eşit kabul etmekte ve toplam akış zamanını en küçüklemeyi amaçlamaktadır. Bu problem için iki sezgisel yaklaşım önerilmiştir. İlk yöntem, alt-gradyan eniyileme prosedürüne iliştirilmiş Lagrange-tabanlı bir çözüm yaklaşımıdır. İkinci yöntem ise probleme özgü sezgisel bir yaklaşımdır. Modellerin performansları, farklı problem parametreleri dikkate alınarak türetilen test problemleri üzerinde değerlendirilmiştir. Ele alınan ikinci problem, işlem sürelerinin keyfi olarak seçilebilmesine izin vermekte ve işlerin en son bitiş süresini (makespan) en küçüklemeyi amaçlamaktadır. Bu problem için, tamsayılı programlama (TP), kısıt programlama (KP) ve bütünleşik TP/KP olmak üzere üç farklı eniyileme modeli geliştirilmiştir. Dört farklı KP arama algoritması test edilmiştir. Önerilen modeller orta büyüklükteki test problemlerine uygulanmış ve önerilen TP/KP bütünleşik modelinin etkinliği gösterilmiştir. Ele alınan son problem 36 makineden oluşan ve gerçek kalıp-makine elverişlilik verisini içeren çizelgeleme problemini ele almaktadır. Bu problem için, TP/TP ve TP/KP ardışıksal yaklaşımları önerilmiştir. Her iki yaklaşım, bir TP modelinin işleri makinelere atadığı ortak bir yükleme aşamasına sahiptir. Çizelgeleme aşamasında ise son çizelgeyi oluşturmak üzere TP ve KP olarak iki farklı model önerilmiştir. Gerçek verilere dayalı olarak türetilen test problemleri üzerindeki değerlendirmeler, TP/KP ardışıksal yaklaşımının etkinliğini ortaya koymuştur. The research in this dissertation is motivated by a real-world scheduling problem in the injection molding department of an electrical appliance company and investigates three resource-constrained parallel machine scheduling problems with machine eligibility restrictions. The first problem assumes that processing times of all jobs are equal and aims to minimize total flow time. For this problem, two heuristic algorithms are proposed. The first one is a Lagrangian-based solution approach embedded into a subgradient optimization procedure. The second one is a problem specific heuristic. The performances of the proposed algorithms are evaluated by means of randomly generated test instances with different problem parameters. The second problem allows arbitrary processing times and aims to minimize makespan. For this problem, three optimization models, namely, integer programming (IP), constraint programming (CP), and combined IP/CP models, are developed. Four different CP search algorithms have been evaluated. The proposed models are then tested through medium size test problems and the efficiency of the proposed IP/CP combined model is demonstrated. The last problem considers the real case with 36 machines and real die-machine compatibility data. For this problem, IP/IP and IP/CP iterative approaches are proposed. Both approaches have a common loading phase where an IP model assigns the jobs to the machines. Subsequently, in the scheduling phase, two alternative models, namely, IP and CP are developed to construct the final schedule. The proposed approaches are evaluated by the test problems generated on real data, and the efficiency of IP/CP iterative approach is investigated.