 Open Access
 Total Downloads : 213
 Authors : Nessren Zamzam, Yomna Sadek, Nahid Afia, Amin ElKharbotly
 Paper ID : IJERTV4IS120081
 Volume & Issue : Volume 04, Issue 12 (December 2015)
 Published (First Online): 04122015
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
MultiManned Assembly Line Balancing using Genetic Algorithm
Nessren Zamzam, Yomna Sadek, Nahid Afia, Amin ElKharbotly
Department of Design and Production Engineering, Faculty of Engineering, Ain Shams University, Cairo, Egypt
Abstract – In this paper, the problem of balancing multi manned assembly line (MAL) is tackled. Those lines are important for the assembly of medium and large sized products such as washers, airconditioners, buses, trucks, helicopters, etc. Nowadays, by the great improvement in the technology it is become possible to produce complex products with hundreds of tasks, this make a need to reduce line length for better space utilization. In this work a hybrid Genetic Algorithm (GA) is developed to solve multimanned assembly line balancing problem. A new indicator (MPNW) is defined to determine the maximum permissible number of workers in the station. Number of stations expressing better utilization of the available area is considered as the performance criteria in this algorithm. To demonstrate the performance of the developed algorithm, it is tested on instances collected from the literature and it shows its effectiveness in solving this problem and gives a comparable results.
Keywords: Multimanned, assembly line balancing problem, genetic algorithm.
1 INTRODUCTION
Assembly is the capstone process for product realization where component, parts, and subassemblies are integrated together to form the final products.Assembly line can be categorized into onesided, twosided, and multimanned assembly lines.
One sided assembly line balancing problem is the problem of finding the best feasible solution of assigning tasks to stations. In one sided only one line is used with at most one worker in each station.
Two sided assembly line balancing problem consists of two serial lines in parallel instead of one line. Each station on the right and left side has at most one worker in which each worker do different works on the same work piece simultaneously
While multimanned assembly line (MAL) balancing problems are a new type of generalized assembly line balancing problems in which there is the possibility of assigning more than one operator to each workstation according to the product features [1]. The differences between the two sided and multi manned are: 1) number of workers in each station and 2) in multi manned it is essential to assign the task to the worker after assigning it to the station as there is more than one worker in each
station. The maximum number of worker is determined by the designer according to certain criteria as the product size, tools availability, workstation design .etc
The MAL is essential these days, especially in the assembly of largesized products, as helicopter, buses and trucks. As the advance in technology and customer demand increases the complexity and number of tasks of product increases. This makes a need to a huge manufacturing plant in case of one sided assembly line. So the use of MAL becomes important especially in these cases.Up to day, factories have produced these types of products by allowing stations having multiple workers working in the same station and balancing the line by trialanderror method [2].
Although multi manned assembly line is very common in real world, only small numbers of researchers focus on it. Dimitriadis [3] was the first one to introduce MAL problem, hisproposed heuristic is a twolevel procedure. The upper level generates all feasible assignable subsets of work elements to L workers working together on the same product and the same workstation, while the lower level proceeds to successfully allocate the work elements to each worker.The proposed approach results in shorter physical line length and production space utilization improvement, because the same number of workers can be allocated to fewer workstations.
Fattahi et al [1] proposed two approaches: (1) a mixed integer programming model for balancing the problem of assembly line with multimanned workstations, and (2) an ant colony (ACO) metaheuristic approach to efficiently solve the medium and largesize scales of this problem.The model minimizes the total number of workers on the line as the first objective and the number of opened multimanned workstations as the second one. The result showed that for a small sized problem, the mixed integer formulation can be used to obtain the optimal solution. However, as the size of the problem grows, the optimal solution may not be found in a reasonable amount of time. While for (ACO) experimental results show that it generates optimal solutions in smallsize problems and outperforms the other approaches in terms of solution quality. Also, the proposed algorithm could reach the optimal number of workers on the line for all of the test problems (medium and large size).
Kellegoz et al [2] addressed assembly line balancing problem which has parallel multimanned stations.A branch and bound algorithm called Jumper wasdeveloped,
to optimally solve the problem. Another branch and bound algorithm in the literature wasmodified to solve it and compared with Jumper. Through an analysis of the results, it is seen that Jumper showed better performance than does the latter one. However, the algorithms performance was questionable to solve big size assembly line balancing problems.
Roshani et al [4] developed simulated annealing algorithm (SA) for MALB problem in order to maximize the line efficiency, minimize the line length and minimize the smoothness index. The proposed SA algorithm is compared with the ACO in minimizing the number of workstations showed that the proposed SA algorithm is effective than ACO in minimizing the number of multimanned workstations.
Kazemi et al [5] used a costoriented approach to model the MALBP with the aim of minimizing total cost per production unit. Genetic algorithm was used to solve medium and large sized problem. The results showed that the GA performs significantly better than other algorithms and for all examples the average required space has reduced to 45.95 percent of its previous value for the traditional approach.
From the previous survey it can be found that, although MAL is important these days only few researchers focus on it. According to literature most researchers consider determining the maximum permissible number of workers per station is the duty of the designer.Kazemi et al [5] states that GA performs significantly better than other algorithms. For this reason a hybrid genetic algorithm is proposed to solve a multimanned assembly line balancing problem. The model aims to minimize the length of the line and improve the space utilization with minimum number of workers. A heuristic is proposed to assign tasks to stations and workers. A new indicator called MPNW (maximum permissible number of worker) is defined to determine the maximum number of workers permitted per station.
The rest of this paper is organized as follows: Section 2 presents description of MAL balancing problem. In section 3, the proposed indictor MPNW is defined, the developed genetic algorithm is explained in section 4. Section 5 concludes the main results, and finally section 6 is the conclusion and future work.

DESCRIPTION OF MULTI MANNED ASSEMBLY LINE BALANCING PROBLEM.
As mentioned before the main characteristic of MAL is that more than one worker can be assigned to each station. Each worker performs different work simultaneously on the same product. The number of worker in each station can be different from one station to other as seen in fig
The basic characteristic of ML can be stated as follows [2]:

More than one worker can perform different tasks simultaneously on the same product

Each worker can perform only one task at a time

Precedence constraint should not be violated when assigning tasks to workers

Number of workers can be different from one station to another

Maximum number of workers in any station cannot exceed the maximal permitted number of workers
The main advantage of MAL over simple assembly line [3]:

It can shorten the line length, i.e. space utilization improvement

It reduce the amount of throughput time and work in process (WIP)

It can lower material handling costs, since it reduces the need for workers to maneuver tools, parts, or the product.
Station 1

There might be time and tool savings since workers working together in the same multi manned workstation can share tools or fixtures
Station 1
Station 2
Station 3
Station 4
Figure 1 Multi manned assembly line



THE PROPOSED INDICTOR MPNW
According to Sanders et al [6] the recommended working area for the human hand is shown inFigure 2. The normal distance is 120 cm while the maximum distance is 150 cm. For the workers in the same station to not interfere with each other or block the movement of each other, each worker need at least distance equal to the maxdistance to work in. If we consider the max distance as the distance in which the worker can work freely. Then the MPNW will be as follows:
Figure 2 : Recommended working area for the hand of humanbien (Sanders and McCormick, 1993)

If all tasks are assembled on one side of the product
(1)

If tasks are assembled on both sides only of the products
(2)

If tasks are a assembled all round of the product
(3)
This indicator is applied for the assembly of products that require the operator to be fixed in his place and the components are reachable to his hand as electronics products (television, computersetc)
WLB
Wmax
Ps tt Ptj
of workers, W
Number
=
Cycle time
:
:
:
:
:
CT NS IDT TNS TNW
Nomenclature :
:


The proposed model
T W
Controlling parameter to give flexibility to the solution by changing UB
: Number of tasks , I =
:
Initial population (encoding stage)
In the proposed model the genetic algorithm is used to sequence the tasks into feasible order. Task based representation scheme of the chromosomes is used. Each gene in the chromosome represents the task number. Beside the random generation of the initial population six well known heuristic is added. This six wellknown heuristics are : (Baykasoglu [7]) maximum ranked positional weight, largest candidate rule, maximum number of followers, min slack value, the minimum early start, and maximum processing time divided by the upper bound of task t.
Decoding stage:
In this stage each chromosome from the encoding stage is assigned to stations according to the following heuristic:
Step 1:
Enter Input data: Cycle time (ct), Precedence matrix (Ptj), Task time (tt), Max number of workers per mated station (Wmax), Min number of worker per station (Wmin), Controlling parameter
Step 2:

Calculate the lower bound of worker (WLB) WLB = Round ( ) (4)
Number of stations Idle time
Total number of all stations Total Number of workers in all stations
: Population size
: Time of task t
: Precedence matrix , where Ptj =

Calculate upper bound of idle time (UB) UB= (5)
Worker lower bound
Maximum number of workers per mated station
Minimum number of workers per mated station
Delay time of station S at right or left side
Worker number W in station S Set of assigned tasks T to station S to worker W
Ideal time per station
Sequence of task come from genetic after mutation and crossover
Number of worker per station S Set of candidate of unassigned tasks
Total work load of worker W in station S
:
:

Number of station (NS)=1 Step 3:
From Scg start with the first element until ; if Scg = go to step 7
:
Wmin
Step 4:
:
:
WWS
:
Dtsr/l

Assign task t to its side to the worker which its TWLws + tt& FTPws + if task t cant be assigned to any worker go to step 6
:
:
ITs Scg

If more than worker fulfill this condition assign the task to the worker that has min delay time (Dt)
Dt = start time of task t end time of task j
:
:
ScUA

If more than worker has equal Dt choose the worker that will start it first (worker with min TWL)
TWLWS :

If more than worker has min TWL choose worker randomly

Update Ptj
Step 5:
Calculate average idle time per station (ITs)
ITs (6)
If ITs> UB and Ws> Wmin cancel one worker at a time and rebalance the problem until ITs
Step 6:
Open new station with NS=NS+1 then go to step 3 Step 7:
End
Fitness function
After decoding stage, each chromosome is evaluated using fitness function, according to the fitness value, the chromosome is selected for the next generation or replaced. The fitness function is derived from the objective function and used in successive genetic operation. The developed GA employs the functions given in Eq (6, and 7) as the fitness function. This function evaluates the number of workers and thenumber of stations.
(7)
(8)
Genetic algorithm operators
In the proposed model the reminder selection of Matlab Â®, two point cross over technique proposed by Leu et al. [8], and scramble mutationare used as genetic operators.Values are listed in Table 1.
Table 1 Parameters of genetic operators
Parameter
problems
Population size (Ps)
20
Crossover rate (Rc)
0.8
Mutation rate (Rm)
0.2
Elite (e)
2
Stopping criteria
Several stopping conditions can be applied for the GA. In the developed GA the stopping condition is reaching a determined number of generations as given inTable 1.


RESULTS
In order to examine the performance of the proposed model, the proposed algorithm was applied to solve 62 instances collected from Talbot et al [9] known as Talbot data set.Five small size problems, proposed by Merten [10], Bowman [11],Jaeschke [12], Jackson [13], and Mansoor [14], four medium size,presented by Mitchell [15], Heskia [16], Sawyer [17], Kilbridge andWester [18], and three largesized problems, presented byTonge [19] and Arcus [20].Table 2 shows the comparison of the results of the proposed algorithm with similar studies from the literature. This studies are:Group forming method (GM) which proposed by Dimitriadis [3]. Ant colony optimization (ACO) is proposed by Fattahi et al [1], and Roshani et al [4] used simulated annealing. Two solution evaluation criteria are considered which are: the numbers of stations (NS), and the number of workers (NW)
From Table 2it can be seen that the proposed algorithm is capable of balancing efficiently the multimanned assembly line balancing problem. The proposed model could find optimum solution in 60 instances out of 62. The results show also the advantage of MAL balaning problem over SALBP as it saves from 25 % to 50 % of the line length, which means better utilization of the available area, lower cost of fixtures and less workers movement. The proposed model gives better space saving than the similar studies from the literaturein 10 instances. This proves the effectiveness of adding wellknown heuristic to the random run of the initial population.

CONCLUSION
In this paper multimanned assembly line balancing problem (MALPB) is addressed in order to minimize the line length and the number of workers. Although MAL is essential as it make better usage of the available area especially for large products as cars, trucks and helicopter only few literatures was concerned with it.
A new indicator called MPNW is defined. It determines the maximum permissible number of workers per station. The designers can use it to state if the product can overloaded more than one worker or not and how many workers can be assigned to it.
The developed GA is compared to the similar studies in the literature and it is foundthat the proposed algorithm could find optimum solution (lower bound of number of workers) in 97 % of the all test problems under consideration. This prove the effectiveness of the proposed hybrid genetic algorithm and the proposed heuristic in solving the problem of MALPB.
The results emphasis the advantage of MAL over simple assembly line, as it saves from 25 to 50% of the total line length, this means better utilization of the available area, lower cost of fixtures and less workers movement.
Table 2Comparison of the resultwith the bench mark problem
Author 
CT 
LB (NW) 
GM 
ACO 
SA 
Prop.GA 

NW 
NS 
NW 
NS 
NW 
NS 
NW 
NS 
% area saving 

Merten (7) 
6 
6 
6 
6 
6 
3 
6 
3 
6 
3 
50 
7 
5 
5 
5 
5 
3 
5 
3 
5 
3 
40 

8 
5 
5 
5 
5 
3 
5 
3 
5 
3 
40 

10 
3 
3 
3 
3 
3 
3 
3 
4 
3 
0 

15 
2 
2 
2 
2 
2 
2 
2 
2 
2 
50 

18 
2 
2 
2 
2 
1 
2 
1 
2 
1 
0 

Bowman(8) 
17 
5 
– 
– 
5 
5 
5 
5 
5 
5 
0 
20 
5 
5 
5 
– 
– 
5 
4 
5 
4 
20 

21 
5 
– 
– 
5 
4 
5 
4 
5 
4 
0 

24 
4 
– 
– 
4 
4 
4 
4 
4 
4 
0 

28 
3 
– 
– 
3 
2 
3 
2 
3 
2 
33 

31 
3 
– 
– 
3 
2 
3 
2 
3 
2 
33 

Jaeschke(9) 
6 
8 
8 
8 
8 
6 
8 
6 
8 
5 
38 
7 
7 
7 
7 
7 
6 
7 
6 
7 
5 
29 

8 
6 
6 
6 
6 
5 
6 
5 
6 
5 
17 

10 
4 
4 
4 
4 
4 
4 
4 
4 
4 
0 

18 
3 
3 
3 
3 
2 
3 
2 
3 
2 
33 

Jackson(11) 
7 
8 
8 
7 
8 
6 
8 
6 
9 
5 
38 
8 
6 
33 

9 
6 
6 
5 
6 
4 
6 
4 
6 
4 
20 

10 
5 
6 
6 
5 
4 
5 
4 
5 
4 
25 

13 
4 
4 
4 
4 
3 
4 
3 
4 
3 
25 

14 
4 
4 
4 
4 
3 
4 
3 
4 
3 
33 

21 
3 
3 
3 
3 
2 
3 
2 
3 
2 

Mansor(11) 
45 
5 
– 
– 
5 
3 
5 
3 
5 
3 
40 
54 
4 
– 
– 
4 
3 
4 
3 
4 
3 
25 

63 
3 
– 
– 
3 
2 
3 
2 
3 
2 
33 

72 
3 
– 
– 
3 
2 
3 
2 
3 
2 
33 

81 
3 
– 
– 
3 
2 
3 
2 
3 
2 
33 

Mitchell(21) 
14 
8 
9 
9 
8 
7 
8 
7 
8 
7 
13 
15 
8 
8 
8 
8 
7 
8 
7 
8 
7 
13 

21 
5 
5 
5 
5 
5 
5 
5 
6 
4 
20 

5 
5 
0 

26 
5 
5 
5 
5 
4 
5 
4 
5 
4 
20 

35 
3 
3 
3 
3 
3 
3 
3 
3 
3 
50 

39 
3 
3 
3 
3 
2 
3 
2 
3 
2 
33 

Heskia(28) 
138 
8 
8 
6 
8 
5 
8 
5 
8 
4 
50 
205 
5 
6 
6 
5 
3 
5 
3 
5 
3 
40 

216 
5 
5 
4 
5 
3 
5 
3 
5 
3 
40 

256 
4 
5 
5 
4 
3 
4 
3 
4 
3 
25 

324 
4 
4 
3 
4 
2 
4 
2 
4 
2 
50 

342 
3 
3 
3 
3 
2 
3 
2 
3 
2 
33 

Kilbridge(45) 
57 
10 
10 
8 
10 
6 
10 
6 
10 
5 
50 
79 
7 
7 
6 
7 
5 
7 
5 
8 
4 
43 

7 
5 
29 

92 
6 
6 
5 
6 
4 
6 
4 
7 
4 
33 

110 
6 
6 
5 
6 
3 
6 
3 
6 
3 
50 

138 
4 
4 
4 
4 
3 
4 
3 
4 
3 
25 

184 
3 
3 
3 
3 
2 
3 
2 
3 
2 
33 

Tonge(70) 
176 
21 
22 
21 
21 
20 
21 
19 
21 
14 
33 
364 
10 
10 
9 
10 
7 
10 
7 
10 
5 
50 

410 
9 
9 
7 
9 
6 
9 
5 
9 
4 
56 

468 
8 
8 
7 
8 
4 
8 
4 
8 
4 
50 

527 
7 
7 
7 
7 
4 
7 
4 
7 
4 
43 
Arcus(83) 
5048 
16 
16 
16 
16 
11 
16 
11 
16 
11 
31 
5853 
14 
14 
13 
14 
10 
14 
9 
14 
10 
29 

6842 
12 
12 
10 
12 
8 
12 
8 
12 
8 
33 

7571 
11 
11 
11 
11 
7 
11 
7 
11 
7 
36 

8412 
10 
10 
10 
10 
6 
10 
6 
10 
6 
40 

8998 
9 
9 
8 
9 
6 
9 
6 
9 
6 
33 

10816 
8 
8 
8 
8 
5 
8 
5 
8 
6 
25 

Arcus(111) 
5755 
27 
27 
24 
27 
20 
27 
21 
27 
14 
48 
8847 
18 
18 
18 
18 
12 
18 
12 
18 
12 
33 

10027 
16 
16 
15 
16 
10 
16 
11 
16 
10 
38 

10743 
15 
15 
14 
15 
10 
15 
10 
15 
10 
33 

11378 
14 
14 
9 
14 
9 
14 
9 
14 
7 
50 

17067 
9 
9 
7 
9 
6 
9 
6 
9 
5 
44 
REFRENCES

Fattahi P, Roshani A, Roshani A. A mathematical model and ant colony algorithm for multimanned assembly line balancing problem. International Journal of Advanced Manufacturing Technology, 2011, 53:363378

Kellegoz T., Toklu B. An efficient branch and bound algorithm for assembly line balancing problems with parallel multimanned workstations. Computers & Operations Research, 2012, 39; 33443360

Dimitriadis SG. Assembly line balancing and group working: a heuristic procedure for workers groups operating on the same product and work station. Computers & Operations Research, 2006, 33; 27572774.

Roshani A.,Roshani A.,Roshani A.; Salehi M., Esfandyari A. A simulated annealing algorithm for multimanned assembly line balancing problem, Journal of Manufacturing Systems, 2013,32; 238 247, 435440

Kazemi A., Sedighi A.A Costoriented model for multi manned assembly line balancing problem, Journal of Optimization in Industrial Engineering, 2013, 13; 1325

Sanders M.S., McCormick J., Human Factors in Engineering and Design, McGraw Hill International.1992

Baykasoglu, A., Dereli, T. Twosided assembly line balancing using antcolony based heuristic. International Journal of Advanced Manufacturing Technology, 2008, 36, 582588

Leu, Y.Y., Matheson, L.A., Rees, L.P. Assembly line balancing using genetic algorithms with heuristic generated initial populations and multiple criteria. Decision Sciences, 1994, 15; 581606.

Talbot FB, Patterson JH. An integer programming algorithm with networkcuts solving the assembly line balancing problem. Management Science 1984; 30:859.

Merten P. Assembly line balancing by partial enumeration. Ablauf und Planungsforschung 1967; 8:42933.

Bowman EH. Assembly line balancing by linear programming. Operations Research 1960; 8(3):3859.

Jaeschke G. Eine allgemaine Methode Zur Losung Kombinatoriiicher Probleme. Ablauf und planungforschung 1964; 5:13353.

Jackson JR. A computing procedure for a line balancing problem. Management Science 1956; 2(3):26172.

Mansoor EM. Assembly line balancingan improvement on the ranked positional weight technique. Journal of Industrial Engineering 1964; 15:737.

Mitchell J. A computational procedure for balancing zoned assembly lines. Research report 6948011R3. Pittsburgh: Westinghouse Research Laboratories; 1957.

Heskiaoff H. A heuristic method for balancing assembly lines. Western Electric Engineering 1968; 12(3):916.

Sawyer JFH. Line balancing. Washington, DC: Machinery and Allied Products Institute; 1970.

Kilbridge MD, Wester L. A heuristic method of assembly line balancing. Journalof Industrial Engineering 1961; 12(4):2928.

Tonge FM. A heuristic program of assembly line balancing. Englewood Cliffs: PrenticeHall; 1961.

Arcus AL. An analysis of a computer method of sequencing assembly line operations.PhD dissertation, University of California; 1963.