Received 13 March 2016; accepted 28 May 2016; published 31 May 2016
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  .
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  .
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.
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  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;
・ Genetic algorithms;
・ Simulated annealing algorithms;
・ ACO algorithm;
・ Multiple colony bees algorithm.
Gokcen and Erel  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  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.  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  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  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  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  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.
Matanachai and Yano  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  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  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.
We thank the anonymous referees for their constructive suggestions, which improved the paper.