Integrating ant colony and genetic algorithms in the balancing and scheduling of complex assembly lines

详细信息    查看全文

• 作者：Ibrahim Kucukkoc ; David Z Zhang
• 关键词：Assembly line balancing ; Model sequencing ; Mixed model parallel two ; sided assembly lines ; Agent ; based ant colony optimization ; Genetic algorithm ; Artificial intelligence
• 刊名：The International Journal of Advanced Manufacturing Technology
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：82
• 期：1-4
• 页码：265-285
• 全文大小：1,377 KB
• 参考文献：1.Kucukkoc I, Zhang DZ (2015) Balancing of Parallel U-shaped Assembly Lines, Computers and Operations Research, doi:10.​1016/​j.​cor.​2015.​05.​014
  2.Ozdemir RG, Ayag Z (2011) An integrated approach to evaluating assembly-line design alternatives with equipment selection. Prod Plan Control 22(2):194–206CrossRef
  3.Battini D, Faccio M, Persona A, Sgarbossa F (2009) Balancing-sequencing procedure for a mixed model assembly system in case of finite buffer capacity. Int J Adv Manuf Technol 44(3-4):345–359CrossRef
  4.Thomopoulos NT (1967) Line balancing-sequencing for mixed-model assembly. Manag Sci 14(2):59–75CrossRef
  5.Akpinar S, Bayhan GM, Baykasoglu A (2013) Hybridizing ant colony optimization via genetic algorithm for mixed-model assembly line balancing problem with sequence dependent setup times between tasks. Appl Soft Comput 13(1):574–589CrossRef
  6.Kucukkoc I, Zhang DZ (2014) Simultaneous balancing and sequencing of mixed-model parallel two-sided assembly lines. Int J Prod Res 52(12):3665–3687CrossRef
  7.Erel E, Gokcen H (1999) Shortest-route formulation of mixed-model assembly line balancing problem. Eur J Oper Res 116(1):194–204CrossRef
  8.Matanachai S, Yano CA (2001) Balancing mixed-model assembly lines to reduce work overload. IIE Trans 33(1):29–42
  9.Vilarinho PM, Simaria AS (2002) A two-stage heuristic method for balancing mixed-model assembly lines with parallel workstations. Int J Prod Res 40(6):1405–1420CrossRef
  10.McMullen PR, Tarasewich P (2003) Using ant techniques to solve the assembly line balancing problem. IIE Trans 35(7):605–617CrossRef
  11.Yagmahan B (2011) Mixed-model assembly line balancing using a multi-objective ant colony optimization approach. Expert Syst Appl 38(10):12453–12461CrossRef
  12.Hamta N, Ghomi SMTF, Jolai F, Shirazi MA (2013) A hybrid PSO algorithm for a multi-objective assembly line balancing problem with flexible operation times, sequence-dependent setup times and learning effect. Int J Prod Econ 141(1):99–111CrossRef
  13.Kucukkoc I, Karaoglan AD, Yaman R (2013) Using response surface design to determine the optimal parameters of genetic algorithm and a case study. Int J Prod Res 51(17):5039–5054CrossRef
  14.Yano CA, Rachamadugu R (1991) Sequencing to minimize work overload in assembly lines with product options. Manag Sci 37(5):572–586CrossRef
  15.Kim YK, Hyun CJ, Kim Y (1996) Sequencing in mixed model assembly lines: a genetic algorithm approach. Comput Oper Res 23(12):1131–1145CrossRef
  16.Zheng YQ, Wang YP, Hu B, Wang YS (2011) A sequencing approach of models in mixed-model assembly lines. Mechanika 17(4):418–422
  17.Bautista J, Cano A (2011) Solving mixed model sequencing problem in assembly lines with serial workstations with work overload minimisation and interruption rules. Eur J Oper Res 210(3):495–513CrossRef
  18.Zhu XW, Hu SJ, Koren Y, Huang NJ (2012) A complexity model for sequence planning in mixed-model assembly lines. J Manuf Syst 31(2):121–130CrossRef
  19.Manavizadeh N, Tavakoli L, Rabbani M, Jolai F (2013) A multi-objective mixed-model assembly line sequencing problem in order to minimize total costs in a make-to-order environment, considering order priority. J Manuf Syst 32(1):124–137CrossRef
  20.Xu S, Li FM (2013) A modified genetic algorithm for sequencing problem in mixed model assembly lines. Adv Mater Res 655–657:1675–1681
  21.Zhang DZ, Kucukkoc I (2013) Balancing Mixed-Model Parallel Two-Sided Assembly Lines. Paper presented at the Proceedings of the International Conference on Industrial Engineering and Systems Management (IEEE-IESM’2013), Rabat, Morocco, October 28 - 30
  22.Boysen N, Fliedner M, Scholl A (2009) Sequencing mixed-model assembly lines: survey, classification and model critique. Eur J Oper Res 192(2):349–373MathSciNet CrossRef
  23.Kucukkoc I, Zhang DZ (2015) A mathematical model and genetic algorithm based approach for parallel Two-sided assembly line balancing problem. Prod Plan Control. doi:10.​1080/​09537287.​2014.​994685
  24.Bartholdi JJ (1993) Balancing 2-sided assembly lines - a case-study. Int J Prod Res 31(10):2447–2461CrossRef
  25.Kim YK, Kim SJ, Kim JY (2000) Balancing and sequencing mixed-model U-lines with a co-evolutionary algorithm. Prod Plan Control 11(8):754–764CrossRef
  26.Gökçen H, Agpak K, Benzer R (2006) Balancing of parallel assembly lines. Int J Prod Econ 103(2):600–609CrossRef
  27.Ozcan U, Gokcen H, Toklu B (2010) Balancing parallel two-sided assembly lines. Int J Prod Res 48(16):4767–4784CrossRef
  28.Kucukkoc I, Zhang DZ (2013) Balancing Parallel Two-Sided Assembly Lines via a Genetic Algorithm Based Approach. Paper presented at the Proceedings of the 43rd International Conference on Computers and Industrial Engineering (CIE43), The University of Hong Kong, Hong Kong, October 16-18
  29.Kucukkoc I, Zhang DZ (2015) Type-E parallel Two-sided assembly line balancing problem: mathematical model and Ant colony optimisation based approach with optimised parameters. Comput Ind Eng 84:56–69 doi:10.​1016/​j.​cie.​2014.​12.​037 CrossRef
  30.Simaria AS, Vilarinho PM (2009) 2-ANTBAL: An ant colony optimisation algorithm for balancing two-sided assembly lines. Comput Ind Eng 56(2):489–506CrossRef
  31.Ozcan U, Toklu B (2009) Balancing of mixed-model two-sided assembly lines. Comput Ind Eng 57(1):217–227CrossRef
  32.Chutima P, Chimklai P (2012) Multi-objective two-sided mixed-model assembly line balancing using particle swarm optimisation with negative knowledge. Comput Ind Eng 62(1):39–55CrossRef
  33.Ozcan U, Cercioglu H, Gokcen H, Toklu B (2010) Balancing and sequencing of parallel mixed-model assembly lines. Int J Prod Res 48(17):5089–5113CrossRef
  34.Battaïa O, Dolgui A (2013) A taxonomy of line balancing problems and their solution approaches. Int J Prod Econ 142(2):259–277CrossRef
  35.Kucukkoc I, Zhang DZ (2014) An Agent Based Ant Colony Optimisation Approach for Mixed-Model Parallel Two-Sided Assembly Line Balancing Problem. Paper presented at the Pre-Prints of the Eighteenth International Working Seminar on Production Economics, Innsbruck, Austria, 24-28 February
  36.Kucukkoc I, Zhang DZ (2014) Mathematical model and agent based solution approach for the simultaneous balancing and sequencing of mixed-model parallel Two-sided assembly lines. Int J Prod Econ 158:314–333CrossRef
  37.Chryssolouris G (2006) Manufacturing systems: theory and practice (2nd edition). SpringerVerlag, New York
  38.Song BL, Wong WK, Fan JT, Chan SF (2006) A recursive operator allocation approach for assembly line-balancing optimization problem with the consideration of operator efficiency. Comput Ind Eng 51(4):585–608CrossRef
  39.Corominas A, Pastor R, Plans J (2008) Balancing assembly line with skilled and unskilled workers. Omega Int J Manag Sci 36(6):1126–1132CrossRef
  40.Manavizadeh N, Hosseini NS, Rabbani M, Jolai F (2013) A simulated annealing algorithm for a mixed model assembly U-line balancing type-I problem considering human efficiency and just-in-time approach. Comput Ind Eng 64(2):669–685CrossRef
  41.Koltai T, Tatay V (2013) Formulation of workforce skill constraints in assembly line balancing models. Optim Eng 14(4):529–545MathSciNet CrossRef
  42.Fattahi P, Roshani A, Roshani A (2011) A mathematical model and ant colony algorithm for multi-manned assembly line balancing problem. Int J Adv Manuf Technol 53(1-4):363–378CrossRef
  43.Jayaswal S, Agarwal P (2014) Balancing U-shaped assembly lines with resource dependent task times: a simulated annealing approach. J Manuf Syst 33(4):522–534CrossRef
  44.Kara Y, Özgüven C, Yalçın N, Atasagun Y (2011) Balancing straight and U-shaped assembly lines with resource dependent task times. Int J Prod Res 49(21):6387–6405CrossRef
  45.Gajpal Y, Rajendran C, Ziegler H (2006) An ant colony algorithm for scheduling in flowshops with sequence-dependent setup times of jobs. Int J Adv Manuf Technol 30:416–424CrossRef
  46.Bard JF, Darel E, Shtub A (1992) An analytic framework for sequencing mixed model assembly lines. Int J Prod Res 30(1):35–48CrossRef
  47.Costa A, Cappadonna FA, Fichera S (2014) Joint optimization of a flow-shop group scheduling with sequence dependent set-up times and skilled workforce assignment. Int J Prod Res. doi:10.​1080/​00207543.​2014.​883469
  48.Ugarte BS, Pellerin R, Artiba A (2011) An improved genetic algorithm approach for on-line optimisation problems. Prod Plan Control 22(8):742–753CrossRef
  49.Dorigo M, Maniezzo V, Colorni A (1996) Ant system: Optimization by a colony of cooperating agents. IEEE Trans Syst Man Cybern Part B-Cybern 26(1):29–41CrossRef
  50.Holland JH (1975) Adaptation in natural and artificial systems. MIT Press, Cambridge
  51.Anosike AI, Zhang DZ (2009) An agent-based approach for integrating manufacturing operations. Int J Prod Econ 121(2):333–352CrossRef
  52.Liang H, Su H, Wang X, Chen MZQ (2014) Swarm aggregations of heterogeneous multi-agent systems. Int J Control 87(12):2594–2603MathSciNet CrossRef
  53.Cordon O, Herrera F, Stützle T (2002) A review on the Ant colony optimization metaheuristic: basis. Model New Trends Mathware Soft Comput 9(3):141–175
  54.Blum C (2005) Ant colony optimization: Introduction and recent trends. Phys Life Rev 2(4):353–373CrossRef
  55.Srinivas M, Patnaik LM (1994) Genetic algorithms - a survey. Computer 27(6):17–26CrossRef
  56.Li YC, Zhao LN, Zhou SJ (2011) Review of genetic algorithm. Adv Mater Res 179–180:365–367CrossRef
  57.Leitao P (2009) Agent-based distributed manufacturing control: a state-of-the-art survey. Eng Appl Artif Intell 22(7):979–991CrossRef
  58.Tasan SO, Tunali S (2008) A review of the current applications of genetic algorithms in assembly line balancing. J Intell Manuf 19(1):49–69CrossRef
  59.Lee ZJ, Su SF, Chuang CC, Liu KH (2008) Genetic algorithm with ant colony optimization (GA-ACO) for multiple sequence alignment. Appl Soft Comput 8(1):55–78CrossRef
  60.Chen SM, Chien CY (2011) Parallelized genetic ant colony systems for solving the traveling salesman problem. Expert Syst Appl 38(4):3873–3883CrossRef
  61.Li N, Wang S, Li Y (2011) A Hybrid Approach of GA and ACO for VRP. J Comput Inf Syst 7(13):4939–4946
  62.Arcus A (1966) COMSOAL, A Computer Method of Sequencing Operations for Assembly Lines. Int J Prod Res 4(4):259–277CrossRef
  63.Helgeson WB, Birnie DP (1961) Assembly line balancing using the ranked positional weight technique. J Ind Eng 12(6):394–398
  64.Talbot FB, Patterson JH (1984) An integer programming algorithm with network cuts for solving the assembly line balancing problem. Manag Sci 30(1):85–99CrossRef
  65.Baykasoglu A (2006) Multi-rule multi-objective simulated annealing algorithm for straight and U type assembly line balancing problems. J Intell Manuf 17(2):217–232MathSciNet CrossRef
  66.Arcus AL (1963) An analysis of a computer method of sequencing assembly line operations. Ph.D. Dissertation, University of California, Berkeley, USA
  67.Tonge FM (1960) Summary of a heuristic line balancing procedure. Manag Sci 7(1):21–42MathSciNet CrossRef
  68.Kim YK, Kim YH, Kim YJ (2000) Two-sided assembly line balancing: a genetic algorithm approach. Prod Plan Control 11(1):44–53CrossRef
  69.Lee TO, Kim Y, Kim YK (2001) Two-sided assembly line balancing to maximize work relatedness and slackness. Comput Ind Eng 40(3):273–292CrossRef
  
• 作者单位：Ibrahim Kucukkoc (1) (2)
  David Z Zhang (1)
  
  1. College of Engineering, Mathematics and Physical Sciences, University of Exeter, Streatham Campus, Exeter, England, UK
  2. Department of Industrial Engineering, Balikesir University, Cagis Campus, Balikesir, Turkey
  
• 刊物类别：Engineering
• 刊物主题：Industrial and Production Engineering
  Production and Logistics
  Mechanical Engineering
  Computer-Aided Engineering and Design
  
• 出版者：Springer London
• ISSN：1433-3015

文摘

Different from a large number of existing studies in the literature, this paper addresses two important issues in managing production lines, the problems of line balancing and model sequencing, concurrently. A novel hybrid agent-based ant colony optimization–genetic algorithm approach is developed for the solution of mixed model parallel two-sided assembly line balancing and sequencing problem. The existing agent-based ant colony optimization algorithm is enhanced with the integration of a new genetic algorithm-based model sequencing mechanism. The algorithm provides ants the opportunity of selecting a random behavior among ten heuristics commonly used in the line balancing domain. A numerical example is given to illustrate the solution building procedure of the algorithm and the evolution of the chromosomes. The performance of the developed algorithm is also assessed through test problems and analysis of their solutions through a statistical test, namely paired sample t test. In accordance with the test results, it is statistically proven that the integrated genetic algorithm-based model sequencing engine helps agent-based ant colony optimization algorithm robustly find significantly better quality solutions. Keywords Assembly line balancing Model sequencing Mixed model parallel two-sided assembly lines Agent-based ant colony optimization Genetic algorithm Artificial intelligence