Machine scheduling with sequence dependent setup time and over time

Bu çalışma kapsamında sıra bağımlı ayar zamanı ile tek makine çizelgeleme problemi ele alınmaktadır. Bir gerçek hayat uygulamasını temel alan problemin amacı, en küçük toplam fazla mesai değeri ile müşteri taleplerinin teslim tarihinden önce hazır olmasını sağlayan haftalık üretim çizelgesini belirlemektir. Fazla mesai ücretleri fazla mesai yapılan süreye bağlı olarak hesaplanmaktadır. Bu problem için günlük detayda çizelgeler oluşturulmaktadır. Problem için öncelikle karma tam sayılı matematiksel programlama modeli geliştirilmiştir. Bu optimizasyon problemi için yapılan testlerde gerçek hayat örnekleri için makul sürelerde çözüm bulunamadığı görüldüğünden çözüm zamanını azaltmak amacıyla bir ayrıştırma algoritması geliştirilmiştir. Mantıksal Benders ayrıştırma algoritması olarak adlandırılan bu yaklaşımla karmaşık esas problem, karma tam sayılı ana problem ve çeşitli sayıda kısıt programlama alt problemleri olarak, görece kolay çözülebilir problemlere ayrıştırılmaktadır. Ana problemde işlerin günlere atanmasına karar verilirken, alt problemlerde bu atamalara göre günlük çizelgeler belirlenmektedir. Algoritma alt problemlerin çözümüne göre tanımlanan olurluluk veya optimallik kesilerinin ana probleme eklenmesi ile devam etmektedir. Çalışma kapsamında algoritma, kesilerin eklenme şekline göre iteratif ve dallandırma ve kontrol olmak üzere iki farklı yaklaşımla uygulanmıştır. Ayrıştırma algoritması ile, makul süre içerisinde optimal çözümü belirlemenin zorlaştığı örnekler için, ayrıca bir tavlama benzetimi algoritması geliştirilmiştir. Tavlama benzetimi için başlangıç çözümü, geliştirilen çözüm kuran algoritmayla, soğuma şeması ise gerçekleştirilen parametre analizleriyle belirlenmiştir. Geliştirilen bütün çözüm yöntemlerinin performansı yapılan deneysel çalışmalarla analiz edilmiştir.In this study we considered a single machine scheduling problem with sequence dependent setup times from a real-world application. Our goal is to determine the weekly production schedule that minimizes the overtime with respect to deadlines. Here the available overtime periods are defined at the end of each day and related costs are calculated based on overtime use. Therefore the amount of overtime used at each day is determined through detailed schedules. We developed a mixed integer programming model for the problem. However our experimental studies showed that this optimization problem is intractable for real-world instances. A decomposition algorithm is proposed in order to decrease solution time. We developed a logic-based Benders decomposition algorithm which decomposes the original problem to a daily assignment problem and scheduling problems based on these assignments for each day. In this approach the master assignment problem is solved with mixed integer programming while sub scheduling problems are solved with constraint programming. The algorithm proceeds as the feasibility and optimality cuts, defined by the solutions obtained from subproblems, are added to the master problem. In the scope of this study related cuts are added either iteratively or with branch-and-check approach. For the instances that the decomposition algorithm could not find the optimal solution in a reasonable time, simulated annealing algorithm is used to obtain feasible solutions. In this context initial solution is determined through the constructive heuristic developed while cooling schedule is defined through parameter analyses. The performances of these solution approaches are tested through experimental studies