An Application on Flexible Job Shop Scheduling Problem with Iterated Greedy Algorithm

Abstract

Optimization is the selection of the best possible solution (min / max) under certain criteria. For the solution of optimization problems; many approaches have been developed in different classes such as exact solution methods, approximation methods, meta-heuristic techniques. However, the enormous size of real-life problems have led researchers to meta-heuristic techniques that provide acceptable solutions in a short time. In this study, an application has been made with the iterated greedy algorithm, which stands out with its simple structure. Flexible job shop scheduling problem is addressed for application. Basically, the iterative greedy algorithm starts the optimization process with a single solution. The current solution then enters the construction-destruction phase to find a better solution. The solution obtained after this stage is replaced with the incumbent solution according to the previously determined acceptance criteria. This cycle, which consists of two operators, construction and destruction, continues until a certain stopping criterion is met. In this study, a problem-specific critical path-based approach was developed in the construction-destruction phase. In addition, a novel approach based on the acceptance of solutions of decreasing quality depending on the number of iterations is proposed. The aim of this study is to contribute to the limited Turkish literature on the application of meta-heuristic algorithms in various fields.En iyileme (optimizasyon), belirli kriterler çerçevesinde muhtemel çözümler arasından en iyinin (min/max) seçilmesidir. En iyileme problemlerinin çözümü için; kesin çözüm yöntemleri, yakınsama metotları, meta-sezgisel teknikler gibi farklı sınıflarda birçok yaklaşım geliştirilmiştir. Ancak gerçek hayat problemlerinin devasa boyutlara ulaşması, araştırmacıları kısa zamanda, kabul edilebilir çözümler veren meta-sezgisel tekniklere yöneltmiştir. Bu çalışma ile meta-sezgisel algoritmaların çeşitli alanlarda uygulanması konusunda kısıtlı olan Türkçe literatüre katkı sağlanması amaçlanmıştır. Bu doğrultuda, sade yapısı ile ön plana çıkan tekrarlı açgözlü algoritması ile bir uygulama yapılmıştır. Uygulama için esnek atölye tipi çizelgeleme problemi ele alınmıştır. Bu çalışmada, yapım-yıkım fazında probleme özgü kritik yol tabanlı bir yaklaşım geliştirilmiştir. Ayrıca iterasyon sayısına bağlı olarak azalan kalitede çözümlerin kabulüne dayalı özgün bir yaklaşım önerilmiştir. Geliştirilen algoritmanın performansı, Fattahi ve ark., (2007) tarafından geliştirilen örnek problemler ile test edilmiş ve sonuçlar literatürde yapılan diğer çalışmalar ile karşılaştırılmıştır.