Filetype PDF | Posted on 14 Sep 2022 | 4 years ago
Authentication
digital resources
339x Filetype PDF File size 0.97 MB Source: ieomsociety.org
Proceedings of the International Conference on Industrial Engineering and Operations Management
Pilsen, Czech Republic, July 23-26, 2019
A Review Paper on Algorithms Used for Simple Assembly
Line Balancing Problems in the Automotive Industry
Salah Eddine Ayoub El Ahmadi,
Laila El Abbadi,
Moulay Taib Belghiti
National School of Applied Sciences
Ibn Tofail University
Kenitra, MOROCCO
salaheddineayoub.elahmadi@uit.ac.ma
laila.elabbadi@uit.ac.ma
Moulaytaib.belghiti@uit.ac.ma
Abstract
An assembly line is a technique used in mass production industries especially in the automotive
industry, it consists of many work stations organized along a belt transport system or another handling
equipment. The Assembly line balancing problem (ALBP) is a crucial question because it affects
directly the productivity of the whole manufacturing system. In this paper we give an up to date review
about this topic and we discuss the development of the classification of the assembly line balancing
problems (ALBP) and the procedures and algorithms that propose solutions to the ALBP in our case.
Keywords
Assembly line, Assembly line balancing problem, Productivity.
1. Introduction
The objective of the assembly line balancing problem (ALBP) is to assign multiple tasks to an ordered sequence
of workstations, such as the precedence relations are satisfied, and some measurements of effectiveness are
optimized. (E.g. to minimize the balance delay or minimize the number of work stations or the cycle time; etc.)
in order to increase the system productivity which is the ratio of output over input and it depends on several factors
such as workers skills, job methods and machines used. (Nuchsara and Nalin 2007).
Salveson was the first who published a paper about the assembly line balancing problems (ALBPs) in 1955, he
suggested a linear programming solution to this type of problems. Since then, the topic of line balancing has been
a great field of research in the industry field. However, since the ALB problem falls into the non-deterministic
polynomial-time hard (NP-hard) class of combinatorial optimization problems, it has consistently developed the
efficient algorithms for obtaining optimal solutions. Many research efforts have been directed towards the
development of algorithms or heuristics that propose solutions to the ALBPs (e.g. Kilbridge and Wester, 1961;
Helgeson and Birnie, 1961; Hoffman, 1963; Arcus, 1966; Baybars, 1986) and exact methods to solve the ALB
problems. (E.g. Jackson, 1956; Bowman, 1960; Van Assche and Herroelen, 1978; Mamoud, 1989; Hackman et
al., 1989; Sarin et al., 1999). Recently two articles by Scholl and Becker (2006); Becker and Scholl (2006) provide
the review of the exact and heuristic solution procedures for simple assembly line balancing (SALB). In this paper,
we give a review about the development of the classification of the ALBPs and a comparison of the procedures
used in the balancing of assembly lines in the automotive industry.
2. The Assembly Line
2.1 Definition
An assembly line consists of a set of work stations where some specific tasks are carried to produce a product.
Work stations are linked together by a transportation system that moves the work in process from one work station
to the other.
© IEOM Society International
1840
Proceedings of the International Conference on Industrial Engineering and Operations Management
Pilsen, Czech Republic, July 23-26, 2019
The first work station is fed by a manufacturing system and after the cycle time (the time between the entry of a
piece into the system and the entry of the following piece. It means also the time that is available for each station
to perform the assigned tasks before the product passes to the next workstation), the product at each station is
transferred to the next station, each task has a process time and each work station process tasks assigned to it
within this cycle time. At the end of each cycle, a product comes out of the last station. Tasks cannot be assigned
to stations arbitrarily. There are some technological constraints, such as tasks that should be processed in a specific
order, i.e. tasks that have some precedence relations (Bulut 2012).
In general, balancing an assembly line means to allocate the elementary operations to be carried out to different
stations, respecting several constraints and according to specific objectives.
For this purpose, the total amount of work necessary to assemble a work piece (job) is split up into a set V =
{1,…., n} of elementary operations named tasks. Performing a task j takes a task time t and requires certain
j
equipment and/or skills of workers. The total workload necessary for assembling a work piece is measured by the
sum of task times ∑t. These elements can be summarized by a precedence diagram as shown in Figure 1. It
contains a node for each task and node weights for the task times (Nuchsara and Nalin 2007).
Figure 1. Precedence diagram
2.2 Types of Assembly Lines
2.2.1 Single-Model Assembly Line
Single-Model Assembly Line is a production system that consists of several workstations aligned along a
conveyor belt. Those workstations are interconnected between them through the conveyor belt whose speed
depends on the total time of the tasks of the bottleneck station (known also as cycle time) to produce only one
model product (Sandeep and Sunil 2014).
2.2.2 Multi Model Assembly Line
In this type of lines, several products are assembled in batches. The batch production line is used in the case of
multiple different products, or family of products, which present significant differences in the production
processes. Using batch production leads to scheduling and lot-sizing problems.
2.2.3 Mixed Model Assembly Line
This type of lines includes different models of the same base product, which have identical production process
and assembled simultaneously in the same line. A typical example is a family of cars with different options: some
of them will have a sunroof, others will have ABS, etc. In this type of line, the same resources are needed to
assemble all the products (Brahim and Alain 2006).
We present in figure 2 the 3 types of assembly lines:
Figure 2. Types of assembly lines
© IEOM Society International
1841
Proceedings of the International Conference on Industrial Engineering and Operations Management
Pilsen, Czech Republic, July 23-26, 2019
2.3 Assembly line balancing in the automotive industry
In the automobile industry an assembly line starts with a bare chassis. Then Components are attached successively
as the growing assemblage moves along a conveyor. Parts are matched into subassemblies on feeder lines that
intersect the main line to deliver exterior and interior parts, engines, and other assemblies. As the units move by,
each worker along the line performs a specific task, and every part and tool is delivered to its point of use in
synchronization with the line.
The assembly plant in the automotive industry is generally composed of 2 workshops, the mechanical workshop
where the workers assemble the basic mechanical parts of the vehicle (the motor, the brakes, the battery, the
radiator, the fuel tank, the gear box…) and the saddlery workshop where they assemble the interior pieces (the
seats, the dashboard, the seatbelt, the steering wheel, the lights, …). Each workshop is composed of elementary
units, and those units are the assembly lines that we must balance in order to get higher productivity and less
workers.
3. Classification of Assembly line balancing problems
There are different kinds of problems in the assembly line balancing. One of the possible classifications is the one
proposed by (Baybars 1986), in which he divides the balancing problems to two major ones: the simple problems
(SALBP) and the general problems (GALP).
SALBP: it refers to Simple Assembly Line Balancing Problem, it’s the simple version of balancing problems,
where the objective is to minimize the cycle time for a fixed number of workstations and vice versa.
GALBP: it refers to General Assembly Line Balancing, it includes the problems that are not included in SALBP.
Those are: mixed model line balancing problem, U-shaped assembly line problems, robotic assembly line
balancing problem and multi-objective assembly line problems.
Our focus in this paper will be more on the Simple ALBPs because they are common in the industry world and
especially in the automotive companies, and the assumptions given by (Baybars 1986) for this type of problems
can be listed as follows:
(S-1) Mass-production of one homogeneous product.
(S-2) All tasks are processed in a predetermined mode (no processing alternatives exist).
(S-3) Paced line with a fixed common cycle time according to a desired output quantity.
(S-4) The line is considered to be serial with no feeder lines or parallel elements.
(S-5) The processing sequence of tasks is subject to precedence restrictions.
(S-6) Deterministic (and integral) task times t .
j
(S-7) No assignment restrictions of tasks besides precedence constraints.
(S-8) A task cannot be split among two or more stations.
(S-9) All stations are equally equipped with respect to machines and workers.
The Simple Assembly Line Balancing Problems are basically classified into SALBP 1 and SALBP 2.
The SALBP 1 is the assembly line balancing problem in which the objective is to group the tasks into a minimum
number of workstations for a given cycle time, which in turn maximizes the balancing efficiency of the assembly
line.
The ALBP 2 is the type 2 of the assembly line balancing problem, in which the tasks are grouped into a given
number of workstations such that the cycle time is minimized.
In the case that we are studying, the cycle time is given (130 seconds) and the objective is to group the tasks into
a minimum number of workstations, so the type of assembly line balancing problems studied in this article are the
Simple Assembly Line Balancing Problems SALBP1.
The simple assembly line balancing problem type 1 is a basic problem of assembly line balancing in the industry
in general. The tasks i= 1….m are defined by the task times t and their positions in the precedence graph (Tom
j
2014).
The goal is to minimize m as number of the charged stations given a fixed cycle time c.
For SALBP-1 a solution is feasible if:
i. The tasks of each station do not have a task time sum larger than c.
j
ii. No predecessor of any task j is assigned to a later station than is assigned to.
© IEOM Society International
1842
Proceedings of the International Conference on Industrial Engineering and Operations Management
Pilsen, Czech Republic, July 23-26, 2019
SALBP-1 is a NP-hard problem, it means that this type of problems is belongs to the non-deterministic
polynomial-time hard class of combinatorial optimization problems so that heuristics are essential to obtain upper
bounds for the problems. In addition to that we need lower bounds methods to assess the quality of found solutions.
The notations considered in the SALBP1 mathematical model are clarified as follows:
s workstation, s = 1, 2, …., n
m machine, m = 1, 2, …., r
w worker, w = 1, 2, …., h
k task, k = 1,2, …, j
C cycle time
As number of workstations
Bm number of machines
Xks = 1 if task k is assigned to workstation s
0 otherwise
t time required by task k
k
Ea earliest task in precedence relation
L latest task in precedence relation
a
x = 1 if earliest task a is assigned to workstation s
as
0 otherwise
The mathematical equation of SALBP-1 with resource constraints is presented in below equations.
f = ∑ (1)
1 =1
The first objective function (1) is to minimize the number of workstations for a given cycle time
∏ =1 (2)
=
Constraint (2) is an assignment constraint, which ensures that each task is assigned only once.
(3)
Constraint (3) is a cycle time constraint, which ensure that the total times in each workstation does not exceed the
given cycle time.
(4)
Constraint (4) is a precedence relation constraint, which guarantees that the precedence relation among tasks is
not violated.
(5)
Constraint (5) is a workstation constraint, which guarantees that a workstation is utilized if the task(s) is/are
assigned to it (Kamarudin 2017).
There are many exact and heuristic procedures, branch and bound procedures and dynamic programming
procedures that propose solutions for SALBP1, we will study in this paper the branch and bound procedures
because those are applicable in the assembly lines in the automobile industry.
4. Comparison between branch and bound procedures
We will compare the 4 basic branch and bound procedures:
• Johnson's (1988) FABLE
• Nourie and Venta's (1991) OptPack
© IEOM Society International
1843
no reviews yet
Please Login to review.
