IIM  Vol.8 No.3 , May 2016
Heuristics for Mixed Model Assembly Line Balancing Problem with Sequencing
ABSTRACT
The growing global competition compels organizations to use many productivity improvement techniques. In this direction, assembly line balancing helps an organization to design its assembly line such that its balancing efficiency is maximized. If the organization assembles more than one model in the same line, then the objective is to maximize the average balancing efficiency of the models of the mixed model assembly line balancing problem. Maximization of average balancing efficiency of the models along with minimization of makespan of sequencing models forms a multi-objective function. This is a realistic objective function which combines the balancing efficiency and makespan. This assembly line balancing problem with multi-objective comes under combinatorial category. Hence, development of meta-heuristic is inevitable. In this paper, an attempt has been made to develop three genetic algorithms for the mixed model assembly line balancing problem such that the average balancing efficiency of the model is maximized and the makespan of sequencing the models is minimized. Finally, these three algorithms and another algorithm in literature modified to solve the mixed-model assembly line balancing problem are compared in terms of the stated multi-objective function using a randomly generated set of problems through a complete factorial experiment.

Received 13 March 2016; accepted 28 May 2016; published 31 May 2016

1. Introduction

Companies engaged in mass production use assembly line balancing to design its assembly line by taking necessary input. Assembly line balancing is the process of grouping the tasks of precedence network of a product that is assembled into a minimum number of workstations such that the sum of the task times in each of the workstations is less than or equal to the cycle time.

The cycle time is computed based on a given production volume per shift using the following formula [1] .

(1)

The process of minimizing the number of workstations amounts to maximizing the balancing efficiency of the assembly line. This type of problem is called as assembly line balancing problem 1 (ALBP 1). In contrary, for a given number of workstations, the objective may be to minimize the maximum of the sum of the task times of workstations. This problem is called as assembly line balancing problem 2 (ALBP 2). This in turn maximizes the production volume per shift.

The balancing efficiency of the solution of the assembly line balancing problem is given by the following formula [1] .

(2)

where,

N is the number of tasks.

tj is the required time of the task j.

CT is the cycle time.

NS is the number of workstations.

Now-a-days, companies assemble more than one model in the same line mainly to meet the demands of its customers on continuous basis, which necessitates the use of mixed-model assembly line balancing. Here, the objective is to maximize the average balancing efficiency of the models. Further, sequencing of the models with minimum makespan along with the maximization of the average balancing efficiency of the models will improve the productivity of the company very much.

In this paper, the ALBP 1 problem with a mixed-model is considered. In this problem, there will be many models which are to be produced in batches using the same assembly line. The presence of a mixed-model makes the design of the assembly line more complex, in terms of processing times of the tasks and cycle times of the model. The average processing time (Tj) of each task as given by the following formula is normally taken as the representative value of the task time for that task.

(3)

where,

tij is the time of the task j in the model i.

N is the number of tasks.

m is the number of models.

Tj is the average time of the task j.

NMj is the number of models in which the processing time of the task j is more than zero.

Researchers in the past except [2] computed average task time for each of the tasks in the combined model. But, in this research, the average task time is not computed. Instead, the original task times of the models are used as such in the design of the assembly line without any modification, because it introduces perfection in the design of the assembly line in terms of reduced number of workstations.

The concept of combined network in the mixed-model assembly line balancing problem is demonstrated using two models, viz. Model 1 and Model 2, whose precedence networks are shown in Figure 1 and Figure 2, respectively. The number by the side of each node represents the respective task time. The combined network of the two models is shown in Figure 3, which consists of the tasks of both models. The set of tasks in the combined model is the union of the tasks of the individual models.

In this paper, the mixed model assembly line balancing problem with sequencing of models is considered with the objective of maximizing the average balancing efficiency of the models and minimizing the makespan of sequencing the models through the workstations.

Figure 1. Precedence network of model 1.

Figure 2. Precedence network of model 2.

Figure 3. Combined model of model 1 and model 2.

2. Literature Review

This section presents the review of literature of the mixed-model assembly line balancing problem. The contributions of the researchers are broadly classified into the following three categories:

1) Mixed model assembly line balancing problems;

2) Sequencing in mixed model assembly lines;

3) Mixed model assembly line balancing problems with model sequencing.

2.1. Mixed Model Assembly Line Balancing Problems

The literature of the mixed model assembly line balancing problem with the primary objective of balancing the line is presented under the following categories:

・ Mathematical models;

・ Branch and bound method;

・ Heuristics;

・ Genetic algorithms;

・ Simulated annealing algorithms;

・ ACO algorithm;

・ Multiple colony bees algorithm.

Mathematical Models

Gokcen and Erel [3] considered the mixed-model assemble line balancing problem and developed a goal programming model with the objective of minimizing the number of workstations. In this model, they introduced assignment constraints, precedence constraints, cycle time constraint, zoning constraints and station constraints. Gokcen and Erel [4] developed a binary integer formulation for the mixed-model assembly line balancing problem in which the number of stations is minimized for given cycle times of the models. Kara et al. [5] considered the mixed-model assembly line balancing problem with model-mix having precedence conflict and duplicate common tasks. They developed a mathematical model for this problem. Sivasankaran and Shahabudeen [6] developed a hybrid mathematical model for the single model assembly line balancing problem. In the first phase, they presented a mathematical model to design the workstations such that the balancing efficiency is maximized for a given cycle time and in the second phase, another mathematical model is presented to minimize the cycle time for the number of workstations which is obtained in the first phase. Akpinar and Baykasoglu [7] developed a mixed-integer linear mathematical programming model to minimize the number of workstations of the mixed- model assembly line balancing problem.

Mathematical models cannot solve large size problems of mixed-model assembly line balancing problems, because the number of variables and the number of constraints that can be used in the software that solves the models are limited in the form of upper limit. So, there use is limited to very small size problems.

Branch and Bound Method

Bukchin and Rabinowitch [8] made an attempt to develop a branch and bound based solution approach for the mixed-model assembly line balancing problem with the objective of minimizing the number of workstations and task duplication costs. Li and Gao [9] considered balancing manual mixed-model assembly lines using overtime work in a demand variation environment with the objective of satisfying the demand in each possible scenario with minimum labour costs paid for both normal shifts and overtime work. A lower bound on the labour costs and a heuristic to find feasible solution are proposed. Then branch, bound and remember (BB&R) algorithm is proposed to find improved solutions. Through an experiment, they found that the use of overtime work and adjustable cycle time significantly reduces the labour costs.

Brach and bound method is a curtailed enumeration method. So, it can solve relatively large size problem when compared to mathematical models. For some problems, the total number of nodes evaluated may be closer to the maximum number of nodes of the branching tree. On such occasion, the time required to solve the mixed model assembly line balancing problem with the objective of minimizing the number of workstations by this method will be too large.

Heuristics

Matanachai and Yano [10] considered the mixed-model assembly line balancing problem with the objective of reducing work overload as well as maintaining reasonable workload balance among the workstations. They developed a heuristic based on filtered beam search for this problem. Jin and Wu [11] developed a heuristic called “variance algorithm” to balance the assembly line of the mixed-model assembly line balancing n are in different units as well as with opposing direction of optimality, the second component, that is the makespan is converted into excess percentage of makespan (EPMS) and subtracted from the first component to maintain the multi-objective function as a maximization type.

In this research, an attempt has been made to develop a set of genetic algorithms to maximize the multi-objec- tive function (ηAVE − EPMS) for the mixed model assembly line balancing problem with sequencing of models

Figure 5. Comparison of actual ranges (AR) with respective least significant ranges (LSR).

and select the best amongst them through a carefully designed complete factorial experiment.

The three genetic algorithms as presented below have been developed. Along with these three genetic algorithms, the authors consider the genetic algorithm with cyclic crossover method (ALG1) developed by Sivasankaran and Shahabudeen [2] with necessary modification to handle model sequencing (ALGS1), which is called as Genetic algorithm with cyclic crossover method for task chromosome and reflection crossover method for model chromosome, for comparison.

・ Genetic algorithm with forward crossover method for task chromosome and reflection crossover method for model chromosome, ALGS2.

・ Genetic Algorithm with reverse crossover method for task chromosome and reflection crossover for model chromosome, ALGS3.

・ Genetic algorithm with cyclic crossover method for task chromosome and reflection crossover method for model chromosome and modified workstation formation, ALGS4.

These four algorithms are compared using a complete factorial experiment with four factors, viz. Problem Size (A), Algorithm (B) and Cycle Time (C). The number of levels of the factor “Problem Size (A)” is 6, viz. 40 tasks, 45 tasks, 50 tasks, 55 tasks, 60 tasks and 65 tasks. The factor “Algorithm (B)” is with two levels, viz. ALGS1, ALGS2, ALGS3 and ALGS4. The cycle time (Factor C) is set at two levels, viz. 75 sec. and 100 sec. The number of replications under each experimental combination of the four-factor experiment is 2.

Based on the results of the four factor ANOVA experiment, it is observed that the Factor A (Problem Size), Factor B (Algorithm), AB (Problem Size x Algorithm) and Factor C (Cycle Time) are having significant effect on the multi-objective function value, which is a combination of the average balancing efficiency of the models and makespan of sequencing the models at a significance level of 0.05. Other components of the ANONA model do not have effect on the multi-objective function value of the mixed model assembly line balancing problem with model sequencing at a significance level of 0.05. From this observation, it is clear that there is significant difference between the genetic algorithms (Factor C) in terms of multi-objective function values.

Since, there is significant difference between the algorithms in terms of the mean of the multi-objective function value [ηAVE − (EPMS)], the best algorithm is determined using Duncan’s multiple range test, which gives ALGS4 (Genetic algorithm with cyclic crossover method for task chromosome and reflection crossover method for model chromosome, and modified workstation formation) as the best algorithm to the mixed model assembly line balancing problem in which the multi-objective function value is maximized.

In future research, probabilistic task times for the mixed model assembly line balancing may be assumed and accordingly the results may be analyzed.

Acknowledgements

We thank the anonymous referees for their constructive suggestions, which improved the paper.

Cite this paper
Sivasankaran, P. and Shahabudeen, P. (2016) Heuristics for Mixed Model Assembly Line Balancing Problem with Sequencing. Intelligent Information Management, 8, 41-65. doi: 10.4236/iim.2016.83005.
References
[1]   Panneerselvam, R. (2012) Production and Operations Management. 3rd Edition, PHI Learning Private Ltd., New Delhi

[2]   Sivasankaran, P. and Shahabudeen, P. (2013) Genetic Algorithm for Concurrent Balancing of Mixed-Model Assembly Lines with Original Task Times of Models. Intelligent Information Management, 5, 84-92.
http://dx.doi.org/10.4236/iim.2013.53009

[3]   Gokcen, H. and Erel, E. (1997) A Goal Programming Approach to Mixed Model Assembly Line Balancing Problem. International Journal of Production Economics, 48, 177-185.

[4]   Gokcen, H. and Erel, E. (1998) Binary Integer Formulation for Mixed-Model Assembly Line Balancing Problem. Computers & Industrial Engineering, 34, 451-461.
http://dx.doi.org/10.1016/S0360-8352(97)00142-3

[5]   Kara, Y., Ozgiiven, C., Seeme, N.Y. and Chang, C.T. (2011) Multi-Objective Approaches to Balance Mixed-Model Assembly Lines for Model Mixes Having Precedence Conflicts and Duplicate Common Tasks. International Journal of Advanced Manufacturing Technology, 52, 725-737.
http://dx.doi.org/10.1007/s00170-010-2779-z

[6]   Sivasankaran, P. and Shahabudeen, P. (2013) Modelling Hybrid Single Model Assembly Line Balancing Problem. Udyog Pragati, 37, 26-36.

[7]   Akpinar, S. and Baykasoglu, A. (2014) Modelling and Solving Mixed-Model Assembly Line Balancing Problem with Setups. Part I: A Mixed Integer Programming Model. Journal of Manufacturing Systems, 33, 177-187.
http://dx.doi.org/10.1016/j.jmsy.2013.11.004

[8]   Bukchin, Y. and Rabinowitch, I. (2006) A Branch-and-Bound Based Solution Approach for the Mixed-Model Assembly Line-Balancing Problem for Minimizing Stations and Task Duplication Costs. European Journal of Operational Research, 174, 492-508.
http://dx.doi.org/10.1016/j.ejor.2005.01.055

[9]   Li, J. and Gao, J. (2014) Balancing Manual Mixed-Model Assembly Lines Using Overtime Work in a Demand Variation Environment. International Journal of Production Research, 52, 3552-3567.
http://dx.doi.org/10.1080/00207543.2013.874603

[10]   Matanachai, S. and Yano, C.A. (2001) Balancing Mixed-Model Assembly Lines to Reduce Work Overload. IIE Transactions, 33, 29-42.
http://dx.doi.org/10.1080/07408170108936804

[11]   Jin, M. and Wu, S.D. (2002) A New Heuristic Method for Mixed-Model Assembly Line Balancing Problem. Computers & Industrial Engineering, 44, 159-169.
http://dx.doi.org/10.1016/S0360-8352(02)00190-0

[12]   Hop, N.V. (2006) A Heuristics Solution for Fuzzy Mixed-Modelling Balancing Problem. European Journal of Operational Research, 168, 798-810.
http://dx.doi.org/10.1016/j.ejor.2004.07.029

[13]   Bock, S. (2008) Using Distributed Search Methods for Balancing Mixed-Model Assembly Lines in the Automotive Industry. OR Spectrum, 30, 551-578.
http://dx.doi.org/10.1007/s00291-006-0069-9

[14]   Mamun, A.A., Khaled, A.A., Ali, S.M. and Chowdhury, M.M. (2012) A Heuristic Approach for Balancing Mixed-Model Assembly Line of Type I Using Genetic Algorithm. International Journal of Production Research, 50, 5106-5116.
http://dx.doi.org/10.1080/00207543.2011.643830

[15]   Su, P., Wu, N. and Yu, Z. (2014) A Petrinet-Based Heuristic for Mixed-Model Assembly Line Balancing Problem of Type E. International Journal of Production Research, 52, 1542-1556.
http://dx.doi.org/10.1080/00207543.2013.849010

[16]   Chutima, P. and Iammi, J. (2003) Application of Genetic Algorithms in Mixed Model Assembly Line Balancing. KMUTT Research & Development Journal, 26, 1-16.

[17]   Bai, Y., Zhao, H. and Zhu, L. (2009) Mixed-Model Assembly Line Balancing Using the Hybrid Genetic Algorithm. International Conference on Measuring Technology and Mechatronics Automation, 3, 242-245.
http://dx.doi.org/10.1109/icmtma.2009.591

[18]   Senthilkumar, P. and Shahabudeen, P. (2006) GA Based Heuristic for the Open Shop Scheduling Problem. The International Journal of Advanced Manufacturing Technology, 30, 297-301.
http://dx.doi.org/10.1007/s00170-005-0057-2

[19]   Yagmahan, B. (2011) Mixed-Model Assembly Line Balancing Using a Multi-Objective Ant Colony Optimization Approach. Expert Systems with Applications, 38, 12453-12461.
http://dx.doi.org/10.1016/j.eswa.2011.04.026

[20]   Akpinar, S. and Baykasoglu, A. (2014) Modelling and Solving Mixed-Model Assembly Line Balancing Problem with Setups. Part II: A Multiple Colony Hybrid Bees Algorithm. Journal of Manufacturing Systems, 33, 445-461.
http://dx.doi.org/10.1016/j.jmsy.2014.04.001

[21]   Dar-El, E.M. and Chcuy, S. (1977) Optimal Mixed-Integer Sequencing for Balancing Assembly Lines. Omega, 5, 333-342.
http://dx.doi.org/10.1016/0305-0483(77)90115-3

[22]   Ding, F.-Y. and Cheng, L. (1993) A Simple Sequencing Algorithm for Mixed-Model Assembly Lines in Just-in-Time Productions Systems. Operations Research Letters, 13, 27-36.
http://dx.doi.org/10.1016/0167-6377(93)90081-Q

[23]   Leu, Y.-Y., Huang, P.Y. and Rusell, R.S. (1997) Using Beam Search Techniques for Sequencing Mixed-Model Assembly Lines. Annals of Operations Research, 70, 379-397.
http://dx.doi.org/10.1023/A:1018938608304

[24]   Ding, F.-Y., Zhu, J. and Sun, H. (2006) Comparing Two Weighted Approaches for Sequencing Mixed-Model Assembly Lines with Multiple Objectives. International Journal of Production Economics, 102, 108-131.
http://dx.doi.org/10.1016/j.ijpe.2005.02.007

[25]   Rabbani, M., Rahimi-Vahed, A., Javadi, B. and Tavakkoli-Moghaddam, R. (2006) A New Approach for Mixed-Model Assembly Line Sequencing. In: Waldmann, K.-H. and Stocker, U.M., Eds., Operations Research Proceedings 2006, Springer, Berlin, 169-174.

[26]   Rahimi-Vahed, A.R., Rabbani, M., Tavakkoli-Moghaddam, R., Torabi, S.A. and Jolai, F. (2007) A Multi-Objective Scatter Search for a Mixed-Model Assembly Line Sequencing Problem. Advanced Engineering Informatics, 21, 85-99.
http://dx.doi.org/10.1016/j.aei.2006.09.007

[27]   Erel, E., Gocgun, Y. and Sabuncuoglu, I. (2007) Mixed-Model Assembly Line Sequencing Using Beam Search. International Journal of Production Research, 45, 5265-5284.
http://dx.doi.org/10.1080/00207540600806497

[28]   Bautista, J. and Cano, A. (2011) Solving Mixed Model Sequencing Problem in Assembly Lines with Serial Workstations with Work Overload Minimization and Interruption Rules. European Journal of Operational Research, 210, 495-513.
http://dx.doi.org/10.1016/j.ejor.2010.10.022

[29]   Gujjula, R., Werk, S. and Giinther, H.O. (2011) A Heuristic Based on Vogel’s Approximation Method for Sequencing Mixed-Model Assembly Lines. International Journal of Production Research, 49, 6451-6468.
http://dx.doi.org/10.1080/00207543.2010.527384

[30]   Lin, D.Y. and Chu, Y.M. (2014) A Lagrangian Relaxation Approach to the Mixed-Product Assembly Line Sequencing Problem: A Case Study of Door-Lock Company in Taiwan. Applied Mathematical Modeling, 38, 4493-4511.
http://dx.doi.org/10.1016/j.apm.2014.02.029

[31]   Scholl, A., Klein, R. and Domschke, W. (1998) Pattern Based Vocabulary Building for Effectively Sequencing Mixed-Model Assembly Lines. Journal of Heuristics, 4, 359-381.
http://dx.doi.org/10.1023/A:1009613925523

[32]   Kim, Y.K., Hyun, C.J. and Kim, Y. (1996) Sequencing in Mixed Model Assembly Lines: A Genetic Algorithm Approach. Computers and Operations Research, 23, 1131-1145.
http://dx.doi.org/10.1016/S0305-0548(96)00033-0

[33]   Leu, Y.-Y., Matheson, L.A. and Rees, L.P. (1996) Sequencing Mixed-Model Assembly Lines with Genetic Algorithms. Computers and Industrial Engineering, 30, 1027-1036.
http://dx.doi.org/10.1016/0360-8352(96)00050-2

[34]   Hyun, C.J., Kim, Y. and Kim, Y.K. (1998) A Genetic Algorithm for Multiple Objective Sequencing Problems in Mixed Model Assembly Lines. Computers & Operations Research, 25, 675-690.
http://dx.doi.org/10.1016/S0305-0548(98)00026-4

[35]   Ponnambalam, S.G., Aravindan, P. and Subbu Rao, M. (2003) Genetic Algorithms for Sequencing Problems in Mixed Model Assembly Lines. Computers & Industrial Engineering, 45, 669-690.
http://dx.doi.org/10.1016/j.cie.2003.09.001

[36]   Su, P. and Lu, Y. (2007) Combining Genetic Algorithm and Simulation for the Mixed-Model Assembly Line Balancing Problem. 3rd International Conference on Natural Computation (ICNC 2007), 4, 314-318.
http://dx.doi.org/10.1109/ICNC.2007.306

[37]   Zhao, X.B. and Ohno, K. (1997) Algorithms for Sequencing Mixed Models on an Assembly Line in a JIT Production System. Computers & Industrial Engineering, 32, 47-56.
http://dx.doi.org/10.1016/S0360-8352(96)00193-3

[38]   Fattahi, P. and Salehi, M. (2009) Sequencing the Mixed-Model Assembly Line to Minimize the Total Utility and Idle Costs with Variable Launching Interval. International Journal of Advanced Manufacturing Technology, 45, 987-998.
http://dx.doi.org/10.1007/s00170-009-2020-0

[39]   Amlashi, Z.Z. and Zandieh, M. (2011) Sequencing Mixed Model Assembly Line Problem to Minimize Line Stoppages Cost by a Modified Simulated Annealing Algorithm Based on Cloud Theory. Journal of optimization in Industrial Engineering, 8, 9-18.

[40]   Rahimi-Vahed, A. and Mirzaei, A.H. (2007) A Hybrid Multi-Objective Shuffled Frog-Leaping Algorithm for a Mixed-Model Assembly Line Sequencing Problem. Computers & Industrial Engineering, 53, 642-666.
http://dx.doi.org/10.1016/j.cie.2007.06.007

[41]   Thomopoulos, N.T. (1967) Line Balancing-Sequencing for Mixed-Model Assembly. Management Science, 14, B59-B75.
http://dx.doi.org/10.1287/mnsc.14.2.B59

[42]   Merengo, C., Nava, F. and Pozzetti, A. (1999) Balancing and Sequencing Manual Mixed-Model Assembly Lines. International Journal of Production Research, 37, 2835-2860.
http://dx.doi.org/10.1080/002075499190545

[43]   Kim, Y.K. and Kim, J.Y. (2000) A Co-Evolutionary Algorithm for Balancing and Sequencing in Mixed Model Assembly Lines. Applied Intelligence, 13, 247-258.
http://dx.doi.org/10.1023/A:1026568011013

[44]   Lovgren, R.H. and Racer, M. (2000) Algorithms for Mixed-Model Sequencing with Due Date Restrictions. European Journal of Operational Research, 120, 408-422.
http://dx.doi.org/10.1016/S0377-2217(99)00091-0

[45]   Hwang, R. and Katayaa, H. (2010) Integrated Procedure of Balancing and Sequencing for Mixed-Model Assembly Lines: A Multi-Objective Evolutionary Approach. International Journal of Production Research, 48, 6417-6441.
http://dx.doi.org/10.1080/00207540903289755

[46]   Ozcan, U., Cercioglu, H., Gokcen, H. and Toklu, B. (2010) Balancing and Sequencing of Parallel Mixed-Model Assembly Lines. International Journal of Production Research, 48, 5089-5113.
http://dx.doi.org/10.1080/00207540903055735

[47]   Mosadegh, H., Zandieh, M. and Ghomi, S.M.T.F. (2012) Simultaneous Solving of Balancing and Sequencing Problems with Station-Dependant Assembly Times for Mixed-Model Assembly Lines. Applied Soft Computing, 12, 1359-1370.
http://dx.doi.org/10.1016/j.asoc.2011.11.027

[48]   Panneerselvam, R. (2016) Design and Analysis of Algorithms. 2nd Edition, PHI Learning Private Ltd., New Delhi.

[49]   Panneerselvam, R. (2012) Research Methodology. 2nd Edition, PHI Learning Private Ltd., New Delhi

[50]   Panneerselvam, R. (2012) Design and Analysis of Experiments. PHI Learning Private Limited, New Delhi.

 
 
Top