A solution approach for parallel machine scheduling problem in TAI-Turkish Aerospace Industries Inc.

TUSAŞ-Türk Havacılık ve Uzay Sanayii A.Ş.’ de paralel makinalarda çizelgeleme problemi için bir çözüm yaklaşımı

İsmail KARAOĞLAN, Fulya ALTIPARMAK, F. Nergis AKGÜL, M. Çağrı DÜZCE, Ozan ERDEM, Aslı KERİMOĞLU, Menekşe KOÇAK

Abstract

In this project, a parallel machine scheduling problem with sequence dependent setup times in the CNC Profile and Part Manufacturing Center of Turkish Aerospace Industries, Inc. has been considered. Firstly, a mixed integer linear programming model is developed for the problem. Since the problem is an NP-hard problem and the work groups to be scheduled consist of 50 or more works, it is not possible to obtain optimal solution with well known solvers such as CPLEX. Therefore, in order to obtain optimal or near optimal schedules in an acceptable time period, a heuristic algorithm based on simulated annealing (SA) algorithm is developed. The performance of the developed algorithm is examined by using multi start local search algorithm in terms of solution quality. While both of the algorithms have same performance for small-size problems, SA algorithm exhibits better performance than multi start local search algorithm for large-size problems. Moreover, an interface integrated with the developed heuristic algorithm is designed. By means of the interface, schedules for the works drawn from the database of firm for each station are obtained.

Özet

Bu projede, TUSAŞ-Türk Havacılık ve Uzay Sanayi A.Ş.’nin CNC Profil ve Parça İmalat Merkezi’ndeki sıra bağımlı hazırlık zamanının söz konusu olduğu paralel makinelerde çizelgeleme problemi dikkate alınmıştır. Problem için öncelikle karışık tamsayılı doğrusal programlama modeli geliştirilmiştir. Dikkate alınan çizelgeleme probleminin bir NP-zor problem olması ve çizelgelenecek iş gruplarının en az 50 yada daha fazla işten oluşması nedeniyle CPLEX gibi bilinen çözücüler ile eniyi çözüme ulaşmak mümkün değildir. Bu nedenle, makul zaman dilimleri içerisinde eniyi ya da eniyiye yakın iş çizelgelerini elde edebilmek için tavlama benzetimi (TB) algoritmasına dayalı bir sezgisel algoritma geliştirilmiştir. Geliştirilen algoritmanın performansı, çözüm kalitesi açısından çok başlangıçlı yerel arama algoritması ile karşılaştırmalı olarak incelenmistir. Küçük boyutlu test problemlerinde her iki algoritma aynı performansa sahipken, büyük boyutlu test problemlerinde TB algoritmasının daha iyi bir performans sergilediği görülmüştür. Ayrıca, geliştirilen sezgisel algoritma ile bütünleşik çalışan bir arayüz tasarlanmıştır. Bu arayüz ile firma veri tabanından çizelgelenecek iş listelerinin çekilmesine dayalı olarak istasyon bazında iş çizelgelerinin oluşturulması sağlanmıştır.