Unidirectional Loop Network Layout Problem in Automated Manufacturing Systems Author(s): Panagiotis Kouvelis and Michael W.

Kim Reviewed work(s): Source: Operations Research, Vol. 40, No. 3 (May - Jun., 1992), pp. 533-550 Published by: INFORMS Stable URL: http://www.jstor.org/stable/171415 . Accessed: 19/03/2012 02:20
Your use of the JSTOR archive indicates your acceptance of the Terms & Conditions of Use, available at . http://www.jstor.org/page/info/about/policies/terms.jsp JSTOR is a not-for-profit service that helps scholars, researchers, and students discover, use, and build upon a wide range of content in a trusted digital archive. We use information technology and tools to increase productivity and facilitate new forms of scholarship. For more information about JSTOR, please contact [email protected].

INFORMS is collaborating with JSTOR to digitize, preserve and extend access to Operations Research.

http://www.jstor.org

UNIDIRECTIONAL LOOP NETWORK LAYOUTPROBLEMIN AUTOMATED MANUFACTURING SYSTEMS

PANAGIOTIS KOUVELIS
Duke University, Durham,NorthCarolina

MICHAEL KIM W.
University California, of Riverside,California (ReceivedFebruary1989;revisionsreceivedNovember 1989,June 1990;acceptedAugust 1990) In this paper,we addressthe designof unidirectional loop networklayoutsfor automatedmanufacturing environments. We show that the problem is NP-complete. Using a workstationinterchangeargument,we develop dominance for of to relationships easy identification local optimalsolutions.Our resultssuggestthe need for simpleheuristics solve the problem.We identifycasesin whichthe heuristics performoptimally,and we analyzethe worstcasebehaviorof the heuristics.We develop an optimal branch-and-bound procedurethat is computationallyefficient for medium-sized problems.We also present a decompositionprinciple helpful for dealing with large workflowmatrices.We report We resultson the heuristics the branch-and-bound and computational procedure. showthatone of the heuristics performs well in termsof solutionqualityand computational time requirements. impressively

layout problem in a manufacturing setting

typesare: a. b. c. d. e. loop unidirectional network; circular machinelayout; machinelayout; linearsingle-row machinelayout;and lineardouble-row clustermachinelayout.

concerns the determination of the relative location of a given number of machines given an equal number of candidate locations. A typical objective is to minimize the total material handling cost, which depends on both the material movement frequencies and the distances between the machines. The most frequently used formulation for modeling the plant layout problem is the Quadratic Assignment Problem (QAP), which is known to be NP-complete (Sahni and Gonzalez 1976). Gilmore (1963) and Lawler (1963) developed optimal solution procedures for the problem. Armour and Buffa (1963), Drezner (1980), Hillier (1963), and Hillier and Connors (1966) proposed heuristic procedures. The physical layout design of an automated manufacturing system is extremely important because it affects the required initial investment, the amount of in-process inventory, the production lead times, the production rate, the material handling costs, and the complexity of the operational control algorithms. Despite this fact, only a limited amount of research has been done on the development of analytical models that concentrate on the special structureof the layout problem for a few commonly used types of workstation layouts in automated manufacturing systems. The most frequently encountered layout

In this paper,we discussonly the layout type a. A of detaileddescription the layouttypesb, c, d, and e, and is foundin Heragu Kusiak(1988).In that paper, the of theauthors question validity a QAPformulation in systemsconfigured for automatedmanufacturing one of the above layout types. They present two to that heuristic procedures attempt exploitthe special for structure the layoutdecisions someof the above of layouttypes. environments,uniIn automatedmanufacturing directional loop networklayouts(ULNL)are extendue to the wide use of efficient sively implemented networks. Suchnetworks handling unicyclicmaterial connect all workstations a path passingthrough by maneachworkstation exactlyonce.In an automated ufacturing the unicyclicmaterialhandlingnetcell work may representa loop conveyor, tow line, overhead monorail systemor wirepathsof a unidirectional automatedguidedvehicle (AGV) system.An is loop exampleof a unidirectional network shownin

Subject classifications. Facilities/equipment planning: facilities planning for manufacturing systems. Manufacturing: layout of automated systems. Manufacturing, automated systems: layout of flexible manufacturing systems. Area of review: MANUFACTURING, PRODUCTION AND SCHEDULING. Operations Research Vol. 40, No. 3, May-June 1992 0030-364X/92/4003-0533 533 $01.25

?) 1992 Operations Research Society of America

534

ANDKIM KouVELIS

lowerinitialinvestment Figure1. Suchlayoutsrequire becausethey contain cost than otherconfigurations, materialhandling the minimumnumberof required and links to connectall workstations, possesshigher Becausethereis at least material handlingflexibility. any one directed pathconnecting pairof workstations, ULNL is flexiblein its abilityto satisfyall material for requirements the parttypesscheduled for handling to on manufacturing the systemandin its ability easily accommodateany future introductionof new part types or process changes.For a discussionon the of advantagesand disadvantages ULNL refer to Afentakis (1989). In this paper,we addressthe designof ULNL for environments.Our forautomated manufacturing mulationof the problemis primarilymotivatedby system(FMS)implecurrentflexiblemanufacturing mentations.The most commonly used operational strategy suchsystems,andthe one we will assume for all the throughout paper,requires parts to enterand exit the system at the load/unload(L/UL) workall station.Therefore, partscompletean integernumber of cycles aroundthe networkbeforeleavingthe
system. When a part has been processedat a particular workstation, it proceeds immediately to the next one

by moving on the unicyclicmaterialhandlingnetis work.If the workstation occupiedthe partis stored to for waiting theworkstation become in a localbuffer, of free.Fora betterunderstanding the assumedoperof referto Figure1. In our discussion ationalstrategy the designprocess,we assumethat the locationand type of the materialhandlingnetwork,and the canof didatelocationsfor the workstations the manufacturingsystemaregiven. loop network designsof unidirectional Suboptimal the syshandicap manufacturing layoutscan severely tem performance becausethey will cause significant parts.To visita givensequence delaysof the processed otherstationson the of stations, partshaveto traverse

Machine

Machine

Load/ Unload

I I<_

L]1

. i

Machine 4

~~~~13

Machine

Figure 1. A unidirectional loop network layout.

unicyclicmaterialhandlingnetwork.A suboptimal the layoutdesignwill increase numberof stationsthe of beforecompletion theirmanpartshaveto traverse ufacturing process,and hence will increasethe travtimes. This will handling eling distanceand material (WIP)levels, resultin an increaseof work-in-process a cycle times and systemcongestion.Consequently, valid design objectiveis to develop a workstation the that layoutfortheloopnetwork minimizes average numberof machinesthat partscross per unit time. loop This designobjective unidirectional network for can strategy, layouts,underthe assumedoperational the as be statedequivalently minimizing totalnumber of partspassing through load/unloadstation,and the is also equivalentto the typical layout objectiveof minimizingthe total materialhandlingcost. Further of discussion the equivalence the aboveobjectives on can be foundin Section 1. in The ULNL problemaddressed this paperwas (1989).The authorprefirstintroduced Afentakis by formulationof programming sents a mathematical the problem,and suggestsan interchange heuristic (1988) procedure its solution.Kiranand Karabati for address ULNL problemundera slightlydifferent the withthe designobjective minof operational strategy, handling cost.A dominance imizingthe totalmaterial local optimalsolutionsis usedto rule for identifying for algorithm developan exactimplicitenumeration the problem. The rest of this paper proceeds as follows: In characterize unidirectional the Section1, we formally loop networklayoutdesignas a hardcombinatorial problem (NP-complete).In Section 2, we use an interchange argumentto presentdomiappropriate for nance relationships easy identificationof local heuristicprooptimalsolutions.Simpleconstructive in ceduresare presented Section3; conditionsunder which the heuristicsolutions are optimal are discussed,and theirworstcase behavioris analyzed.In Section 4, an optimalbranch-and-bound procedure thatis enhanced withthe dominancerelationships of Section2, is presented. largeworkflow For matrices a decomposition principlethat reducesthe size of the is subproblems layoutproblem solvingappropriate by in presented Section5. Thoughthe worstcasebehavtheir ior of the heuristicsis rather disappointing, observed over performance a largeset computational of real-sizelayout problemsis adequatefor design purposes.Discussionof the qualityof the heuristic solutionsand the computational of performance the can procedure be found optimalbranch-and-bound in Section6.

LayoutinAutomated Manufacturing Systems / 535

1. THE UNIDIRECTIONAL LOOP NETWORK LAYOUTPROBLEMFORMULATION

TheULNLproblem be statedformally follows: can as

Given workstations 0, 1, . . ., N, with workstation 0

underthe assumed operational strategy, minimization of the totalmaterial handling is equivalent our cost to statedobjective. Observe thatthe average also number of machines thatpartscrossperunit time is givenby
N N N

being the load/unload station, and nonnegative is wi1, 1 s i, j < N, where w1j the numberof parts processed stationi perunittimethatmustbe routed in to station andassuming the candidate ], that locations of the workstations set up in a closedloop, where are all the movementtakesplacein a prespecified direcof tion, whatis the ordering the workstations yielding the minimum number of parts that have to pass through stationO? Let us definea workstation vectoras a assignment
permutation of the integers 1, 2, . .., N denoted by a = (a(l), ..., a(N)), wherea(i) is the location of

(N + 1) E, w0 +
i= I

i=1 i=l

wijI(a(i), a( ))

To formallyestablishthe NP-completeness the of unidirectional network we loop layoutproblem, reformulatethe problem the following in terms.
Problem P

Given a matrix W = (wij) E (Z+)NXN and a scalar B E Z+, is therea permutation = (a(i)) suchthat a
N

wi,

s B?

stationi. Let
N N

i= I a(j)<a(i)

f(a)

E
i=1 j=1

wj1 (a(i), a(j)),

where l(a(i), a(j)) =f1, if a(i) > a(j) =0, otherwise,

In Afentakis (1989)it was hintedthatproblemP is NP-complete. The use of a transformation from the feedbackarc set problemwas suggested. Below we providea formalproofof the aboveresult.
Theorem 1. P is NP-complete.

is an indicator function. ThentheULNLproblem can be statedas that of findingan assignmentvector a that minimizesthe expression f(a), i.e.,
min {f(a)},
aEn

Proof. We use a transformation from the Feedback Arc Set (FAS) problem(Gareyand Johnson 1979). Thisproblemis formulated follows. as
Problem FAS

where II is the set of all permutations integers of

1, . .. , N.

We will commentfurther the objective on function givenabove.Underthe assumedoperational strategy, will an parts complete integer of number cyclesaround the network beforeexitingthe system.A lowerbound on the numberof cyclesof a partaroundthe network is 1. Usingthis fact,we can express total material the handlingcost, i.e., the productof materialflowsand distances betweenthe machines, as:
/N N N

Given a directedgraphG = (V, A) and a positive integerB < IA 1, is there a subset A' C A with IA' I < B, such that A' contains at least one arc from everydirected cyclein G? W Construct fromthe datain G = (JV, by letting A)
fl,
wi1190

if(i,j)EA otherwise.

Then, the answerto FAS is yes if and only if the answer this instanceof P is yes. to Assume that there exists a permutationa of
{l,...,IVI}suchthat
I VI
i= 1 a(j)<a(i)

YJ i= I

woi+ E E wijI(a(i), a(j))

i=1 j=1

wj-<B.

where = woi the materialflow fromthe load/unloadstation to stationi; c = the lengthof the unidirectional loop. Butthe firsttermin theaboveexpression thetotal is numberof partsto be processed the system,which in is independent the layoutdecision.Consequently, of

Thenthe set A' 5 A, A' = {(ij) E A: a(j) < a(i)} givesa solutionfor FAS since G' = (V,A - A') is an acyclicdirected graph,and
I VI
I X, 'I v v -<B

536 / KOUVELIS AND KIM Assume now that there exists a solution for FAS given by A' 5 A. We can label the nodes in G' = (V, A - A') in such a way that
(cx(i), a(j)) E A
-

the defined, followingholds: a,1and 2previously

f(a2) -f(ai)
$.
iel

A' - a(i) < a(j).

(Wji

Wij)

(Wik -

Wki)} I ? W

WkJ.

Then,usingthatlabeling ourpermutation, must as we have

I Vl

Proof. By definition
N i=lj=l N N

I wi IA' I< js

I fa =E Y,wij(ai(i),ai(j)) (oi)
N

i= I a(j)<a(i)

as all arcssatisfying a(j) < cx(i) must be in A'. This completes proof. the
2. DOMINANCE RULES FOR IDENTIFYING LOCAL OPTIMALSOLUTIONS

= E

E
N

wiml(a (i) ,ai(m))

i n=I i~j,k m5j,k

+
i~k
N

j {wij1(a(i), ai(j)) + wjil(ai(j), ai(i))}

{Wik (al (i), a (k))

In this section,we presentnecessary optimalityconditions for the unidirectional loop networklayout problem.Such conditionsare useful in developing both heuristic algorithms exactimplicitenumerand for ationprocedures the solutionof the problem. LetRj = a N=I wji, i.e., the totalflow fromj to other stations and Cj = a N=l wij, i.e., the total flow from otherstationsto j. We referto the specialcase
that Rj = Cj for j = 1, . . ., N as the "balanced case." In general,however,Rj $ Cj. Under our assumed

isi i54j + Wkil(al(k), ai(i))} + Wk1.

Then
f(a2) -f(ai)
N

= wij[1(a2(), a2(j))i~k + wi[1(a2(j),

N

1(a(i), a (j))]
(j), a (I))]}
1(a,(i),

of there is conservation flow at operational strategy everyworkstation i.e., Ad o wji= ZjX wij. Observe i, o thatthe flow conservation does not alwaysleadto the abovedefinedbalanced case.
Consider the following two workstationassignment vectors: a,1= (. . ., ai(j) = p, . . ., a[(k) = p +3,...)
=

a2(i))-1 (-a1

+ isj

{WIk[1(a2(i), a2(k))-

a,(k))]

+ Wki[l(a2(k), a2(l)) -l
+ Wjk Wkj + (Wik-Wki)}

(a (k), ao(i))]}

I {(Wji-Wij)
iEI

+ Wjk

Wkj

and a2 = (... .,
a2( j) = P +
a2(i)

aa.

,02(k) = p,...)

Keeping in mind the assignment vectors an and a2 previously presented, let us define the quantity ejlk(I)= f(ae2) - fg(ot). In the case that f = 1, i.e., I=
ejk
=

witha, (i) = are: 1

forall i $ j, k. Theparameter ranges and 1

d

p<N-1

N-p

< N - 1.

q,

we denote:

Let I denotethe set of workstations are between that stationsj and k in the assignmentvectora, (or a2),
i.e.,

ek (?)

wjk -

wk-

(by Theorem 2). 1 the

CallS= {1, 2, . . ., N}. Inthecasethat3=Nset I = S\ j, k}, and we denote

N-I N ejk = eJk (S\{ j, k}) N N (wj
-

I = {i: p < a1(i)

a2(i) < P + d}.

theorem ObviouslyII I = d - 1. Then,the following

comparesf(a1) and f(a2). Theorem 2. For the workstation assignment vectors

Wij)

(Wik -

Wki) + Wjk

WkJ

i~k

isj
+ Wk;-Wjk.

=(Rj-Cj)-(Rk-Ck)

Layout in AutomatedManufacturingSystems / Observe that in the balanced case, i.e., Rj = Cj for all j E S,
eJk = -ejN.-i

537

for all j, k e S.

Using the previously establishednotation, we can state the following corollaries of Theorem 2.

1. holds Corollary Thefollowingrelationship

e" (I) = E (e'~ + en) + e'u
iEl

b. Let i E S denotea workstation has onlyone that incoming (the arc (0, i)) in G'. Thenthereexists arc at least one optimalsolutionin whichi is locatedat thefirst candidate location(e.g., a*(1) = i). c. Let i E S denotea workstation has onlyone that outgoing (thearc(i, 0)) in G'. Thenthereexistsat arc least one optimalsolutionin whichi is locatedat the last candidate location(e.g., a*(N) = i). Proof. a. If a is locallyoptimal,then for i = 1,..., N- 1 ea(i),a(i+l) > 0 and,consequently, induceddirected an cycleon G' is defined. b. Supposethat a*(j) = i, j > 1. Let a* be the corresponding optimalworkstation assignment vector andK = {k:a *(k) < j}. Also,let kodenotethe station in K such that a*(ko) = a*(i) - 1. Since wki = 0, must be zero (otherwise, is not optimal).We a* wi4< interchange and i and find thatthe objectivefuncko tion value does not change.Repeating this adjacent station i can be locatedat the pairwiseinterchange, first location, with the objective function value unchanged. c. Thisis provedby an argument similar the one to in b. Note thatthe firstcandidate locationis the location next to the L/UL station in the direction of the movementof the materialhandlingsystem,and the last candidate locationis next to the L/UL stationin the oppositedirection that movement. of
Corollary3. If G' has a unique directed Hamiltonian

Corollary 2. If e' >- 0, e'k > Oforall i E I C S\{ j, k} and ek >- 0, theneok(I)> 0 We will use the term location assignment vectorfor a permutation of the integers 1, 2, . .. , N denoted by a = (a(1), ..., a(N)), where a(i) is the workstation assigned to location i. Note its difference from the workstationassignment vector,a. For convenience in presenting what follows, we will use the term assign-

ment vectorwhen we mean a location assignment

vector.We also call
N-i i=l N

f (a)= Wa(=)a(i) E E
j=i+l

Consider the directed graph G = (S, A) with S = 1> {1, ..., N} and A = {(i, j), i e S, j e S: e' 0}. Denote by 0 a dummy node and call SO= S U {0}. Develop the directed graph G' = (SO,A') with

A' = A U {(0, i) for all i e S}

U {(i, 0) for all i e S}. Call G" = (SO,A") the undirected version of G'. An assignment vector a = (a(i)) induces the subgraph "=(SO,A") on G" where: " A = {(a(i), a(i + 1))i = 1, . . ., N - 1} U {(0, a(1)), (a(N), 0)}. The induced subgraphG" is a cycle, and if it does not violate the arc directions in G', it will be referred to as an induced directed cycle in G' by the assignment vector a. As can easily be seen, it is actually a Hamiltonian tour of G'. We say that an assignment vector, a, is locally optimal if it is not possible to improve the value of the objective function f(a) by interchangingthe position of any two workstations. Then we get the next theorem.

tour,thena localoptimalsolutionis globallyoptimal. of Leta "partial assignment sizeq"be a permutation

of integers 1, 2, ... , N taken q integers at a time.

We denote a partialassignmentof size q by aq*=

(a*(1), . . ., a *(q)). A completion of a partial assign-

vectorfor mentof size q is definedas an assignment which the first q integersare those of the partial
= assignment. Let aq*c (a*(1), . . ., a*(q), a(q + 1),
.
. ,

of a(N)) denotea completion a partial assignment

=

of size q. We can write aq*c

(a(q + 1),
. . .,

(a*ac-q),

where a-q

a(N)).

Corollary4. Givena partialassignment size q, aq* of

the resultsof Theorem3 apply to the nonassigned stationsand the vector ac-q (or to spell it out,for the workstation corresponding assignment vector). For specialcasesof the flow matrix,the following observations the interesting regarding optimal location of certainworkstations be made. can

Theorem3. a. An assignmentvector,a, that is locally optimalfor the unidirectional loop network layoutproblem, definesa Hamiltonian touron G'.

538 / KOUVELIS AND KIM Theorem 4. a. In an optimal solution a workstationi E S thathas onlyincomingflows (fromother workstations) will be located at the last candidate
location, i.e., a*(i) = N for an optimal workstation assignment vector a*. If there are k(k < N) work-

b. This is proved by using argumentssimilarto thosein the proofof a. 5. Corollary Givena partialassignment size q, a*, of the results Theorem applyto the remaining of 4 workmatrixafterwe deleterowsand columnscorreflow spondingto alreadyassignedstationsand the vector workstation aNq (or,to spellit out, the corresponding assignment vector). Theorem A ULNLproblemwithworkflow 5. matrix W = (wij) is equivalentto a ULNL with workflow matrix W' = (w') = (wij - iwi'), where iv minIwij, wji},i, j E S.
=

stationshavingtheabove property, willbe located they at the last k-candidate locations,and their relative positiondoes not affectthe optimalobjective function value. i b. In an optimalsolutiona workstation E S that has onlyoutgoingflows otherworkstations) be (to will locatedat thefirst candidate locationi.e., a *(i) = 1,
for an optimal workstation assignment vector a'*. If

there are k(k < N) workstations having the above property, they will be locatedat thefirst k-candidate locations theirrelative and positiondoes notaffectthe optimalobjective functionvalue. Proof. a. By definition
N N

Proof. By definition:
N N N N

f(t)=

Z Z wij I(a (i), a (j)) = i=lj=l

E
i=lj=l

* [W1 (a (i), a (j)) + wji I (a (j), a (i))]

f(a)

=
N

Z
m=1 n=1 N

Wmnl(a(m),a(n))

-2 2.
i=I j=I

[(Oij + (Wij- 7ij)) I (a (i), ae (j))

m=I n=1 mwi n~i N

E E

wo (of1(a(m),a(n))

+ (iwvji(wji- Oji))1I (j), a (i))] + (a

IN N

f (a)
winI(a(i),

2,
i IN

Y, O j I (a (i), at(j))
j=1 N

E
n=1 N

a(n))

+2- E Z 2 i=lj=I
wmil(a(m), a(i)).
IN
N

ji I (a (j),

a (i))

E
m=1

Note that wmi> 0 for all m and win = 0 for all n becauseworkstation has only incomingflows. The i firstterm is independent i; therefore, need to of we find a that minimizesthe last term. Since wmi 0 3 for all m, the last term is minimized if 1(a(m), a(i)) = 0. So, for the optimal a* and for all m # i,
1(a*(m), a*(i)) = 0 o# a*(m) < a*(i). That implies that a *(i) = N.

wo= t j=a
N

+ - ) (Wiit sedej)cn(dt(i), )j)) aj

N N

+ Z Z (W=i
i=1 j=I

- w (-) )j), a (i))) i I(a

Since = if hij fji, the lasttwo termsareidentical the indices i and j are interchanged. After replacing s(oe(j),a (i))in the secondtermwith - e (ad(i), (j)), aa
we obtain
IN
M N N

Forthe casein whichtherearek workstations with only incoming flows, call K = {1: wlj = 0 for all i # 1}. Observethat the term we are interestedin a minimizing through selectionof a(i) for i E K is
N N

f~oa) = 2 Z

i =l j=l

Z Oij + Z

i=l j=l

Z (wij - Oij)I(ae(i),

ae(j)).

Since the first term is independent of the assignment vector, the validity of the proposition follows. By observing the workflow matrix, it is easy to identify cases in which Theorem 4 applies. For some of those cases, application of Theorem 4 and

E
m4K

wmil(a(m),

a(i))

E
mEK

wmil(a(m),

a(i)).

Butbecausethe secondtermin the abovesummation is zero,the impliedconditionfor optimality is a *(m) < a *(i) for m e K.

5 Corollary can even leadto a quickidentification of the optimalsolution.An illustrative examplefollows. Example 1. Consider a 7-station automated

LayoutinAutomated ManufacturingSystems 539 /

manufacturing system, with the L/UL station being station 0. Between the stations we have the workflows described in matrix W: 0 0 0 0 10 20 30 0 80 50 100 0 60 0 0 0 0 00 0 0 0 10 50 80 60 90 40 100 120. 0 01 70 0J station 0) with the following workflow matrix W: 0 260 320 180 80 350

W=

250 300 150 70 300

0 80 150 280 160 100 0 260 390 140 100 200 0 285 120 200 300 185 0 0 100 100 0 70 0

0
0

After the transformationthe resulting matrix W' is

By application of Theorem 4: a*(1) = 1, a*(5) = 6. After we eliminate rows and columns 1 and 5, the remaining work flow matrix is: To From 2 3 4 6 2 3 4 6 60 40 120 0

0 10 20 30 10 50 0 0 0 50 80 60 WI= 0 20 0 60 90 40 0 0 0 0 100 1201. 0

1 0 0 0

70

Oj

0 80 50 100 0 60 0 0 0 0 0 0

By repeated application of Theorem 4 (similar to the procedure used in Example 1) we obtain the optimal solution to the problem a* = (1, 3, 2, 4, 6, 5). 3. HEURISTIC SOLUTIONPROCEDURES In this section, we present simple heuristic procedures for the solution of the ULNL problem. Development of such procedures,in addition to its obvious value of providing solutions to the problem, is also a way to test simple ideas. In many cases practitioners find simple heuristic procedures intuitively appealing and easy to implement. The heuristics we propose are mainly supported by the results presented in Section 2. Their attractivefeaturesare simplicity, ease of implementation, intuitive appeal, computational efficiency, and adequate to impressive solution effectiveness (measured in terms of the deviation from optimality). We defer comparison of the heuristics, and discussion of their features and associated computational results to Section 6. We startour presentationwith the simplest heuristic procedure. Heuristic Procedure KK-1 Step 0. Initialize an N X N matrix W' by setting WI = W, where W = (wij) is the workflow matrix. Step 1. Calculate the row sums RI of the matrix W,. Step 2. Determine k such that R k = maxjR). Break ties arbitrarily.Assign workstation k to the first available candidate location. Step 3. Erase column k and row k of matrix W'. Reset the remaining submatrix as matrix W'. Repeat

Applying Theorem 4 and Corollary 5, we get a *(6) = 5. After eliminating row and column 6 we obtain To From 2 3 4 2 3 4

0 80 50 100 0 60 0 0 0

Application of Theorem 4 and Corollary 5 gives a *(4) = 4, a *(3) = 2. Consequently, a *(2) = 3. So, three simple applications of Theorem 4 provide the optimal workstation assignment vector for this example: a* = (1, 3, 2, 4, 6, 5) (and the optimal location assignment vector a* = (1, 3, 2, 4, 6, 5)). Because application of Theorem 4 will eliminate all zero rows or columns from the relevant workflow matrix, by optimally assigning the corresponding workstations,we can assume in our furtherdiscussion that we are dealing with workflow matrices that do not have any zero rows or columns. A preprocessingstep useful for some ULNL problems is to transform the workflow matrix W into the equivalent workflow matrix W', as we show in Theorem 5. We have found that in some cases use of this transformation,in combination with Theorem 4, makes it easy to detect the optimal solution of the ULNL problem. An example follows. Example 2. Consider 7-station automated manufacturing system (assuming that the L/UL station is

AND 540 / KOUVELIS KIM Steps1-3 untilthe new matrixW' consistsof a single element. A variantof heuristicKK-1 is to determinek in Step 2 as C' = Mini Cj, whereCj's are the column the exhibits same sumsof the matrixW'. Thisvariant featuresas heuristicKK-1and will not be discussed further. is idea behindthe heuristic simple, The motivating correctin all cases. It would, in but not necessarily be general, betterto locatestationswithhighoutflows guaranaheadof the others.This idea unfortunately tees an optimalsolutiononly for systemswithN = 2. the The following example demonstrates heuristic procedure.
Example 3. Consider a ULNL problem with N= 4 Theorem 6. The heuristic KK-1for the ULNLprob-

lem withN > 2 can be arbitrarily bad. Proof. The worst case for the heuristicis a ULNL problemwith the workflowmatrixpresented below nonzeroelements): (theshadedarearepresents
wo
=

WO

matrixW: workflow andthe following /0 3 6 f 12 0 5 W 4 3 0 \6 2 4 4\ R =R1 = 13-Max 2 R=2R2= 9 Row Sums

0

4/R=R4 = 12

R3

= R3 = 8

R1

where:R

R5

... R

1 location, Assignworkstation to the firstcandidate is = 1, and the resulting submatrix i.e., a(l)
(0

5 2\ R =7*-Max 1 |3 0 0 R2= 4 2 4 0/ R3 = 6

R? In the casein whichwo - wo?, + W?+1,1+1, 1 <1< > j I N, 1 j < i, KK-1 will produceas a solution the
assignment vector a
=

2 locaAssignworkstation to the secondcandidate submatrix is tion, i.e., a(2) = 2. The resulting

(

(1, 2, . .., N) and an objective

functionvalueof
N N

O i'\R,-1

\4 0/ R=42

= Max

i=l j=l

E E

w~- Rol.

Hence, a(3) = 4. The resultingsolution is a = (1, 2, 4, 3) with the objectivefunctionvaluef'(a) = 18. The variant of the heuristicprocedureKK-1, workingwith the column sums, producesthe solution a'
=

We could producesimilarworst case examplesfor max R, and in those casesthe objectivefunction valueof the heuristic solutionis
R=
N N

(4, 2, 1, 3) withf'(a')

17.
ZH w=o

on Let us now try to applythe heuristic the transmatrixW': formed

0O 1 2 0 W'0 2 0 92 0 3 O0

i=1 j=1

- max Rj.
J.

The lower bound on an optimal solution for the matrixWis: LB = min(miniRi, minjCj). Letus consider specialcaseof the matrixWI), a where Co = min. C?, and Co < R?. Also, wo > 0, 2 < i s N and wij = 0 for 3 i < N, 3 <j < i. For this case the optimal solution is a = (1, 3, 4, ... , N, 2) (it achievesthe lower bound), and the optimal objective value is Zopt = Co, or in more general terms The ZH is still the previously Zopt = minj CJO speci-

The resultingsolution is a" = (4, 1, 2, 3) with f'(a") = 16. By applyingTheorem4 we can easily vectoris optimal. observethat the above assignment But thatis not the casein general(see Section6). The above example illustratesthat the heuristic solutionsobtainedby applyingKK-1on W and W' the arenot necessarily same(andwe cannotdetermine solutionis better). a prioriforwhichcasethe resulting

fied one. So, in the worst case, the deviationfrom

Systems / 541 Manufacturing LayoutinAutomated

optimality of KK-1 is
ZH
-

Zopt

E xz=l

EJ'=iw?

- max,

RJ - minj CJ

Zopt

minj C5?

But, in that case:

N N N

because the node a( 1) has only outgoing arcs to nodes in the set S, the node a(N) has only incoming arcs from the nodes in S, and the node a(i), 1 < i < N, can be visited only by nodes a (j), j < 1. Consequently, by Corollary 3 the assignment vector a is optimal. Let us consider the matrix E' = (e j), which results from the application of permutation a on the matrix E. Observethat repeated application of Theorem 4 to E' will lead to an optimal solution to the corresponding ULNL problem (with workflow matrix E'), an assignment vector a as described in the conditions of Proposition 1. Proposition 2. If there exists a permutation, a, of the integers I1, . .. , NI such that the ULNL problem with workflowmatrix E' (obtained by applying permutation a on matrix E) can be solved to optimality with repeated application of Theorem 4, then KK-2 will provide the optimal solution to the ULNL problem with the workflowmatrix W that induced the development of matrix E. The proof of Proposition 2 resembles that of Proposition 1, and is omitted. The significance of the proposition is the indication that many different patterns of pE for a permutationa are sufficientto guarantee optimality of KK-2. Below we give some examples of such patterns:

E
i=1 j=1

= maxj R? + min, Cj + E wo
i=3

and
ZH
-

Zopt

El =3 Wi2

Zopt

minj Co

If wo, = Co - (N- 2)cE, wo =Co-c, 3 < i < N, then

Efw=
For NZ
Zopt

-P

(N_ 2)(1-C)
I

oo0, -*

O we have Efw -? ?o.

According to Theorem 6, the simple (and for some designers intuitive) heuristic KK-1 can lead to clearly suboptimal layout designs. The second heuristic procedure we are going to propose operates like KK-1, but on a different matrix.
Heuristic Procedure KK-2

Step 0. Using as input the workflow matrix W= (wij), develop the matrix E = (Eij),where: I1+ {+j

1.

6 for e liwij -wii for e wijwij-wji=

otherwise

> O. i

a.
j

P= (N-

1,N-

,N-35-5.N-i

N-i-

Oi

1, ... 0) with

E(a(l),

a(2))

E(a(2),

a(l))

1, and

and 6 is a small positive number (6 < 1/N). Step 1. Apply heuristic KK-1 on matrix E. Let us call PE(k) the number of nonzero elements of row k in matrix E (excluding the diagonal elements). Proposition 1. If there exists a permutation a of the integers 1, ..., NJ such that Pa = (PE(a(k)) = ), thenKK-2 (N- 1, N- 2, ... N- i, N- i 1. ... will provide an optimal solution to the ULNL problem that induced the developmentof matrix E. Proof. First observe that KK-2, under the conditions of the proposition, will produce as an assignment vector the permutation vector a. Then, using Corollary2 we see that for the assignment vector a:
ea(i),a(i+3)(I)2 0 withI- ={a(i for i E S

all the other nonzero elements of E greaterthan one. 1,N1,Nb. PE=(N1,N-4, ...,N-i,
i - 1, . .. 0) with E(a(1), a(2)) = E(a(2), a(1)) = E(a(l), a(3)) = E(a(2), a(3)) = E(a(3), a(2)) = 1, and N-

all the other nonzero elements of E greaterthan one.

C aE (N 1,

N-

25

... .,

-i

1,

-i

1,

N-

i -

1, ...

0) with E(a(i

1), a(i))

= E(a(i),

a(i - 1)) = 1, and all other nonzero elements of greaterthan one.

As we observe from the above examples, their common characteristicpropertiesare:

i. PE (a (k))>N-k
ii. P"--(a(k 1)) = N -

> 1 sikfN
k > N -

k 1, if

3k, 1,1

<

k < N. I , k,

such that
PE(a(k))
=

PE(a(k- 1)) =...

=

= PE(a(k

1)),

+ 1), ..., a(i + -1)) and I <, N - i. This implies that a is locally optimal. But, the graph G' has a unique directed Hamiltonian tour

and
E(a(m), a(n))

1for k -

1s m

s k, k - 1 - n

k,

542 / KOUVELIS AND KIM

and iii. all the nonzero elements of E that do not satisfy ii, are greaterthan one.

where E is a very small positivequantity.Then, the

resulting matrix E?O= (c

) is
andi =j+ 1,i>3,
andj =l,i3,

Ofori=j, o_
J

6. Corollary If there exists a permutation, of the a, integers{1, ..., NA such that the vectorpE satisfies the abovepropertiesi, ii and iii, then the heuristic KK-2willprovidethe optimalsolutionto the ULNL problemwiththe workflow matrixWthatinduced the development matrixE. of Example4. Consider a ULNLproblem with N = 4
and the same workflow matrix as in Example 3. The matrices E' = (es) and E = (El) are /0 1 2 -2\

andi 2,j= N
fi= andi= 1j=2 I +afori= 1,j,3,

andi=j- Ij >3, andi=Nj=2, andi= 2,j= 1

1otherwise. The resulting solution for the heuristic is a = (1, 2, 3, ..., N) with '(a) = ((N2/2)- 2N+2)e + M.
A better solution is a' = (2, 1, 3, ..., f'(a') = ((N2/2) - 2N + 3)E.So ZH -

N) with

E~~~~ E' d1 \2
/0 E (0 0

0 2 0 3

0 0/
1.10 1

Zopt

f'(a) - f'(a')
f'(a')

Zopt M-e

1.10 1.10 0

(N2/2

2N + 3)f
-*

0
1

\1.10 2.20 2.10 0 3.20

1.10 0/

Since M is a bounded positive integer, as e -.oo. Efw

0 then

Row Sums of E

We used 6 = 0.10. Application of KK-1 to matrix E produces the assignment vector a = (4, 1, 2, 3) with f'(a) = 16, which is the optimal solution. Observe that for the permutation a = (4, 1, 2, 3), the vector PE is (3, 2, 2, 0). The vector pE and the matrix /0
El

The motivationbehind KK-2 is summarizedin 2. Corollary KK-2is an attemptto generatea local optimal solution by positioningstation i with the largestnumberof nonnegative entriesel! in the first location. candidate Ourthirdheuristic is procedure as follows.
Heuristic Procedure KK-3

Step 0. Initializean N x N matrix W' by setting

W/ = W,whereW= (wej)is the workflow matrix.

E' I

1.10 1 1.10 0 1.10 1.10

0 0 1.10

the Step1. Calculate rowsumsR) andthe column sumsCj)of the matrixW'. Step 2. Determinea pair (k, 1) such that RCkl=
Max(Ij)Ij? RCij, where RCjj = (RI - C' )-(RI

satisfy the conditions of Corollary6. That is sufficient to guarantee the optimality of the heuristic in this case.

Theorem7. The heuristic KK-2for the ULNLproblemfor N> 2 can be arbitrarily evenif theentries bad, matrixare bounded of the workflow integers.
Proof. The worst case for the heuristic is a ULNL problem with the workflow matrix W0= (w?) as: G0 wo =

- Cj;)+ w; - w. Break arbitrarily. ties Assignworkstation to the first k 1 candidate locationand workstation to the lastone. Step 3. Eraserows k, I and columns k, I from matrix W'. Reset matrix W' to the remainingsuband matrix, repeat Steps1-3 untilthe resulting matrix W' consists of a single element or is completely exhausted.

for i =j, and i = j + 1, i > 3,

4. Proposition Heuristic procedure KK-3provides an optimalsolutionto the ULNLproblem N < 3. for Proof. For N = 2 the proof is an immediateconsequence of Theorem2. For N = 3 we considerthe generic assignment vector a = (i, j1 k) with i, j, k E
{1, 2, 3 1. Interchangingthe locations of stations i and

Le

and i= 2,j= IN 2f for i =1,j 3 M fori=2,j= 1

otherwise,

Layout in AutomatedManufacturingSystems /
Jo

543

~~~~~~~~~~~I-

Pair(i, j) (1,2) (1,3) (1,4) (2, 1) (2,3) (2, 4) (3, 1) (3,2) (3, 4) (4, 1) (4,2) (4,3)

Quantity RC1j 1 - 1 -3+2=-I 1-(-7)-6+4=6 1-5-4+6=-2 +1 1-(-7)-5+3=6 1 -5-2+2=-4 -6 -6 1 +4=-9 -7-5+2 +4 9 -Max

(a)

(b)

Figure2. Graph G'

for assignment vectors:

a) ao = (ioIo, ko);b) a = (i,j, k), a = ao.

k will changethe objective functionvalueby

e,j + eik + eik = (-l)Ie,21
+ (-l)

Ie23I + (-l)"Ie 3I

(1)

for appropriate values of the constantsa, y, y E {1, 2}. The heuristic assignsvaluesto i, i, k in sucha
way that the quantity {eij + ejk + eik} is maximized. If there exists an ao = (io, Jo, k1), such that ezit > 0, will pick it 3 ejOkk 0, and es0tk, 0, then the heuristic

4 Assignworkstation as the firstcandidate location and workstation as the last one. Erasecolumnsand 3 rows3 and4 fromthe matrix. resulting The submatrix
is

+ as its solution.In that case, Ie0ojo ejO + eiOkO 0 }> also. So, the resultingsolution is locally optimal. In that case, the corresponding graph G' (referto Figure2a) has a unique directedHamiltoniantour, since node iocan be visitedonly by node 0 and node 1 can visit only node 0. By Corollary in that case, 3, the validityof the propositionfollows. But, if such an ao does not exist, then the graphG' looks as in Figure2b for any feasiblevector(i, j, k). But, since wji < wi1, Wkj4 Wjk,and Wik < Wki, we get for any a:
f '(a) > wji + Wkj + Wik= LB

(0 3) R 3 Cl = 2 \2 o R2 = 2 C2 =3 Pair (1, 2) QuantityRCij: 1 -1 (2, 1) the vectoris a = Consequently, resulting assignment (4, 1, 2, 3), withf '(a) = 16, which is actuallythe optimalsolution. Theorem8. The heuristicKK-3 for the ULNLfor N > 3 can be arbitrarily bad. Proof. Considerthe followingULNL problemwith N = 4 and workflow matrix: 0 1 0 M\ 0 1 0 M 0

(2)
(3)

and f'(a)
-

LB

eki.

Wo=

The heuristic,in that case, selects a solution that

maximizes teij + ejk + eik}, which according to (1) is equivalent to selecting an eki = Mini Ie12 l, I e13 I,

where M > 1.

the Consequently, heuristicsolutionfrom (2) and (3) is optimal.

I e23
l

}.

Call Al = RI - C1, 1 = 1, ..., 4. Then l O, 3 = M,A 4 =-(M + 1),and RC12= 1 -0RC13= 1

1, 2

1 + M= M,
1M,

Example5. Apply KK-3 to a ULNL problemwith N = 4 and the sameworkflow matrixas in Examples 3 and 4.
/0 4 3 6 4\

M + 0

= RC14 1 + M + 1

M = 2,
1, 1,

RC23=0-M-M- 1 +M=RC24=0+M+ RC34= M +M+ R.-C,

Rf-Cf=1

4 3 0 1) 6 2 4 0

1 +0=M+

1 - 1 = 2M -Max.

R.-13
R'=9

C, =12
C =8

=1

R3 = 8 C3 = 15 RM-C'=-7 5 R4-C' R4= 12 C=-7

Sincethe heuristic breaks arbitrarily, heuristic the ties solution could be a = (4, 2, 1, 3) with f'(a) = 2M + 2. The optimal solution is a* = (3, 2, 1, 4)

544

AND / KoUVELIS KIM

=

with f'(a*)
EfWO-

2. So, = 2M+ 2-2 2

4. AN OPTIMALBRANCH-AND-BOUND SOLUTIONPROCEDURE

= ZH-Zopt

fopt

Z.M2

-As M-- +oo the EfX0 +oo. Observe that the proof holds even for bounded entries of the workflow matrix. Replace w?2= 23 W= E.Then

procedureis enThe proposedbranch-and-bound and relationships resultsof hancedby the dominance in sizedproblems, automated Section2. Forpractical is systemdesignthe procedure commanufacturing will be shownin Section6. efficient,as putationally in is The procedure described detailbelow.
Preprocessing Steps

M
Efwo e

As E

0, for a bounded M, then Efo

-- +oo

The proof of Theorem 8 might mislead one to believe that the relative magnitude of the entries in the workflow matrix determines the efficiency of KK-3. Example 6 demonstrates that this is not true. Example 6. Consider the workflow matrix W= (w=), where 0 fori=j r for2si<N, j=i-1 J 1 forIisN-1,j=i+1 with ra largepositive integer, ) and ea small positive quantity e otherwise

a. ApplyTheorem4a and b, if possible,to reduce asthe size of the workflowmatrixby appropriately workstations onlyincoming outgoing) with (or signing flows. b. From the workflowmatrix W, developmatrix the E1 = (es). Use the entriesof EI to construct sets
Fi =(j 96 i, j E- S: eIle' 0 1, i E S.

c. Checkif 3 i: IFi =N- 1 or IF = 0. If such an i exists apply Theorem3b and c to locate that workstation. d. Use any of the previouslydescribedheuristic to procedures obtainan initialsolution.The valueof the objectivefunctionfor that solutionwill serveas the initialupperbound UBALL.
Branching

Wsi=

It is easy to observe that the heuristic will produce the optimal solution for this example: a* = (N, N - 1,
N -2, .. . 1).

The motivating idea behind heuristic KK-3 is simple. Since the workstation assignment at the first and the last candidate locations determines the values of a relatively large number of entries in the objective function, we want to avoid the error of having a pair of workstations assigned to these locations in an incorrect order. The above error is captured in the quantity RCIj,which is the backbone of the heuristic. We report detailed results in Section 6 that KK-1 (or its variant), which takes into account only the relative magnitude of either row sums or column sums of the workflow matrix, does not perform adequately well. (See Section 6 for a detailed discussion of our results). So, we attempted to develop a heuristic that takes into account the relative magnitude of both row and column sums of the matrix. As the computational results indicate, KK-3, judged by the quality of solution and computational time requirements,is superiorto other heuristics for the ULNL problem.

to Branchon workstations be allocatedto a certain location.At levelj of thetree, workstations candidate j locations, havebeen assignedto the firstj candidate emanatefromeachnode,one for and N - j branches that workstation is a potentialcaneach unassigned location.In otherwords, didatefor the next available a partialassignment sizej a* = (a *( 1), .. ., a *(j)) of for hasbeendefined,andwe aresearching an optimal of completion thatpartialassignment.
Bounding

of Let us considera node with a partialassignment Forthe completionof aq* have we size q.
q-1 q q N

fI(aq)

= i=1 j=i+1 N-1

Wa*(j)a*(i)+

E
i=l1j=q+1

Wa(j)a*(i)

Z
i1+ I j=i+ I

Wa(j)a(i)

(4)

that Observe the firsttwo termsin (4) are fixedfor a given partialassignment. the quantitywe want So,

Systems / Manufacturing LayoutinAutomated

to minimize is
N N

545

'(aN-q)

i=q+1j=i+1
N-1
=

Ewijl(a(i),
N 5Wa)j)a(i) 1

a( ))

i=q+1j=i+

which reducesour problemto a ULNL problemof size N - q. If the reducedsize is 2 or 3 the KK-3 immediately providesthe optimalcompletionto the partial assignment size q. If thisis not the case,then of we proceedin our branch-and-bound (B&B)procedureby obtaininga lowerbound at the node, as we below. describe Considerthe submatrixWN-q = (Wij), i = q + 1,
. .., N, andj= q + 1, . . ., N. Call Nq = N- q. Select aq = (Nq - 1)Nq/2 smallest values of the elements in WN-q (excluding diagonal elements) and arrangethem in an ascendingorderto obtaina vectorIq*Then a lowerboundforf '(aNCq) is - Iq(i). Consequently,

to a b. Letus consider nodecorresponding a partial assignmentaq* of size q 5 N with a*(q) = i. If F' (a*) = Fi n (N/A*) = X, then fathomthe node. c. If IF'(a *) = 0, the workstationi has to be located at the last candidate location in an optimalpartialcompletionaq 1,c (i.e., a(N) = j). If F' (a*) I= Nq, thenin an optimalpartial completion of a_1, c we will havea(q) = i. Implementation these enhancesthe powerof the B&Bproceobservations paths a dureby eliminating largenumberof potential in the tree. the we purposes consider Example7. For illustrative proof application our proposedbranch-and-bound presented layoutproblem cedureto the 4-workstation in Examples 3-5. 0 3 6 2 05 ~ 4 23 0 5 2 ) 6 2 4 0 1 0 -2 {-2 2 0 0 1 2 -2\ 2 01 0 -3). 3 0

f '(aq*) >

q q-1 q + E E Wa*(j)a*(i)E
i=1 j=i+I
aq

Wja*

i=1 jEN/A*

+ EIq(i),
i=1

whereA* =k: a*(i) = k,i=

1,. . .,q.

To check if the resultinglower bound can be attained,the following procedureshould be used:

Permute the integers 1, ..., aq in such a way that

elementsof the vectorIq comingfromthe same column of the matrixWNq are next to each other,and the columnwiththe mostelementsin Iqis represented in the firstleftmostpositionsof the vector,the second one in termsof the numberof elementsin Iq immediately and vector follows, so on.Letuscalltheresulting II = (I""),i = I + 1, . . ., N), where: is a permutation
of the integers {q + 1,
...,

by We use as an initialsolutionthe one provided the column variateof KK-1in Example1. The value of the objective function,whichbecomesourinitial UB, is 17. From matrixE we can immediatelyobservethat | F4 I = 3 and, consequently,station 4 should be location.Also IF3 I = 0, locatedin the firstcandidate so station 3 will be located in the last candidate location. But, for the purposeof our example,we of in proceed the development the treeandthe bound The develignoringthese observations. calculations tree oped branch-and-bound and all relevantlower bound calculationsare presentedin Figure 3. The resultingoptimalsolutionis (4, 1, 2, 3). Note that, evenwithoutthe observations comingout of the local tree optimality conditions, the branch-and-bound examinedonly 8 out of the 40 possiblenodes that

N) and I"") denotes

-

subvectors with all their elementscoming from the samecolumn of WNq. Call II( 1 If 6 = (6i) =
(Nq- 1, Nq - 2, ... ., 1, 0) and I"") = (wj,(i), j 0 0(1), ..,0(i - 1)), i = q + 1, .., N, then the above
2+4+6+1+2+2-17>UB

calculated lowerboundcorresponds a feasible workto

station assignment (a*(i) . . . a*(q)13(q + 1) . . .(N)),

A3+3+2+1+4+4-17>UB

2 4+2+1+244+3-16F 6+5+4+2+2+2-23>UB 4+2+1+2+4+3-16 4+2+1+2+4+5-18>UB

and the corresponding functionvaluecould objective be used, if appropriate, updatethe currentupper to bound.
Fathoming Tests

4+2+1+2+3+3-15

4+2+1+3+3+4-17>UB

4+2+1+5+6+2-20>UB

Candidate LocationI

Candidate Location2

Candidate Location 3

a. Fathoma node if its lowerboundis greater than the current upperbound.

Figure3. Brand-and-bound tree for the example problem.

AND 546 / KOUVELIS KIM

an exhaustiveenumerationprocedurewould have examined.

7

SI

S 3

S9

~~~~~~~~~0~//

PRINCIPLEFOR LARGE 5. DECOMPOSITION MATRICES WORKFLOW

S.
S3

Let us considerthe class of workflowmatrices W in represented Figure4. For the set of stationsS = Si U S2 U S3 holds that wuj= 0, for i E SI, j E S2,
and i E S2,j E Si. Call W1= {wij:ij E S U S3}, and W2 = {w,1, i, j E S2 U S3}. The two ULNL problems,

are matricesWIand W2,respectively, with workflow

completely independent if S3 = 4. In certain cases, with S3 $ 0, a simple decomposition principle allows

S2

us to obtainthe optimalsolutionto the ULNL probmatrixW. lem withworkflow matrix W strucTheorem 9. Considerthe workflow turedas in Figure4 withS3 = {j). Let us call a* the to vector the ULNLproblemwith optimalassignment
workflow matrix WI, where a*(k)
=

j and a*

4. Figure Schematic representationof a specially workflow structured matrixW.The shaded areas representnonnegative(mostly positive) elements. The above structure is referredto as a two-block (subproblem) workflow matrix.

subvectors. Call )j(c1),withb1,c, as theappropriate (b1 vectorto the ULNLproba* the optimalassignment
lem with workflowmatrix W2, where am*y() = j and suba2 = ((b2)j(c2)), withb2, c2 as the appropriate

But for workstationassignmentvector, a, for the wholeproblem have we

f(t) =

vectors. Then, an optimal solution to the ULNL matrixW is a* = (a*(i)): problemwithworkflow a*(i) b,U) b2(i-k+ 1) j c,(i- (k+ ay)+1) c2(i-(k+ ISI1)+ 1) l< ,k ki k ,i ,k + i -k+-yk+yo is
<1ISI

E
iES;US

E
mES' US'

I(a wiml (i),

a(m))

=f

(a,)

+f2(a2)

I y- 2 1 k+ I SI I-1
+ IS21 +

since wmi= 0 form ES1, i ES2, and m ES2, i ES,. If ao*and a* are the corresponding optimalwork-

stationassignment vectorsfor the two subproblems, observethat for a*, the corresponding workstation assignment vectorto a*, we have
fi(a*)=fi(a*)

and

k+ ISIi

1.

f2(a*)=f2(a*).

withthe has The problem multipleoptimalsolutions, assignmentvectors having the same corresponding as relativeorderof workstations the optimalassignmentvectorsa* and a* a workstationassignmentvector for the first subproblem(matrixWI),then,
fi(ai)=
iEs; mES

Consequently, a * (or its correspondinga*) is optimal for the problem. The propertiesf (a) = f,(a *) and f2(a) =f2(a *) hold for any workstation assignment

vector that preserves relativelocation of workthe stationsi E S. (i E Sf) with respectto theirrelative
locations in ao*(in a*).

Proof. Call S = S1 U {j}, and S' = S2 U {j}. If is a,

Ewiml(ai(i),ai(m)).

Forthe secondsubproblem (matrixW2),

f2 (a2)i=

ES wimmI(a2(i),
S iGE GES'2

a2(M))

Observethat the above principlecan be extended to casesin which IS3 I > 1, underthe conditionthat i the resulting relative locationof workstationsE S3 is the sameas thatin a pairof optimalsolutionsforthe ULNL problemswith matricesWI and W2,respectively. The principleis easy to extend to workflow with morethantwo blocks(subproblems). matrices Let us call W. = Iwij, i, j E S.} and W' =
Iwij, i,j E S2}.

LayoutinAutomated Manufacturing Systems / a structured Corollary8. Consider two-block specially matrix W, withthe additional property that Wim
ieS3,meSi,andieS2,meS3.Leta' anda'
=
Stations a*(i), . Stations

547

Sttosa*(J),

1?J<.y

0,
be
Cell [I 1 tion Statio Cell2

theoptimal assignment vectors the ULNL for problems with workflowmatrices W. and W, respectively. Then, the optimalassignmentvectorto ULNL with matrixW is
a* =
((a')(S3)(a'))

C
k<~IsSi

Cell 2

Stations

al(i),

Stations

a*(i) 7<i.'SS31

Figure5. Unidirectionalmaterial handling system designwithtwo load/unloadstations.

a structured Corollary9. Consider two-block specially that matrix W, withthe additional property Wim = 0, ieS1, mreS3, and i ES2, me S3. Let a anda' be the theoptimal assignment vectorsfor ULNL problems with workflow matrices W' and W, respectively. Then,the optimalassignmentvectorto ULNL with matrixW is
a* =
((S3)(a')(a')).
Station

w.-~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~
V

L/U

Corollary 10. Considera two-block speciallystruc-

tured matrix W. with the additionalpropertythat wim = 0, i E S1, m E S3, and i E S3, m E S3. Let a, and a' be the optimal assignmentvectors the for ULNLproblems withworkflow matricesW. and WL respectively. Then, the optimalassignmentvectorto ULNLwithmatrixW is

Figure Unidirectionalmaterial handling system 6. designwitha singleload/unloadstation.

6. COMPUTATIONAL RESULTS

a*
=

((af )(S3)(a

').

is Thedecomposition principle extremely important for real-world of implementation automatedmanufacturing systems.Most of thesesystemsaredesigned to with according cellularmanufacturing principles, only a few machinessharedamong manufacturing cells.Thismanufacturing environment leadsnaturally to workflowmatriceswith the block structurewe Evenformanufacturing withdense discussed. systems workflowmatrices, can applythe decomposition we principle. Theorem5 assures out of sucha matrix that we candevelopan equivalent withat least50% matrix for Sucha matrix sparsity our optimization purposes. can easilybe brought on into a blockstructure, which the decomposition can principle be applied. The decompositionprinciplealso has certainimportantimplicationsfor the design of the unidirectionalmaterial handling system.Fora manufacturing the systemwith a workflowmatrixsatisfying conditionsof Theorem9, two feasible designsof a unidirectionalloop conveyor of system,consisting twodisjoint in The loops,arepresented the nexttwo figures. design in presented Figure5 uses two load/unloadstations, whilethe one in Figure6 needsa singleL/UL station.

In this section, the performanceof our heuristic algorithms and the computational efficiencyof the branch-and-bound procedure discussed. three are The constructive heuristicprocedures KK-1, KK-2, and KK-3,a standard pair interchange and the heuristic, block interchange procedure(Afentakis1989) were programmed FORTRAN77 and testedon a VAX in 11/780. The optimalsolutionfor the testedproblems wasgenerated fromthe branch-and-bound procedure developed this paper,whichwas also implemented in on the samesystem.All test problems wererandomly For generated. the workflowmatrixits densitywas firstspecified densitywas measured a percent(the as age of nonzeroelementsin the matrixover all nondiagonalelements).Then the nonzero entrieswere generated randomnumbersin the range[0, 200]. as Fora specificsize of the workflow matrixand a given densityof it five test problemswere generated. The heuristicswere tested againstthe optimal solution generated the B&Bprocedure. by TableI summarizes the results. Boththe worstobserved performance and the averageperformance each heuristic(over five of test problems) reported eachcase. for are From Table I, we see that KK-3 provideshigher qualitysolutionsthanthe othertwo heuristics, KK-1, KK-2.The pair interchange heuristichas the worst performanceamong all the heuristics.The block

548 / KoUVELISAND KIM Table I

Heuristics Performance Comparison (Deviation = (ZH-Z-p,/Zopt)
PairInterchange BlockInterchange HeuristicKK-1 HeuristicKK-2 HeuristicKK-3 Heuristic Heuristic Density Worst of Worst Worst Worst Worst No. of Workflow Average Observed Average Observed Average Observed Average Observed Average Observed Workstations Matrix Deviation Deviation Deviation Deviation Deviation Deviation Deviation Deviation Deviation Deviation 4 0.99 0.75 0.50 0.25 0.1 0.99 0.75 0.50 0.25 0.1 0.99 0.75 0.50 0.25 0.10 0.99 0.75 0.50 0.25 0.10 0.99 0.75 0.50 0.25 0.1 0.99 0.75 0.50 0.25 0.10 0.99 0.75 0.50 0.25 0.10 0.01 0 0.05 0 0 0 0 0.02 0.03 0.025 0.08 0.05 0.04 0.15 0 0.01 0.21 0.09 0.11 0.14 0.04 0.22 0.24 0.1 0.11 0.1 0.12 0.1 0.18 0.38 0.09 0.1 0.25 0.48 0.25 0.07 0 0.09 0 0 0 0 0.05 0.06 0.06 0.12 0.07 0.05 0.24 0 0.02 0.32 0.19 0.135 0.25 0.06 0.38 0.37 0.19 0.24 0.2 0.23 0.15 0.26 0.45 0.14 0.19 0.39 0.62 0.4 0 0.1 0.3 0 0 0.1 0.1 0.35 0.4 0.42 0.09 0.05 0.05 0.2 0.04 0.09 0.2 0.2 0.015 0.18 0.06 0.3 0.32 0.6 0.52 0.12 0.4 0.5 0.6 0.8 0.1 0.25 0.2 0.4 0.51 0 0.3 0.45 0 0 0.16 0.18 0.46 0.5 0.5 0.135 0.08 0.07 0.3 0.06 0.11 0.3 0.24 0.02 0.25 0.09 0.52 0.52 0.81 0.7 0.2 0.54 0.71 0.89 1.01 0.2 0.37 0.3 0.6 0.06 0 0 0.01 0 0 0 0 0.02 0.025 0.022 0.01 0.03 0.03 0.04 0 0.01 0.06 0.07 0.01 0.055 0.025 0.05 0.05 0.067 0.11 0.06 0.06 0.065 0.12 0.11 0.04 0.09 0.05 0.1 0.06 0 0 0.025 0 0 0 0 0.05 0.05 0.05 0.03 0.06 0.046 0.06 0 0.023 0.1 0.11 0.024 0.1 0.05 0.09 0.1 0.15 0.2 0.11 0.12 0.15 0.2 0.2 0.07 0.19 0.09 0.2 0.1 0.2 0.2 0.8 0.3 0.5 0.25 0.1 0.9 0.2 0.4 0.4 0.35 0.8 0.25 0.45 0.5 0.4 0.8 0.35 0.4 0.5 0.4 0.85 0.3 0.4 0.8 0.85 0.99 0.98 0.45 1.1 1.5 0.6 0.5 0.4 0.6 0.5 0.95 0.45 0.6 0.65 0.25 1.2 0.3 0.6 0.7 0.5 1.35 0.4 0.6 0.8 0.5 1.2 0.5 0.7 0.85 0.6 1.5 0.6 0.7 1 1.2 1.6 1.6 0.6 2 3.1 0.9 0.8 0.6 0 0.005 0 0 0 0 0 0.03 0.005 0.02 0.005 0.01 0.02 0.01 0.01 0.01 0.02 0.05 0.015 0.01 0.02 0.025 0.06 0.04 0.05 0.05 0.05 0.05 0.06 0.06 0.05 0.05 0.06 0.08 0.09 0 0.01 0 0 0 0 0 0.05 0.01 0.05 0.01 0.02 0.05 0.02 0.02 0.02 0.03 0.08 0.03 0.02 0.03 0.035 0.1 0.06 0.1 0.08 0.09 0.09 0.1 0.12 0.08 0.095 0.1 0.12 0.15

10

12

interchangeheuristichas the best performancein most cases, with KK-3 a close second. It would be unfair to judge the different heuristics by only the solution quality, without much regard to computational time requirements. Heuristic KK-3 can, in most cases, be executed ten times faster than the block interchange heuristic. Actually, KK-1, KK-2, and KK-3 for workflow matrices of a size up to 20 x 20 can be executed in less than three seconds of CPU time. None of our proposed three heuristic procedures guarantees the generation of a locally optimal solu-

tion. It was interesting to observe that when we took the heuristic solution of KK-3 and applied it on the standard interchange heuristic procedure, very few station interchangeswere involved (<3 in most cases). The resulting solution was, in most cases, the best heuristic solution for the test problem. These results are summarized in Table II. The branch-and-bound procedure was computationally efficient for the layout design problem. On all test problems this procedure required less than 20 CPU minutes for generatingan optimal solution. The

Layoutin Automated Manufacturing Systems / 549 Table II AveragePerformanceof the Best HeuristicsOver 175 Test Problems
No. of Workstations 4 5 6 8 9 10 12 HeuristicKK-3 CombinedWith Pair Interchange at LastSteps 0.001 0.01 0.015 0.015 0.04 0.06 0.062 BlockInterchange Heuristic 0.001 0.011 0.011 0.021 0.039 0.054 0.066

HeuristicKK-3 0.002 0.013 0.022 0.041 0.06 0.08 0.068

Table III ComputationalPerformanceof the Branch-and-Bound Procedureon VAX 11/780

No. of Workstations -,< 3 4-6 7-9 10-12 CPU Time (Sec.) <1 <30 <300 <1200

results are summarized in Table III. We decided to test small to medium sized problems (,<12 stations) for two main reasons: most implementations of automated manufacturing systems (particularly FMS) have 5-8 workstations;for larger systems, our observations on the decomposition of large workflow matrices apply (see Section 4), and the resulting size of the subproblemsto be solved is less than 12. 7. CONCLUSIONS Unidirectional loop network layouts have been implemented extensively in automated manufacturing environments. We have studied the appropriate arrangements of machines around such a simple closed loop under a commonly used operational strategyfor such systems. This operational strategy requires all parts to enter and exit the system at a single load/ unload workstation. Under this strategythe objective of material handling cost minimization is equivalent to that of minimizing the total number of partspassing through the load/unload facility. Using this fact, and a set of theoretically derived dominance relations, we developed heuristic procedures to address the problem. Our computational results indicate that our heuristics are nearly optimal for realistically sized problems. For small to medium sized problems our

branch-and-boundapproach can be used to optimally solve the problem. For large sized problems, with a special structurein their workflowmatrix (block structured matrices), the decomposition approach developed in the paper can be used to drastically reduce their size. There are other layout types that have been implemented to some extent in automated manufacturing systems (referto Heraguand Kusiak). Furtherresearch is needed on analyzing the machine arrangementfor these layout types under appropriateoperationalstrategies. The authors have undertaken research on the study of single-rowand double-row layout implementations in automated manufacturingenvironments.

ACKNOWLEDGMENT We thank Dr. Francisco Prieto for valuable discussions on the problem. Mr. Birendra Mishra devoted significanteffort to coding the various algorithms,and we sincerelythank him for that. The three anonymous referees provided insightful comments on an earlier version of the paper that significantly improved the presentation of our work.

REFERENCES 1986. A Model for Layout Design in Flexible Manufacturing Systems. In Modellingand Design of Flexible Manufacturing, Kusiak (ed). A. North-Holland, Amsterdam. AFENTAKIS,P. 1989. A Loop LayoutDesign Problemfor Flexible ManufacturingSystems. Int. J. Flexible Mfg. Syst. 1, 175-196. ARMOUR, G. C., AND E. S. BUFFA. 1963. A Heuristic Algorithmand SimulationApproachto the Relative Locationof Facilities.Mgmt. Sci. 9, 294-309. DREZNER, Z. 1980. DISCON: A New Method for the LayoutProblem.Opns.Res. 28, 1375-1384.
AFENTAKIS, P.

550 / KoUVELISAND KIM

GAREY,M. R., AND D. S. JOHNSON. 1979. Computers F. 1966. Quadratic HILLIER, S., AND M. M. CONNORS.

A and Intractability: Guide to the Theory of NPCompleteness. H. Freeman,New York. W. GILMORE, P. C. 1963. Optimal and SuboptimalAlgorithms for the Quadratic Assignment Problem. SIAMJ. 10, 305-313.
HERAGU, S., AND A. KUSIAK.1988. Machine Layout S.

AssignmentProblem:Algorithmsand the Location of IndivisibleFacilities.Mgmt. Sci. 13, 42-57.

KIRAN, A. S., AND S. KARABATI. 1988. The Station

Problemin FlexibleManufacturing Systems.Opns. Res. 36, 258-268. HILLIER, S. 1963. Quantitative F. Tools for PlantLayout Analysis.J. Indus. Eng. 14, 33-40.

Location Problemon Unicyclic MaterialHandling Networks. Working Paper, ISE Department,Universityof SouthernCalifornia,Los Angeles. LAWLER, L. 1963. The QuadraticAssignmentProbE. lem. Mgmt. Sci. 9, 586-599.
SAHNI, S., AND T. GONZALEZ.1976. P-Complete

Approximation Problem.J. ACM 23, 555-565.