Copyright © 2002 IFAC

15th Triennial World Congress, Barcelona, Spain

www.elsevier.com/locate/ifac

ASSEMBLY LINE DESIGN: A SURVEY

Brahim Rekiek*, Alain Delchambre*,

Alexandre Dolgui** and Antoneta Bratcu**

* CAD/CAM Department
Université libre de Bruxelles
Av. F. D. Roosevelt 50, CP 165/14
B -1050 Brussels, Belgium
Email: [email protected], [email protected]

** Industrial Engineering Department

University of Technology of Troyes
12, rue Marie Curie B.P. 2060
10010 TROYES Cedex France
Email: [email protected]

Abstract: The problem of optimal design of the assembly lines is considered. The paper
is especially focused on the line balancing and resource planning step for the
preliminary design stage. A survey of existing methods and software tools are given.
Copyright © 2002 IFAC

Keywords: Manufacturing systems, Assembly, Design, Optimisation.

1. INTRODUCTION the most interesting performance index is stations

workload’s balancing.
Assembly line are the most commonly used method
in mass production environments because they This paper is dedicated to works on the assembly line
enable assembly of complex products by workers design, especially the line balancing and the resource
with limited training. The main objective of assembly planning. It gives a brief description of the methods
systems designers is to increase the efficiency of the applied to the assembly line design problems: exact
line by maximising the ratio between throughput and methods, heuristics, metaheuristics, etc.
required costs. Thus, assembly line design is a
problem of considerable industrial importance.
2. SIMPLE-PRODUCT LINE
Each company taking the decision that assembly is a
strategic core activity, is faced with the question of Lucertini (Lucertini, 1998) has shown that despite
how to utilise and develop the assembly system in the hundreds of works on assembly line design, little
most efficient way in order to become successful. number of companies use published techniques to
The assembly activities performed within the balance their lines. One of the reasons is that the
assembly system not only determine the final quality models usually adopted to solve the problem suffer
of the products, but also affect time-to-market, of a substantial loss of information. In fact, little
delivery, etc. Emphasising the way in which an work has been done to model the full range of
assembly system is designed will, therefore, control practical considerations in assembly line design.
its efficiency and quality. For manual assembly line Most of the time, line balancing methods tackle

155
linear assembly line, without confluence of or 2.2. Precedence constraints
separation into sub-lines. The common performance
indices are the cycle time and the number of stations, Precedence graph generation. An ALB problem can
whereas other factors may also heavily affect the be presented as an optimally partitioning the
system performances. Some of these, such as traffic precedence graph. Works dedicated to the systematic
problems, station congestion and transportation generation of the precedence graphs are not so many.
network are often considered to be marginal in the Having conceived LEGA, a powerful software for
design stage of the assembly line. An introduction to obtaining the set of all the assembly trees (sequences)
optimal approaches of the assembly line balancing for a given product (Henrioud and Bourjault, 1991),
(ALB) problem and its varieties can be found in researchers from LAB (Besançon, France) intended
(Baybars, 1986) and (Scholl, 1999). to give a method of connection between this set and
the corresponding precedence graph(s). Thesis of
Chen (1996) and of Bratcu (2001) concern the
2.1. Bin Packing approach systematic generation of the set of precedence graphs
equivalent to a given set of assembly sequences.
The ALB problem usually refers to single product
assembly line. The simplest version of the problem is More recent works have focused on deducing the
the well-known bin packing problem (BPP), where precedence graphs in the multiproduct case (for a
the aim is to pack uni-dimensional ‘objects’ of family of products). The method proposed by
various sizes into as few identical ‘containers’ of a Naphade et al. (1999a, 1999b), consisting in the
given capacity as possible. Assuming that the generation of all the precedence graphs starting from
durations of the tasks to be performed are fixed, they a given set of precedence constraints – failed in
can be taken for the unique dimension of the treating the disjunctive constraints, as it could
‘objects’. Then, casting the cycle time as the capacity produce cyclic graphs. De Lit (2000) proposed the
of the bins, the problem becomes how to distribute improvement of this method, by constructing a tree
operations among stations in such a way that no of all possible solutions, by successively adding
station overflows the cycle time and a minimum precedence constraints.
number of stations is used. Note however that this
simple formulation does not take into account the Optimisation. Salveson (1955) was the first to
precedence constraints between operations, which empirically address the ALB problem. He described
amounts to assume that a product can be assembled it as a set of precedence constraints between tasks
by any succession of operations. Fitted with acyclic that must be adhered to. Salveson formulated the
precedence constraints (Sacerdoti, 1977), the BPP SALB problem as a linear programming problem
becomes the simple assembly line balancing problem including all possible combination of station
(SALB). assignments. His model, by definition, can result in
splitting tasks and may generate infeasible solutions.
Two versions of this problem are known (Scholl, Bowman (1960) was the first to provide a ‘non-
1999): divisibility’ constraint, by changing the linear
programming formulation to a zero-one integer
SALBP-1 consists to assign tasks to stations so that programming. Due to the high number of variables
the number of stations is minimised for a given the method requires, even for small problems, the
production rate. work of both Salveson and Bowman is impractical to
find optimal solutions.
SALBP-2 aims maximising the production rate, or
equivalently, minimising the sum of the idle times for The SALBP can be also represented by a tree in
a given number of stations. which each path corresponds to a feasible solution
with each arc representing a station. Jackson (1956)
Wee and Magazine (1982) showed that SALBP-1 is was the first to propose an algorithm for SALBP-1
NP-hard since it is a special case of the BPP which is using the notion of a tree. A station is termed
known to be NP-hard. The authors proposed to solve maximal if no task can be assigned to it without
the problem by means of the generalised bin packing violating the precedence and the cycle time
heuristics. A B&B method similar to the one used for constraints. The method starts by generating all
the BPP is used. The authors also proposed feasible assignments to the first station (one of these
techniques used in the BPP like the first-fit- feasible assignments will obviously be part of the
decreasing (FFD) rule and the immediate-update optimal solution). Then it generates all feasible
FFD (IUFFD) to the ALBP. In the FFD rule method, assignments to the second station, given the first
the tasks are listed in a non-increasing order of station assignments. Then for each first-second
process time. In the case of IUFFD, the set of station combination, all feasible solutions are
available tasks is immediately updated and arranged constructed for the third station, etc.
in non-increasing order of process time. In general,
these two heuristics give good results. The process is repeated, each time adding one
station. Jackson uses dominance arguments to
eliminate inferior feasible assignments: after

156
generating all feasible assignments, these sets are precedence constraints applies equally well to the
compared to eliminate subsets that contain exactly hybrid GGA of (Falkenauer, 1996).
the same tasks as other subsets and to eliminate the
dominated subsets. A set is said to be dominated if it 2.3. Process time
contains fewer tasks than another subset and does not
contain any tasks that are not also in the other subset. The task process time is an essential parameter in the
Jackson’s method does not require the generation of assembly line balancing. Indeed, depending on the
all feasible sequences, but still uses exhaustive search nature of tasks and the skills of operators or the
of all remaining possibilities. reliability of the dedicated machine or robot, the
operation time may vary. Simple tasks may have a
Agnetis (1997) addressed the problem of assigning small process time variance, while complex and
and sequencing tasks to stations with the objective of unreliable tasks may have high varying execution
minimising the inventory costs or the completion times. In the case of human workers, factors such as
time of a set of identical jobs. They consider the skills, motivation, communication among the group,
standard (tasks and their pre-processing tasks are etc., have a great influence on the whole assembly
grouped on the same station) and the look-ahead line. The following situations may arise.
(tasks and their pre-processing tasks are not
necessarily grouped on the same station) assignment Deterministic time. In the case of manual assembly
policies. Three types of sequencing policies are line, the task time will stay constant only in case of
proposed where the main difference is the order in highly qualified and motivated workers. Modern
which the tasks assigned to a station are executed. machines and robots are able to work permanently at
The method is limited to a single product and it is a constant speed. The use of deterministic times is
based on the dynamic programming technique. always justified if the expected process time
variability is sufficiently small (this happens case of
Shtub (1990) pointed out the gap existing between simple and well defined tasks).
literature dealing with the ALB problem and
technical documentation used by engineers to Pinto et al. (1983) discussed processing alternatives
describe assembly operations. Comparing the in a manual assembly line as an extension of SALB
precedence graph to the assembly chart, it is obvious by relaxing the assumption that all stations are
that precedence graph which presents tasks by their identical. Each processing alternative was related to a
times and precedence relations does not fully given set of tasks. The problem was to decide which
describes the relations between a task and the alternative (from the existing ones) to use in order to
subassemblies on which this task is performed. An shorten the task duration for a given total cost. Since
ALB method based only on precedence graph is the line is manual, each task may be performed at any
likely to generate solutions that minimise idle time station. The authors proposed an integer
by loading each station with tasks performed on programming formulation of the problem. Their
several subassemblies. Such solutions are in solution procedure consisted of a B&B algorithm in
contradiction with the very basic principles of which a SALB problem is solved in every node of
improving work methods and enriching employee the tree. Therefore, this method may be used only for
jobs. The author proposed two ways to deal with the a small number of possible processing alternatives.
relationship between a task and the subassemblies on This study presented the interesting advantage of
which the task is performed. The first approach aims working on a set of precedence constraints instead of
to minimise the number of subassemblies handled by a fixed sequence.
each station. The second approach aims to constraint
the number of sub-assemblies by each station. The Stochastic time. In automated flow line-production
method is applied to SALBP-1 and SALBP-2. varying production rates may result from machine
breakdowns (Rekiek, 1998). To incorporate the
On the evolutionary algorithm side, to our process time variability (manual or automated line),
knowledge, the first attempt was by Falkenauer and operation time may be modified by adding the
Delchambre (1992) who used a grouping genetic stochastic component reflecting the MTBF (mean
algorithm (GGA). The authors generalised their bin time before failure) and the MTTR (mean time to
packing GGA to obtain a fast algorithm supplying repair). When dealing with manual assembly line, the
high-quality approximated solutions of the ALB process time variability may result from the task
problem. One advantage of their method was its complexity, skills level and motivation of the worker,
ability to handle problems with sparse, even empty etc.
precedence constraints, thanks to its bin packing
‘ancestor’. Another advantage lies with the fact that Moodie and Young (1965) presented a modified
the GA is a gradual improvement method, thus formulation of ALB problem that includes task time
giving the user the possibility when the variability. Tasks times are considered to be
computational resources allow it to extend the search independent normally distributed with known mean
and to continue to improve the currently available and variance. Their standard heuristic places tasks
solution. Note that the mechanism of complying with into stations starting with tasks having the longest
processing time. A task cannot be placed into a

157
station unless all of its immediate predecessors have radius of optimal line balance with respect to
been already assigned. The shortest time algorithm perturbations of some operation times. It is proven
places tasks into stations according to the shortest the necessary and sufficient conditions for stability of
processing time. an optimal line balance. The authors present upper
bound of stability radius of an optimal line balance. It
Suresh and Sahu (1994) developed a simulated should be noted that all these conditions may be
annealing heuristic for the ALB problem. They tested in polynomial time, which is important for real
considered the problem of stochastic task durations. assembly lines with a large number of operations.
They only considered single objective problems.
Their aim was to minimise the smoothness index Hidden times. In the case of automated stations, the
introduced in (Moodie and Young, 1965). The global duration of a ‘complex’ operation is not
smoothness index intends to distribute work among always the sum of the operating times of every
stations as evenly as possible equipment in the group. A hidden time represents
McMullen and Frazier (1998) presented a ‘simulated parts of the operation that can be executed at the
annealing’ (SA) method to address the ALB with same time than other tasks belonging to the same
multiple objectives. Two kind of objectives were station (Pellichero, 1999).
used: the single and the composite objectives. Three
single objectives which are: (1) minimise the design Minzu and Henrioud (1997) presented a general
cost associated with both labour requirement and algorithm for the stations determination, for mono-
equipment requirement, (2) minimise the smoothness variant products. It was based on the use of a so-
index which intended to distribute work into the called assembly graph, which combines the
station as evenly as possible, and (3) minimise the advantages of the assembly tree and the precedence
probability of lateness to deal with the stochastic graph, i.e. it combines the precedence constraints
nature of task durations. They also introduced three information with geometrical information like the
composite objectives which are expressed as the relative orientations of the components. A method of
weighted sum of the first and the third objective. tasks-to-equipment assignment based on this graph
Different weights were attributed to objectives to lay was proposed, as well as the operative sequences for
stress on the favourite criteria. The choice of relative the equipment and the computation of the process-
weights used for the different composite objectives time of a station. These methods are very interesting,
was quite arbitrary–the approach was very over- especially for the evaluation of the process time of a
fitted. The authors pointed out the difficulty to deal station which allows taking into account the hidden
with the multiple objective nature of the problem times, the operators moving, and the setup time. The
using the weighted sum approach. authors used the ‘constraint propagation’ method
embedded in the ‘Prolog’ language and a
Suresh (1996) used a GA to solve the single model backtracking approach. A depth-first ‘backtracking’
stochastic version of ALBP. A modified GA, method was used during the tasks-to-station phase.
working with two populations (one allowing However, two drawbacks can be mentioned for these
infeasible solutions), and exchange of specimens at methods. The first one was that they did not take cost
regular intervals, is proposed for handling irregular and availability factors into account. The second
search spaces, i.e. the unfeasibility problem due to drawback of these methods, already mentioned in
precedence relations. The authors claimed that a (Petit, 1999), was that they had not been linked to an
population of feasible solutions would lead to a equipment database and were not really considering
fragmented search space, thus increasing probability the technical station design.
of getting trapped in a local minimum. Infeasible
solutions can be allowed in the population only if the Dynamic time. In case of human workers, systematic
genetic operators can lead to feasible solutions from reductions are possible due to learning effects or
infeasible ones. Some solutions are exchanged at successive improvements of the production process.
regular intervals between the two populations; the Thus the manual lines have to be balanced on
exchanged solutions have the same rank of fitness average, the accent must not be highly put on the
value in their own populations. The results of the process time. The equal piles philosophy is well
experiments indicated that the GA working with two suited for such lines (Rekiek et al., 1999, Rekiek
populations can give better results than the GA with 2000).
only feasible population.
Bartholdi and Eisenstein (1996) introduced the
Sotskov and Dolgui (2001) address the SALB-1 concept of ‘operation of bucket brigades’ for manual
~ line, used for example in the automotive industry. It
problem. Subset V of set V of all operations works as follows: each worker carries a task towards
includes manual operations, for which it is hard or completion; when the last worker finishes his product
even impossible to fix processing time for the whole he sends it off and then walks back upstream to take
life cycle of the assembly line. It is assumed that if over the work of his predecessor, who walks back
~
j ∈ V , then given operation time tj can be different and takes over the work of his predecessor and so on.
for different cycles of production process. They In such a configuration the workers play the role of
introduced the notions of stability ball and stability the buffers, by supporting the variability of the

158
operating times (due to stochastic phenomena or Gustavson (1986) developed heuristic methods for
differences between the operations according to the solving both the single and multiple product
variants). equipment selection problem. The author proposed
an alternative to avoid the problem of the non-serial
The main advantage of this kind of lines is the self- line layouts. These heuristics were also based on a
balancing: they can be configured to spontaneously fixed assembly sequence with the inconveniences
maintain the optimal production rate. It is sufficient already mentioned above. Of course, being heuristics,
to place the workers from slowest to fastest in the these methods cannot guarantee that an optimal
sense of products advancing. A simulation study of solution will be found.
such lines is reported by Bratcu and Mînzu (1999).
The same authors have shown that bucket brigades Graves and Holmes (1988) considered the design
can be regarded as hybrid dynamic systems (with problem with several equipment alternatives, when
autonomous switching and autonomous jumps), multi-products are assembled on the same line. They
whose stability properties are related to the property assumed a complete ordering of tasks of the same
of self-balancing (Bratcu, 2001; Bratcu and Mînzu, product and large similarities among different
2001). products. These assumptions resulted in a relatively
small number of candidate stations and therefore
simplified the problem considerably. The method
2.4. Equipment selection
seeks to assign tasks to stations and selects
equipments for each of them. It aims to minimise the
Most of the research on balancing deals with the so-
total cost of the assembly line and it is composed of
called SALB problems in which no alternative
two steps. The first step consists in enumerating all
equipments are considered. That is, each task’s
candidate stations for the system and selecting the
process time is fixed, and the aim is to determine the
least-cost resource type for each candidate station.
sets of tasks to be performed on each station. With
The second step consists in finding the least-cost
respect to more than one type of equipment, there are
assembly system. For this purpose, a graph in which
relatively few studies that address this problem. The
each candidate station corresponds to an arc is used,
problem is known as the Resource planning (RP).
the length of the arc being proportional to the cost of
The SALB problem is proven to be a NP-Hard
the station. The least-cost assembly system is then
problem, by the way the RP problem is NP-Hard as
found by solving a shortest-path problem in the
well.
network of feasible stations. They addressed this
problem, using a method similar to the one of
Graves and Withney (1979), in one of the first works
(Gutjahr, 1964). Their algorithm enumerates all
on the field, presented a method for the single
feasible stations, selects the best equipment for each,
product equipment selection problem. The approach
and then chooses the best set of stations. The method
was based on linear programming techniques and
guarantees the feasibility of the layout by restricting
solved by a B&B procedure. The method did not deal
the system to a linear floor layout. However, given
with precedence constraints, rather a sequence, and
the implicit enumeration of all possible stations, the
permitted non-serial line layouts in which an
method is impractical for large problem instances.
assembly unit visits more than once a given station.
The goal was to select equipment and make task-
Falkenauer (1995) proposed a genetic algorithm for
assignment so as to minimise the sum of fixed and
ALB with ‘resource dependant tasks times’ algorithm
variable costs.
based on a GGA and a B&B algorithm. The method
was able to supply a well balanced and cheap
Graves and Lamar (1983) extended the work of
assembly line. The minimal and maximal number of
Graves and Withney (1979) and developed an integer
stations was computed by solving the classical ALB
programming cost-based model to the automated
problem with respectively the fastest and slower
system design problem. A column generation
resource assigned to all tasks. The GGA distributed
procedure was applied to solve the integer
the tasks onto stations, while the B&B algorithm
formulation of the problem. Their aim was to
selected the optimal resource for each station.
determine the type and the number of stations, and
the operations assigned to these stations. The
Sysoev and Dolgui (1999) present an equipment
approach used a fixed assembly sequence, which is a
selection problem as a multi-criteria decision making
first inconvenience, but their main limitation, as in
problem. To solve it, the authors propose an iterative
(Graves and Withney, 1979), was that they permitted
Pareto optimization method with heuristic procedures
non-serial line-layouts. Their model did not explicitly
of selection at each step. The convergence of this
try to balance the total workload across the stations,
method is proved and an application example is
rather the design criterion is to minimise total system
given.
costs, while satisfying a desired production rate. The
station loads were often highly unbalanced. As a
Bukchin and Tzur (2000) developed an optimal
result of allowing unrestricted floor layouts for the
method and a heuristic algorithm to design flexible
problem, the solutions found were not necessarily
assembly line when several equipment alternatives
physically feasible.

159
are available. Tasks are subject to precedence production objectives (cycle time and number of
constraints. The objective was to minimise total station) as well as worker physical constraints. The
equipment cost, given a pre-determined cycle time. method takes into account the physical requirements
They developed an exact B&B algorithm which was of tasks. The method is based on the GA and applied
capable of solving practical problems. The to the SALBP-2 where the aim is to minimise the
algorithm’s efficiency was enhanced due to the cycle time for a given number of stations. The
development of good lower bounds, as well as the authors used three search algorithms: (1) a multiple
use of dominance rules to reduce the size of the tree. rank heuristic (MRH), (2) a combinatorial GA, and
They also suggested to use a B&B based heuristic (3) a problem space GA (PSGA). The MRH is a
procedure for large problems. For large problems that combination of 81 separate heuristics that utilises
cannot be solved by the optimal algorithm, the three search methods (lower bound, upper bound and
authors developed a heuristic procedure. The binary search), three ranking criteria (rank positional
procedure’s control parameters may be chosen weight, number of successors, number of paths),
according to the size of the problem. The control three tasks assignment (forward, backward, bi-
parameter determines how many nodes of the tree directional) and three weighting factors. The
may be skipped, and therefore was responsible for sequence-oriented coding combinatorial GA assigns
the running time, for the memory requirements, as tasks to stations as the classical GA, the main
well as for the distance from optimality of the difference is the fact that the number of stations is
resulting solution. The method dealt with many fixed. Thus, the cycle time constraint is not enforced
realistic features of assembly line, unfortunately it when assigning tasks to the last station. This ensures
did not deal with the operating mode of tasks which that all tasks will be assigned. Tests let the authors to
is one of the hardest constraints of the problem. conclude that the PSGA perform better than the
MRH and the classical GA.

2.5. Additional constraints Buffers. Malakooti and Kumar (1996) used a multi-
criteria decision-aid method for ALB problems
The classical line balancing problem can be where the objectives were the number of stations, the
improved to include other factors in order to deal cycle time, the buffer size and the total cost of the
with real-world problems. Dealing with constraints operations. For the single objective ALB problem
and user’s preferences reduces the number of task- with buffers, the authors used a three steps interactive
station combination and at the same time the search method to minimise the total cost of the line. The
space of the problem. Such constraints have the same method first balanced the line using the RPW
influence on the complexity of the problem as the algorithm (Helgeson, 1961). It then looked for the
precedence constraints of the product. required buffer size using an empirical formulation.
Finally the total cost of the line is estimated. For the
In spite of the existence of many commercial multiple objective ALB problem, the authors used an
software of ‘balancing’, less than 10% of companies additive utility function based on decision maker’s
use such software. The reason is that industrial preferences (weights). They divided the whole into
balancing problems present most of the time, three simple problems: (1) minimise the number of
particularities which are not always considered by the stations when the cycle time is given, (2) minimise
standard software. Lapierre (1999) presented the the cycle time when the number of stations is given
COMSOAL algorithm (Arcus, 1965) programmed on and (3) minimise the total cost when the cycle time is
the software package Microsoft Access'97. The given and the number of stations has to be
author modified the COMSOAL algorithm in order determined. Solving the three problems for different
to deal with constraints such as the position (rear, values of the cycle time and the number of stations
front, centre, etc.) and the level (high and low) of may lead to different solutions. The best solution
tasks. Thus, the method aims to avoid grouping tasks from the efficient alternatives was chosen using a
having different levels on the same station. Tasks ‘ranking alternatives by strength of preferences’
requiring heavy equipment or parts must not be method. The attributes of the additive utility function
assigned to the same station. The approach is very were the cycle time, the number of stations, the
interesting, however, we think that the ALB problem buffer size and the total cost.
is quite difficult to be solved by a simple
‘spreadsheet’ software. We believe that the simple Dolgui et al., (2002b) consider a buffer allocation
version of the ALB is quite difficult to be solved by problem under machines breakdowns. The line
such a method. Anyway, the author recommends balancing problem is supposed resolved. So, the
using metaheuristics to deal with ALB problem. buffer allocation problem consists in determining the
buffer capacities with respect to a given optimality
Operators. Although different variations of the ALB criterion, which depends on the average production
problem have been explored by researchers (Scholl, rate of the line, the buffer acquisition and installation
1999), little concern has been given to the physical cost, the inventory cost. A genetic algorithm where
demands placed on workers when assigning tasks to the tentative solutions are evaluated with a method
stations. Carnahan et al. (1999) proposed a based on the Markov models is proposed.
methodology for the ALB considering both

160
 3. GENERALIZED PROBLEMS algorithm which is restricted to looking one layer
behind and one layer ahead in filling the stations.
3.1. Heuristic models This heuristic is easy to implement and gives good
Single product line. Since the ALB problem falls into solutions for dense and uniform graphs. The more the
the NP-hard class of combinatorial optimisation graph contains sprays, less the method yields good
problems, numerous research efforts have been balancing.
directed towards the development of computer
efficient approximation or heuristics algorithms Multiple product line (mixed/batch production).
(Ghosh, 1989). Traditionally assembly line balancing and variants
ordering (for mixed-production) have been
One of the first proposed heuristic was the ranked considered as two separate, but related problems.
positional weight (RPW) (Helgeson, 1961). The main Most of the research on assembly line sequencing
idea behind the RPW heuristic is to first assign the considers scheduling products after assembly line
tasks which have long chains of succeeding tasks. balancing. By separating the two problems, sub-
The length of the chain can be measured either by the optimal solutions are often obtained. Rekiek and
number of successor tasks, or by the sum of the task Delchambre (1998) introduce the balance for
times of the successor tasks. In the RPW method, the ordering (BFO) concept to treat both problems
sum of the task process time and the process times of simultaneously.
the successor tasks is defined as the positional weight
of the task. The tasks are ranked in descending order In (McMullen and Frazier, 1998) the trade, transfer,
of the positional weights with ties broken arbitrarily. compression as well as expansion heuristics are used
The tasks are then picked in their ranked order and as local improvements. The initial solution is based
assigned to stations if (1) all predecessors of the task upon the ‘incremental utilisation’ heuristic (Gaither,
have already been assigned and (2) the task fits in the 1996).
remaining time on the station. If a task does not fit in
the remaining time on a station it is skipped and the Lee and Johnson (1991) proposed an iterative method
next task in the ranked order is selected. If no task based on integer programming, depth-first B&B and
fits into the station, the station is closed and a new queuing network analysis. The approach allowed to
station is opened. The tasks are then scanned from deal with multiproduct assembly line. The objective
the beginning of the list and an attempt is made to was to minimise the cost of work-in-process
assign unassigned tasks to the new station. The inventory, machine investment and maintenance and
process is repeated until all tasks are assigned. Since material handling. They considered five design
the weight of an element depends on the process time factors: the number of stations, the number of parallel
of its predecessors, the algorithm tends to treat the machines, the tasks assignment, the number of pallets
elements near the end of precedence graph first. This and fixtures and finally the number of automated
procedure is quite simple, it can deal with user’s guided vehicles. The method suffered from a severe
preferences but gives good results only for simple restriction: each station consists in a single machine
problems. or in identical parallel machines.

The ‘reversed ranked positional weight’ (RRPW) is

the RPW method applied to the problem with the 3.2. Line configurations
reversed precedence constraints. After a balance is
found for the reversed problem, the problem is ‘un- Several line configurations are possible, for example:
reversed’ to get a balance solution for the original
problem. Serial line: single stations are arranged in a straight
line along a conveyor belt. Each station performs one
Kilbridge and Wester (1961) proposed a heuristic or more tasks on the partially finished product
based on the cumulative performance times. First the (Baybars, 1986; Scholl 1999).
‘layers’ are identified in the precedence graph. Tasks
with no predecessors are in the first layer. Tasks that U-Line: as a consequence of introducing the just-in-
are preceded directly by tasks in layer i are placed in time production principle it has been recognised that
layer i+1, etc. Then, it computes the time for each arranging the stations in a U-line has several
layer (sum of process time of tasks belonging to a advantages over the traditional configuration. Thus,
given layer), as well as the cumulative performance workers acquire multiple skills leading to higher
time of each layer (sum of its time and times of the motivation, improve quality of products and
layers it succeeds). Moving from the left to the right increased flexibility (Scholl, 1999).
in units of a layer, it finds the layer that just fills or
overfills the station. It begins by the first layer and go Parallel stations: with high production rates, the
in order through the remaining layers. Tasks of a longest task time sometimes exceeds the specified
given layer are assigned to a given station unless the cycle time. A common remedy is to create stations
precedence constraints will be violated or the cycle with parallel or serial posts, where two or more
time will be exceeded, otherwise they are assigned to workers perform an identical set of tasks. This
the next station and so on. The method is a search procedure reduces the average value of the task

161
duration proportionally to the number of workers on balancing for paced transfer lines with workstations
the station (McMuller and Frazier, 1998). in series and with block of parallel operations at the
workstations. The problem is to minimise a cost
Bard (1989) presented a dynamic programming associated with the number of workstations and the
algorithm for solving the ALB problem with parallel number of blocks, providing a given cycle time and
stations. Solutions represent a trade-off between the specified technological constraints. Two methods are
minimum number of stations required to achieve a developed to solve the problem. The first method is
balance and the cost of installing additional facilities. based on a transformation of the initial problem into
Both equipment cost and task cost are considered. a constrained shortest path problem (Dolgui et al.,
The algorithm takes into account the unproductive 1999, 2000a). The second method uses mixed integer
time during a cycle. programming formulations of the problem (Dolgui et
al., 2000a, 2001, 2002a). Both graph and mixed
Lee et al. (1999) presented a GA to deal with ALB programming methods are combined with some
problem with parallel stations. The GA is hybridised heuristic techniques in order to solve large-scale
with two local search procedures: the trade and problems (Dolgui et al., 2000a).
transfer heuristics. The trade procedure is used to
exchange tasks between two adjacent stations. The Robotic assembly lines. Rubinovitz and Bukchin
transfer procedure has two varieties: the expansion (1993) introduced the robotic assembly line
transfer aims to create additional stations if needed, balancing (RALB) algorithm for solving single
while the compression transfer aims to decrease the model ALB problems. The method was based on a
number of stations. The method aims to minimise the B&B algorithm and aimed to design (balance)
weighted sum of (1) the total cost of the line and (2) robotic assembly line when several robot types are
the lateness across all stations. They used the available. Their model supposed that all the
sequence-oriented representation–the tasks are equipment alternatives have an identical purchasing
sequentially listed in the order in which they are cost. The objective was to find a line balance which
assigned to the stations. This representation is clearly minimises the number of stations for a given
not grouping-oriented and leads to an inefficient production rate. Rubinovitz and Levitin (1995)
encoding. proposed a genetic algorithm for this problem.

Parallel lines: permits to decrease the failure

sensitivity and increase the flexibility of the system. 3.3. Design objectives
The use of parallel lines allows the enlargement of
the cycle time(s). Thus, the extent of labour division Depending on the line layout many objectives may
is relatively small so that only few operators are be sought after.
employed in every parallel line. These units are
organized as autonomous work teams. For SALB, Minzu and Henrioud (1997) proposed a
‘kangaroo’ algorithm (a stochastic descent method)
Süer (1998) proposed a 3-phase methodology to deal to treat the problem of assembly line with a fixed
with assembly lines having high production volume. number of stations. The stochastic descent method
The objective is to determine the number of assembly aims to minimise the maximum work content of the
lines (in parallel) with minimum total manpower. In stations, which leads to a well balanced line. The
the assembly line balancing phase, tasks are grouped computational tests proved that the ‘kangaroo’
into stations for various configurations (1-station, 2- algorithm supplies good solutions in a small number
station, …, n-station; where n is the number of tasks). of iterations.
Thereafter, the parallel station phase determines the
number of operators that should be assigned to each EPLBP: (Equal Piles for Assembly Line Balancing
station (parallel stations). The parallel lines phase Problem): warrants to obtain the desired number of
determines the number of lines and their stations, and tries to equalise the station loads
configuration with the objective of minimising the (Rekiek et al., 1999).
total number of operators.
Rachamadugu (Rachamadugu, 1991) investigated the
Workcenters: for complex products, the assembly levelling of workloads across stations which is an
system is most of the time decomposed into important problem especially in manual assembly
subsystems which are easier to manage than the lines. Indeed, uneven assignments are viewed as
entire one. The line is decomposed into several inherently unfair and usually call for some kind of
linked sub-lines (workcenters). The routing of a compensatory actions from management such as
product from one workcenter to another is fixed, differential pay. A mean absolute deviation of
according to a line flow topology. The main topology workloads criteria is used as an objective function to
of the line is not necessarily a linear one (Rekiek et distribute the workload as evenly as possible. The
al., 1999). author identified the notion of dominance between
solutions and incorporated it into an iterative
Parallel tasks (blocks). Dolgui et al. (1999, 2000a, heuristic. Given any heuristic or optimal solution to a
2001, 2002a) consider a new problem of line SALBP-1 or SALBP-2, the levelling procedure

162
reassigns tasks among the stations to smooth the optimisation problem, a special decomposition
workload across stations. It is a kind of local scheme is proposed, which is based on parametric
optimisation used after the global one. The proposed decomposition technique.
method yields better allocation of work in the case of
SALBP-1 and SALBP-2.
3.4. Simulation and Interactivity
SALBP-G: aims to minimise the sum of the idle
times with a varying production rate and a changing On the side of interactive and iterative methods,
number of stations (Scholl, 1999). Nevins and Withney (1989) presented a method
based on technical and economical considerations.
RP: find an assignment of the tasks to stations along The method helps to construct the cheapest
the line, and determine the resources to be allocated technically feasible assembly line. The method
to each task among the possible ones for that task presented the advantage of being complete, but could
(Rekiek et al., 1999). Many objectives can be found become very time consuming to apply if the number
in the literature: minimise total line cost, maximise of operations and the set of usable resources for each
reliability, etc. operation become too important. Another weakness
was that the assembly sequence was fixed before the
MOALBP: (multi-objective line balancing problem): application of the method. This could be too
most real world problems involve multiple restrictive and lead the system to miss the most cost-
objectives. In the assembly line problem, designers effective solutions.
deal with objectives like: line efficiency, smoothness
index (imbalance), cost, reliability, buffers, stations Praça (1999) proposed an architecture based on
space, etc. (Chow, 1990). multi-agent simulation (called SimBa). The system
helps in balancing and distributing the human
Kim et al. (Kim, 1996) developed a GA to solve resources in manual assembly line. The system is
multiple objective ALB problem. They addressed composed of a balancing and simulation modules.
several types of ALB problem. They considered the The balancing module which implements three
following objectives: (1) minimise number of heuristic rules from (Helgeson, 1961) and (Boctor,
stations; (2) minimise cycle time; (3) maximise 1995) allows the user to obtain different line
workload smoothness; (4) maximise work relatedness configurations. The simulation module is used to
(interrelated tasks are allowed to the same station as evaluate the performance of the proposed
much as possible); and (5) a multiple objective with configurations. The aim of agent design is to create
(3) and (4). The authors used a sequence-oriented programs which interact intelligently with their
coding, as well as a repair routine to deal with environment. The multi-agent system is introduced to
infeasible solutions. A set of ordering-oriented simulate the human behaviour in a given assembly
crossover and mutation operators were used. Their line.
emphasis is placed on seeking a set of diverse Pareto
optimal solutions. The multiple objective GAs seem Tsai and Yao (1993) proposed an integer
to be very promising, in contrast the encoding programming model combined with a simulation
scheme is not well suited for the grouping problem adjustment phase. The approach was used to design a
they deal with. flexible robotic assembly line which produces a
family of products. Given the work to be done at
Lee and Stecke (1996) presented an integrated design each station, the demand of each product and a
support method for flexible assembly systems. The budget constraint, the method determined the robot
utility of a multi-criteria optimisation tool is type and number of robots required in each station
underlined in that work. But one of its main along a serial robotic line. Their objective was to
weaknesses is that the optimisation was applied only minimise the standard deviation of the output rates of
to the cost while satisfying a set of constraints. all stations, which is the measure for a balanced line.

Ponnambalam et al. (1998) used the sequence- Okano (1993) proposed a generator of logical
oriented representation for a multiobjective GA expressions able to generate all feasible resource
(MO-GA). They used 14 simple heuristics (Talbot et groupings for a given sequence of assembly
al., 1986) to initialise the population and used operations. After obtaining valid combinations of
classical genetic operators to evolve solutions. The resources, a simulation tool was used to evaluate the
method aims maximising the line efficiency as well different solutions and select the best one. Since the
as the smoothness index. During the execution of the method was based on an assembly sequence, a first
MO-GA, a tentative set of Pareto optimal solutions fit heuristic method was used to group tasks, where
are stored and updated at each generation. the constraint was the cycle time calculated on the
basis of production volume. The criteria for the
In the work (Dolgui et al., 2000b) the goal function is grouping of operations and resource assignment were
to minimise the line life cycle cost per piece. The the production volume and the production cost. The
model is formulated in terms of mixed (discrete and approach was based on the risky assumption that the
non-linear) programming. For solving the

163
constraints of the problem will avoid the the assembly line design must be formulated as a
combinatorial explosion of the possible solutions set. multi-objective problem rather than to aim at
minimising the number of stations or the imbalance
between the stations. Efficient methods in Assembly
3.5. Software tools Line Balancing (ALB) and Resource Planning (RP)
should be able to deal with conflicting objectives or
A lot of software development companies try to offer take users preferences into account. They should be
the best optimisation solution for the assembly quick enough to allow the designer testing many
systems design. They are confronted with a very alternatives.
sharp concurrency fight, giving a high dynamics to
the concerned market. Starting from some basic REFERENCES
design conception – such as 3D product modelling,
multiple users, web accessible data bases, friendly Agnetis, A. and C. Arbib (1997). Concurrent
graphical interfaces and, not at least, powerful operations assignment and sequencing of
interactive simulation tools – and being fully object- particular assembly problems in flow lines.
oriented, the commercial software products offer a Annals of Operations Research, 69, 1-31.
virtual environment to assembly systems design and Arcus, A.L. (1966). COMSOAL: A computer
management. method of sequencing operations for assembly
lines. International Journal of Production
Delmia (see http://www.delmia.com) from Dassault Research, 4, 259-277.
Systems company presents ErgoFab, a modular tool Bard, J.F. (1989) Assembly line balancing with
aiming at covering all the production optimisation parallel workstations and dead time,
aspects: line balancing, cost optimisation, resource International Journal of Production Research,
planning, etc. Offering three user options – manually 27, 1005-1018.
balancing, half automatic and fully automatic Bartholdi J.J., and D.D. Eisentein, (1996). A
balancing – ErgoFab offers also simulation facilities, production line that balances itself, Operations
by either Simple++, or Dosimis-3, or Arena based Research, 44, 21-35.
integrated packages. Line balancing is started right Baybars, I. (1986). A survey of exact algorithms for
from reading the production structure, yielding the the simple assembly line balancing, Management
work plans and imposing the precedence constraints. Science, 32, 909-932.
However, this software has limited capabilities of Boctor, F.F. (1995). A multiple-rule heuristic for
working with hidden times of operations. assembly line balancing, J. of Oper. Res. Society,
46 (1), 62-69.
Some of the products use classical, well known Bowman, E.H. (1960). Assembly line balancing by
modelling concepts and optimisation algorithms – for linear programming, Operations Research, 8 (3),
example, Tecnomatix (http://www.tecnomatix.com)
385-389.
gives sequencing and line balancing optimal
Bratcu, A. and V. Mînzu (1999). A Simulation Study
solutions based upon COMSOAL. Whereas others
of Self-balancing Production Lines. In:
try to minimise the skill level required to the user:
Proceedings of the 1999 IEEE International
Simas II (http://www.cimpact.ch) works with user
Conference on Intelligent Engineering Systems
defined assembly rules; Streamline of Factory Logic
(INES ’99), pp. 165-170, Stará Lesná, Slovakia.
(http://www.factorylogic.com) uses universal
machine models. Use of recent modelling techniques Bratcu, A and V. Mînzu (2001). Modeling and
it can be noticed also as a trend: knowledge data base Analysis of Self-balancing Manufacturing Lines
based modelling (KAPES) – allowing a more as Hybrid Dynamic Systems. In: Preprints of the
accurate representation of experts experience – or 9th IFAC/IFORS/IMACS/IFIP Symposium on
Large Scale Systems: Theory and Applications
either trials to model the human behaviour
(CircuitCam, http://www.contax.co.uk). There are (LSS 2001), pp. 6-11, Bucharest, Romania.
software packages developing an iterative design Bratcu, A. (2001). Détermination systématique des
(and redesign) approach, while minimising the graphes de précédence et équilibrage des lignes
number of iterations until finding a good (and d’assemblage, Ph.D. Thesis, Université de
possibly optimal) solution (EASE, OptiLine, etc.). Franche-Comté, Besançon, France.
Bukchin, J. and M. Tzur (2000). Design of flexible
assembly line to minimize equipment cost, IIE
4. CONCLUSION Transactions, 32, 585-598.
Carnahan, B.J., M.S. Redfen and B.A. Norman
Despite the number of works on assembly line design (1999). Incorporating physical demand criteria
and balancing, academic algorithms are not used by into assembly line balancing, Pittsburgh
industrial companies. This is because, despite their University, Internal Report TR99-8.
effectiveness and the easiness of their use, they use Chen, K. (1996). Contribution à une méthode
little data and suffer on substantial loss of systématique de détermination des graphes de
information, solving fictitious rather than industrial précédence pour l’assemblage, Ph.D. Thesis,
problems. As many practical optimisation problems, Université de Franche-Comté, France.

164
Chow, W.-M. (1990). Assembly line design - Ghosh, S. and R. J. Gagnon (1989). A comprehensive
methodology and applications, Marcel Dekker, literature review and analysis of the design,
New York. balancing and scheduling of assembly systems,
De Lit, P. (2000). A comprehensive and integrated Int. J. of Prod. Res., 27, 637-670.
approach for the design of a product family and Graves, S. C. and D. E. Withney (1979). A
its assembly system, Ph.D. Thesis, Université mathematical programming procedure for
Libre de Bruxelles, Belgium. equipment selection and system evaluation in
Dolgui, A. (2001). Automated Production Line programmable assembly, In: Proceedings of the
Design (Preface for the Special Track), IEEE Decision and Control, pp. 531-536. IEEE
Management and Control of Production and Press.
Logistics: A Proceedings Volume, Pergamon, Graves, S. C. and B. W. Lamar (1983). An integer
Elsevier Science. programming procedure for assembly system
Dolgui, A., N. Guschinski, and G. Levin (1999). On design problems, Operations Research, 31(3),
Problem of Optimal Design of Transfer Lines 522-545.
with Parallel and Sequential Operations, In: Graves, S.C. and C. Holmes Redfield (1988).
Proceedings of the 7th IEEE International Equipment selection and task assignment for
Conference ETFA'99, Barcelona, vol. 1, pp. multi-product assembly system design,
329-334, IEEE Press. International Journal of Flexible Manufacturing
Dolgui, A., N. Guschinsky and G. Levin, (2000a). Systems, 1, 31-50.
Approaches to balancing of transfer line with Gustavson, R. E. (1986). Design of cost effective
block of parallel operations, Preprint N°8, 42 assembly systems, C.S. Draper Laboratory
pages. University of Technology of Troyes/ Report, N°P-2661, Cambridge.
Institute of Engineering Cybernetics, Minsk. Gutjahr, A.L. and N.K. Nemhauser (1964). An
Dolgui, A., N. Guschinski and G. Levin (2000b) algorithm for the line balancing problem,
Optimizing Parameters of Transfer Lines with Management Science, 11 (2), 308-315.
Parallel Machining, In: Proceedings of the 16th Helgeson, W. B. and D. P. Birnie (1961). Assembly
International Conference on CAD/CAM, line balancing using the ranked positional weight
Robotics and Factories of the Future, Trinidad technique, J. Ind. Engng, 12 (6), 394-398.
W.I., pp. 317-324. IEE/ISPE. Henrioud, J.-M. and A. Bourjault (1991). LEGA: A
Dolgui, A., N. Guschinski, and G. Levin (2001). 'A computer-aided generator of assembly plans. In:
Mixed Integer Program for Balancing of Computer-Aided Mechanical Assembly Planning,
Transfer Line with Grouped Operations', In: Homem de Mello and S. Lee (Ed), Chapter 8,
Proceedings of the 28th International Conference Kluwer Academic, 1991.
on Computer and Industrial Engineering, Jackson, J.R. (1956). A computing procedure for the
Florida, USA. pp. 541-547. line balancing problem. Management Science, 2,
Dolgui, A., N. Guschinski, Y. Harrath and G. Levin, 261-271.
(2002a). Une approche de programmation Kilbridge, M.D. and L. Wester (1961). A heuristic
linéaire pour la conception des lignes de method for assembly line balancing. Journal of
transfert, European Journal of Automated Industrial Engineering, 12, 292-298.
Systems (RAIRO-APII-JESA), 36, to appear Kim, Y.K., Kim Y.J. and Y. Kim (1996). Genetic
Dolgui, A., A. Ereemev, A. Kolokolov, and V. algorithms for assembly line balancing with
Sigaev, (2002b). A Genetic Algorithm for various objectives. Computers & Industrial
Allocation of Buffer Storage Capacities in Engineering, 30 (3), 397-409.
Production Line with Unreliable Machines. Lapierre, S.D. and A. Ruiz (1999). Equilibrer une
Mathematical Modelling and Algorithms, to chaîne d’assemblage avec Microsoft
appear. ACCESS97. In: Proceedings of 3rd International
Falkenauer, E. (1996). A hybrid grouping genetic Industrial Engineering Conference, pp. 357-364.
algorithm for bin packing. Journal of Heuristics, Presses Internationales Polytechnique, Montreal.
2 (1), 5-30. Lee, C.Y., M. Gen and Y. Tsujimura (1999).
Falkenauer, E. (1995). Solving equal piles with a Multicriteria assembly line balancing problem
grouping genetic algorithm, In: Proceedings of with parallel workstations using hybrid Gas. In:
the Sixth International Conference on Genetic Proceedings of EDA’99, pp. 115-122.
Algorithms (ICGA95), pp. 492-497. Morgan Lee, H.F. and R.V. Johnson (1991). A line balancing
Kaufmann Publishers, San Francisco. strategy for designing flexible assembly systems.
Falkenauer, E. and A. Delchambre (1992). A genetic Int. J. of Flexible Manuf. Systems, 3, 91-120.
algorithm for bin packing and line balancing, Lee, H.F. and K.E. Stecke (1996). An integrated
In: Proceedings of the IEEE International design support method for flexible assembly
Conference on Robotics and Automation, pp. systems, J. of Manuf. Systems, 15 (1), 13-32.
1186-1192, IEEE Computer Society Press. Lucertini, M., D. Paccearelli, and A. Pacifici (1998).
Gaither, N. (1996). Production and operations Modeling an assembly line for configuration and
management, Belmon, CA: Duxbury. flow management. Computer Integrated
Manufacturing Systems, 11 (1-2), 15-24.

165
Malakooti, B. and A. Kumar (1996). A knowledge- Rekiek, B.B. and A. Delchambre (1998). Ordering
based system for solving multi-objective varinbats and simulation in multiproduct
assembly line balancing problem, Int. J. Prod. assembly lines. In: Proceedings of VR-Mech'98,
Res., 34 (9), 2533-2552. pp. 49-54. Brussels, Belgium.
McMullen, P.R. and G.V. Frazier (1998). Using Rekiek, B., P. De Lit, F. Pellichero, F. Falkenauer
simulated annealing to solve a multiobjective and A. Delchambre (1999). Applying the equal
assembly line balancing problem with parallel piles problem to balance assembly lines. In:
stations. International Journal of Production Proceedings of ISATP'99, pp. 339-404. Porto,
Research, 36, 2717-2741. Portugal.
Minzu, V. and J-M. Henrioud (1997). Assignment Rekiek, B. (2000). Assembly line design, Ph.D.
stochastic algorithm in multi-product assembly Thesis, Université libre de Bruxelles.
lines, In: Proceedings of ISATP’97, pp. 109-114, Rubinovitz, J. and J. Bukchin (1993). RALB - A
IEEE Press. Heuristic Algorithm for Design and Balancing
Moodie, C. L. and H. H. Young (1965). A heuristic of Robotic Assembly Lines. Annals of the
method of assembly line balancing for CIRP, 42 (1), 497-500.
assumptions of constant or variable work Rubinovitz, J. and G. Levitin (1995). Genetic
element times. J. Ind. Eng., 16 (1), 23-29. Algorithms for Assembly Line Balancing,
Naphade, K. S., R. H. Storer and S. D. Wu (1999a). International Journal of Production Economics,
Graph theoretic generation of assembly plans, 41, 343-354.
Part i: Correct generation of precedence graphs, Sacerdoti, E. D. (1977). A structure for plans and
IMSE Technical Report 99T-003, Lehigh behavior. Stanford Research Institute, Elsevier
University, Bethlehem, Pennsylvania, U.S.A. North-Holland Inc.
Naphade, K. S., S. D. Wu and R. H. Storer (1999b). Salveson, M.E. (1955). The assembly line balancing
Graph theoretic generation of assembly plans, problem. J. Ind. Engng., 6 (3), 18-25.
Part ii: Problem decomposition and optimization Scholl, A. (1999). Balancing and sequencing of
algorithms, IMSE Technical Report 99T-004, assembly lines. Heidelberg Physica.
Lehigh University, Pennsylvania, U.S.A. Shtub, A. and E.M. Dar El (1990). An assembly chart
Nevins, J.L. and D. E. Withney (1989). Concurent oriented assembly line balancing approach. Int.
design of product and process, Mc Graw-Hill, J. of Prod. Res., 28 (6), 1137-1151.
New-York. Sotskov, Yu. N. and A. Dolgui (2001). Stability
Okano, A. (1993). Computer-aided assembly process Radius of the Optimal Assembly Line Balance
planning with resource assignment. In: with Fixed Cycle Time. In: Proceedings of the
Proceedings of the IEEE Conference on Robotic IEEE Conference ETFA'2001, pp. 623-628.
and Automation, Atlanta-Georgia, pp. 301-306. IEEE Press.
Pinto, P. A., D. G. Dannenbring and B. M. Süer, G.A. (1998). Designing parallel assembly lines.
Khumawala (1983). Assembly line balancing Computers Ind. Eng., 35 (3-4), 467-470.
with processing alternatives: an application. Suresh, G. and S. Sahu (1994). Stochastic assembly
Management Science, 29, 817-830. line balancing using simulated annealing. Int. J.
Praça, I.C. and C. Ramos (1999). Multi-agent Prod. Res., 32 (8), 1801-1810.
simulation for balancing of assembly lines. In: Suresh, G., V. V. Vinod and S. Sahu (1996). A
Proceedings of ISATP’99, pp. 459-464. genetic algorithm for assembly line balancing.
Pellichero, F. (1999). Computer-aided choice of Production Planning and Control, 7, 38-46.
assembly methods and selection of equipment in Sysoev, V. and A. Dolgui (1999). A Pareto
production line design, Ph.D. Thesis, Université optimization approach for manufacturing system
libre de Bruxelles. design. In: Proceedings of the International
Peterson, C. (1993). A tabu search procedure for the Conference on Industrial Engineering and
simple assembly line balancing problem. In: Production Management (IEPM’99), Glasgow,
Proceedings of the Decision Science Institute Book 2, pp. 116-125. FUCAM.
Conference, pp. 1502-1504. Washington, DC. Talbot, F.B., J.H. Patterson, and W.V. Gehrlein
Petit, F. (1999). Interactive design of a product and (1986). A comparative evaluation of heuristic
its assembly system, Ph.D. Thesis, Université line balancing techniques. Management Science,
Catholique de Louvain. 32, 430-454.
Ponnambalam, S. G., P. Aravindan and G. Tsai, D.M. and M.J. Yao (1993). A line-balanced
Mogileeswar Naidu (1998). Assembly line base capacity planning procedure for series-type
balancing using multi-objective genetic robotic assembly line. Int. J. of Prod. Res., 31,
algorithm. In: Proceedings of CARS&FOF’98, 1901-1920.
pp. 222-230. Coimbatore, India. Wee, T.S. and M.J. Magazine (1982). Assembly line
Rachamadugu, R. and B. Talbot (1991). Improving balancing as generalized bin packing.
the equality of workload assignments in Operations Research Letters, 1, 56-58.
assembly lines. Int. J. Prod. Res., 29 (3), 619-
633.

166