article

A Hybrid Genetic Algorithm for Assembly Line Balancing

Authors:

José Fernando Gonçalves,

Jorge Raimundo De AlmeidaAuthors Info & Claims

Journal of Heuristics, Volume 8, Issue 6

Pages 629 - 642

https://doi.org/10.1023/A:1020377910258

Published: 01 November 2002 Publication History

Abstract

This paper presents a hybrid genetic algorithm for the simple assembly line problem, SALBP-1. The chromosome representation of the problem is based on random keys. The assignment of the operations to the workstations is based on a heuristic priority rule in which the priorities of the operations are defined by the chromosomes. A local search is used to improve the solution. The approach is tested on a set of problems taken from the literature and compared with other approaches. The computation results validate the effectiveness of the algorithm.

References

[1]

Baybars, L. (1986). "A Survey of Exact Algorithms for the Simple Assembly Line Balancing Problem." Management Sci. 32, 909-932.

Digital Library

[2]

Bean, J. C. (1994). "Genetic Algorithms and Random Keys for Sequencing and Optimization." ORSA Journal on Computing 6(2), 154-160.

[3]

Bock, S. and O. Rosenberg. (1997). "A New Distributed Fault-Tolerant Algorithm for the Simple Assembly Line Balancing Problem 1," Technischer Bericht tr-rsfb-97-040.

[4]

Boctor, F. F. (1995). "A Multiple-Rule Heuristic for Assembly Line Balancing." Journal of Operational Research Society 46, 62-69.

[5]

Domschke, W., A. Scholl, and S. Voß. (1993). Produktionsplanung--Ablauforganisatorische Aspekte. Berlin:Springer.

[6]

Easton, F. F. (1990). "A Dynamic Program with Fathoming and Dynamic Upper Bounds for the Assembly Line Balancing Problem." Computers and Operations Research 17, 163-175.

Digital Library

[7]

Erel E. and S. C. Sarin. (1998). "A Survey of the Assembly Line Balancing Procedures." Production Planning and Control 9(5), 414-434.

[8]

Gen, M.,Y. Tsujimura, and Y. Li. (1996). "Fuzzy Assembly Line Balancing Using Genetic Algorithms." Computers and Industrial Engineering 31(3-4), 631-634.

[9]

Ghosh, S. and R. J. Gagnon. (1989). "A Comprehensive Literature Review and Analysis of the Design, Balancing and Scheduling of Assembly Systems." International Journal of Production Research 27, 637-670.

[10]

Goldberg, D. E. (1989). Genetic Algorithms in Search Optimization, and Machine Learning. Addison-Wesley, Reading, MA.

Digital Library

[11]

Hackman, S. T., M. J. Magazine, and T. S. Wee. (1989). "Fast, Effective Algorithms for Simple Assembly Line Balancing Problems." Oper. Res. 37, 916-924.

Digital Library

[12]

Held, M., R. M. Karp, and R. Shareshian. (1963). "Assembly Line Balancing Dynamic Programming with Precedence Constraints." Operations Research 11(3), 442-459.

Digital Library

[13]

Helgeson,W. and D. Birnie. (1961). "Assembly Line Balancing Using the Ranked Positional Weight Technique." Journal of Industrial Engineering 12, 394-398.

[14]

Hoffmann, T. R. (1990). "Assembly Line Balancing: A Set of Challenging Problems." International Journal of Production Research 28, 1807-1815.

[15]

Hoffmann, T. R. (1992). "EUREKA: A Hybrid System for Assembly Line Balancing." Management Science 38, 39-47

Digital Library

[16]

Johnson, R. V. (1988). "Optimally Balancing Large Assembly Lines with FABLE." Management Science 34, 240-253.

Digital Library

[17]

Kilbridge, M. and L. Wester. (1961). "A Heuristic Method for Assembly Line Balancing." Journal of Industrial Engineering 12, 292-298.

[18]

Klein, R. and A. Scholl. (1996). "Maximizing the Production Rate in Simple Assembly Line Balancing--A Branch and Bound Procedure." European Journal of Operational Research 91, 367-385.

[19]

Moodie, C. and H. Young. (1965). "A Heuristic Method of Assembly Line Balancing for Assumptions of Constant or Variable Work Element Times." Journal of Industrial Engineering 16, 23-29.

[20]

Nourie, F. J. and E. R. Venta. (1991). "Finding Optimal Line Balances with OptPack." Operations Research Letters 10, 165-171.

Digital Library

[21]

Ponnambalam, S. G., P. Aravindan, and G. M. Naidu. (1999). "A Comparative Evaluation of Assembly Line Balancing Heuristics." International Journal of Advanced Manufacturing Technology 15(8), 577- 586.

[22]

Scholl, A. (1993). "Data of Assembly Line Balancing Problems," Working Paper, TH Darmstadt.

[23]

Scholl, A. (1995). Balancing and Sequencing of Assembly Lines. Heidelberg: Physica-Verlag.

[24]

Scholl, A. and R. Klein. (1997). "SALOME: A Bidirectional Branch and Bound Procedure for Assembly Line Balancing." INFORMS Journal on Computing 9, 319-334.

Digital Library

[25]

Scholl, A. and R. Klein. (1999). Balancing Assembly Lines Effectively: A Computational Comparison." European Journal of Operational Research 114, 50-58.

[26]

Scholl, A. and S. Voß. (1994). "A Note on Fast, Effective Heuristics for Simple Assembly Line Balancing," Working paper, TH Darmstadt.

[27]

Scholl, A. and S. Voß. (1996). "Simple Assembly Line Balancing--Heuristic Approaches." Journal of Heuristics 2(3), 217-244.

[28]

Schrage, L. and K. R. Baker. (1978). "Dynamic Programming Solution of Sequencing Problems with Precedence Constraints." Operations Research 26, 444-459.

Digital Library

[29]

Spears, W. M. and K. A. DeJong. (1991). "On the Virtues of Parameterized Uniform Crossover." In Proceedings of the Fourth International Conference on Genetic Algorithms, pp. 230-236.

[30]

Sprecher, A. (1999). "A Competitive Branch-and-Bound Algorithm for the Simple Assembly Line Balancing Problem." International Journal of Production Research 37(8), 1787-1816.

[31]

Talbot, F. B., J. H. Patterson, and W. V. Gehrlein. (1986). "A Comparative Evaluation of Heuristic Line Balancing Techniques." Management Sci. 32, 430-454.

Digital Library

[32]

Tonge, F. (1961). A Heuristic Program of Assembly Line Balancing. Englewood Cliffs, NJ: Prentice-Hall.

Cited By

Noronha TRibeiro C(2024)Biased random-key genetic algorithms: A tutorial with applicationsProceedings of the 2024 8th International Conference on Intelligent Systems, Metaheuristics & Swarm Intelligence10.1145/3665065.3665083(110-115)Online publication date: 24-Apr-2024
https://dl.acm.org/doi/10.1145/3665065.3665083
Morais ISouto GRibeiro GMendonça IGonzález P(2022)A Hybrid BRKGA Approach for the Multiproduct Two Stage Capacitated Facility Location Problem2022 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC55065.2022.9870321(1-8)Online publication date: 18-Jul-2022
https://dl.acm.org/doi/10.1109/CEC55065.2022.9870321
Sun BZhou Y(2022)Bayesian network structure learning with improved genetic algorithmInternational Journal of Intelligent Systems10.1002/int.2283337:9(6023-6047)Online publication date: 30-Jul-2022
https://dl.acm.org/doi/10.1002/int.22833
Show More Cited By

Index Terms

A Hybrid Genetic Algorithm for Assembly Line Balancing

Recommendations

Mixed-Model Assembly Line Balancing Using the Hybrid Genetic Algorithm
ICMTMA '09: Proceedings of the 2009 International Conference on Measuring Technology and Mechatronics Automation - Volume 03

In view of the existing problem of mixed-model assembly line balancing, a mathematical model is proposed based on two factors, which are integrated including the workstation number and the assembly line efficiency. Then a new hybrid genetic algorithm is ...
An Effective Hybrid Genetic Simulated Annealing Algorithm for Process Planning Problem
ICNC '09: Proceedings of the 2009 Fifth International Conference on Natural Computation - Volume 05

Process planning is an essential part for a Computer Aided Process Planning (CAPP) system in the dynamic workshop environment. It is a combinatorial optimization problem to conduct operations selection and operations sequencing simultaneously with ...
A hybrid genetic algorithm that optimizes capacitated vehicle routing problems

This study primarily focuses on solving a capacitated vehicle routing problem (CVRP) by applying a novel hybrid genetic algorithm (HGA) capable of practical use for manufacturers. The proposed HGA has three stages. First, the nearest addition method (...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Heuristics

Journal of Heuristics Volume 8, Issue 6

November 2002

70 pages

ISSN:1381-1231

Issue’s Table of Contents

Copyright © Copyright © 2002 Kluwer Academic Publishers.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 November 2002

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

32
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Noronha TRibeiro C(2024)Biased random-key genetic algorithms: A tutorial with applicationsProceedings of the 2024 8th International Conference on Intelligent Systems, Metaheuristics & Swarm Intelligence10.1145/3665065.3665083(110-115)Online publication date: 24-Apr-2024
https://dl.acm.org/doi/10.1145/3665065.3665083
Morais ISouto GRibeiro GMendonça IGonzález P(2022)A Hybrid BRKGA Approach for the Multiproduct Two Stage Capacitated Facility Location Problem2022 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC55065.2022.9870321(1-8)Online publication date: 18-Jul-2022
https://dl.acm.org/doi/10.1109/CEC55065.2022.9870321
Sun BZhou Y(2022)Bayesian network structure learning with improved genetic algorithmInternational Journal of Intelligent Systems10.1002/int.2283337:9(6023-6047)Online publication date: 30-Jul-2022
https://dl.acm.org/doi/10.1002/int.22833
Souto GMorais IFaulhaber LRibeiro GHenrique González P(2021)A Hybrid BRKGA Approach for the Two Stage Capacitated Facility Location Problem2021 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC45853.2021.9504856(2007-2014)Online publication date: 28-Jun-2021
https://dl.acm.org/doi/10.1109/CEC45853.2021.9504856
Sun BZhou Y(2021)Biased Random-Key Genetic Algorithm for Structure LearningAdvances in Swarm Intelligence10.1007/978-3-030-78743-1_36(399-411)Online publication date: 17-Jul-2021
https://dl.acm.org/doi/10.1007/978-3-030-78743-1_36
Thiruvady DNazari AElmi A(2020)An Ant Colony Optimisation Based Heuristic for Mixed-model Assembly Line Balancing with Setups2020 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC48606.2020.9185757(1-8)Online publication date: 19-Jul-2020
https://dl.acm.org/doi/10.1109/CEC48606.2020.9185757
Kong MLiu XPei JCheng HPardalos P(2020)A BRKGA-DE algorithm for parallel-batching scheduling with deterioration and learning effects on parallel machines under preventive maintenance considerationAnnals of Mathematics and Artificial Intelligence10.1007/s10472-018-9602-188:1-3(237-267)Online publication date: 1-Mar-2020
https://dl.acm.org/doi/10.1007/s10472-018-9602-1
Dinh MNguyen VTruong VDo PPhan TNguyen D(2019)Simulated Annealing for the Assembly Line Balancing Problem in the Garment IndustryProceedings of the 10th International Symposium on Information and Communication Technology10.1145/3368926.3369698(36-42)Online publication date: 4-Dec-2019
https://dl.acm.org/doi/10.1145/3368926.3369698
Andrade CByers SGopalakrishnan VHalepovic EPoole DTran LVolinsky C(2019)Scheduling software updates for connected cars with limited availabilityApplied Soft Computing10.1016/j.asoc.2019.10557582:COnline publication date: 1-Sep-2019
https://dl.acm.org/doi/10.1016/j.asoc.2019.105575
Martarelli NNagano M(2019)Optimization of the Numeric and Categorical Attribute Weights in KAMILA Mixed Data Clustering AlgorithmIntelligent Data Engineering and Automated Learning – IDEAL 201910.1007/978-3-030-33607-3_3(20-27)Online publication date: 14-Nov-2019
https://dl.acm.org/doi/10.1007/978-3-030-33607-3_3
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents