Approaches to Line Balancing

COMSOAL & RPW

Active Learning
Module 2

Dr. César O. Malavé

Texas A&M University
Background Material
Modeling and Analysis of Manufacturing Systems
by Ronald G. Askin , Charles R. Standridge, John
Wiley & Sons, 1993, Chapter 2.
Manufacturing Systems Engineering by Stanley B.
Gershwin, Prentice – Hall,1994, Chapter 2.
Any good manufacturing systems textbook which
has detailed explanation on reliable serial systems.
Lecture Objectives

At the end of this module, the students should be

able to
 Explain the approaches to line balancing
 COMSOAL Random Sequence Generation
 Ranked Positional Weight Heuristics
 Solve and find the optimal solutions to line
balancing problems using the above techniques
Time Management

Introduction 5
Readiness Assessment Test (RAT) 5
COMSOAL Procedure 12
Spot Exercise 5
RPW Procedure 15
Team Exercise 5
Assignment 3
Total Time 50 Mins
Readiness Assessment Test (RAT)
1. In a layout, work stations are arranged according to the general function
they perform without regard to any particular product.
a) product, b) process, c) fixed position, d) storage
2. A product layout is more suited to situations where product demand is stable than
when it is fluctuating.
a) True, b) False
3. Fixed position layouts are used in projects where the product cannot be moved,
and therefore equipment, workers, and materials are brought to it.
a) True, b) False
4. In general, work-in-process inventory is large for a product layout and small for a
process layout.
a) True, b) False
5. Which of the following characteristics is associated with process layout?
a) stable demand b) less skilled workers
c) specialized machinery d) low volume
e) product for general market
RAT – Solution
1. In a Process layout, work stations are arranged according to the
general function they perform without regard to any particular product.
2. True. A product layout is more suited to situations where product
demand is stable than when it is fluctuating.
3. True. Fixed position layouts are used in projects where the product
cannot be moved, and therefore equipment, workers, and materials
are brought to it.
4. False. In general, work-in-process inventory is large for a process
layout and small for a product layout.
5. Low Volume is associated with process layout.
Approaches to Line Balancing
Three Basic Approaches for finding a solution
 COMSOAL – Basic random solution generation

method
 Ranked Positional Weight Heuristic – Good

solutions found quickly

 Implicit Enumeration Scheme

Assumptions
Required cycle time, sequencing restrictions and task
times are known
COMSOAL Random Sequence Generation

A simple record-keeping approach that allows a large

number of possible sequences to be examined
quickly
Only tasks that satisfy all the constraints are
considered at each step.
Sequence discarded as soon as it exceeds the upper
bound.
Sequence saved if it is better than the previous upper
bound and the bound is updated.
Efficiency depends on the data storage and
processing structure
COMSOAL – Cont…
COMSOAL uses several list for speed computation.
 NIP(i)  Number of immediate predecessors for each task i.
 WIP(i)  Indicates for which other tasks i is an immediate
predecessor.
 TK  Consists of N tasks.
During each sequence generation,
 List of unassigned tasks (A)
 Tasks from A with all immediate predecessors (B)
 Tasks from B with task times not exceeding remaining cycle
time in the workstation (F – Fit List)
are updated.
COMSOAL Procedure
1. Set x = 0, UB = , C = Cycle Time, c = C.
2. Start the new sequence : Set x = x+1, A = TK,
NIPW(i) = NIP(i).
3. Precedence Feasibility : For all, if NIPW(i) = 0, add
i to B.
4. Time Feasibility : For all i B, if ti ≤ c, add i to F. If F
empty, Step 5; otherwise Step 6.
5. Open new station : IDLE = IDLE + c. c = C. If
IDLE > UB go to Step 2; Otherwise Step 3.
COMSOAL Procedure – Cont…
6. Select Task : Set m = card {F}. Randomly generate
RN  U(0,1). Let i* = [m.RN]th task from F. Remove
i* from A, B, F. c = c – ti*. For all i  WIP(i*),
NIPW(i) = NIPW(i) – 1. If A empty, go to Step 7;
otherwise go to Step 3.
7. Schedule completion : IDLE = IDLE + c. If IDLE ≤
UB, UB = IDLE and store schedule. If x = X, stop;
otherwise go to Step 2.
COMSOAL – Advantages
The technique is relatively easy to program.
Feasible solutions are found quickly.
Greater the computational effort expended, the better
the expected solution .
Basic idea can be applied to many decision
problems, the only requirement being that we can
build solutions sequentially and a function evaluation
can be performed to rank candidate solutions.
COMSOAL – Example
Task Activity Assembly Immediate
Time Predecessor
a Insert Front Axle / 20 -
Wheels
b Insert Fan Rod 6 a
c Insert Fan Rod Cover 5 b
d Insert Rear Axle / 21 -
Wheels
e Insert Hood to Wheel 8 -
Frame
f Glue Windows to top 35 -
g Insert Gear Assembly 15 c, d
h Insert Gear Spacers 10 g
i Secure Front Wheel 15 e, h
Frame
j Insert Engine 5 c
k Attach Top 46 f, i, j
l Add Decals 16 k
COMSOAL – Example
Data Known :
 Two 4 hour-shifts, 4 days a week will be used for

assembly.
 Each shift receives two 10 minute breaks.

 Planned production rate of 1500 units/week.

 No Zoning constraints exist.

Example Solution
Model Car Precedence Structure
20 6 5 5
a b c j

21 15 10
d g h

8 15 46 16
e i k l

35
f
Example Solution – Cont…
1 Week days shifts minutes minutes
C 4 2  220  1.17
1500 Units week day shift unit
To meet demand C = 70 Seconds.
Initially four potential tasks a, d, e, or f
Generate random number between 0 and 1. Say
outcome in our case is 0.34
R is in second quadrant so keep d as first task.
Continue the random generation.
Quick check of lower bound

K0  
l
r a r

t C   202 70  3
Thus Better
Solutions may exist
Single COMSOAL Sequence Results
Step List A List B List F U (0,1) Selected Station
Tasks (Idle Time)
1 a through l a, d, e, f a, d, e, f 0.34 d 1(49)
2 a through l, -d a, e, f a, e, f 0.83 f 1(14)
3 a, b, c, e, g, h, i, j, k, l a, e e - e 1(6)
4 a, b, c, g, h, i, j, k, l a - Open
Station
4 a, b, c, g, h, i, j, k, l a a - a 2(50)
5 b, c, g, h, i, j, k, l b b - b 2(44)
6 c, g, h, i, j, k, l c c - c 2(39)
7 g, h, i, j, k, l g, j g, j 0.21 g 2(24)
8 h, i, j, k, l j, h h, j 0.42 h 2(14)
9 i, j, k, l i, j j - j 2(9)
10 i, k, l i - Open
Station
10 i, k, l i i - i 3(55)
11 k, l k k - k 3(9)
12 l l - Open
Spot Exercise
Solve the following line balancing problem using
COMSOAL procedure. Assume demand is 100/day.
Task Time Immediate
Predecessor
a 2 -
b 1 a
c 2 a
d 3 b, c
e 1 d
f 3 e
Exercise Solution

1 Production time available

b
C
2 3 1 3 Desired units of output
a d e f 8 Hours  60 Minutes/ho ur
2

c 100
 4.8 Minutes

K0  
l
r a r

t C  12 / 4.8  2.5  3
Exercise Solution – Cont…
Step List A List B List F U(0,1) Selected Station
Task (Idle
Time)
1 a to f a a - a 1(2.8)

2 b to f b, c b, c 0.68 c 1(0.8)

3 b to f, -c b b - b 2(3.8)

4 d to f d d - d 2(0.8)

5 e, f e e - e 3(3.8)

6 f f f - f 3(0.8)
Ranked Positional Weight Heuristic
A task is prioritized based on the cumulative assembly
time associated with itself and its successors.
Tasks are assigned in this order to the lowest
numbered feasible workstation.
Cumulative remaining assembly time constrains the
number of workstations required.
Illustrates the greedy, single pass heuristics.
Procedure requires computation of positional weight
PW(i) of each task.
RPW Procedure
Let S(i)  Set of successors of tasks i.
Example, j  S(i) means j cannot begin until i is
complete.

Compute PWi = ti + rS (i ) t r
Tasks ordered such that i < r implies i not  S(r).
Task r is then a member of S(i) only if there exists an
immediate successor relationship from i to r.
Immediate successors IS(i) are known from the
inverse of the IP(i) relationships.
RPW Procedure – Cont…
1. Task Ordering : For all tasks i = 1,…,N compute
PW(i). Order (rank) tasks by nonincreasing PW(i)
2. Task Assignment : For ranked tasks i = ,…,N assign
task i to first feasible workstation.

Precedence Constraints : assignment to any workstation

at least as large as that to which its predecessors are
assigned
Zoning & Time Restrictions : Checked on placement.
RPW Procedure - Example
Task Activity Assembly Immediate
Time Predecessor
a Insert Front Axle / 20 -
Wheels
b Insert Fan Rod 6 a
c Insert Fan Rod Cover 5 b
d Insert Rear Axle / 21 -
Wheels
e Insert Hood to Wheel 8 -
Frame
f Glue Windows to top 35 -
g Insert Gear Assembly 15 c, d
h Insert Gear Spacers 10 g
i Secure Front Wheel 15 e, h
Frame
j Insert Engine 5 c
k Attach Top 46 f, i, j
l Add Decals 16 k
Example Solution
Model Car Precedence Structure
20 6 5 5
a b c j

21 15 10
d g h

8 15 46 16
e i k l

35
f
RPW Procedure - Solution
Positional Weight calculated based Task PW Ranked PW
on the precedence structure a 138 1
(previous slide). b 118 3
c 112 4
PWl = its task time = 16 d 123 2
e 85 8
PWk = tk + PWl = 46+16 = 62
f 97 6
PWj = tj + PWk = 5+62 = 67 g 102 5
h 87 7
i 77 9
j 67 10
k 62 11
l 16 12
RPW Solution Cont…
Assignment order is given by the rankings.
Task a assigned to station 1.
 c - ta = 70 – 20 = 50 seconds left in Station 1.
Next Assign task d
 50 – 21 = 29 seconds left in Station 1.

Station Time Remaining Tasks

1 70, 50, 29, 23, 18, 3 a, d, b, c, g

2 70, 35, 25, 17, 2 f, h, e, i

3 70, 65, 19, 3 j, k, l

Team Exercise
Assembly of a product has been divided into elemental
tasks suitable for assignment to unskilled workers. Task
times and constraints are given below. Solve by RPW
Procedure
Task Time Immediate
Predecessors
a 20 -
b 18 -
c 6 a
d 10 a
e 6 b
f 7 c, d
g 6 e, f
h 14 g
Exercise Solution
Task PWi Rank
6
c a 63 1
7
b 44 2
f
20 10
6 14 c 33 4
a d
g h d 37 3
18 6
e 26 6
b e
f 27 5

g 20 7
Workstation Assigned Remaining
Tasks Time h 14 8
1 a, d 30, 10, 0
2 b, c, e 30, 12, 6, 0
3 f, g, h 30, 23, 17, 3
Assignment
Write a flowchart for COMSOAL using the decision rule
that feasible tasks are selected with probability
proportional to their positional weight.