Decomposition of the Design

Process
A. Kusiak
J. Wang
Intelligent Systems Laboratory,
Department of Industrial Engineering,
The University of Iowa,
Iowa City, IA 52242

In concurrent engineering, an attempt is made to perform design and other related

activities simultaneously rather than in series as in the case of traditional design.
This may result in a reduction of the duration of the design project, cost savings,
and better quality of the final design. However, the concurrent engineering approach
might increase the complexity of the design process and make it more difficult to
manage. One way to reduce the complexity of a large scale design project is to apply
decomposition. This paper presents a methodology for decomposition of a design
process to enhance concurrency. The incidence matrix is used to represent the relationship between tasks and design parameters. The decomposition of a task-parameter incidence matrix is discussed. The constraint-variable decomposition, which
is a special case of the task-parameter decomposition, is also presented for the
management of constraints. Clustering of tasks involved in the design process allows
one to determine a potential group of tasks that might be performed simultaneously
or tasks that need a special attention during the design process. As a result of
decomposition, the design cycle might be reduced. Another advantage of grouping
tasks is the simplification of scheduling and management of the design project.
Finally, the proposed approach provides a systematic way of decomposing a design
problem into subproblems.

Introduction
Design may require the coordination of many design and
analysis procedures. Due to the decreasing life cycle of products, it is important to reduce the time and cost of product
development. It has been identified that 70-80 percent of the
final production cost is determined during the design stage
[20]. In recent years, the concept of concurrent design has
emerged. It attempts to incorporate various constraints related
to the product life cycle, i.e., manufacturability, quality, and
reliability, in the early design stages. Concurrent design aims
at improvement of product quality, reducing the development
time and cost. However, due to the interaction between various
tasks, the complexity of the design process increases and makes
the process difficult to manage. Decomposition might be a
tool for simplifying the design process.
Decomposition has long been recognized as a powerful tool
for analysis of large and complex systems [4]. The advantage
of decomposition is that it reduces the complexity of the design
problem. Consider a problem with 120 variables that decomposes into 6 independent subproblems each with 20 variables.
Assume that each subproblem is solved in 20 seconds and the
computational time of solving the problem is proportional to
the number of variables. The computational time of solving
the main problem is the 6 x 20 = 120 seconds. In fact, for
most problems, the solution time increases at a higher rate,
e.g., exponentially, as a function of the size of a problem. This
makes the computational time more sensitive to the increase
in the number of variables.
Contributed by the Design Theory and Methodology Committee for publication in the JOURNAL OF MECHANICAL DESIGN. Manuscript received August
1991; revised August 1992. Associate Technical Editor: E. K. Antonsson.

Most research advocates the use of decomposition that allows to exhibit a high degree of cohesion within modules, and
low coupling between modules. The literature concerning research of decomposition in design is not very extensive. Brown
and Chandrasekaran [2, 3] presented a "design refinement"
approach that views design as a hierarchical system. The problem is solved by a top-down approach and refining the design
at each level of the hierarchy. Zarefar et al. [23] developed a
program for the design of a drive system with parallel axis
gears that is divided into a gear design module, axis design
module, and lubricant selection module. The three modules
are controlled by a system coordinator. Verrilli et al. [18]
presented a computer program for hierarchical distributed
problem solving. Hoeltzel and Chieng [5] proposed the distributed system architecture and planning control for concurrent engineering design environment. Johnson and Benson [6]
developed a two-stage decomposition strategy for design optimization. The strategy assumes that all the subproblems are
independent of each other. Azarm [1] applied decomposition
to problem solving using the concept of monotonicity. Most
of the previous research used intuitive methods that consider
the physics of the system as the prime factor directing the
decomposition. However, the quality of the results generated
by an intuitive method depends heavily on designers' experience. With the growing interest in engineering design, need for
a formal decomposition approach is apparent.
Some of the earlier work in the decomposition applied to
design include the research performed at NASA [14, 15, 16]
is concerned with the implementation of Steward's partitioning
algorithm [17] for identification of coupled design tasks. StewDECEMBER 1993, Vol. 115 / 687

Journal of Mechanical Design

Copyright 1993 by ASME

Downloaded From: http://mechanicaldesign.asmedigitalcollection.asme.org/ on 03/24/2016 Terms of Use: http://www.asme.org/about-asme/terms-of-use

a b c d e f g h
1 * * *
2 * * *
3
*~~*~|
4
**
5
I< *
6
* * *
7
* * *

Fig. 1

]
2
3
4
5

a b c d
* * *
* * *
*
*
*
'
1

f g h
* *
* *
* * * *
* * * *
* * * *
>
1

iC)

a b c d e f
1 * * *
2 * * *
3
* * *
4
|* * *
5 * * * * * *
6
* * * * * *

Three types of matrices

(a) decomposable matrix
(b) nondecomposable matrix with overlapping parameters
(c) nondecomposable matrix with overlapping tasks

to simplify the constraint management problem and to reduce

the computational time of constraint evaluation.
The paper is organized as follows. The decomposition of a
matrix representing relationship between tasks and parameters
is presented in Section 2. The constraint-variable matrix decomposition which is the special case of the task-parameter
matrix decomposition is discussed in Section 3. Conclusions
are presented in Section 4.

2 Decomposition of a Task-Parameter Matrix

ard's algorithm identifies tasks that are strongly connected or
form cycles [9].
In this paper, the design process is defined as a hierarchy
of design tasks with precedence relationships among them.
Each task is driven by certain input parameters and produces
output parameters. The information can be represented at
various levels of abstraction. Several tasks may be performed
by the same designer or groups of specialists. Before each task
is performed, one constructs a problem statement that encompasses the preconditions, information required, and precedence constraints. The person performing a design task applies
the knowledge in the domain of each task to reach the goal.
The knowledge may include equations, procedures, rules from
accepted practice, and judgment based on experience.
The objective of this paper is to develop a systematic approach for the decomposition of an overall design task into
subtasks with the minimal interdependence between subtasks
to enhance concurrency of the design process. The paper is
based on the premise that in order to significantly reduce the
design cycle, one has to decompose the design process. The
decomposition approach allows one to identify processes that
can be performed simultaneously or formulate strategies leading to their separation, e.g., considering alternative tasks, and
adding new resources. Incremental improvements of individual
design tasks are not likely to drastically reduce the design cycle.
The salient features of the decomposition approaches proposed in the paper are as follows:
low computational time complexity
a structured and systematic approach
suitability of human interaction or interfacing with an
intelligent software
the proposed approach is more general than the approaches presented in the literature.
The functional relationship between various tasks and parameters is represented with an incidence matrix [19]. An entry
" * " denotes that parameter j (for the matrix in Fig. 1(a), j
= a, . . . , h) appears in task / (in Fig. 1(a), / = 1, . . . , 7).
The organized matrices can be categorized as decomposable
and nondecomposable. An incidence matrix is decomposable
if its rows and columns can be grouped in such a way that the
matrix separates into mutually exclusive submatrices [see the
matrix in Fig. 1 (a)]. Analogously, an incidence matrix is nondecomposable if it cannot be arranged into mutually separable
submatrices [see the matrices in Fig. 1(b) and (c)\.
As the tasks and parameters associated with each of the
three submatrices in Fig. 1(a) are independent, they can be
computed simultaneously. In a nondecomposable matrix, submatrices are interdependent due to the overlapping parameters
[parameters g and h in Fig. 1(b)] and overlapping tasks [tasks
5 and 6 in Fig. 1(c)]. In order to be able to consider simultaneously the two clusters of tasks in Fig. 1 (b), an additional
action is required, e.g., the values of the overlapping parameters g and h could be provided.
In addition to tasks and parameters, decomposition strategy
can be applied to the management of constraints. Design constraints frequently show some degree of coupling which complicates the computational process and tool used for constraint
management. In this paper, a decomposition approach is used
688 / Vol. 115, DECEMBER 1993

2.1 Decomposition Concept. Design and analysis activities involve a large number of tasks, e.g., layout design, finite
element analysis, and testing. To design new products of high
quality in less time, one should explore the possibility of the
decomposition of the design task into a group of tasks. The
relationship between tasks is analyzed in order to detect potential tasks that can be performed simultaneously.
The decomposition problem is formulated as follows:
Decompose a task-parameter incidence matrix into mutually separable submatrices (groups of tasks and groups
of parameters) with the minimum number of overlapping
tasks subject to the following constraints:
Constraint CI: Empty groups of tasks or parameters
are not allowed.
Constraint C2: The number of tasks in a group cannot
exceed the upper limit b (or alternatively, the number of parameters in a
group is not to exceed, d).
Of course, other constraints, for example, a resource cannot be used for two different tasks at the same time, can
be considered.
The objective function is "to minimize the number of overlapping parameters." An alternative objective function may
be used, for example, "to maximize the measure of effectiveness" defined in McCormick et al. [13].
To deal with the overlapping tasks, the following actions
can be taken:
Al. One can take advantage of the special structure of
the matrix and apply appropriate solution approaches.
A2. One may replace an overlapping task with an alternative task that involves different parameters.
A3. The design parameter can be decomposed into subparameters and each subparameter assigned to a
group of tasks that have some commonality with
that subparameter.
A4. An overlapping task can be removed from the matrix.
A5. The duration of the overlapping task can be shortened (e.g., by better management of resources or
tools used).
The concept of decomposition simplifies the design process.
Also, it explores the potential concurrency among design tasks
and reduces the time involved in the design process. The challenge is to decompose the overall design process into groups
of tasks that are of acceptable size, can be easily solved, and
for which an overall solution can be generated from the partial
solutions.
The decomposition concept is illustrated in Example 1.
Example 1
Consider a hypothetical design scenario involving ten design
tasks and seventeen design parameters. The relationship between tasks and parameters is represented as a flow diagram
shown in Fig. 2. For example, xs is the input parameter and
#15 and xn are output parameters of task px.
The task-parameter incidence matrix corresponding to the
network in Fig. 2 is shown in matrix (1):
Transactions of the ASME

Downloaded From: http://mechanicaldesign.asmedigitalcollection.asme.org/ on 03/24/2016 Terms of Use: http://www.asme.org/about-asme/terms-of-use

: Source or destination

: Design task

fr- : Parameter flow

Fig. 2 A flow diagram of the design process

Fig. 3 Three independent groups of tasks and parameters

Parameter
x2
x

Task

X4
x

noX "12x "14x

13
15
*9
H

Pi
P2
P3
P4
Pj
P6
P7
P8

*
*

*
*
*
*

P9

*
*

*
*
*
*

PlO

17

(1)
Matrix (1) is nonstructured and it is difficult to recognize
any groupings among the tasks and parameters. The problem
to be solved is to cluster the incidence matrix into groups of
tasks and parameters.
Applying the cluster identification (CI) algorithm [8] to matrix (1) results in matrix (2):
Parameter
G-2
J

G-i
I

1I

X]3

x5

Task

Pi
Pi
GP-1
Ps
Pio
P3
GP-2
P4
Lp8
GP-3

X,

x, 5

* * *
*

X6

x3

* * *
*
*
*
*

JP6

'

X 16

X2

xn

I I

xu

X14

X9

x7

"* * *
*
* *
*
*

G-3
l_

x4

x,o

1
X 12

x8

~* *
* * *
*
* *

(2)
Three mutually exclusive groups of task GP-1 = \pu p2,
Ps,P\o], GP-2 = {p 3 ,p 4 ,p 8 ],GP-3 = {p6,Pi,P9} and three
groups of parameters G-l = {xu JC3, x5, x6, xn, x15, x, 7 |, G2 = \xj, Xyt Xg, Xn, Xis], G-3 = [X4, x$, Xio, X\2, X\$\, are

visible in matrix (2). Based on the clustered matrix (2), it is

clear that the three groups of tasks can be performed simultaneously (Fig. 3).
If an incidence matrix cannot be decomposed into mutually
separable submatrices, a number of actions can be taken. One
is to identify the overlapping parameters or overlapping tasks
and remove them from the matrix. A decomposition algorithm
is discussed that is a modified version of the clustering algorithm presented in Kusiak and Cheng [7] and includes a new
branching scheme.
2.2 Algorithm 1. The branch-and-bound algorithm presented in this section analyzes the task-parameter matrix and
Journal of Mechanical Design

attempts to detect the potential tasks that can be performed

simultaneously in order to reduce the time of product development.
The algorithm iteratively examines each unfathomed node
in the enumeration tree. The upper bound Zy on the objective
function is the number of tasks being removed from the initial
matrix. The lower bound ZL is calculated only after a feasible
solution has been determined. Tasks having the highest number
of parameters are removed one at a time. The algorithm is
presented next.
Branch-and-Bound Algorithm
Step 0. (Initialization)
Initialize the initial code containing the incidence
matrix (ay). Set the upper limit Zy = + oo.
Step 1. (Branching)
Based on the depth-first search strategy, select an
active node (not fathomed). Apply the CI algorithm to the submatrix of a node that does not
satisfy constraint C2. When the submatrix cannot
be partitioned, apply a branching scheme to the
submatrices at the same level.
Branching scheme:
Remove a task with the largest number of parameters, one at a time.
Step 2. (Bounding)
For each new node, obtain a lower limit ZL.
Step 3. (Fathoming)
Exclude a new node from further consideration if:
Test 1: ZL > Zv,
Test 2: Any corresponding submatrix violates constraints CI or C3,
Test 3: All corresponding submatrices satisfy the
three constraints. If ZL < Zv, store this solution
as the new incumbent solution, set Zu = ZL, and
reapply test 1 to all remaining unfathomed nodes
created previously.
Step 4. (Stopping rule)
Stop when there are no unfathomed nodes remaining; the current incumbent solution is final.
Otherwise, go to step 1.
Example 2
Consider the design of an electro-mechanical product. Five
departments are involved in the design process. Department
A is responsible for the definitions of the specifications for
the product. Departments B, C, and D are in charge of electrical
design, mechanical design, and cabinet design, respectively.
The testing and documentation of the product is performed
by department E. The flow diagram and the corresponding
task-parameter matrices and precedence matrices for each department are shown in Fig. 4. The precedence matrix indicates
the precedence relationship between design tasks; e.g., if an
entry av is nonempty, then task j precedes task i.
DECEMBER 1993, Vol. 115 / 689

Downloaded From: http://mechanicaldesign.asmedigitalcollection.asme.org/ on 03/24/2016 Terms of Use: http://www.asme.org/about-asme/terms-of-use

Combining the task-parameter matrix and the corresponding

precedence matrix of five departments results in matrix (3) and
(4):
X2
Xl

X4
X3

Department A

X6
Xg Xio X 1 2 X M X)6 X[g X20 X J J X24 X 2 6 X 2 g
X 5 X 7 X 9 X n X l 3 Xlj X17 X19 X21 X23 X25 X 2 7

(rs)*"'

XI X2X3 X20X4X6X9

P |

Pl

P6

X9X23X28X5

P2
PlS

P2P15
P2
Pl5

(a)
Department C

j * 2 i ^0
(j6)&~
x

(3)
P2
Pi

23

x 6 X7X23X 2 6 X 2 7XgXi3

P4P11P16

X4 X7X21XMX25X22Xio

P5 I * * * *

P4 P t Pa P10 P12 P>4 P i 6

P 3 P s P7 P 9 P n P13 P i s P17

P s P 3 PloPl2
P

P3
PlO
Pl2

Pi
P2
P3
P4
Ps
Pe
P7
Pn
P9
PlO
pn
P12
P 13
Pl4
Pl5
Pl6

(d)

(C)

Department E

Pn
(4)

Applying the branch-and-bound algorithm to matrix (3) produces matrix (5).

X2
X

Pl
Ps
P3
PlO
Pl2
P2
Pis
Pll
Plfi
P7
P13
Pl4

X3

Pi
P6
P4

Pa

P8
P9
P7
Pl3
Pl4
Pl7

, , ,,
* **
* *
* *

* * * *

* *l
*

-fr-

(5)
Matrix (5) contains a valuable information. First of all, it has
been determined that the overlapping tasks p4, p6, and ps are
critical to the design process. In the absence of the three tasks,
the design process would decompose into seven separable processes (see Fig. 5) that could be performed simultaneously. A
product planner may develop strategies leading towards the
weakening of the precedence relationship between tasks p4, p&,
and ps and the remaining tasks. He may focus especially on
the critical tasks and those related to them. Close analysis of
these tasks should improve the design process. Each of the
seven subprocesses in Fig. 5 can be also closely analyzed for
potential inconsistencies and improvements. It should be
stressed that the decomposition approach simplifies analysis
of the design process.
2.3 Analysis of Design Tasks. Whenever a task-parameter flow diagram can be decomposed into mutually separable
groups, no analysis of relationships between groups is needed.
690 / Vol. 115, DECEMBER 1993

p8
P9
P7
Pl3
Pl4
Pl7

* * * * * * * \*****
* * \
* *\
*\ **
\* *
\ ** *

* * *;

Pn

Ps P9P7P13P14P17

x 5 xgxtoxisx^xuxtsxwxtextgxnxw

x 2 8 x 26 x27 x l l X16 x 17 x 12 X 6
X2o x 7 X 2 4 X22 x 9
x
x
X 4 X 2 , X 2 5 Xic X23 X 5 Xs
13 x 14 X18 XIS
15

*
* *
* *
* * ~*

(e)
: Source or destination

: Design task

: Parameter flow

1. Customer requirements
2. Cabinet design
3. Components available
4. Mechanical design
5. Electrical design
6. Design specifications
7. Test assembly
8. Complete assembly

9. Complete documentation
10. Circuit boards available
11. Make parts
12. Assemble boards
13. Field tests O.K.
14. Environmental tests O.K.
15. Make cabinet
16. Make castings
17. Begin production

Fig. 4 Flow diagrams, task-parameter matrices, and precedence matrices of the design process

GP-2

Fig. 5

Flow diagram of the design process after decomposition

Transactions of the ASME

Downloaded From: http://mechanicaldesign.asmedigitalcollection.asme.org/ on 03/24/2016 Terms of Use: http://www.asme.org/about-asme/terms-of-use

However, if overlapping tasks exist, analysis of the relationship

between groups is required.
An overlapping task can be viewed as an internode between
groups of tasks. For example, task ps in Fig. 5 has to be
performed prior to the group of tasks GP-2 and GP-6. Also,
one can notice that the overlapping tasks, i.e.,p4,p6,ps, should
be performed as early as possible during the design process in
order not to delay the completion time of the design project.
Furthermore, it is important to shorten the duration of the
overlapping tasks in order to reduce the product development
time.
Finally, the overlapping tasks may be redefined in order to
enhance concurrency. The degree of concurrency may be defined as follows:
Degree of concurrency =

max {T,\
i

where 7} is the time to perform group / of tasks

The higher the degree of concurrency, the shorter the duration
of the design process. As an example, action A2 (replacement
of an overlapping task with an alternative task) could be taken
so that task p 4 is replaced with task pi with parameters x1
removed. As the result of action A2, five groups of tasks have
been created [see matrix (6)].
It is important to interpret the meaning of the removal of
input parameters. Having removed the link x6 in Fig. 5, task
pi can be performed without waiting for the completion of
task Pi. However, an alternative input information has to be
provided for task pi in order to produce the output required.
In order to delete cycles from an incidence matrix, the triangularization algorithm [9, 10] can be used. Additionally, the
size of the design problem can be reduced by labeling several
input parameters as one parameter. The local parameters generated for a task do not have to be considered, because they
do not influence other tasks.

X2
Xl

Pi
P5
p3
PiO
Pl2
P2
PlS
Pi I
Pl6

P4
P7
p13
Pl4
Pl7

P9
p6

Ps I

X3

Decomposition of the Constraint-Variable Matrix

3.1 Problem Definition. Complex designs may involve a

large number of design constraints and variables. In most
situations, design constraints exhibit some degree of coupling,
which tends to complicate the constraint management and tools
used during the design process. To simplify the constraint
management problem and reduce the computational time of
constraint evaluation, the decomposition approach is applied.
To detect the potential groups of constraints that can be
evaluated simultaneously, two cases are considered: identifying
overlapping variables and overlapping constraints. The objective is "to minimize the number of overlapping variables or
constraints''; i.e., " to minimize the dependency between groups
of constraints."
To deal with the overlapping variables, the following actions
can be taken:
Bl. Assume that the value of each overlapping variable
is known whenever possible.
B2. One could duplicate the overlapping variable in each
group of constraints that the variable is included.
However, the consistency among partial solutions
derived from each group of constraints has to be
preserved.
In some cases, the value of the overlapping variable is difficult
to estimate or the overlapping variable is the variable that
should be derived; the previously mentioned action A2 is taken.
Similar to variables, the overlapping constraints may have
the following properties:
D l . The overlapping constraints can be removed from
the matrix. This process is known in optimization
theory as constraint relaxation.
D2. The overlapping constraint can be reformulated to
affect the structure of the incidence matrix [22].
D3. One can take advantage of the special structure of
the matrix and apply appropriate algorithms for
solving the set of equations, e.g., Benders' decomposition method.

X 2 0 X 2 1 X25 Xio X23 X S

Xg
Xn Xu
X16
X17 X , 2
X4
X24 X 2 2 X 9
X^ XM
X27 X6
X14 X18 X19
x15

3.2 Algorithm 2. The branch-and-bound algorithm presented in this section analyzes the constraint-variable matrix
and identifies the potential constraints that can be evaluated
simultaneously during the design process in order to reduce
the product development time.
The algorithm iteratively examines each unfathomed node
in the enumeration tree. The lower bound ZL on the objective
function is the number of overlapping variables in the matrix.
The upper bound Zy is calculated only after a feasible solution
has been determined. The decomposition algorithm for the
constraint management problem is identical to Algorithm 1
presented in Section 2 with the exception of Step 1, which has
to be replaced with Step 1 presented next.

* * * *

IT-*
1
.

*
*

*

^ ^
.
*
*
I
* *

. .

I*

__
(6)

2.4 Benefits from Decomposition of the Design Process.

Grouping tasks involved in the design process allows one to
determine a potential group of tasks that might be performed
simultaneously. The degree to which the tasks can be performed simultaneously depends on the quality of clusters and
the nature of relationship between tasks.
Another advantage of grouping tasks is the simplification
of scheduling and management of the design project [11, 21].
Scheduling a number of subnetworks with a small number of
tasks is easier than scheduling the entire network.
Furthermore, it is advantageous that a related group of tasks
be located in the same physical area. Close interaction of members of a group allow for efficient resolving of design conflicts.
Journal of Mechanical Design

Step 1.

(Branching)
Based on the depth-first search strategy, select an
active node (not fathomed). Apply the CI algorithm
to the submatrix at a node that does not satisfy constraint C2. When the matrix does not decompose into
mutually separable submatrices, apply a branching
scheme to the submatrices at the same level.
Branching scheme:
Calculate the value of the overlapping measure (OM)
for each variable (constraint) and remove the variable
(constraint) with the highest value of the overlapping
measure. The overlapping measure OMj for variable
(constraint) j is defined as the number of distinct
variables that are included in at least one constraint
required by the variable j .
The following two conditions are considered:
DECEMBER 1993, Vol. 115 / 691

Downloaded From: http://mechanicaldesign.asmedigitalcollection.asme.org/ on 03/24/2016 Terms of Use: http://www.asme.org/about-asme/terms-of-use

Fig. 6 Helical compression spring

(7) If more than one variable have the same value

of the overlapping measure, then remove a variable corresponding to the constraint with the
minimum number of variables.
(2) If the number of nonempty elements in a row
is equal to one, then remove the row (constraint)
and variable corresponding to the nonempty element from the matrix.
Next, the decomposition concept used in the constraint management problem is illustrated with the example of a helical
spring [12].
Example 3
Figure 6 shows a helical compression spring used in the
poppet relief valve. The poppet relief valve allows flow of a
fluid from the inlet to the outlet when the pressure of the fluid
exceeds a certain threshold pressure called the ' 'cracking" pressure. If a pressure is greater than the cracking pressure the
fluid opens the poppet valve and holds it in equilibrium against
a helical compression spring. As pressure is below the cracking
pressure, the poppet valve is held against a seal due to the
helical spring and thereby cuts off fluid flow from the inlet to
outlet. The helical spring, which is the main component of the
poppet relief valve, is used to illustrate the decomposition
concept.
The equations pertaining to design of the helical compression
spring are as follows [12]:

A:
h:

fi:

FC = P<A

Assuming that all design variables in constraints (7) through

(16) are unknown, the design variable with the largest value
of OMj is variable d (see matrix (18)). Removing variable d
(i.e., fixing the value of variable d) causes that the variable 5
can be computed from constraint/ 2 . Thus, constraint/ 2 and
variable d are removed from the matrix (18).

-4
144p<72

_
^d

(9)

gA

Fd

h-

(10)

=T

Gd4
8D*R
Ls = d(N+2)
N=5-

Fc

4C-1

0.61

* * *

f3

where:
Fd
Fc
A
5
d
Pc
q

=
=
=
=
=
=
-

dynamic force (lb)

cracking force (lb)
area (in )
stroke (in)
wire diameter (in)
cracking pressure (psi)
flow (ftVsec)

692 / Vol. 115, DECEMBER 1993

q
Fd

S
R

5 4 2 3 3 3

D
F

N
K

Ls
G

Li
Lf

* *

u
n

* * * *

<

* *
*

V2

V]

(18)

(13)
Similarly, variables R, Fd, and constraint / 4 are removed
from the matrix (18). The enumeration tree of the branch-andbound algorithm for matrix (17) is shown in the Appendix.
The result is shown in matrix (19).

(15)
A
Pc

C-d

fl

Fc

/,o-

Pc

f7
fs
f9
fio

OMi

4 3 10 4 2 9 4 4 8 5

(12)

(14)

R
K

(11)

52

(8)

2.55FD
S= d,
K

f.

spring rate (lb/in)

stress (psi)
load on spring (lb)
mean coil diameter (in)
Wahl factor
number of active coils
torsion modulus (psi)
solid height (in)
free length (in)
installed length
spring index
water density (lb/in 3 )
acceleration of gravity (ft/s2)

(17)

f,:

=
=
=
=
=
=
=
=
=
=
=
=
=

The incidence relationship between constraints and variables

is shown in matrix (17):

(7)

h'

R
S
F
D
K
N
G
Ls
Lf
L;
C
P
g

(16)

fl
f3

is
f6
f7

u
12
fio

Lf
q

Li

D
F

U
G

* * *
* *
*
* *

d
Fd

*
* * * *
*
* *
*
*
*
*
*
*

*
*
* *
*

*
*
*
* *
*
(19)

Transactions of the ASME

Downloaded From: http://mechanicaldesign.asmedigitalcollection.asme.org/ on 03/24/2016 Terms of Use: http://www.asme.org/about-asme/terms-of-use

One easily observes in matrix (19) that assigning values to

the variables d and R (action Bl) decomposes the matrix into
two groups of constraints, GF-1 = [fufi<A\
and GF-2 =
[fs, fe< /?. fs, /io). and two groups of variables, GV-1 = [Fc,
Pc, A, q, L}, L{\ and GV-2 = [S, F, D, K, N, G, Ls, C).
Each of them could be solved independently [see matrix (20)].
However, more than one iteration may be required, because
the quality of the solution obtained depends on the assumed
values of the overlapping variables d and R. If the obtained
solution is not satisfactory, one needs to adjust the value of
the overlapping variables and solve the subproblems again.
The value assigned to the overlapping variable may come from
handbooks, design specifications, or experience.

Another way to increase the concurrency in the evaluation

of constraints is to identify overlapping constraints. Applying
the branch-and-bound algorithm to matrix (17) results in matrix (23). Two groups of constraints, GF-1 = (/,, / 3 ) and GF2 = I/2, fi, /9. /io). and two groups of variables, GV-1 =
[Fc, Pc, A,Fd,q)
and GV-2 = [5, d, D, K, N, Ls, C), could
be formed. However, to obtain a feasible solution to the original matrix, the solution obtained from groups GF-1 and GF2 in matrix (23) would have to satisfy constraints/4,/s,/ 6 , and

u
Fc

A
Pc

GV-2
I

GV-1
A

Lf

Pc

r f i

* * *
*
*

1 I
S
D
N
Ls
L;
F
K
G
C

f6
f?

*
(20)

Duplicating (action B2) the overlapping variables d and R

from matrix (19) results in matrix (21). Two groups of constraints GF-1 = | / , , / 2 , / 3 , / 4 , / 8 ) and GF-2 = [fs, f 6 , / 7 , / , ,
fio) and two groups of variables GV-1 = [Fc, Pc, A, g, Lf,
L S, Fd, d, R) and GV-2 = \S,F, D, K, N, G, Ls, C,d,R]
are formed and can be solved simultaneously. However, a
conflict may occur among solutions generated from each of
the two groups of constraints. A compromise solution can be
reached, for example through negotiation.
GV-2

GV-1

i
r
-\
Fc
A
Lf
8
(dY_S
D
N
Ls ( d L
Pc
q
Li
Fd
F
K G
C (8)
fl
f3

* * *
*

* *

f4

*
*
*
* *
*
_ _ _-
*
* *
* *
*
* *
*
*
*
* *

h
U

f?
O
f9
L
fio
Cu-

(21)
In the case when the value of the overlapping variable d
(wire diameter) is duplicated (action B2) and the value of variable R is assumed (action Bl), the resultant matrix is shown
in (22).
GV-2

GV-1
I
Fc

A
Pc

fl
f3
fs
f2
.f4
f5
is
0 . - f?
f9
D
fio

Lt
q

8
Li

* * *
* *
*
* *
"~-

1 r
S
Fd

D
F

N
K

* *
~

Ls
N

**

* *

S
C

Lr

**
* **

Conclusions
In this paper, a methodology was presented for the decomposition of the design process. The incidence matrix was used
to represent the relationship between design parameters (variables) and tasks (constraints). Two cases of decomposition
were discussed. In the first case, the incidence matrix was
decomposed into mutually separate submatrices. No analysis
of the relationship between groups of tasks (constraints) was
needed. In the case of overlapping tasks (constraints), analysis
of the relationships between the groups of tasks (constraints)
was required. Three observations can be drawn:
(1) The overlapping tasks should be performed as early
as possible during the design process in order not
to delay the completion time of other activities.
(2) One may redefine (reformulate) the overlapping
tasks (constraints) in order to enhance degree of
concurrency.
(3) Decomposition strategy simplifies the constraint
management and reduces the computational time
for solving the resultant subproblems.
Groups of tasks (constraints) involved in the design process
allow one to determine a potential group of tasks (constraints)
that might be performed simultaneously. The latter should
reduce the time of product development. Another advantage
of grouping tasks (constraints) is the simplification of scheduling and management of the design project (constraint management).

*
* * * *

*
*

* *
*
*

*~

*
*
*
* *

References

(22)
Journal of Mechanical Design

* **
* * #

K
D

Acknowledgment
The research presented in this paper has been partially supported by research grants (DDM-9007158 and DDM-9215259)
from the National Research Foundation and research contracts
from Rockwell International.

*
*

f7
f9
f 10
fs
f6
fs
f4

d
5

(23)
In some cases, the reformulation of the overlapping constraints (action D2) is possible. The reader interested in constraint reformulation may refer to Watton and Rinderle [22].

* *
*
*

fio

rh
u

* *

rfs

GP-2

I
Fc

q
Fd

1 Azarm.S., 1987, "Optimal Design Using a Two-Level Monotonicity-Based

Decomposition Method," Proceedings of the 1987 ASME Design Automation
Conference, Boston, MA, pp. 41-48.
2 Brown, D.C., and Chandrasekaran.B., 1985, "Expert Systems for a Class

DECEMBER 1993, Vol. 115 / 693

Downloaded From: http://mechanicaldesign.asmedigitalcollection.asme.org/ on 03/24/2016 Terms of Use: http://www.asme.org/about-asme/terms-of-use

of Mechanical Design Activity," Knowledge Engineering in Compuler-Aided

Design, Gero, J. S., ed., Elsevier, North-Holland.
3 Chandrasekaran, B., 1989, " A Framework for Design Problem-Solving,"
Research in Engineering Design, Vol. 1, No. 2, pp. 75-86.
4 Courtois, P. J., 1985, "On Time and Space Decomposition of Complex
Structures," Communication of ACM, Vol. 2, No. 6, pp. 590-603.
5 Hoeltzel, D. A., and Chieng, Wei-Hua, 1990, "Systems for Unified LifeCycle Mechanical Engineering Design: Shared-Tool Architectures Versus Distributed Tool Architectures," Engineering with Computers, Vol. 6, pp. 211222.
6 Johnson, R. C , and Benson, R. C , 1984, " A Basic Two-Stage Decomposition Strategy for Design Optimization," ASME JOURNAL OF MECHANICAL
DESIGN, Vol. 106, pp. 380-386.
7 Kusiak, A., and Cheng, C. H., 1990, " A Branch-and-Bound Algorithm
for Solving the Group Technology Problem," Annals of Operations Research,
Vol. 26, pp. 415-431.
8 Kusiak, A., and Chow, W. S., 1987, "Efficient Solving of the Group
Technology Problem," Journal of Manufacturing Systems, Vol. 6, No. 2, pp.
117-124.
9 Kusiak, A., and Wang, J., 1993, "Efficient Organizing of Design Activities," International Journal of Production Research, Vol. 31, No. 4, pp. 753769.
10 Kusiak, A., and Wang, J., 1993, "Decomposition in Concurrent Design,"
Concurrent Engineering: Automation, Tools, and Techniques, Kusiak, A., ed.,
John Wiley & Sons, New York, pp. 481-507.
11 Kusiak, A., and Park, K., 1990, "Concurrent Engineering: Decomposition
and Scheduling of Design Activities," International Journal of Production Research, Vol. 28, No. 10, pp. 1883-1900.
12 Lyons, J. L., 1982, Lyons' Valve Designer's Handbook, Van Nostrand
Reinhold Publishing Co.
13 McCormick, W. T., Schweitzer, P. J., and White, T. W., 1972, "Problem

Decomposition and Data Reorganization by Clustering Technique," Operations

Research, Vol. 20, pp. 992-1009.
14 Rogers, J. L., 1989, "DeMAID: A Design Manager's Aided for Intelligent
Decomposition User's Guide," NASA TM-I0157S, Langley Research Center,
Hampton, VA.
15 Sobieszczanski-Sobieski, J., 1982, "A Linear Decomposition Method for
Large Optimization ProblemsBlueprint for Development," NASA TM-83248,
Langley Research Center, Hampton, VA.
16 Sobieszczanski-Sovieski, J., 1989, "Multidisciplinary Optimization for Engineering Systems: Achievements and Potential," NASA TM-101566, Langley
Research Center, Hampton, VA.
17 Steward, D. V., 1981, Systems Analysis and Management: Structure, Strategy, and Design, Petrocelli Books, New York.
18 Verrilli, R. J., Meunier, K. L., Dixon, J. R., and Simmons, M. K., 1987,
"Iterative Respecification Management: A Model for Problem-solving Networks
in Mechanical Design," Proceedings of the ASME Computers in Engineering
Conference, ASME, New York, pp. 103-112.
19 Warfield, J. N., 1973, "Binary Matrices in System Modeling," IEEE
Transactions on Systems, Man, and Cybernetics, Vol. SMC-3, No. 5, pp. 441449.
20 Whitney, D. E., 1988, "Manufacturing by Design," Harvard Business
Review, pp. 83-91.
21 Wiest, J. D., and Levy, F. K., 1977, A Management Guide to PERT/
CPM, Prentice-Hall, Englewood Cliffs, NJ.
22 Watton, J. D., and Rinderle, J. R., 1990, "Improving Mechanical Design
Decisions with Alternate Formulations of Constraints," Proceedings of the
Second International Conference on Design Theory and Methodology, ASME,
Chicago, IL, pp. 69-75.
23 Zarefar, H., Lawley, T. J., and Etesami, F., 1986, "PAGES: A Parallel
Axis Gear Drive Expert System," Proceedings of the ASME Computers in
Engineering Conference, ASME, New York, pp. 145-149.

(continued on p. 695)

694/Vol. 115, DECEMBER 1993

Transactions of the ASME

Downloaded From: http://mechanicaldesign.asmedigitalcollection.asme.org/ on 03/24/2016 Terms of Use: http://www.asme.org/about-asme/terms-of-use

A P P E N D I X
The Branch-and-Bound Tree for Branch-and-Bound Algorithm

*
5 2 4 3 10 4 2
9 4 4 8 5 5 4 2 3 3 3
FcnA
d q
S
D N It U
Pc
6 Fd R F
K G Lf C
fl
f2
f3

+ *

* *
*

*
*
*

f5
f6
f7
fg
f9
flO

* * * *

* *

,1,00
5 2 4 3 2
FcAT,q
P0 F d

7 3 3 7 4 4 3 1 3 3 2
S D N L, L;
F
K G Lf C

fl
tl
f4
f5
f
f7

* * *
* * *
*
*

+ * * *
+

* *
*

fl
f^
fs

\@0

N L Lj
K G Lf C

*
* *

*
* * * *

*
*

*
*

Lower bound
=2

* *
*
*

Algorithm
Fc

A
Pc

# * *
*
*

Li Lj
G Lf

* *
*
*
*

Algorithm
Fc A
L{ S
D N Ls
5 d
Pc
q
Li
F
K G C Fd R
fl
f3
fs
fs
f6
f7
f9
flO
f2
f4

N
F

* *

f7
fs

*
*

* *

S
R

* * *

fl
t3
f4
fs

* * * *
*
* *
*
*
*

Fd

Pc

Fc

* * *

f7
f8
f9
tio

s
q

@/
Pc

f9
flO

Fc

Lower bound
=1

+ *

*
*
*

*
*
*
* *
*

fl
f3
f4
f
f7
Is
ts

q
Fd

N
R

L Li F
G Lf S

* * *
* * *
*
*
* * *
*
*

*
* *

Lower bound
=2

* *
Fathomed

Upper bound = 2

Journal of Mechanical Design

DECEMBER 1993, Vol. 115/695

Downloaded From: http://mechanicaldesign.asmedigitalcollection.asme.org/ on 03/24/2016 Terms of Use: http://www.asme.org/about-asme/terms-of-use