İlişkisiz paralel makine çizelgeleme probleminde eniyi makine sayısının belirlenmesi içinbir doğrusal tamsayılı matematiksel model ve çözüm yaklaşımları

A mix integer programming model and solution approach to determine the optimum machine number in the unrelated parallel machine scheduling problem

Özet

Paralel makine çizelgeleme problemlerini ele alan çalışmalarda genellikle tüm makinelerin kullanılacağı varsayılmaktadır. Ancak devreye alınması sırasında çok yoğun enerji tüketilen büyük fırınların yer aldığı özel süreçlere sahip bazı işletmeler için işlerin en az sayıda fırın kullanılarak tamamlanması çok kritik olabilmektedir. Ayrıca pek çok işletme için de işlerini daha az makine ile gerçekleştirmek, üretimde kullanılmayan makinelerin başka bir işletmeye kiralanabilmesi veya boş kalan makinelerin kapasitesi kadar ek iş kabul edebilmesi fırsatlarını yaratmaktadır. Bu nedenle bu çalışmada, tüm makinelarin kullanılacağı varsayımı kaldırılmıştır, sıra ve makine bağımlı hazırlık sürelerinin ve makine uygunluklarının dikkate alındığı ilişkisiz paralel makine çizelgeleme probleminde hem hangi makinelarin kullanılacağına hem de kullanılacak makinelerde hangi işlerin hangi sırada üretileceğine karar verecek bir matematiksel model önerilmiştir. Ele alınan problemin amaçları, kullanılacak makine sayısının ve son işin tamamlanma zamanının enküçüklenmesidir. Önerilen çok amaçlı matematiksel modelin amaç fonksiyonları, ağırlıklı toplam yöntemi kullanılarak birleştirilmiştir. Matematiksel modelin çözüm performansının gösterilebilmesi için rassal türetilen test problemleri, GAMS/CPLEX ile çözülmüştür. Büyük boyutlu problemlerin çözümünde GAMS/CPLEX ile çözüm elde edilememesi nedeniyle bir yerel arama algoritması ve bir genetik algoritma önerilmiştir. Büyük boyutlu problem için tüm ağırlık çiftleri dikkate alındığında, genetik algoritma, yerel arama algoritmasından çözüm kalitesi açısından ortalama %25,64, süre açısından ise ortalama %50,31 daha başarılı olmuştur.

Abstract

It is assumed that all machines will be used in studies dealing with parallel machine scheduling problems. However, for some businesses having special processes, where large furnaces with very intense energy consumption are used during commissioning, it can be very critical to complete jobs using the least number of furnaces. In addition, for many businesses, doing their jobs with fewer machines creates opportunities for unused machines to be rented to another company or to accept additional jobs as much as the capacity of idle machines. For this reason, in this study, the assumption that all machines will be used has been removed and a mathematical model has been proposed that will decide both which machines will be used and which jobs will be produced in which order on these machines, for the unrelated parallel machine scheduling problem with sequence and machine dependent setup times and machine eligibility restriction. The objectives of the considered problem are minimizing the number of machines to be used and the completion time of the last job. The objective functions of the proposed multi-objective mathematical model are scalarized using the weighted sum method. In order to show the solution performance of the mathematical model, randomly generated test problems were solved with GAMS / CPLEX. To solve the large problems, a local search algorithm and a genetic algorithm have been proposed due to the lack of feasible solutions with GAMS / CPLEX. In the large-scale problem, when all weight pairs are taken into account, genetic algorithm is more successful than local search algorithm an average of 25.64% in terms of solution quality and 50.31% in terms of time.