Product assignment in flexible multilines : Part 2 - Single-state systems with no demand splitting

330

B3S5 ST*

Faculty Working Paper 93-0107 ^93: 10? copy 2

^— "Y

\

^;

->

Product Assignment in Flexible Multilines
Part 2: Single Stage Systems with No Demand Splitting

Udatta 5. Palekar Narayan Raman

Department of Mechanical Department of Business Administration
and Industrial Engineering University of Illinois

University of Illinois

Bureau of Economic and Business Research

College of Commerce and Business Administration

University of Illinois at Urban a-Champaign

BEBR

FACULTY WORKING PAPER NO. 93-0107

College of Commerce and Business Administration

University of Illinois at (Jrbana-Champaign

January 1993

Product Assignment in Flexible Multilines
Part 2: Single Stage Systems with No Demand Splitting

Gdatta S. Palekar
Department of Mechanical and Industrial Engineering

Narayan Raman
Department of Business Administration

Digitized by the Internet Archive

in 2012 with funding from

University of Illinois Urbana-Champaign

http://www.archive.org/details/productassignmen93107rama

Product Assignment in Flexible Multilines
Part 2: Single Stage Systems with No Demand Splitting

Udatta S. Palekar

Department of Mechanical and Industrial Engineering

University of Illinois at Urbana-Champaign

Urbana, Illinois

Narayan Raman

Department of Business Administration

University of Illinois at Urbana-Champaign

Champaign, Illinois

January 1993

ABSTRACT

This study deals with the multiline design problem in an automated manufacturing system. This
system is identical to one considered in a companion work (Raman and Palekar 1993); however, we
deal with the case in which each product is required to be assigned to exactly one line. We show
that this requirement renders the multiline design problem NP-complete. We construct several
lower bounds for the problem. In so doing, we show that a greedy procedure presented in the
companion study, for the case in which a product can be assigned to multiple lines, yields a strong
lower bound to the problem considered here. We construct heuristic and exact solution methods
for this problem and report our computational experience with these methods. These experiments
show the efficacy of the suggested heuristic approach as well as the proposed lower bounds.

We first recapitulate the manufacturing system addressed in the companion study (Raman and
Palekar 1993) that extends to this paper. We consider a facility that manufactures a set Af of
N products in medium to large volumes. Each product has an associated processing time and a
demand rate. These products are processed on one or more lines, each line comprising of one or
more identical machines operating in parallel. These machines are flexible in the sense that they
can switch from one product to another with negligible changeover time. Products assigned to
the same line share the same cycle time that equals the longest processing time of the products
assigned to that line. Given the costs for opening a line and procuring a machine, the objective of
the flexible multiline design problem is to determine a minimum cost partition of M that assigns
each subset to exactly one line. In this paper, we consider the problem in which the subsets are
mutually exclusive which corresponds to the requirement that each product be produced on exactly
one line. Such a constraint is imposed in practice for reasons of technological requirements, ease of
supervision and limitations on available tooling.

This paper is organized as follows. The problem is formulated in §1. We show that the multiline
design problem is NP-complete. Note that the FMD1 problem considered in Raman and Palekar
(1993) which permits the demand of a product to be split across multiple lines is solvable in
polynomial time. In §2, we present an efficient graph representation of the problem. In §3, we
develop several lower bounds. We show that a greedy procedure presented in Raman and Palekar to
solve FMD1 yields a lower bound to the problem considered here. We construct a heuristic solution
method in §4, and an exact algorithm based on implicit enumeration in §5. Our computational
experience with these solution approaches as well as the lower bounds is discussed in §6. We
conclude in §7 with a summary discussion of the main results of this paper.

1 Introduction

An integer programming formulation of the multiline design problem is given below. First, we
restate the notation used in Raman and Palekar (1993). It is useful to note that the cycle time of
any line in a feasible solution must equal the processing time of its pivot product, i. e., the product
with the longest processing time that is assigned to that line.

M = the set of products, and \Af\ = N
F\ = fixed cost per line

F2 =

Pj =

Ji =

Ij =

dj =

A =

n

7T(1)

Hi =

fixed cost per machine

processing time of product j, j € Af

set of products with processing times greater than or equal to i, {j\pj > Pi, j G Af}

set of products with processing times less than or equal to j, {i\pi < Pj, i G A/}

per period demand of product j, j £ Af

available time per period on any machine

cycle time of line /

index of the pivot of line /

index of the line for which j is the pivot

the number of machines required at line X(j)

As in Raman and Palekar (1993), we assume that A > p3, Vj £ Af so that |_^/PjJ
multiline design problem can be stated as

FMD2

A/pj. The

subject to

where

and

N

Minimize Z = /XFiyj + i^rc?)

^T x3i = 1, i e Af
jeJ,

Pj f J2 dixji ) ^ Anji 3 € Af

xji <yj, i,j eAf

Xji g {0,1}, i,j6 Af
yj G {0, 1 } ; n j > 0, integer, j G Af

Vj = \

1, if a line is opened with pivot j
0, otherwise

Xj{ —

1, if product i is assigned to a line \(j)
0, otherwise.

(1)

(2)

(3)
(4)
(5)
(6)

Equation (2) insures that the demand of each product is fully assigned, and a product is assigned
only to lines with cycle times no less than the processing time of the product. Constraint (3)
requires that all product-to-line assignments be capacity feasible. Constraint (4) insures that the
fixed cost of opening a line is accounted for. Finally, constraints (5) and (6) specify the nature of
the variables.

FMD2 differs from the FMDl problem discussed in Raman and Palekar (1993) in that it requires
each product to be assigned to exactly one line. It is easy to see that the total number of machines
required on any line / with pivot j is given by

nj =

A

where \f\ is the smallest integer greater than or equal to /. The unused capacity on this line,
hereafter the remnant, is

N

Rj = Arij/pj - f ^2 dixJi J •

While Raman and Palekar show that FMDl is polynomially solvable, the following result indicates
that it is unlikely that an efficient solution exists for FMD2.

Theorem 1. FMD2 is NP-complete in the strong sense.

Proof: FMD2 is clearly in NP. We show that the 3-PARTITION problem which is known to
be NP-complete in the strong sense (Garey and Johnson 1979) is reducible to FMD2. Consider an
arbitrary instance of 3-PARTITION given by a set Q of 3q elements of size S{ for each i 6 Q, and
a positive integer B such that i) 5/4 < s, < 5/2, Vz £ Q, and ii) YiieQSi = $&• ^ne recognition
version of the 3-PARTITION problem is stated as: Is there a partition of Q into q disjoint subsets
(Qi, Q2, • • • , Qq) such that £i€Cj at = B, for 1 < j < qt

The equivalent instance of FMD2 is:

\M\ = 4q

j, j = 1,2,...,Q

Pj =

1, j = q+l,q + 2,...,4q.

qB, j = l,2,...,g

A = qB + B
Fx = 0.

Given an instance of 3- PARTITION, this instance of FMD2 can be constructed in polynomial time.
We show that for this instance, Z < F2q{q + l)/2, if and only if 3-PARTITION has a solution.

Denote the set of products j = l,2,...,g by M\, and let A/2 = M\M\. First suppose that 3-
PARTITION has a solution. The required solution for FMD2 is constructed by forming q lines
such that each product j £ A/"i is a pivot. The number of machines required individually for any
product assigned to a line with pivot j is

jqB

(lj =

and the resulting remnant on this line is

(qB + B)

(7)

Pi

The total number of machines required under this assignment for products in M\ is Ya=\ ' =
9(9 + l)/2. Clearly, if 3-PARTITION has a solution, A/2 can be partitioned into q disjoint subsets
A/21, A/22, • • -<,Miq such that ^2jetf2. dj = B, I = 1,2, . . .,q. Each of the q lines is assigned one of
these subsets to give the desired solution with cost Z = F2q{q + l)/2.

Next, we show that if Z < F2q(q + l)/2 under an assignment a (say), then 3-PARTITION has a
solution. First, note that because p, > pj, i £ Af\,j £ A/2, there must be at least one line in a that
has a pivot which belongs to M\. [In particular, q must be a pivot.] More generally, suppose that
a has L +T lines, of which the pivots for the first L lines belong to M\. Clearly, L < q. Let C\
be the set of products assigned to line /, and let C) = {j\j £ Af\ C\ £/}, / = 1,2, ...,X, denote a
subset of Ci that belongs to set Af\ as well. Also, let 7/ be the cardinality of CJ. First consider the
assignment of products in M\ in these L lines.

Lemma 1. Cj = {/}, / = 1, 2, . . ., L, and hence, L = q.

Proof: Let the products assigned to line / under a be

C] = {*i,*2» — >*-yi}

such that *i < t'2 < ••• < £7,. Since the processing times of products in M\ are the same as their
index and since a product in M\ can only be assigned to a line with a pivot with an equal or
higher index, it follows that i-y, < /. Now consider an alternative assignment a' in which products
ii,*2, • • • , 2-y,-i are pivots for their individual lines. From (7), the total number of machines required
under a' for these 7/ products is

m = z'x + 1*2 + h *-y|— 1 + i-n

< (l - 1)(7, - 1) + /.

(9)

Note that (9) is satisfied as an equality only if either Cj = {/} or Cj = {I — 1,1}. The number of
machines required on line / under a is given by

ni =

qB + B

, hi

hi -

9 + 1

> If 1 — (7/ - 1), because I < q + 1

> (/ - 1)(7, - 1) + /

> n\.

Hence,

L L

Y, n< ^ E n'i = l + 2 + • ■ • + <? = <?(<? + l)/2.
/=1 /=1

But Z < F2q{q + l)/2 implies that

and therefore,

5>i<4f(?+l)/2,

J>/ = 9(9+l)/2.

Furthermore, T = 0, and either Cj = {/}, or C] = {I - 1, /}, / = 1,2,...,//,

Now, suppose that £] = {j — 1,7} for some j, 1 < j < L. Then

2j<z£

Uj =

qB + B
2j

2i-

9+1

Because j < q + 1, either rij = 2j or rij = 2j — 1. But if rij = 2j, then

L J-2 q

J>z > X>; + 2j + E n'

= 1+2 + . . . + (j - 2) + 2j+(jf + 1) + . . . + 9
> ?(<?+l)/2

which is not feasible. Hence, it must be true that rij = (2j — 1). The capacity available on line j
for assigning products in A/2 is

CAP(i) = [(2j - 1)(95 + 5) - 2i</5]/j < 2B units. (10)

From (8), the capacity available on any line /, such that Ci = {/} is B units. Hence, the total

capacity available on all L lines for products in M2

L
J2 CAP(l) <2B + (L- 2)B < qB.

1=1

But the minimum capacity required for products in M2 is

\q 3q

j=q+l « = 1

which implies that Cj ^ {j — l,j}, and the only feasible configuration under a is C\ — {/}, / =
1, 2, . . . , X, and therefore, L = q. □.

Now consider the products in A/2. Given that there are <? lines, each with a residual capacity of B
after assigning products in A/"i, a feasible solution to FMD2 can exist only if A/°2 can be partitioned
into q disjoint subsets A/21, A/22, • • -,A/29 such that 5Zj€JV2i dj = B, I = 1,2, . . .,9. But this implies
that 3- PARTITION has a solution. □

Note that FMD2 is NP-complete even when there are no line costs, i.e., Fi = 0.

2 Problem Representation

Without any loss of generality, we assume in the rest of this paper that products are indexed such
that if i < j, then pi > pj. Similar to the representation of FMD1 in Raman and Palekar (1993),
it is possible to represent FMD2 on graph Q = (V,£) shown in Figure 1. In this graph, node V{j,
which is depicted as ij, represents an assignment in which product j is produced on a line with

(

pivot i. Because Vij is feasible only if pj < p,, the graph is upper triangular. We append a dummy
source node S and a dummy sink node T to Q.

Arc-set S — {Efj } consists of arcs connecting contiguous nodes VtJ and Vu<J+i. S can be
partitioned into disjoint subsets H, B and T where H is the set of horizontal arcs (h-arcs) of the
form E\f , while B is the set of backward arcs (b-arcs) of the form E^J+1 where u < i. T comprises
the forward arcs (f-arcs) Efj such that u > i. Without any loss of generality, we assume that
all arcs leading from 5 and leading into T are f-arcs.

INSERT FIGURE 1 HERE

Raman and Palekar (1993) show that the following result holds for FMDl.

Sequential Assignment Property (SAP): There exists an optimal solution with the property that if
Xji > 1, then Xjq = 1 for q — j -f 1, j + 2, . . .,i — 1.

However, if a product can be assigned to only one line, the remnant available at any line cannot be
utilized for meeting the partial demand of a product from another line. In such a case, it is easy
to show that the sequential assignment property is no longer dominant for FMD2. In the absence
of this property, there is no "natural" order of products assigned to any line because the optimal
solution can consist of one or more b-arcs. However, Q is a sufficient representation of FMD2 in
the sense that any solution to FMD2 can be depicted as a path from S to T with no cycles, and
the optimal solution can be posed as a shortest path problem on Q. Consequently, in order to keep
the notation simple, we assume without loss of generality in the rest of the paper that any product
is assigned only after all lower numbered products are assigned, and define the arc costs as well as
the remnants accordingly. This essentially enables us to scan Q from left to right.

Following this approach, we now determine the cost of each arc in Q. Consider node Vjk in Q.
The number of machines Mjk required at line X(j) corresponding to this node will only consider
products j,j+ 1,. . .,&; hence

Pj (Eu=j duxJU)

Mjk =

The remnant available at Vjk is

A

r]k ~ \ 2^/ duXju j .

AMjk

<U=J

j,k+l

The cost of h-arc £jjj. "*" is

and the cost of f-arc Ej£1,k+1 is

#+1 = F*

Pj (<4+i - rjk)

(ID

.*+!.*+! =Fl+F2

Pk+idk+i

(12)

Note that the costs of all f-arcs incident on node Vjt+i,jt+i are the same. It is also easy to see that
a pivot product must be assigned to its own line in an optimal solution because otherwise, the
products assigned to this line are being produced at higher than required cycle time. Consequently,

Remark 1. If an optimal path consists of an f-arc E^ , u > j, or a b-arc Ejj. , u < j, then
this path must pass through Vuu and V3J as well.

It follows that

W.A+1

Corollary 1. If the f-arc E-Jk , I ^ k + 1 is contained in any optimal path, then such a path
must include one or more b-arcs as well.

The cost of arc £a+ , I ^ k + 1 then equals

Cjk ~ *2

Pl(dk+l ~ rik)

(13)

3 Lower Bounds on FMD2

In this section, we construct four lower bounds for FMD2. The first bound is obtained by relaxing
the integrality requirements on the number of machines required. The second bound is obtained
by allowing a product to be produced on multiple machines, and solving the resulting FMD1
problem by the Greedy heuristic discussed in Raman and Palekar (1993). The other two bounds
are derived by relaxing constraints (2) and (3), respectively, and solving the resulting Lagrangean
problems.

3.1 Fractional Machines

The first bound LB1 is obtained by relaxing the integrality requirement for nj in constraint (6).
In any optimal solution, constraint (3) is then satisfied as an equality. In particular,

n3 = s.CjjXji, where Cji = dzpj/A.

FMD2 then reduces to
FMD2-FM

subject to

LBl - min MT Fxy3 + ^ Yl fajiXji

j «

Y. X3i = l

Xji < Vj

Xjiiyj e {0,1}.

Proposition 1. There exists an optimal solution to FMD2-FM that follows SAP.

PROOF: Let a\ be an optimal solution to FMD2-FM that does not have this property. Then
there must be a pair of products s and t, s < t, such that s is assigned to line X(j) and t is assigned
to line A(A:) with k < j. Let a2 be identical to a\ except in that t is produced on line \(j). Let
Z(-) denote the cost of solution (•). Then

Z(<t1) - Z(a2) = — jL = (pk- P])— > 0.

Hence, 02 is optimal as well. Repeating this argument for all such pairs (s, t) gives the desired
result. □

Now consider the following problem discussed by Corneujols, Nemhauser and Wolsey (1990).

Tree Partitioning Problem: Suppose G — (A/*, E) is a tree graph, and D is a |AT| by \M\ matrix with
elements Di3 that represent the distance between nodes v,- and vJt for all V{,Vj 6 A/. Let the weight
of any subtree G3 — (Wj,£j) be w(Gj) = maxv e^ (^2v e^» DkA. Determine the partition of G
into subtrees that minimizes the sum of subtree weights.

Corneujols et al. present a dynamic programming algorithm that solves the tree partitioning
problem in 0(|AH2) time. Given the sequential assignment policy, FMD2-FM can be modeled
as a tree partitioning problem as follows. Let AT = {t?i,. . ., vjv} denote products 1 through N,
and let S = {-E^'"1"1 : i = 1, 2, . . . , N — 1} be the set of arcs that connects consecutively numbered
products. Note that, in any feasible solution, there is a unique path, comprising one or more pivots,

from v\ to vpj. Furthermore, in any solution to this problem, each pivot generates a subtree. The
equivalence is complete if we assign

Da = F1 + fA and

A

n F2P1 E!=j dt

Dij = lfKj

= 00 otherwise.

for any i,j £ M. LB\ can, therefore, be determined in 0(N2) time.

3.2 Demand Splitting

The second bound is obtained by relaxing constraints (5) to read Xj, > 0, and solving the resulting
FMD1 problem using algorithm Greedy described in Raman and Palekar (1993). Let the resulting
solution value be LB2.

Proposition 2. LB2 is a lower bound on the optimal solution value for FMD2.

Proof: In the following, QG denotes the subgraph followed by the Greedy algorithm when demand
splitting is permitted (see Raman and Palekar 1993). We show that the cost of the optimal path
0* in Q from \\\ to T is no less than the cost of at least one path between these two nodes in QG .

Let C(-) [CG(-)] denote the cost, and t](-)[tjg(')] denote the number of machines required by path
(•) in Q [G ]. Let <tq be the longest segment of Q* that originates at Vji and consists only of f- and
h-arcs, and let Vuv be the node at which o$ terminates. Such a segment must exist because only
an f-arc and a b-arc emanate from V\\\ also, u > 2. In Figures 2a and 2b, cr$ is the path E\l - E^
- £44, and Vuv is V44. Because it does not include any b-arcs, <7q must exist in QG as well and is,
therefore, considered by Greedy.

INSERT FIGURES 2a AND 2b HERE

Let Vq be the set of pivots visited by <7o- At the end of cr0, for any line A(/), / £ Vo, let Ri denote
the remnant in Q, RG the remnant in QG, ni the number of machines in Q and nf be the number
of machines in QG . Recall that because demand splitting is permitted in QG , the remnant RG at
any line will be used for partially meeting the demands of products from subsequent lines. Then,
for A(/) = 1,

10

rii = nG,

and for A(/) > 2,

<

P, (ES",+1)-' di - *?-i)

P, (zW)+l)-1 <*.)

= m.

(14)

Hence, the number of machines saved by permitting demand splitting is

i = Ti(<T0)-riG(<ro)

> 0.

(15)

Since the number of pivots in <7q is the same in both Q and QG ', C(ao) > CG(<7o) and the proof is
complete if Q* = <r0. Otherwise, suppose that Q* consists of one or more b-arcs. At the end of a0
in Q, the remnant at any line A(/),/ E Vo is

*(A(/)+l)-l

#/ =

An/
Pi

and the total idle capacity available for possibly absorbing demands of subsequent products is

J2izv0 R-l- On tne other hand, the total idle capacity available at the end of ao in QG is RG which

is given by

AnG v
Ru = — - — } dt + RT

Pu t=u

where r = ir(\(u) — 1) is the pivot of the line immediately preceding \(u). From induction, it is
easy to show that

Ar)G v

*? = E^-E*

leVo rt t=i

iev0

Yl {ni ~ n?) I Pi

iev0

iev0

Pu

(16)

11

because pu < pi, I G Vq. Let <j\ denote the segment on Q* that originates at Vuv (with a b-arc)
and ends with an f-arc incident upon a node (say) VgtV+k such that 9 > u. Note that there will
always be such a segment given that the terminal node T is reachable only with an f-arc. Figure
2a depicts the case in which 9 = u, and G\ is the path E\\ - E^l - E\l - Eyj. Figure 2b depicts
the case in which 9 > u, and <j\ is the path JEff - £35 - E\l - Efj. Let the set of pivots visited by
<j\ be V\. Note that

vu<vu v/e?>i\{0}. (17)

Let Ai denote the set of products assigned to pivot /,/ G V\ along o\. Consider the following cases:
Case I: 9 = u.

From Remark 1, we have in this case

Vi C Vq.

(18)

Let a[ denote the path E%$+1 Kll+k-v In Figure 2a' ai is the Path Etl ~ Ett ~ Eil ~

E$. We will show that

C((ToU<71)>Cg((ToU<t;).

Note that

and

,G/_/

*/>!) =

Pu [(£/€*>! Et€ A rf<) ~ fl«

P/ (E<€A rf* ~ gj)
Pu (Et€-4, rf< ~ Rl)

from (17)

>

E/€Pi P« (E*€A rf< " ^0

Pu [(E/€Pi EtG-4, d«) - E/GPi #/

>

Pu [(£/€?! £t€>*i rf«) ~ ^

"£

= >?Vi)-['/N-^o)

(19)

(20)

12

where (19) follows from the well-known inequality

Y

' Y

E M *

J2av

y=i

y=i

and (20) follows from (16) and (18). Hence, r)(a0) + 77(0-1) > r)G((70) + rjG(a[). Since no new pivots
are opened under both o\ and cr[, C(cro U c\) > Cg{oq U <J2)-

Case II: 9 > u.

In this case, 9 = v + k and

?i\{0} C V0.

(21)

Let a'{ denote the path ££#+1
- £ff . We will show that

ifl.U + ifc

^I+J-r In Figure 2b^ *i' is the Path £44 " E$t - EU

C(<r0U(7i)>CG((7oUO-

We have

^1)= E

Pi [UteA, dt ~ Ri)
A

+

Peds

Using arguments similar to those used in case I, it can be shown that

Hence

/e?i\{0}

PI (Et6A d* ~ Rl)

>

Pu (E/e^AW EteA dt) - RG

A

-z

l(*i) >

Pu

(E/e^AW E«e.4, dtJ - RG

-t

+

pe (d9 - RG)

,G, „n

= n"tf)-(.

Since 01 and o" have the same number of pivots, C(ao U cr\) > CG(<Jo U <t").

Therefore, in both cases, the proof is complete if fi* = oq U 0\. Otherwise, we identify the next
segment 02 in fi* that originates at Ve,v+k with a b-arc and ends with an f-arc incident upon a
node V$i)V+k+k' such that 9' > 9. Note that both <7\, and a[ and o" terminate on the same node
VgtV+k- Set (To = <7o U o-! , and repeat the above arguments for 02 • n

The following result shows that this bound is at least as strong as LBl.

13

Proposition 3. LB2 > LBl.

Proof: We show that the cost of any path Q from Vn to T under Greedy is at least as large as
the cost of the same path when fractional machines are permitted. Let the set of pivots on Q, be
V, and let P = \V\. Also, let C\(i),l G V denote the set of products assigned to pivot /. Then the
total cost of 0, given fractional machines is

PI £<€£*(,) dt

C1(Sl) = PF1+F2Y,

lev
and the cost of Q, under Greedy, with Rq = 0, is

c2(n) = pfx + f2^

lev

= PF, + F2J2

lev

Pi {Htecn(n dt - R?.x + R?)

= C1(Sl) + F2/AYlPi(R?-B?-i)

lev

= d{n) + F2/A

> C!(ft)

£ *f(pi-j*+i) + JR?

liev\{P}

because p, > pl+l for all / G V\{P} and Rf > 0, V/. □

(22)

3.3 Lagrangean Relaxation 1

The third bound LBS is obtained by Lagrangean relaxation (see, for example, GeofFrion 1974). We
dualize constraints (2) with nonnegative multipliers ut. The resulting problem is

LR1

subject to

N N I

Minimize Z(u) = J^(Fijfj- + F2n3) - ^ u{ I ^ xJt - 1

Pi ( ]C *** ) - An^ J e ^

Xji < Vj, i,j G M

xJt6{o,i}, ijeM

Vj G {0, 1}; rij > 0, integer, j G M

(23)

14

For given multipliers, LR1 separates into N independent problems, where the jth problem is
LRlj

subject to

Minimize Zj(u) = F\y3 + F2TIJ — Y^ UiXji (24)

*13

Pj ( S diXJ* I - Anh (25)

Xji<Vj, (26)

zit€{0,l}, iCZj (27)

Vj G {0,1}; tij > 0, integer, (28)

LRlj is separable and it can be solved by solving the following knapsack problem
KPj

Yj(u) — min I Fq/Ij — Y^ UiXji

subject to

Pj Yl diXi* ) - An^

Xji G {0, 1}, i e I j

Note that Yj < 0, in an optimal solution since nj = 0,Xji = 0, Vz is a feasible solution to KPj.
If Yj < —F\, then y3 — 1 in an optimal solution to LR17 with a solution value of Z* = F\ — Yj.
Otherwise, yj = n3 = xJt = 0 in the optimal solution for all i, yielding the optimum solution value

z; = o.

The Lagrangean dual problem is
LRD1

N N

LBS = max ^ Zt(u) + ^ u% (29)

1=1 :=1

with U{ unrestricted. However, we need consider only nonnegative values of these multipliers,
because if ut < 0 for any i, then xJt = 0 in an optimal solution to LRl. While it is possible to
use subgradient optimization, it is often more effective to first use a dual ascent technique that can

15

guarantee bound improvement at each iteration. We use an ascent approach that exploits violation
of constraints (2). Define

X1 = {i\ £ ** = 0}
jeJ,

and

X2 = [i\ J2 *ji > 2}
jeJi

First consider the products in set X1, i. e., those products that have not been assigned to any line.
The minimum increase required in u, for any i E X1 before it can be assigned to a line depends
upon the status of the line. Based upon the solution to problems LRlj, j 6 Af, a line corresponding
to pivot j can either be

i) open; i.e., yj = 1, or

ii) closed, but with assignable products; i.e., yj = 0, and — Fi < Yj(u) < 0. Note that in this case

£,€!, Xji > ^ OI*

iii) closed with no assignable products; i.e., yj — 0, and Yj(u) = 0. In this case, J2%el xJi ~ ^,

In case i), the number of machines required to include i in line X(j) is \pj(d{ — Rj)/A\. Therefore,
an increase of

Vj = F2\pj(di - Rj)/A] - Ui

in Ui will guarantee that Xji = 1. However, this increase may result in a decrease in the value of Zj.
To insure that this does not occur, we first solve KPj with multiplier w( = U{ + Vj. If the resulting
solution value is Ynew, then the largest increase in w, that does not result in any increase in Zj is

6j = {vj - Ui) - (Yj - Ynew) .

Consequently, based only on the open lines, the maximum permissible increase in wt to insure
HjGJi X3* ~ 1 is

Ai = vain {Sj\yj = 1}.

Using similar arguments in case ii), the maximum permissible increase in w, based upon lines X(j)
that are currently closed with assignable products is

A2 = min {Fx + (F2\Pj(dt - Rj)/A] - ut + Yj) - [Y3 - Ynew) \Vj = 0, Yj < 0},

16

and in case iii), the maximum permissible increase in w, based upon lines X(j) that is currently
closed with no assignable products is

A3 = min {Fl + (F2\Pjdt/A] - ut) - {Yj - Ynew) \y3 = 0, Yj = 0}.

Therefore, the overall maximum permissible increase in U{ to insure that Xji — 1 is A = min {Ai, A2, A3}
and the bound value LB3 increases by A.

Next consider the set X2, i. e., the set of products that have been assigned to more than one line.
For any i & X2, we first compute the minimum amount by which w, needs to be decreased in order
to be excluded from any line A(j) that it is currently assigned to. If w, is decreased by

Wj = U{ - F2 <

Pj Ylq£l} dqXjq

Pj [Zqelj d1XJ<1 - di)

then Vs contribution to Yj becomes positive, and consequently, xJt = 0 in an optimal solution to
LRlj. However, this increase may lead to a decrease in Z; as well. In order to determine the
maximum decrease in tz,2 that will retain the same value of Zj, we next solve KPj with multiplier
U{ — Wj. If the resulting solution is Ynew, then the largest decrease in U{ that does not result in a
decrease in Zj is

6j = (Ui - Wj) - {Yj - Ynew) ■

The second largest value of such decreases across all open lines is

A = maxyzj^j.) {63}

where j* = arg maxj^j^Sj}. If w, is decreased by A, then an alternative optima to LR1 is
obtained in which i is assigned to exactly one line. Note that this results in an overall bound
increase of ( | J2jeJt xji\ — l) ^«

It is always possible to further improve this bound by using a subgradient method (see, for example,
Held, Wolfe and Crowder 1974) to search for multipliers after the ascent stops. This was done in
the computational study reported in §6.

3.4 Lagrangean Relaxation 2

We add the following inequalities to the formulation (1) - (6) of FMD2.

/ 1

51 51 Pjdixjt < A XI nJ ' = ii2, . . ., jv

3=1 i€Ji j'=l

17

Clearly, any solution that satisfies (3) will satisfy the above inequalities as well. Now we relax con-
straints (3) by dualizing them with nonnegative multipliers Uj. The resulting Lagrangean problem
is

LR2

N N / \

Minimize Z(u) = ^(Fiyj + F2nj) + ^ u3 I pj JT Pjd{Xji - Arij I (30)

subject to

£>j, = l, «€JV (31)

SXlM^ < ^X>j /=l,2,...,iV (32)

j=iteJ, j=i

Xji < yJ: (33)

^,£{0,1}, m€JV (34)

% G {0, 1}; nj > 0, integer, j e Af (35)

The objective function can be restated to read

N N N

z(u) = 5Z F*yj + J2 (F2 - Auj) nj + 51 MiPj H <*«■**

j=l j=l i=l i€T,

Note that Z is unbounded from below for any value of Uj such that F2 < Au3. Therefore, in order
to obtain a meaningful bound, we enforce the constraints

F2 - Auj > 0 Vj (36)

Proposition 4. Suppose that the multipliers Uj,j= 1, 2, . . . , N are selected such that for any
j,k (E M, Pj > pk implies UjPj > UkPk- Then there is at least one optimal solution to LR2 that
follows the sequential assignment policy.

Proof: From (32), it follows that the surplus capacity «/ available at line A(/) is carried forward
to the next line. In particular, for the first line,

and in general, for any pivot /,

K\ = An\ — 2_. d{X\i
i€li

ki = Ani - 22 d%xn + Kq

18

where q is the pivot of the line immediately preceding A(/). Let a\ be an optimal solution to LR2
that does not possess the sequential assignment property. Then there must be a product t that is
assigned to line X(k) while another product s, s < t, is assigned to line X(j) with k < j. Let a2 be
identical to o\ in the number of machines as well as the products assigned to each line, except in
that t is produced on line X(j). This solution is feasible because it results in an increase of pkdt in
the surplus capacity of all lines X(k) through X(j) — 1, and an increase of (pk — p3)dt > 0 in the
surplus capacity of all the subsequent lines. If Z(-) denotes the cost of solution (•) to LR2, then

Z{al) - Z[a2) = (ukpk - UjPj) > 0

and if a\ is optimal, then so is a2- Repeating the above argument whenever necessary gives the
desired result. □

Similar to the demand splitting problem FMD1 discussed in Raman and Palekar (1993), LR2 can
then be posed as a shortest path problem on graph Q = (V,£). Following arguments analogous
to Raman and Palekar, it can be shown that the number of machines required, as well as the
surplus capacity available at any node depends upon the path selected to reach that node. For a
path Q in which i and j, j > i, are adjacent pivots, the number of machines required at line X(j)
corresponding to node Vjk is

\Pj {Zu=jdu) -Qij-l

Mjk=

where £>2,j_i is the surplus capacity at Kj-i- At any node Va, t = 1,2, .. .,iV, the surplus capacity
Q\t — r\t- In general, the surplus capacity at Vjk is

Qjk - AMjk - 1^2 du + Qij-i

k"=?

The cost of h-arc E3.'k + is

c#+1 = (*2 - AUj)

and the cost of the f-arc £JJJ"1,fc+1 is

Jfe+i,jfe+i

Pjdk+i - Qjk

+ UjPjdk+i,

«-'•"•» = Fl + (F2 - Ami)

Pjdk+i ~ Qjk

+ Wit+iPfc+l^A:+l,

(37)

(38)

LR2 can be solved in polynomial time using the algorithm described in Raman and Palekar ( 1993).
The Lagrangean dual problem is

19

LB4 = max Z(u)

subject to

F2 - Auj > 0 Vj

uJ+1-ujPj/pJ+l<0 ; = l,2,.,.,i\T-l (39)

uj > 0. Vj

We solve for the multipliers using the subgradient optimization method with a simple modification
to account for the upper bounds given by (39).

4 A Heuristic Algorithm

Given the strong NP-completeness of FMD2, it is likely that most real problems will need to be
solved using heuristic approaches. In this section, we construct an efficient solution method that
is an improvement heuristic. Note that while the optimal solution need not satisfy the sequential
assignment property (SAP), such a policy can be enforced to obtain a heuristic solution. The
proposed method starts with the SAP solution and iteratively improves upon it.

Given the sequential assignment policy, FMD2 reduces to a tree partitioning problem by assigning

dipt

Da = Ft +

, and

Pi El=j dt
A

= oo otherwise.

Da = F2

, if i < j

Following Corneujols, Nemhauser and Wolsey (1990), the optimal SAP solution can be found in
0(N2) time. Note that

Remark 2. If the path corresponding to an optimal solution to FMD2
does not contain any b-arcs, then the SAP solution is optimal.

Proof: From Corollary 1, it follows that if there are no b-arcs in the optimal path, then all f-arcs
in that path must be of the form fjjf1' . Since the SAP solution considers all such f-arcs and all
resulting h-arcs, it must be optimal. □

20

Clearly, any improvement on the SAP solution is predicated on the existence of one or more b-arcs.
Consider an optimal path ft* from 5 to T in Q that consists of a b-arc E^\_x. From Remark 1,
both j and u must be pivots. Let

Pudk

Vuk = —j-

be the (possibly) fractional number of machines required on line X(u) to produce k ignoring any
available remnant. Also, let p,jk = ctjk + fijk, where ct3k is the integer part of [ijk. j3jk = fijk — |_/f?fcj,
where \_f\ is the largest integer no greater than /, is the purely fractional part of //jfc- Then

Proposition 5. auk < ctjk + !•

PROOF: If ft* does not have this property, then construct an alternative path ft' which differs from
ft* only in that product k is assigned to line A(j). Let n'^ denote the resulting number of machines
on \(j). Then

nn =

>

Pu 2-~ii "i^-tii

Pu(YLtdiXui ~ dk)

+

Pudk

- 1

= < + \auk + /Ul - 1

(40)
(41)

where (40) follows from the inequality

It can similarly be shown that,

[a + 6] > ("a] + ffl - L

Wj > n'3 - \ajk + (3jk\

(42)

Because ft* is optimal, nu + n3 < n'u + n'-. From (41) and (42), it then follows that

\(*uk + fluk] < \<*jk + Pjk] + 1
Since, 0 < fljk,l3uk < 1, this is possible only if auk < &jk + 1- D

The following corollary extends the above result to include b-arcs involving a subset of products.

Corollary 2. Let TJt denote a subset of products that is assigned to line j in the SAP solution.
IfTjt is assigned to line \(l), I < j, in an optimal solution then jn < 7jt + 1, where

21

V= T^—

There are two kinds of b-arcs imbedded in any SAP solution. The first kind, hereafter referred to
as a Type 1 b-arc, exists within each line. Identifying such b-arcs and updating the SAP solution
accordingly results in the single line being split into two or more lines. Consider the following
3-product problem: Fl = 250; F2 = 130; A = 800; pi = 10; p2 = 5; p3 - 2; dx = 100; d2 = 280;d3 =
60. The SAP solution, in = X\2 = £13 = 1, results in a single line. However, the optimal solution
to this problem is in = x22 = £13 = 1 which induces the b-arc E\2 as shown in Figure 3. Updating
the SAP solution results in an additional pivot at product 2.

INSERT FIGURE 3 HERE

The second kind of b-arc, hereafter a Type 2 b-arc, exists across lines; these b-arcs result in re-
assigning a product to a different line. However, such b-arcs do not create any new lines. Consider
the following 4-product example illustrated in Figure 4: F\ = 1000; F2 = 100; A = 800; p\ = 10;
p2 = 9; p3 = 2; p4 = 1; dx = 100; d2 = 200; d3 = 1590; d4 = 20. The SAP solution is
£11 = £12 = £33 = £34 = 1 with two lines having pivots 1 and 3 respectively. The optimal solution
is £n = £12 = £33 = £14 = 1 that induces the b-arc £33 resulting in product 4 being re-assigned
from line 2 to line 1.

INSERT FIGURE 4 HERE

The proposed solution method is an improvement heuristic that modifies the SAP solution by
iteratively identifying Type 1 and Type 2 b-arcs and updating the solution accordingly. A formal
statement of the algorithm is given below.

Algorithm MultilineDesign

Step 0: Initialization: Determine the optimal SAP solution. In case of multiple optima, select the
solution with the largest number of pivots; break ties arbitrarily. Go to Step 1.

Step 1: Identification of Type 1 b-arc and Solution Update: Determine if a Type 1 b-arc exists that
can result in a cost reduction. Update the current solution accordingly. Go to Step 2.

22

Step 2: Identification of Type 2 b-arc and Solution Update: If a Type 2 b-arc exists that can result
in a cost reduction, then update the current solution accordingly and go to Step 1. Else, stop.

Steps 1 and 2 are now discussed in detail.

4.1 Identification of Type 1 b-arcs

Suppose that the SAP solution results in L lines. Starting with line 1, we consider each line in
order, and attempt to determine the optimal solution with respect to the products allocated to
that line. This is done by identifying the b-arcs, if any, that are imbedded within that line. Note
that any improvement at this step is contingent upon the existence of one or more b-arcs, and any
such b-arc must result in the generation of one or more additional pivots.

Consider an arbitrary line /, and let Ci = (7r(/), . . ., 7r(/ -f- 1) — 1} be the set of Q (consecutively
numbered) products assigned to this line under SAP. Note that in the SAP solution, xu = 1 V i G
£/. Let SP2/ denote the subproblem of FMD2 that considers only those products that are in Ci,
and let SP1/ denote the corresponding problem in which demand splitting is permitted. Since each
line can be treated independently, hereafter in this subsection we renumber the products in C[ as
1,...,Q and suppress subscript /. Note that the SAP solution to SP2 consists of a sequence of
n~ circs -Cyi -i ... .£/■• r\ ■* .

First we state the condition under which no b-arcs exist in a given line, and consequently, the SAP
solution is optimal to SP2. From Proposition 2, recall that the Greedy solution to SP1 is a lower
bound on SP2. Therefore,

Remark 3. The SAP solution is optimal to SP2, if it is the Greedy solution to SP1 as well.

When this above condition is not satisfied, the optimal solution to SP2 may consist of pivots in
addition to 1. We now construct a heuristic method that solves SP2 through a 2-stage approach.
In the first stage, we identify the additional pivots required, and in the second stage the various
products are assigned to these pivots. These two stages are now discussed.

4.1.1 Determination of Pivots

Suppose that the optimal solution to SP2 consists of K lines with pivots from the set K =
{7r(l),7r(2), . . . ,x(A')}. Consider the path that passes through these pivots and that satisfies the
sequential assignment property, i.e., the path E$))£$+1 K(i)*(2)-i K(K)',Q-r

23

INSERT FIGURE 5 HERE

Let Cg((t) be the cost of this path in QG . Let Z"(-) and Zs(-) denote the cost of the optimal and
the SAP solutions, respectively, to problem (•). Then from the proof of Proposition 2, it follows
that

Remark 4. CG(a) < Z*(SP2) < ZS(SP2).

Remark 4 suggests that the set of optimal pivots can be found by first constructing a graph QG
corresponding to SP2, identifying a path in this graph that has a lower cost than Zs , and selecting
the pivots corresponding to this path. However, there are two problems with such an approach.
First, the number of paths to be investigated can be large. This problem can be circumvented
by considering a limited number of paths; in the computational experiments, we consider only the
Greedy solution to FMDl. Second, a path in QG may contain one or more "spurious" pivots,
i.e., pivots that may be efficient for FMDl but that lead to inferior solutions for FMD2. For
example, consider the following 3-product problem: F\ — 250; F2 — 130; A — 800; p\ = 10;
p2 = 5; P3 = 2; d\ = 100; d2 = 280; d^ — 80. The optimal solution to SP2 is the SAP solution
Xn = X\2 = X13 = 1. However, the Greedy solution to this problem is x\\ = #22 = ^23 = 1 which
generates an additional, spurious pivot at product 2.

It is, however, possible to eliminate one or more spurious pivots by the following result which
requires that under a relatively weak condition, each pivot other than 1, must be associated with
one or more b-arcs in at least one optimal solution. Suppose that the optimal set of pivots for SP2
is K — {7r(l),7r(2), . . . ,7r(A')}, and let a be the path that passes through these pivots and that
satisfies the sequential assignment property. Define a pivot in a as a donor if one or more products
assigned to it is reassigned to a lower numbered pivot in the optimal solution to SP1. Alternatively,
pivot A: is a receiver if a subset of products assigned to a higher numbered pivot in a is reassigned
to it in the optimal solution to SP1. Figure 5 shows a in broken lines and the optimal path in bold
lines. With respect to this figure, pivots 5 and 7 are donors while 3 is a receiver. A pivot can be
both a donor and a receiver. Let iftjk denote the integer part of the number of machines required
to produce products k, k -f 1, . . . , Q on line A(j), i.e.,

1>jk =

Pj E?=* dq

24

Remark 5. Suppose that k 6 /C\{1} is a pivot in an optimal solution to SP2 such that
iplk > 0JfeJfe + 1- Then k must be either a donor pivot or a receiver pivot.

Proof: First note that Step 0 of MultilineDesign insures that the SAP solution selected as
(say) is one with the maximum number of pivots in case of multiple SAP solutions with the same
value. Therefore, with respect to the products in £/, as uniquely has the lowest solution value
among all SAP solutions. as is the path connecting Vn, V\2 — • • • — Vi.Q-i and V\q in Figure 6.
Suppose there exists an optimal path o* that contains a pivot k which is neither a donor nor a
receiver, but ^u > ipkk + 1. o* is shown with bold lines in Figure 6. Let a\ be another path that
is identical to a* except that all products assigned to pivot k in cr* are now assigned to pivot 1.
Then

C(ai)-C{**)

-F, + F2

Pi (Ei€£iU£A(fc)rfi)

Pi (E»€£i di)

Pk (E.-€£M») di)

> 0.

(43)

Now construct another path a2 in which products 1 through fe — 1 are produced on line 1, and
products k through Q are produced on line 2 with pivot k. Clearly, a2 is another SAP solution,
and

C(as)-C(<r2) = -Fi + F2

Pi

(£?=, *)

Pi

(ES *■)

Pk

(£?■**)

A

< 0 (44)

because as has uniquely the lowest cost among all SAP solutions. Note that Ci\JC\(k) Q
{1,2,...,Q}, and C\(k) Q {k,k + l,...,Q}. Following arguments similar to those used in the
proof of Proposition 5, it can then be shown that Equations (43) and (44) are consistent only if
^ik < ^Jtfc + 1- But this contradicts the original assumption. □

INSERT FIGURE 6 HERE

Note that this result may not hold if the integer number of machines required for all products
k,k + 1, ...,Q at line A(Ar) differs from the number of machines required for these products on
line A(l) by no more than one machine. However, this is a relatively weak condition that is likely
to be satisfied in most real problems. Also note that the sets of donors and receivers cannot be
determined exactly unless the optimal solution to SP2 is known. However, we make use of the fact
that such a solution must satisfy the condition stated in Proposition 5.

25

We now formally state the procedure that determines the "best" set of pivots for SP2. In the
following, V and 7Z denote the set of donor and receiver pivots, respectively.

Algorithm SetPivots

Step 0: Set j - 0.

Step 1: Solve SP1 using the Greedy approach. If the optimal Greedy solution is the same as the
SAP solution to SP2, stop. Else, let O = {a\CG{a) < ZS{SP2)} be the set of candidate paths to
be investigated. Arrange these paths in the nondecreasing order of their costs. Go to step 2.

Step 2: Select the path Q. from the top of the list; let /C = be the set of pivots in Q, and K = |/C|.
Set / = 1; V = 0; 11 = {1}. Go to step 3.

Step 3: a) Set / «- / + 1.

b) If ct^i^i < (*Tr(t),i + 1 for some i and t such that ir(l) < i < Q, and t (E 7ZIJV, then set

V = V(J{*(I)}

n = n\J{t}

K = £\{ir(/)}

and go to step 4. Otherwise, delete Q. from O and go to step 5.

Step 4- If / 7^ A' — 1, go to step 3a), else go to step 5.

Step 5: Stop if all paths in O are scanned. Else, go to step 2.

Using Remark 3, Step 1 checks for the optimality of the SAP solution by solving SP1 with the
Greedy approach. If this test fails, then SetPivots first identifies the stack of paths with solution
values less than ZS(SP2). For any path Q, from this stack, step 3 enforces the condition stated in
Remark 5 to check if each pivot, other than 1, is either a donor or a receiver. If any path fails this
test, then it is removed from the candidate list of paths to be pursued further.

26

4.1.2 Product Assignment to Sublines

At the end of SetPivots, we have a stack O of paths; each path in this stack decomposes what
was originally one line into A', K > 2 sublines. Furthermore, we have identified the sets V and 1Z of
donor and receiver pivots, respectively, within each path ft in this stack. Note that ft consists of only
f-arcs and h-arcs resulting in sequential assignment of all products. While this path is suboptimal
for SP2, we now attempt to improve it by reassigning products and in so doing, generate b-arcs.
Let njt, k = 1,2,..., A' denote the number of machines required and Rk be the remnant at line
A(fc) in ft.

Let j G V be a donor pivot in ft. Let TJt, t = 1,2,.. . denote the subsets of products that are
currently assigned to line \(j) but that are eligible for reassignment to another line. TJt is eligible
if there exists a line A(/), / £ TZ\{j} such that assigning TJt to A(/) results in a reduction in the
number of machines Wj + n/ at lines X(j) and A(/). This is possible only if Tjt makes use of the
remnant Ri available at line A(/). In particular, the fractional part of the machines required by Tjt
at A(/) should be no more than i2/, i.e.,

Pi E«6rJt di

,, drf (Pi52ierJtdi

A

Pi

Let (f>l-t = 1 rfTjt can be reassigned to A(/), zero otherwise. Also, let V3 = {TJt} denote the collection
of product subsets that are assigned to pivot j in ft and that are eligible for reassignment. The
product reassignment problem can then be formulated as

GAP

Maximize ££ £ <plJtYJt (45)

ieizj€vr]tev}

subject to

£ £ K/,<i jev (46)

ieizr}tev}

E E tittjtYJt < Ri V/Eft (47)

j€PrJt6Pj

Yjt 6 {0, 1} V TJt e Vj, V> 6 P, and V/ G U (48)

where Yjt equals 1 if subset TJt is reassigned to line /, 0 otherwise. The objective function (45)
maximizes the number of reassigned subsets. Constraints (46) specify that no more than one subset
is reassigned from any line. In particular, because a job can belong to more than one subset, these

27

constraints guarantee that job reassignments are not duplicated. Constraint (47) is a knapsack
constraint that insures that the fractional machine required for any reassigned product subset is
no more than the available remnant.

GAP is a generalized assignment problem. [See, for example, Ross and Soland 1975; Fisher,
Jaikumar and van Wassenhove 1986; Guignard and Rosenwein 1989; Martello and Toth 1990].
While this problem is NP-complete, there are reasonably efficient solution methods available for it.
This problem is easily solved in our case in particular because in SP2, the number of alternative
lines that a product subset can be reassigned to is usually very small which yields a sparse $ = [<f>jt]
matrix.

4.2 Identification of Type 2 b-arcs

Let the incumbent solution at the end of Step 1 comprise L lines. At the second step, we consider
each line in order, and .try to minimize the idle capacity on this line by reassigning a subset of
products that is currently assigned to higher numbered lines (and thereby, generating b-arcs).
Suppose that the line being considered is A(/). We enumerate all subsets TJt of products that are
currently assigned to some other line A(j>), j ^ /, and that are eligible for being reassigned to A(/).
Let Qji denote the set of feasible product-subsets that are currently assigned to line q and which
are candidates for assigning to line /. The resulting problem to be solved for line / is formulated as:

KP,

L

Maximize S^ ^ w]t^^ (^9)

3=1+1 rjtSBjt

subject to

J2 YJ^1 J = h..-,L;j?l (50)

£ £ SlJtYJt<Rt (51)

j=i+i r}teQji

^€{0,1} VfyeOji, and /=1,2,...,Z (52)

where Yjt equals 1 if subset TJt is reassigned to line /, 0 otherwise. The objective function (49)
maximizes the weighted number of reassigned subsets. The weight w3^ assigned to subset TJt is
selected such that a higher weight is given to subsets at lines with smaller indices so that ties are
broken in the favor of these subsets. Because the lines are considered sequentially starting with the

28

smallest indexed line, this objective facilitates better reassignment in the subsequent steps. Also,
among the various subsets on the same line, higher weight is given to the subset that frees up more
capacity. In the computational experiments reported in §6, the functional form wJJt = exp(S3Jt/j)
was used. Constraints (50) and (51) parallel constraints (46) and (47), respectively.

Problem KP/ is a knapsack problem with generalized upper bound constraints (50). This is a well-
studied problem (see the related references in Martello and Toth 1990). Dyer, Kayal and Walker
(1984) provide an effective algorithm for solving it.

5 An Exact Algorithm

We now present an implicit enumeration method for solving FMD2 exactly. Branching in the
solution tree shown in Figure 7 is based on the assignment of products to lines. For greater clarity,
the vertices shown in the tree are labeled according to the nodes V{j that they correspond to in Q.
The root vertex corresponds to the assignment of product 1 to line 1; clearly line 1 must be opened
in any feasible solution because product 1 has the largest processing time. Each subsequent level
in the enumeration tree corresponds to the assignment of a product considered sequentially in the
order of its index. At level j of the tree, we generate vertices in the solution tree corresponding
to each feasible assignment of product j to a line. Since each product i < j is potentially a pivot,
this step requires generating j vertices corresponding to each of the nodes V\j, V^, . • • , Vjj in Q. A
depth-first strategy is used to search the enumeration tree.

INSERT FIGURE 7 HERE

Lower Bounding

The lower bound at any vertex in the enumeration tree is determined by using LB2 discussed in
§3.3. Consider vertex u in the tree that corresponds to V{j in Q. Let O denote the path leading
from the root vertex to u. Q represents the partial solution comprising of assignments of products
1,2,..., j. Let C(u) be the cost of ft, and let pu denote the sum of the remnants on all lines
opened in ft. The lower bound LB(u) at vertex u is determined by first netting pu units from
the demands of products j + 1,...,JV considered in that order. Suppose that pu can completely
meet the demands of products j + 1 through k — 1, and partially satisfy the demand of k. Let d't,
k < t < N denote the net demands remaining to be satisfied. Then

29

dk 5: dk, and

d't = dt for k + 1 < t < N. (53)

Define P^ as a relaxed subproblem of FMD2 that considers only products fc, k + 1, . . . , JV, and that
permits demand splitting. Product demands and processing times are given, respectively, by d't,
and p't = pt, k < t < N . Let ZG (P^) denote the Greedy solution value for P^. Then, from (53)
and Proposition 2, ZG (Pi) is a lower bound on any completion of path Q if product k generates
a new line.

Consider another subproblem P£ that differs from P* only in that p'k = p,. This essentially insures
that product k is assigned to the line with pivot i. Let ZG (P„) denote the Greedy solution value
for Py. Then, as above, it follows that ZG (P„)— F\ is a lower bound on any completion of path ft
if product k does not generate a new line.

A valid lower bound on u is then given by

LB(u) = C(Q) + min [ZG (Pj), ZG (P2u)-Fl}.

Upper Bounding

The upper bound at vertex u in the tree is similarly derived by solving two subproblems. Let R{
denote the remnant at line \(i) after assigning product j. We first net R{ units from the demands
of products j + l,...,iV considered in that order. At the end of this step, suppose that the
products with positive net demands are k,k + 1, . . .,N. Let d'{ denote the net demand of product
t, k < t < N . Then, d'£ < dk, and d'{ = dt, k + 1 < t < N . We now consider two subproblems
of FMD2 at u. In the first subproblem P^, we assign k to line A(i). P^ is defined for products
k,k + 1, . . ., N, with demands d", k < t < N , and processing times p% = pi, and p'{ = pt for
k + 1 < t < N. If Zs (Pj) is the SAP solution value for Pj, then Zs (Pj)-Fi is a feasible upper
bound on any completion of path Q. that assigns product k to line A(z').

We define P£ as the other subproblem of FMD2 in which k generates its own line. P£ considers
products k,k + 1, ...,JV, with demands dt and processing times pt, k < t < N . Then its SAP
solution value Zs (P^) provides another feasible upper bound on any completion of path Q. An
overall upper bound at u is then given by

UB(u) = C(ft) + min [ZG (Pj)-ik, ZG (Pj),]

30

J

Branching Strategy

While determining the upper bound at u if it can be determined that there are no b-arcs in an
optimal completion of the partial solution at w, then from Remark 2, u is fathomed with solution
value U B(u). Noting that u corresponds to node Vtj in G, the non-existence of b-arcs in any optimal
completion at u is guaranteed from Proposition 5 if an > an + 1 for all j " + 1 < t < N , and for
any / that is a pivot on path Q. This approach is implemented in the algorithm by scanning the
pivots along Q in the decreasing order of their indices. Since an > am if / < k, scanning can be
terminated whenever this condition is satisfied at any pivot.

Similar arguments are used to limit the number of descendants generated at an vertex. Consider a
descendant v of u that represents the assignment of product j + 1 to line \{g) such that 1 < g < i.
The generation of v augments Q with a b-arc Efj3 . Clearly, if agj+i > ai,j+i + 1, then this
augmentation can never be a part of an optimal solution, and v is fathomed. In order to exploit
this dominance, we generate the descendants in the decreasing order of the pivot indices. The
generation of additional descendants is terminated whenever a descendant is dominated.

Further efficiency is gained by using the notion of remnant dominance. Consider the vertices
corresponding to the assignment of product j. Let ZG (P^) and ZG (P^) correspond to the
assignment of j to lines k\ and k2, k2 > kl, respectively. If pu\ < /V2, then ZG (P^) < ZG
(Py2). Thus, if the vertices are scanned in the decreasing order of the line assignments, then it is
possible to avoid bound calculation at any vertex by first attempting to fathom against previously
calculated bounds.

6 Computational Experience

Our computational experience comprises two sets of experiments. In the first set, we use the opti-
mum solution obtained by the enumeration procedure described in §5 to evaluate the performance
of algorithm MultilineDesign as well as the various lower bounds discussed in §3. Because of
the computational burden involved, this set is restricted to small problems. The second set deals
with larger problems of the size that we have encountered in an existing system in the automo-
tive industry. In this set, we use the tightest lower bound value as the benchmark for evaluating
MultilineDesign and the lower bounds. The product demand and processing time values used in

31

both sets reflect the characteristics of this facility. However, additional scenarios are generated to
provide a wider range of problem instances.

The fixed cost per line F\ is randomly generated from the discrete uniform distribution £/£>(0,50),
while the machine cost Fi is sampled from £/£>(100, 1000). Part processing times are generated from
the continuous uniform distribution U(0. 1,5.0). The total time available per period per machine
A is retained at 800 across all experiments. Finally, product demands are sampled from two
demand streams with equal probability. The demand for large-volume products is generated from
the discrete distribution £/£>(100, 2000) while the demand for medium- volume products is generated
from ?7d(5, 100). In the first set, the number of products N is sampled from Ud(10, 20), while in
the second set N is generated from £/£>(10,50). All experiments were conducted on an IBM RS
6000 workstation.

The first set consists of 20 different problem scenarios generated randomly. These are shown in
Table 1 together with the solution value Z(MLD) obtained using algorithm MultilineDesign
(MLD), as well as the lower bound values LB2 and LBS. LBS is computed by the dual ascent
method described in §3.3 augmented by a subgradient optimization procedure with 30 iterations.
LB4 was dominated in all instances by at least one of LB2 and LBS, and therefore, it is not
reported. All values are normalized with respect to the optimum solution. These results indicate
that MLD yields excellent solution values; it is optimal is 18 instances. Z(MLD) is 0.4% more
on average, and 4.5% more in the worst case, than the optimal solution. Both LB2 and LBS are
seen to be strong bounds; neither one dominates the other. LB2 is, on average, 3.8% less than the
optimal value; in the worst case, it is 8.1% less. LBS has a somewhat better average performance,
although is more variable. It is 3.1% and 13.2% away from the optimal solution, on average and in
the worst case, respectively.

INSERT TABLE 1 HERE

The second set consists of 40 problem instances; these are shown in Table 2. As with the first
experiment, LB4 was dominated in all instances by at least one of LB2 and LBS, and it is,
therefore, not reported. The lower bound and solution values shown in Table 2 are normalized with
respect to the largest lower bound Lmax = max (LB2, LBS).

32

)

INSERT TABLE 2 HERE

These results indicate that the strong performance of MultilineDesign, and LB2 and LB3 extend
to larger problems as well. MLD is about 1.1% more than Lmax on average, and 3.0% in the worst
case, across the 40 problems. It required an average computational time of 0.334 seconds. Between
LB2 and LB3, neither is dominant across all problems. LB2 is, on average, 1.0% less than Lmax; in
the worst case, it is 5.3% less. The corresponding values for LB3 are 2.2% and 14.8%, respectively.
The average computational times for LB2 and LBS are 0.02 seconds and 147.6 seconds, respectively.

In both sets, we also monitor the intermediate SAP solution values obtained while implementing
MultilineDesign. In the first set, the SAP value is found to be 3.1% more on average, and 6.6%
more in the worst case, than the optimal solution. In the second set, it is 3.8% more than Lmax on
average. However, in the worst case, it is about 27% more than Lmax (which is also the optimal
solution value in this instance). Thus, while the average SAP solution value is reasonably good, it
has high variability.

7 Conclusion

This paper addresses the design of a single-stage manufacturing system with parallel lines com-
prising flexible workcenters. For a given set of products with their processing requirements and
demands, the objective of the design problem is to determine the product-to-line allocation that
minimizes the total investment in the lines and the workcenters. In this paper, we consider the
problem in which each product is required to be assigned to exactly one line.

We show that the flexible multiline design problem FMD2 is NP-complete. In view of its com-
plexity, we develop an implicit enumeration approach for solving this problem. We present several
lower bounding procedures for this problem based on various relaxations. In so doing, we show that
an effective lower bound for this problem is obtained by heuristically solving a relaxed problem in
which a product can be assigned to multiple lines. As shown in our computational study, this ap-
proach generates fairly strong bounds quite rapidly. We also construct a heuristic solution method
which efficiently exploits certain properties of the optimal solution. Our computational experience
reports the effectiveness of this method under a variety of problem scenarios.

33

REFERENCES

1. Corneujols, G., G. L. Nemhauser and L. A. Wolsey (1990), "The Uncapacitated Plant Lo-
cation Problem," in Discrete Location Theory, edited by R. L. Francis and P. Mirchandani,
John Wiley and Sons, New York, NY.

2. Dyer, M. E., N. Kayal and J. Walker (1984), "A Branch and Bound Algorithm for Solving the
Multiple- Choice Knapsack Problem," Journal of Computational and Applied Mathematics,
Vol. 11, 231-249.

3. Fisher, M. L., R. Jaikumar and L. Van Wassenhove (1986), "A Multiplier Adjustment Method
for the Generalized Assignment Problem," Management Science, Vol. 32, 1095-1103.

4. Garey, M. R. and D. S. Johnson (1979), Computers and Intractability: A Guide to the Theory
of NP-Completeness, W. H. Freeman and Company, New York, NY.

5. GeofFrion, A. M. (1974), "Lagrangean Relaxation for Integer Programming," Mathematical
Programming Study, Vol. 2, 82-114.

6. Guignard, M. and M. Rosenwein (1989), "An Improved Dual-Based Algorithm for the Gen-
eralized Assignment Problem," Operations Research, Vol. 37, 658-663.

7. Held, M., P. Wolfe and H. P. Crowder (1974), "Validation of Subgradient Optimization,"
Mathematical Programming, Vol. Vol. 6, 62-88.

8. Martello, S. and P. Toth (1990), Knapsack Problems: Algorithms and Computer Implemen-
tations, John Wiley and Sons, New York, NY.

9. Raman, N. and U. S. Palekar (1993), "Product Assignment in Flexible Multilines, Part 1:
Single-Stage Systems with Demand Splitting," Working Paper, Bureau of Economic and
Business Research, University of Illinois at Urbana-Champaign, Champaign, IL.

10. Ross, G. T. and R. M. Soland (1975), "A Branch and Bound Algorithm for the Generalized
Assignment Problem," Mathematical Programming, Vol. 8, 91-103.

34

Table 1
Computational Results - Set I

No.

N

Fi

F2

Lower

Bounds

Z(MLD)

LB2

LBS

1

15

32

302

1.000

0.969

1.000

2

15

42

131

0.987

0.957

1.000

3

16

47

135

0.947

0.990

1.000

4

14

46

712

0.923

0.952

1.038

5

15

44

570

0.962

0.986

1.000

6

10

15

932

0.935

0.915

1.000

7

16

31

751

0.932

0.957

1.000

8

14

36

417

0.953

0.951

1.000

9

16

40

965

0.998

0.952

1.045

10

15

13

861

0.959

0.997

1.000

11

15

5

340

0.962

0.959

1.000

12

16

26

295

0.968

0.946

1.000

13

17

30

508

0.936

0.997

1.000

14

15

44

312

0.958

0.989

1.000

15

15

48

376

1.000

0.868

1.000

16

12

18

670

0.953

1.000

1.000

17

14

42

639

0.919

0.988

1.000

18

15

48

531

0.959

0.949

1.000

19

14

42

145

0.981

0.998

1.000

20

16

2

685

1.000

0.964

1.000

35

Table 2
Computational Results - Set 2

No.

iV

*i

F2

Lower

Bounds

Z(MLD)

No.

n

*i

F2

Lower

Bounds

Z(MLD)

LB2

LB3

LB2

LBS

1

10

15

980

1.000

0.852

1.000

21

21

9

836

0.975

1.000

1.015

2

35

39

189

1.000

0.992

1.012

22

24

32

490

0.993

1.000

1.005

3

21

49

107

1.000

0.911

1.011

23

40

10

100

1.000

0.909

1.028

4

10

11

362

0.960

1.000

1.007

24

45

50

880

1.000

0.914

1.015

5

40

9

110

1.000

0.959

1.029

25

13

48

577

1.000

0.989

1.025

6

35

22

796

0.991

1.000

1.015

26

21

37

455

0.992

1.000

1.009

7

41

47

363

1.000

0.953

1.021

27

14

12

657

0.947

1.000

1.003

8

48

24

951

1.000

0.955

1.016

28

10

29

324

1.000

0.986

1.000

9

30

24

932

0.989

1.000

1.017

29

21

47

733

1.000

0.993

1.024

10

18

17

680

0.984

1.000

1.003

30

28

36

211

1.000

0.975

1.014

11

39

3

859

0.993

1.000

1.008

31

22

29

282

0.999

1.000

1.018

12

37

18

866

1.000

0.972

1.024

32

25

23

559

0.990

1.000

1.025

13

15

7

513

0.940

1.000

1.003

33

36

25

288

1.000

0.904

1.025

14

17

4

904

0.967

1.000

1.000

34

48

47

439

1.000

0.956

1.009

15

12

49

209

1.000

0.993

1.030

35

45

38

312

0.996

1.000

1.022

16

11

9

113

0.985

1.000

1.014

36

35

25

824

1.000

0.972

1.000

17

24

29

679

0.975

1.000

1.005

37

46

10

891

1.000

0.988

1.020

18

24

12

900

0.987

1.000

1.001

38

30

47

479

1.000

0.890

1.000

19

26

10

658

1.000

0.998

1.012

39

34

34

389

1.000

0.867

1.000

20

23

26

963

0.964

1.000

1.002

40

47

49

107

1.000

0.979

1.000

36

© 0

Si

b£)

fa

37

©®®©®©®©©

© © © ©
© © ©
© ©

©©©>©©

U

a
o

CO
O

o,
o

Ph

o
o

Eh

Ph
I

CM

0>
M

fa

38

©00Q00000

©00000

© ©

© ©

to

a
O

CO

O

o

—

39

©

Figure 3 - A Type 1 b-arc

0

Figure 4 - A Type 2 b-arc

40

00000000

© ©

00

© © © © © ©

85

© © © © ©

v©

0 0 0 0 0

© © © ©

© ©

©

O

>

>

'o>
u
a>

-a

=

s-
C

a
z

•—
'00

Q ©

41

©0©@©OOO

OOQ. OOOOO

o

o o o o o o

<s

O O J

©

O O O O 0 o

© ©

o
o

—

0*

(1)

3)

42

Figure 7 - The Enumeration Tree

43