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.

Keywords

• Combinatorial optimization
• Iterated greedy algorithm
• Flexible job shop scheduling problem

Tekrarlı Açgözlü Algoritması ile Esnek Atölye Tipi Çizelgeleme Problemi Üzerine Bir Uygulama

Abstract

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.

Keywords

• Kombinatorial en iyileme
• tekrarlı açgözlü algoritma
• esnek atölye tipi çizelgeleme problemi

References

1. Al Aqel G, Li X, Gao L, Gong W, Wang R, Ren T, Wu G, 2018. Using Iterated Greedy with a New Population Approach for the Flexible Jobshop Scheduling Problem. In 2018 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM), 1235-1239.
2. Al Aqel G, Li X, Gao L, 2019. A modified iterated greedy algorithm for flexible job shop scheduling problem. Chinese Journal of Mechanical Engineering, 32(1): 21.
3. Antczak A, Antczak P, Witkowski T, 2009. Using of evolving cellular automata for flexible job shop with makespan criterion. In 2009 IEEE International Workshop on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications, 297-302.
4. Amjad MK, Butt SI, Kousar R, Ahmad R, Agha MH, Faping Z, ... Asgher U, 2018. Recent research trends in genetic algorithm based flexible job shop scheduling problems. Mathematical Problems in Engineering.
5. Bagheri A, Zandieh M, Mahdavi I, Yazdani M, 2010. An artificial immune algorithm for the flexible job-shop scheduling problem. Future Generation Computer Systems, 26(4), 533-541.
6. Bruker P, Schlie R, 1990 Job-shop scheduling with multi-purpose machines. Computing 45(4):369–375.
7. Chaudhry I A, Khan A A, 2016. A research survey: review of flexible job shop scheduling techniques. International Transactions in Operational Research, 23(3): 551-591.
8. Demir Y, İşleyen SK, 2014. An effective genetic algorithm for flexible job-shop scheduling with overlapping in operations. International Journal of Production Research, 52(13): 3905-3921.

9. Fattahi P, Saidi Mehrabad M, Jolai F, 2207. Mathematical modeling and heuristic approaches to flexible job shop scheduling problems. Journal of Intelligent Manufacturing, 18(3): 331-342.
10. Gao J, Sun L, Gen M, 2008. A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems. Computers & Operations Research, 35(9): 2892-2907.
11. Gao K, Cao Z, Zhang L, Chen Z, Han Y, Pan Q, 2019. A review on swarm intelligence and evolutionary algorithms for solving flexible job shop scheduling problems. IEEE/CAA Journal of Automatica Sinica, 6(4): 904-916.
12. Garey M R, Johnson D S, 1979. Computers and intractability (Vol. 174). San Francisco: freeman.
13. Gen M, Cheng R, 1997. Genetic algorithms & engineering design. NewYork:Wiley.
14. Jacobs L W, Brusco M J, 1995. A local search heuristic for large set-covering problems. Naval Research Logistics Quarterly, 42(7): 1129–1140
15. Kacem I., Hammadi S, Borne P, 2002. Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 32(1): 1-13.
16. Lin S. W, Ying K C, Huang C Y, 2013. Minimising makespan in distributed permutation flowshops using a modified iterated greedy algorithm. International Journal of Production Research, 51(16): 5029-5038.
17. Pezzella F, Morganti G, Ciaschetti G, 2008. A genetic algorithm for the flexible job-shop scheduling problem. Computers & Operations Research, 35(10): 3202-3212.
18. Pinedo M, 2002. Scheduling theory, algorithms, and systems. Englewood Cliffs, NJ: Prentice-Hall.
19. Riahi V, Chiong R, Zhang Y, 2020. A new iterated greedy algorithm for no-idle permutation flowshop scheduling with the total tardiness criterion. Computers & Operations Research, 117, 104839.
20. Rodriguez FJ, Lozano M, Blum C, GarcíA-MartíNez C, 2013. An iterated greedy algorithm for the large-scale unrelated parallel machines scheduling problem. Computers & Operations Research, 40(7): 1829-1841.
21. Ruiz R, Stutzle T, 2007. A Simple and Effective Iterated Greedy Algorithm for the Permutation Flowshop Scheduling Problem, European Journal of Operational Research, 177, 2033–2049.
22. Xie J, Gao L, Peng K, Li X, Li H, 2019. Review on flexible job shop scheduling. IET Collaborative Intelligent Manufacturing, 1(3): 67-77.
23. Zandieh M, Mahdavi I, Bagheri A, 2008. Solving the flexible job-shop scheduling problem by a genetic algorithm. JApSc, 8(24): 4650-4655.
24. Zhang G, Gao L, Shi Y, 2011. An effective genetic algorithm for the flexible job-shop scheduling problem. Expert Systems with Applications, 38(4): 3563-3573.