An Application On Flowshop Scheduling

Year 2013, Volume 1, Issue 1, 2013, 47 - 56, 01.12.2013

Sündüs Dağ

Abstract

Flow shop scheduling problem has been well known as a research field for fifty years. In recent years, researchers have suggested many heuristic procedures to solve this type of problems. Most of these proposed algorithms in flow shop literature were applied to the benchmark problems. Few studies in flow shop literature include a real production application. The aim of this paper is to apply scheduling activity in a real flow shop production line. A cable production line is choosen for the application. All of the jobs are processed with same order which is named as permutational environment. The production line which is composed of eight different machines produces twelve kinds of cable. In other words, the problem size is 12 jobs x 8 machines. The objective of this problem focuses on minimizing total completion time and makespan. An ant colony algorithm is proposed to solve the problem. By changing initial solution of the algorithm, effect on objective function was monitored.

Keywords

Scheduling, Flowshop, Ant colony, Real Production Environment

Akiş Tipi Çizelgeleme Üzerine Bir Uygulama

Abstract

Akış tipi çizelgeleme problemi yaklaşık elli yıldır araştırmacıların fazlasıyla ilgisini çeken bir konu haline gelmiştir. Son yıllarda, bu tip problemlerin çözümüne yönelik birçok meta-sezgisel algoritma önerilmiştir. Çizelgeleme literatürüne bakıldığında, yapılan çalışmalarda geliştirilen algortimaların kıyaslama problemleri üzerinde denendiği gözlenmiştir. Gerçek üretim problemleri üzerinde yapılan çalışma sayısı çok azdır. Bu çalışmanın amacı, gerçek bir akış tipi üretim hattında çizelgeleme çalışmasının uygulanmasıdır. Uygulama alanı olarak kablo üretim sektöründen bir firma seçilmiştir. Seçilen üretim hattındaki makineler akış tipi üretime uygun bir biçimde sırlanmıştır ve tüm işlerin bu makinelerden geçiş sırası aynıdır. Üretim hattı sekiz makineden oluşur ve bu hatta oniki çeşit kablo üretilmektedir. Problemde amaç, maksimum tamamlanma zamanı ve toplam akış zamanını enküçüklemektir. Problemin çözümü için bir karınca koloni algoritması önerilmiştir. Ayrıca algoritmanın başlangıç çözümü değiştirilerek sonuç üzerindeki etkisi değerlendirilmiştir.

Keywords

Çizelgeleme, Akış tipi atölye, Karınca koloni algoritması, Gerçek Üretim Uygulaması

References

• Ashour, S. (1970). An experimental investigation and comparative evaluation of flowshop sequencing techniques.
• Operations Research, 18, 541–549. Ben-Daya, M., & Al-Fawzan, M. (1998). A Tabu Search
• Approach for the Flowshop Scheduling Problem. European Journal of Operational Research, 109, 88-95. Bullnheimer, B., Hartl, R.F. & Strauss, C. (1999). A New
• Rank-based Version of the Ant System: A Computational Study. Central European Journal for Operations Research and Economics, 7, 25–38. Campbell, H.G., Dudek, R.A., & Smith B.L. (1970). A
• Heuristic Algorithm for the n Job m Machine Sequencing Problem. Management Science, 16, 10-16. Colorni, A., Dorigo, M., & Maniezzo, V. (1992a).
• Distributed optimization by ant colonies. In F. J. Varela & P. Bourgine (Eds.), Proceedings of the first European conference on artificial life (pp. 134–142). Cambridge: MIT Press. Colorni, A., Dorigo, M., & Maniezzo, V. (1992b). An investigation of some properties of an ant algorithm. In R.
• Manner & B. Manderick (Eds.), Proceedings of PPSN-II, second international conference on parallel problem solving from nature 509–520). Dag, S. (2012). Optimizatıon of flowshop scheduling problems using heuristic techniques. Istanbul University, Ph.D.
• Thesis, Istanbul, Turkey: Department of Business Administration (in Turkish). Dannenbring, D.G. (1977). An Evaluation of Flowshop
• Sequencing Heuristic”, Management Science, 23, 1174-1182.
• Dorigo, M., Maniezzo, V., & Colorni, A. (1991a).
• Positive feedback as a search strategy. Technical Report, 91016, Italy: University of Milan.
• Dorigo, M., Maniezzo, V., & Colorni, A. (1991b). The ant system: An autocatalytic optimizing process. Technical Report, 91-016 (Revised), Italy: University of Milan.
• Dorigo, M., Maniezzo, V., & Colorni, A. (1996). The ant system: Optimization by a colony of cooperating agents. IEEE Transactions on
• Systems, Man, and Cybernetics – Part B, 26, 29–41. Dorigo, M., & Gambardella, L.M. (1996). A Study of Some Properties of Ant-Q. In Proceedings of PPSN Fourth International Conference on Parallel Problem Solving From Nature, 656-665.
• Dorigo, M., & Gambardella, L.M. (1997). Ant Colony System: A Cooperative Learning Approach to the TSP. IEEE Transactions on Evolutionary Computation, 1, 1-24.
• Eksioglu, B., Eksioglu, S. D., & Jain, P. (2008). A tabu search algorithm for the flowshop scheduling problem with changing neighborhoods, Computers and Industrial Engineering, 54, 0360-8352.
• Framinan, J.M., & Leisten, R. (2003). An efficient constructive heuristic for flowtime minimisation in permutation flow shops. Omega-International Journal of Management Science 31, 311-317.
• Gambardella, L. M., & Dorigo, M. (1995). Ant-Q: A reinforcement learning approach to the traveling salesman problem. In A. Prieditis & S. Russell (Eds.), Proceedings of the Twelfth international conference on machine learning (ML-95) (pp. 252–260). Palo Alto: Morgan Kaufman
• Gambardella, L. M., & Dorigo, M. (1996). Solving symmetric and asymmetric TSPs by ant colonies. In Proceedings of the 1996 IEEE international conference on evolutionary computation (pp. 622–627). Piscataway: IEEE Press
• Grabowski, J., & Wodecki, M. (2004). A Very Fast Tabu Search Algorithm for The Permutation Flowshop Problem with Makespan Criterion. Computers and Operations Research, 31, s.1891–1909.
• Grabowski, J., & Pempera, J. (2007). The permutation flow shop problem with blocking. Omega, 35, 302-311.
• Gupta, J.N.D. (1971). A Functional Heuristic Algorithm
• For Flow-Shop Scheduling Problem. Operations Research, 22, 39Ho, J.C., & Chang, Y. (1991). A New Heuristic For The n-Job, m-Machine Flowshop Problem. European Journal of
• Operations Research, 52, 194-202. Hundol, T.S., & Rajgopal, J. (1988). An Extension of
• Palmer’s Heuristic for the Flow shop Scheduling Problem. International Journal of Production Research, 26, 1119-1124.
• Ignall, E., & Schrage, L. (1965). Application of the branch and bound technique to some flowshop scheduling problems. Operations Research, 13, 400-412.
• Ishibuchi H., Misaki, S., & Tanaka, H. (1995). Theory and Methodology Modified Simulated Annealing Algorithms for The Flowshop Sequence Problem. European Journal of
• Operations Research, 81, 388-398. Jarboui,B., Eddaly,M., & Siarry,P. (2009). An estimation of distribution algorithm for minimizing the total flowtime in permutation flowshop scheduling problems. Computers &
• Operations Research 36, 2638-2646.
• Johnson, S.M. (1954).Optimal two three-stage production schedule with setup times included. Naval Research Logistics Quarterly, 1, 61-68.
• Kalczynski, P., & Kamburowski, J. (2008). An improved
• NEH Heuristic to Minimize Makespan in Permutation Flowshops. Computers and Operations Research, 35, 3001300
• Lageweg, B. J., Lenstra J., K., & Rinnooy Kan A., H, G. (1978). A general bounding scheme for the permutation flowShop problem. Operations Research, 26, 53-67.
• Li, X.P., Wang,Q., & Wu, C. (2009) Efficient composite heuristics for total flowtime minimization in permutation flow shops. Omega-International Journal of Management Science 37 (1), 155-164.
• Liu, J., & Reeves, C.R. (2001). Constructive and composite heuristic solutions to the P// ∑ Ci scheduling problem. European Journal of Operational Research 132,439– 452 .
• Lominicki, A.Z. (1965). A Brunch and bound algorithm for the exact solution of the three-machine scheduling problem. Operational Research Quarterly, 16, 439–452.
• McMahon, G. B., & Burton, P. (1967). Flowshop scheduling with branch and bound method. Operations Research, 15, 473–481.
• Nawaz, M., Enscore, J.E., & Ham, İ. (1983). A Heuristic
• Algorithm For The m-Machine, n-Job Flow-Shop Sequencing Problem. Omega, 11, 91-95. Ogbu, F., & Smith, D. (1990). Simulated Annealing for
• The permutation Flowshop Problem. Omega, The International Journal of Management Science, 19, 64-67. Osman, H.İ., & Potts, C. (1989). Simulated Annealing for
• Permutation Flowshop Scheduling. Omega, The International Journal of Management Science, 17, 551-557. Palmer, D.S. (1965). Sequencing jobs through a multistage process in minimum total time a quick method of obtaining a near optimum. Operational Research Quarterly, 16, 101-10
• Rad, S.F., Ruiz, R. & Boroojerdian, N. (2009). New High Performing Heuristics for Minimizing Makespan in Permutation Flowshops. Omega, 37, 331-345.
• Rajendran, C., & Chaudhuri D. (1991). An Efficient Heuristic Approach to the Scheduling of Jobs in a Flowshop. European Journal of Operational Research, 61, 318-325.
• Rajendran, C. (1993). Heuristic algorithm for scheduling in a flowshop to minimize total flowtime. International Journal of Production Economics 29,65–73.
• Rajendran,C., & Ziegler, H. (1997a). Heuristics for scheduling in a flowshop with setup, processing and removal times separated. Production Planning and Control 8,568–576. Rajendran, C., & Ziegler, H. (2004). Ant-colony algorithms for flowshop scheduling to minimize makespan/total flowtime of jobs. European Journal of Operational Research, 155, 426–438.
• Smith, R.D., & Dudek, R. A. (1967). A General algorithm for the solution of the n job, m machine sequencing problem of the flowshop. Operations Research 15, 71–82.
• Stafford, E.F. (1988). On the development of a mixedinteger linear programming model for the standard flowshop. Journal of the Operational Research Society 39, 1163–1174.
• Stutzle, T., & Hoos, H. (1996). Improving the ant system: A detailed report on MAX-MIN ant system. Technical Report, AIDA-96-12 (Revised version), Darmstadt: Darmstadt University of Technology.
• Stuetzle,T., (1998). An ant approach for the flow shop problem. In: Proceedings of the 6th European Congress on Intelligent Techniques and Soft Computing (EUFIT _98),vol. Verlag Mainz,Aachen,Germany, 1560–1564.
• Stutzle, T., & Dorigo, M. (2003). The ant colony optimization metaheuristic: Algorithms, applications, and advances. In F. Glover & G. Kochenberger (Eds.), Handbook of metaheuristics (pp. 251–285). Norwell, MA: Kluwer Academic Publishers.
• Taillard, E. (1990). Some Efficient Heuristic Methods for The Flowshop Sequencing Problem. European Journal of Operational Research, 47, 65-74.
• Taşgetiren, M.F., Liang, Y.C., Şevkli M. & Gençyılmaz, G. (2007). A Particle Swarm Optimization Algorithm for Makespan and Total Flowtime Minimization in the Permutation Flowshop Sequencing Problem. European
• T’kindt, V., Monmarche, N., Tercinet, F., & Laugt, D. (2002). An Ant Colony Optimization Algorithm to Solve a 2machine Bicriteria Flowshop Scheduling Problem. European Journal of Operational Research,142, 250–257.
• Watson, J.-P., Barbulescu, L., Whitley, L.D., & Howe, A.E. (2002). Contrasting structured and random permutation flow-shop scheduling problems: Search-space topology and algorithm performance. INFORMS Journal on Computing 14, 98–123
• Widmer, M., & Hertz, A. (1989). A New Heuristic Method for The Flowshop Sequencing Problem. European Journal of Operational Research, 41, 186–193.
• Wodecki, M. & Bozejko, W. (2002). Solving the Flow Shop Problem by Parallel Simulated Annealing. In Parallel Processing and Applied Mathematics, 2328, 236–244.
• Woo, H. S., & Yim, D.S. (1998). A heuristic algorithm for mean flowtime objective in flowshop scheduling.
• Computers and Operations Research 25, 175–182. 5 Yağmahan, B., & Yenisey M.M. (2010). A Multiobjective Ant Colony System Algorithm for Flowshop Scheduling Problem. Expert system with Aplication, 37, 01361-1368. 5 Ying, K.C. ve Liao, C.J., 2004 An Ant Colony System for Permutation Flowshop Sequencing”, Computers and Operations Research, C:31, No:5, s.791-801. 5
• Zhang, C., Ning, J., & Ouyang, D. (2010). Hybrid Alternate Two Phases Particle Swarm Optimization Algorithm for Flow Shop Scheduling Problem. Computers and Industrial Engineering, 58, 1-11. 5
• Zegordi, S.Y., Itoh, K. & Enkawa, T. (1995). Minimizing Makespan for Flowshop Scheduling by Combining Simulated Annealing with Sequencing Knowledge. European Journal of Operational Research, 85,. 515-531.