Optimizing the Permutation Flowshop Scheduling Problem by Scatter Search

Abstract

Scheduling is one of the decision-making processes that play a critical role in the production and service industries. Flow job scheduling is one of the types of scheduling where "n" job can be processed at "m" machines consequently. When the complexity of this problem increases, obtaining the optimum solution becomes difficult. But, solution can be found near the optimum in these complex problems by using the scatter search which is one of the meta heuristics. Scatter search method which is a branch of the evolutionary approach is an advantageous optimization technique due to producing two or more solution. In this study, the new model is developed for optimizing the permutation flowshop scheduling problem by scatter search

Keywords

• Scheduling, Permutation Flow Job Scheduling Scatter Search

Permütasyon Akış Tipi Çizelgeleme Probleminin Dağınık Arama İle Optimizasyonu

Abstract

Çizelgeleme, üretim ve hizmet endüstrilerinde kritik rol oynayan karar verme süreçlerinden bir tanesidir. Çizelgelemenin türlerinden biri olan akış tipi çizelgeleme, n işin m adet makinede aynı sırada işlem görmesidir. Bu problemin karmaşıklığı arttıkça en iyi çözüme ulaşılması zorlaşmaktadır. Fakat bu karmaşık problemlerde, meta sezgisel yöntemlerden biri olan dağınık arama metodu kullanılarak en iyi sonuca yakın çözümler bulunabilmektedir. Dağınık arama metodu evrimsel yaklaşımın bir kolu olmasıyla birlikte iki veya daha fazla çözüm üretmesi optimizasyon teknikleri açısından oldukça avantajlıdır. Bu çalışmada, permütasyon akış tipi çizelgeleme problemlerinin çözümü için dağınık arama ile bir model geliştirilmiştir

Keywords

• Çizelgeleme, Permütasyon Akış Tipi Çizelgeleme, Dağınık Arama

References

1. Ali, M. ve Dapoigny, R. (2006) “Advances in Applied Artificial Intelligence: 19th International Conference on Industrial”, Engineering and Other Applications of Ap- plied Intelligent Systems, IEA/AIE 2006, Annecy, France, June 27-30, 2006, Proceedings.
2. Cano, D.B., Santana, J.B., Rodriguez, C.C., Del Amo, I.J.G., Torres, M.G., Garcia, F.J.M., Batista, B.M., Perez, J.A.M., Vega, J.M.M., Martin, R.R. (2004) “Nature-inspired Components of the Scatter Search”, Technical Report.
3. Chang, P.C., Hsieh, J.C., Chen, S.H., Lin, J.L. ve Huang, W.H. (2009) “Artificial Chromosomes Embed- ded in Genetic Algorithm for a Chip Resistor Scheduling Problem in Minimizing the Makespan” Expert Systems with Applications, 36(3-2):7135-7141.
4. Çörekcioğlu, M. ve Güngör, A. (2005) “Havsız Kumaş Üretimindeki Dokuma Çizelgeleme Problemine Bir Çözüm Yordamı”, İstanbul Ticaret Üniversitesi V. Ulusal Üretim Araştırmaları Sempozyumu Bildiriler Kitabı: 225-230.
5. Dolgui, A., Morel, G. ve Pereira, C.E. (2006) “In- formation Control Problems in Manufacturing 2006”, A Proceedings Volume from the 12th IFAC Conference, 17-19 May 2006, Saint-Etienne, France.
6. El-Sayed, S.M., El-Wahed, W.F.A. ve Ismail, N.A. (2008) “A Hybrid Genetic Scatter Search Algorithm for Solving Optimization Problems”, The 6th International Conference on Informatics and Systems (INFOS2008), 27-29 Mart 2008, Faculty of Computers and Informa- tion, Cairo University, Kahire, Mısır.
7. Eren, T. ve Güner, E. (2005) “İki Ölçütlü Beklemesiz Akış Tipi Çizelgeleme Problemi: Toplam Tamamlanma Zamanı ve Maksimum Gecikme”, İstanbul Ticaret Üniversitesi V. Ulusal Üretim Araştırmaları Sempozyumu Bildiri Kitabı: 231-236.
8. Fink, A. ve Voß, S. (2003) “Solving the Continuous Flow-Shop Scheduling Problem by Metaheuristics” Euro- pean Journal of Operational Research, 151: 400-414.

9. Gao, J. ve Chen, R. (2011) “An NEH-based Heuristic Algorithm for Distributed Permutation Flowshop Sched- uling Problems” Scientific Research and Essays, 6(14): 3094-3100.
10. Goldberg D.E. (1989) “Genetic Algorithms in Search, Optimization and Machine Learning”, Addison-Wesley, USA.
11. Graves, S.C. (1981) “A Review of Production Sched- uling” Operations Research, 29(4): 646-675.
12. Haq, A.N., Saravanan, M., Vivekraj, A. R. ve Prasad, T. (2007) “A Scatter Search Approach for General Flow- shop Scheduling Problem” The International Journal of Advanced Manufacturing Technology, 31(7-8): 731–736.
13. Ho, Y.C., Zhao, Q.C. ve Jia, Q.S (2008) “Ordinal Optimization: Soft Optimization for Hard Problems”, Springer Science & Business Media.
14. Jini, F., Song, S. ve Wu, C. (2007) “An Improved Version of the NEH Algorithm and Its Application to Large-Scale Flow-Shop Scheduling Problems” IIE Trans- actions, 39: 229–234.
15. Kobu, B. (1989) “Üretim Yönetimi”, İstanbul Üniver- sitesi İşletme Fakültesi Yayını, Yedinci Baskı, İstanbul.
16. Kocamaz, M. (2009) “Üretim Programlama ve Üretim Parti Büyüklüklerinin Toplam Hazırlık Zamanı Üzerine Etkisi: Bir İşletme Uygulaması” Ege Akademik Bakış, 9(1):173-185.
17. Kocamaz, M. ve Çiçekli, U.G. (2010) “Paralel Makinaların Genetik Algoritma ile Çizelgelenmesinde Mutasyon Oranının Etkinliği” Ege Akademik Bakış, 10(1):199-210.
18. Kumar, S. ve Jadon, P. (2014) “A Novel Hybrid Algorithm for Permutation Flow Shop Scheduling” “Scatter Search Based Metaheurıstıc for Robust Opti- International Journal of Computer Science and Information mization of the Deploying of “DWDM” Technology on Technologies, 5(4):5057-5061.
19. Laguna M. ve Marti R. (2003) “Scatter Search: Meth- odology and Implementations in C”, Springer Science + Business Media, LLC.
20. Li, X. ve Yin, M. (2013) “An Opposition-Based Differential Evolution Algorithm for Permutation Flow Shop Scheduling Based on Diversity Measure” Advances in Engineering Software, 55(2013):10–31.
21. Liu, H., Gao, L. ve Pan, Q. (2011) “A Hybrid Particle Swarm Optimization with Estimation of Distribution Algorithm for Solving Permutation Flowshop Scheduling Problem” Expert Systems with Applications, 38(4): 4348- 4360.
22. Luo, Q., Zhou, Y., Xie, J., Ma, M. ve Li, L. (2014) “Discrete Bat Algorithm for Optimal Problem of Per- mutation Flow Shop Scheduling” The Scientific World Journal, 2014:1-15.
23. Marti, R., Laguna, M. ve Glover, F. (2006) “Princi- ples of Scatter Search” European Journal of Operational Research, 169:359-372.
24. Mobini, M.D.M., Rabbani, M., Amalnik, M.S., Razmi, J. Ve Rahimi-Vahed, A.R. (2009) “Using an enhanced scatter search algorithm for a resource-con- strained project scheduling problem” Soft Computing, 13:597-610.
25. Nedjah, N., Coelho, L.S. ve Mourelle, L.M. (2008) “Quantum Inspired Intelligent Systems”, Springer Sci- ence & Business Media.
26. Oktay, S. ve Engin, O. (2006) “Endüstriyel Prob- lemlerin Çözümünde Dağınık Arama Yöntemi: Literatür Araştırması” Sigma Mühendislik ve Fen Bilimleri Dergisi, 3:144- 155.
27. Osman, I.H. ve Kelly, J.P. (1996): “Meta-heuristics: An Overview” içinde: Osman, I.H. and J.P. Kelly (Ed.), Meta-Heuristics: Theory and Applications, Kluwer, Boston: 1–21.
28. Osman, I.H. ve Laporte, G. (1996) “ Metaheuristics: A Bibliography” Annals of Operations Research, 63: 513- 623.
29. Perez, J.A.M., Batista, B.M. ve Laguna, M. (2005) Optical Networks with Survivability” Yugoslav Journal of Operations Research, 15(1):65-77.
30. Pinedo, M. (2002) “Scheduling Theory, Algorithms and Systems”, Prentice Hall, Second Edtion, Upper Saddle River, New Jersey.
31. Reeves, C.R. (1995) “A Genetic Algorithm for Flowshop Sequencing” Computers & Operations Research, 22(1):5-13.
32. Reeves, C.R. ve Yamada, T. (1998) “Genetic Algo- rithms, Path Relinking and the Flowshop Sequencing Problem” Evolutionary Computation Journal, MIT, 6(1):230–234.
33. Russell, R.S., Taylor III, B.W. (2000) “Operation Management”, 4th Edition, Prentice Hall, New Jersey.
34. Sagarna, R. ve Lozano, J. A. (2006) “Scatter Search in Software Testing, Comparison and Collaboration with Estimation of Distribution Algorithms” European Journal of Operational Research, 169(2):392-412.
35. Sheikh, K. (2003) “Manufacturing Resource Plan- ning (MRP II) with an Introduction to ERP, SCM, and CRM”, McGraw-Hill.
36. Soyuer, H., Kocamaz, M. ve Kazançoğlu, Y. (2007) “Scheduling Jobs Through Multiple Parallel Channels Using an Expert System” Production Planning & Control: The Management of Operations, 18(1):35-43.
37. Tavakkoli-Moghaddam, R., Javadian, N., Khorrami, A. ve Gholipour-Kanani, Y. (2010) “Design of a scatter search method for a novel multi-criteria group scheduling problem in a cellular manufacturing system” Expert Sys- tems with Applications, 37:2661-2669.
38. Yin, M. ve Li, X. (2011) “A Hybrid Bio-Geography Based Optimization for Permutation Flow Shop Schedul- ing” Scientific Research and Essays, 6(10):2078-2100.
39. Yuan, K, Henequin, S, Wang, X ve Gao, L. (2006) “A New Heuristic-EM for Permutation Flowshop Sched- uling”, In Proceedings of the 12th IFAC Symposium on Information Control Problems in Manufacturing (INCOM06), May 17–19, 2006, Saint-Etienne, France.