Expert Systems With Applications: Wen-Chin Chen, Yung-Yuan Hsu, Ling-Feng Hsieh, Pei-Hao Tai
Expert Systems With Applications: Wen-Chin Chen, Yung-Yuan Hsu, Ling-Feng Hsieh, Pei-Hao Tai
Expert Systems With Applications: Wen-Chin Chen, Yung-Yuan Hsu, Ling-Feng Hsieh, Pei-Hao Tai
a r t i c l e i n f o a b s t r a c t
Keywords: Research in assembly planning can be categorised into three types of approach: graph-based, knowledge-
Assembly sequence planning based and artificial intelligence approaches. The main drawbacks of the above approaches are as follows:
Assembly precedence diagrams the first is time-consuming; in the second approach it is difficult to find the optimal solution; and the
Neural networks third approach requires a high computing efficiency. To tackle these problems, this study develops a
Design of experiment
novel approach integrated with some graph-based heuristic working rules, robust back-propagation neu-
Taguchi method
ral network (BPNN) engines via Taguchi method and design of experiment (DOE), and a knowledge-based
engineering (KBE) system to assist the assembly engineers in promptly predicting a near-optimal assem-
bly sequence. Three real-world examples are dedicated to evaluating the feasibility of the proposed
model in terms of the differences in assembly sequences. The results show that the proposed model
can efficiently generate BPNN engines, facilitate assembly sequence optimisation and allow the designers
to recognise the contact relationships, assembly difficulties and assembly constraints of three-dimen-
sional (3D) components in a virtual environment type.
Ó 2009 Elsevier Ltd. All rights reserved.
1. Introduction product and verifying the liaison sequence. Homen de Mello and
Sanderson (1991a) made a representation of the directed AND/
In general, assembly involves the integration of components and OR graphs to create feasible assembly sequences. In addition, Kroll
parts to create a product or system through computer-aided design (1994) used graph-based procedures with conventional represen-
and manufacturing (CAD/CAM) systems. Assembly planning is a cru- tations to reduce the number of sorting operations required. He
cial design step for generating a feasible assembly sequence. Tradi- then extended his previous approach from uniaxial assemblies to
tional assembly planning is manual and based on the experience triaxial assemblies and presented a set of rules for resolving con-
and knowledge of industrial engineers; however, manual analysis flicts between multiple parents and multiple offspring. However,
does not allow the feasibility of assembly sequences to be easily ver- in practice most assembly companies use semi-automatic systems
ified. In the electronics industry, the approximate 40–60% of total to generate an assembly plan and employ 2D cross-sectional views
wages was paid to assembly labors (Kalpakjian, 1992). The imple- to represent their heuristic models (Lin & Chang, 1993).
mentation of design for assembly (DFA) and design for manufactur- Assembly planning is also regarded as ‘‘assembly by disassem-
ing (DFM) resulted in enormous benefits, including the bling,” i.e., an assembly sequence results from systematically disas-
simplification of products, reduction of assembly product costs, sembling the final product and reversing the disassembling
improvement of quality, and shrinkage of time to market (Kuo, sequence (Lee, 1989). This approach usually employs the contact-
Huang, & Zhang, 2001). Good assembly sequence planning (ASP) based feature to represent the precedence relationships of the
has been recognised as a practical way of reducing operational diffi- product. A designer can successively assign the assembly relations
culties, the number of tools and the working time (Lai & Huang, to form the assembly plan based on the precedence diagram. How-
2004). ever, the contact-based precedence diagram cannot effectively ex-
De Fazio and Whitney (1987) adopted the concept of Bourjault press the complexity of the assigned assembly relations. An
(1984) to generate a complete set of assembly sequences. They effective assembly plan must include other graphs, such as the
generated sequences in two stages – creating the precedence explosion graph, the relational model graph, the incidence matrix,
relations between liaisons or logical combinations of liaisons in a the assembly precedence diagram (APD), etc. In reality, few experts
or engineers know exactly how to derive a correct explosion graph,
draw a complete relational model graph or incidence matrix
* Corresponding author. Tel.: +886 3 518 6585; fax: +886 3 518 6575.
E-mail addresses: cheng.liu@shef.ac.uk (W.-C. Chen), yyhsu@chu.edu.tw among the components, or determine a complete APD to generate
(Y.-Y. Hsu). an optimal assembly sequence (Chen, Lu, & Tai, 2004b, 2008).
0957-4174/$ - see front matter Ó 2009 Elsevier Ltd. All rights reserved.
doi:10.1016/j.eswa.2009.05.098
W.-C. Chen et al. / Expert Systems with Applications 37 (2010) 716–726 717
based on rules and the powerful CAD/CAM applications that used Item Control factor Level 1 Level 2
to design, configure and assemble products, examples of which in- A Number of neurons in the hidden layer 4 18
clude the so-called expert systems, web-based knowledge bases B Learning rate 0.3 0.9
involving the engineering knowledge (i.e., Knowledge Fusion) C Momentum 0.5 0.9
and becoming an critical part of business strategy (Homen de D Number of epochs 10,000 50,000
Table 1
Information on the factors’ assumed settings at different levels via Taguchi Method.
Main Effects Plot (datameans) for SN ratios Main Effects Plot (datameans) for Means
ActiveFunction Neuron LearningRate ActiveFunction Neuron LearningRate
70.0
0.05
67.5
0.04
65.0
62.5 0.03
Mean of SN r at ios
Mean of Means
60.0
0.02
Sigmoid_Axon Tanh_Axon 8 13 18 0.7 0.8 0.9
Sigmoid_Axon Tanh_Axon 8 13 18 0.7 0.8 0.9
Momentum Epoch Momentum Epoch
70.0
0.05
67.5
65.0 0.04
62.5
0.03
60.0
0.02
0.7 0.8 0.9 20000 35000 50000
0.7 0.8 0.9 20000 35000 50000
Signal-to-noise:Nominalisbest(-10*Log(s**2))
Liu, Liu, & Zhang, 2001; Maier & Dandy, 1998; Yao, Yan, Chen, & BPNN include the number of hidden layers, number of hidden neu-
Zeng, 2005). The superiority of a network’s functional approach de- rons, learning rate, momentum, etc. All of these parameters can
pends on the network architecture and parameters, as well as the significantly impact the performance of the neural network. Fogel
problem complexity. If inappropriate network architecture or (1991) proposed a final information statistical (FIS) process based
parameters are selected, undesirable results may be obtained. Con- on Akaike’s information criterion (AIC) to determine the number
versely, the results will be much more significant if good network of hidden layers and neurons. One hidden layer is sufficient to
architecture and parameters are selected. The BPNN consists of an compute arbitrary decision boundaries and quite adequate to
input layer, hidden layer, and output layer. The parameters for the model nonlinearity in most cases of the BPNN (Anjum, Tasadduq,
C21
20PPS2 19PPS1
C40
C29 C28 C22
C30 C27
10GS3_1
4GS1_1
C32 C31
C39
C33 C26
C19
11GS3_2 17PP1 18PP2
C23
C34
8GS2_2 7GS2_1
C25
C37 C24
9GS2_3 22RD
28SR C7
C8 C18
C6
C5
27SP2 2CP 14LFW 21RA
C9
C11
C2 C17
13LBW
16BS2 C13 C10
C4
C1 C12 C16
15BS1 25SL 24RFW
C3
C14
1MB 26SP1 23RBW
C15
& Al-Sultan, 1997; Khaw, Lim, & Lim, 1995). The limitation of Fo- The activation function is a hyperbolic sigmoid function. According
gel’s research is that the process can only perform simple binary to past studies (Cheng & Tseng, 1995; Hush & Horne, 1993), there
classifications. Murata and Yoshizawa (1994) and Onoda (1995) are a few conditions for network learning termination: (1) when
respectively proposed methods to improve AIC. These methods, the root mean square error (RMSE) between the expected value
called the network information criterion (NIC) and neural network and network output value is reduced to a preset value; (2) when
information criterion (NNIC), use statistical probabilities together the preset number of learning cycles has been reached; and (3)
with an error energy function to determine the number of hidden when cross-validation takes place between the training samples
neurons. and test data. The first two methods are related to the preset val-
In this research, the steepest-descent method was used to find ues. This research adopts the first and second approaches by grad-
the weight change and to minimize the error energy function. ually increasing the network training time to gradually decrease
the RMSE until it is stable and acceptable. The RMSE is defined as where N; di , and yi are the number of training samples, the actual
follows: value for training sample i, and the predicted value of the neural
vffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi network for training sample i, respectively.
u
u1 X N
In network learning, input information and output results are
RMSE ¼ t ðdi yi Þ2 ; ð1Þ
N i¼1 used to adjust the weighting values of the network. The more de-
tailed the input training classification and the greater the amount Table 3
of learning information which are provided, the better the output The optimal assembly sequence of a toy car.
will conform to the expected result. Since the learning and verifica- Optimal assembly sequence Parts AI TPV FN Weight Volume
tion data for the BPNN are limited by the functional values, the 1 2 CP 19 47 9 981.88 125415.99
data must be normalized by the following equation: 2 22 RD 4 8 10 31.42 11246.39
3 3 DG 5 8 27 4.83 3452.57
P Pmin 4
PN ¼ ðDmax Dmin Þ þ Dmin ; ð2Þ 17 PP 10 29 11 83.64 29935.98
P max Pmin 5 9 GS2 3 3 5 22 1.96 1397.92
6 8 GS2 2 3 5 22 1.12 802.85
where PN is the normalized data, P is the original data, Pmax is the 7 7 GS2 1 6 16 1 3.07 392.7
maximum value of the original data, P min is the minimum value of 8 12 PO 2 3 2 56.34 20165.61
the original data, Dmax is the expected maximum value of the nor- 9 11 GS3 2 3 5 26 2.28 1628.77
malized data, and Dmin is the expected minimum value of the nor- 10 10 GS3 1 6 16 1 3.07 392.7
11 6 GS1 3 3 5 22 1.08 771.23
malized data. 12 5 GS1 2 3 5 22 0.87 623.61
When applying the neural network to the system, the input and 13 4 GS1 1 6 16 1 3.07 392.7
output values of the neural network fall in the range of [0.1, 0.9]. 14 18 PP2 8 22 11 17.66 6321.76
15 19 PPS1 4 6 3 0.13 14.99
16 20 PPS2 4 5 3 0.11 14.86
4. Taguchi method 17 28 SR 7 4 4 27.58 3522.26
18 21 RA 7 13 3 29.79 3804.98
Taguchi’s parameter design method normally selects an appro- 19 13 LBW 2 5 7 308.9 219936.4
priate formulation of the S/N ratio and calculates the S/N ratio for 20 23 RBW 2 3 7 307.67 219928.32
21 14 LFW 2 3 9 176.9 119227.68
each treatment. There are three types of S/N ratios: nominal the 22 24 RFW 2 3 9 164.33 119214.45
best, the larger the better, and the smaller the better. Most engi- 23 26 SP1 2 6 3 9.99 1288.59
neers choose the highest S/N ratio treatment as the preliminary 24 27 SP2 2 6 3 9.85 1276.48
optimal initial process parameter setting. Taguchi method has also 25 25 SL 2 3 2 234.01 83756.14
26 1 MB 7 17 28 932.5 333750.12
been used to design the parameters for neural networks in previ-
27 15 BS1 4 10 3 2.38 303.99
ous research (Khaw et al., 1995; Santos & Ludermir, 1999). Khaw 28 16 BS2 4 10 3 2.36 302.45
et al. (1995) applied Taguchi method to design the parameters
and verified that the method could rapidly and robustly design
the optimal parameters. Santos and Ludermir (1999) applied a fac-
torial design to assist the design and implementation of a neural Table 4
network. The formulae of the three types of S/N ratios are given The optimal assembly sequence of a toy motorbike.
as follows: Optimal assembly sequence Parts AI TPV FN Weight Volume
2
y 1 9 MMB1 5 13 20 7.35 7697.04
nominal the best : S=N ¼ 10 log ; ð3Þ 2 13 MPE 9 19 4 5.19 5176.46
S2
! 3 10 MMB2 5 17 20 6.78 7696.73
1X n
1 4 14 MS 3 8 2 1.53 2297.29
the larger the better : S=N ¼ 10 log ; and ð4Þ 5 11 MN 3 10 3 0.78 856.50
n i¼1 y2i
6 17 MW3 1 9 4 8.13 7296.14
! 7 3 MB2 1 4 23 3 1.2 1931.29
1X n
2
the smaller the better : S=N ¼ 10 log 2 þ S2 ;
y ¼ 10 log½y 8 6 MB3 2 3 16 5 1.41 1892.18
n i¼1 i 9 1 MA 8 52 2 3.32 2907.56
10 16 MW2 2 9 4 8 7295.23
ð5Þ 11 4 MB2 2 4 18 3 1.18 1930.96
12 5 MB3 1 3 5 5 1.4 1891.72
where yi is the response value of a specific treatment under i 13 2 MB1 4 11 4 2.49 3841.38
is the average of all
replications, n is the number of replications, y 14 15 MW1 2 4 4 7.99 7294.86
yi values, and S is the standard deviation of all yi values. 15 12 MPN 3 12 5 1.28 1619.55
16 7 MH1 2 4 3 0.17 231.61
17 8 MH2 2 3 3 0.15 230.56
5. Optimization of the neural network parameters using RSM &
Taguchi method
Table 5
In this research, we applied the Taguchi method and DOE to
The optimal assembly sequence of a toy boat.
obtaining the optimal parameter settings of the BPNN. Since the
number of hidden layers did not have a significant effect on con- Optimal assembly sequence Parts AI TPV FN Weight Volume
vergence, the number of hidden layer was set to 1. The controlling 1 13 BP 12 28 4 40.53 5176.46
factors of Taguchi method are transfer function ðF t Þ, the number 2 9 BN1 3 7 3 6.81 857.5
of hidden neurons ðN h Þ, learning rate ðRl Þ, momentum ðMt Þ, and 3 2 BB1 4 10 4 10.95 1393.43
4 10 BN2 3 8 3 6.71 857.1
Epochs ðEp Þ. The numbers of neurons in the hidden layer under 5 3 BB2 4 11 4 10.9 1392.87
different levels were obtained by the method proposed by Khaw 6 1 BM 7 34 12 86.96 11105.48
et al. (1995) and Haykin (1999). Information on the factors’ 7 15 TM 7 30 12 75.11 9591.47
assumptive settings at different levels is listed in Table 1. Apart 8 6 BH1 2 3 3 1.82 231.61
9 7 BH2 2 3 3 1.81 230.92
from transfer function ðF t Þ, the number of hidden neurons ðN h Þ,
10 4 BC 5 20 8 19.98 2551.01
learning rate ðRl Þ, momentum ðMt Þ and the numbers of calculation 11 11 BN3 3 7 3 6.61 856.2
generations i.e. epochs ðEp Þ are determined by first finding the 12 14 BS 8 26 2 17.99 2297.29
range in which these factors have better converging results, and 13 12 BPR 4 6 2 2.4 306.77
second by determining the equal-distance value for the three 14 5 BF 2 3 11 26.63 3401.12
15 8 BL 4 8 3 5.69 726.57
levels.
724 W.-C. Chen et al. / Expert Systems with Applications 37 (2010) 716–726
Under the condition of five factors, one for two levels and four factor levels. is the average of two Y’s in each replication. The
for three level, and no correlation among the five factors, the total optimal combination of factor levels is the experiment with the
degrees of freedom were 17 (i.e., 1 ð2 1Þ þ 4 ð5 1ÞÞ. An largest S/N ratio. From the experimental results of Taguchi method,
L18 ð21 34 Þ orthogonal array is selected for arranging the factors the main effects plots of BPNN’s factors through Taguchi method
and carrying out the experiment. In this experiment, there are can be seen in Fig. 3. The optimal combination of factor levels is
two replications, and the predicted performance (Mean square er- represented by the following: BPNN architecture of 5-13-1, the
ror, MSE) of Y is the evaluation value for different combinations of transfer function is Hyperbolic Tangent, the number of calculation
Table 6
Comparisons of BPNN performance between Taguchi method and DOE approach.
generations of 35,000, a learning rate of 0.9, and a momentum of tion. However, these are uncertain factors prior to the determination
0.9. of the optimised assembly scheme and the completion of the jig and
Subsequently, the result of the DOE with response surface fixture. The proposed model adopts a three-stage integrated assem-
methodology (RSM) on the factors’ assumptive settings at two lev- bly planning approach to express the complexity of the assembly
els listed in Table 2 is revealed: the number of neurons of 15, a relations and to evaluate the feasibility of the respective assembly
learning rate of 0.9, a momentum of 0.9, and the number of calcu- sequences in the design phase. The experimental results for the case
lation generations of 50,000. The response optimization of BPNN’s study verify the feasibility of the proposed approach, which facili-
parameters via DOE is represented in Fig. 4. tates the DFA in potential applications of 3D component models to
assist manual or automatic assembly in a virtual environment, and
allows the designer to recognise the relative position, geometric con-
6. Illustrative examples straints and relationships of the 3D components using the following
graph-oriented methods: the Above Graph, APD and relational mod-
In this section, the examples of a toy car, a toy motorbike and a el graph. The planner can further generate a correct explosion graph
toy boat are used to demonstrate the generation procedures of and construct an incidence matrix for validating the assembly rela-
assembly planning. tions through applying the Above Graph and relation models. In
addition, this three-stage integrated approach can effectively pro-
6.1. Creating the exploded view, RMG and APD mote the quality of the generated assembly plan and facilitate
assembly sequence optimization via knowledge-based engineering
The exploded view can be directly created from the Above (KBE) system and a robust BPNN engine.
Graph, which possesses the contact relationships of a spatial struc-
ture. Fig. 5 shows the parts list, assembly codes and the exploded
view. The validity of each exploded view can be confirmed by Acknowledgement
the contact relationships of the spatial structure and Above Graphs.
Applying a correct exploded view allows us to derive the exact Financial support from the National Science Council, Taiwan,
assembly plans. For brevity, the detailed planning steps are omit- ROC, under contract NSC 97-2221-E-216 -026 and Chung Hua
ted. Fig. 6 shows the complete relational model graph (RMG) and University, under contract CHU-96-M-001.
APD for the proposed case study.
Kuo, T. C., Huang, S. H., & Zhang, H. C. (2001). Design for manufacture and design Marian, R. M., Luong, L. H. S., & Abhary, K. (2003). Assembly sequence planning and
for‘X’: Concepts, applications, and perspectives. Computers & Industrial optimisation using genetic algorithms. Applied Soft Computing, 2(3), 223–253.
Engineering, 41, 241–260. Murata, N., & Yoshizawa, S. (1994). Network information criterion-determining the
Lai, H. Y., & Huang, C. T. (2004). A systematic approach for automatic assembly number of hidden units for an artificial neural network model. IEEE Transaction
sequence plan generation. International Journal of Advanced Manufacturing on Neural Network, 5, 865–872.
Technology, 24, 752–763. Onoda, T. (1995). Neural network information criterion for optimal number of
Lee, S. (1989). Disassembly planning by subassembly extraction. In Proceedings of hidden units. In Proceedings of the IEEE international conference on neural
the third ORSA/TIMS conference on flexible manufacturing systems (pp. 383– networks (Vol. 1, pp. 270–280).
388). Cambridge. Santos, M. S. & Ludermir, B. (1999). Using factorial design to optimize neural
Lin, A. C., & Chang, T. C. (1993). An integrated approach to automated assembly networks. In International joint conference on IEEE neural networks (Vol. 2, pp.
planning for three-dimensional mechanical products. International Journal of 857–861). Washington, DC.
Production Research, 31(5), 1201–1227. Sinanoglu, C. (2006). A neural predictor to analyze the effects of metal matrix
Liu, Y., Liu, W., & Zhang, Y. (2001). Inspection of defects in optical fibers based on composite structure (6063 Al/SiCp MMC) on journal bearing. Industrial
back-propagation neural networks. Optics Communications, 198(4-6), 369–378. Lubrication and Tribology, 58(2), 95–109.
Maier, H. R., & Dandy, G. C. (1998). Understanding the behaviour and optimising the Yao, S., Yan, B., Chen, B., & Zeng, Y. (2005). An ANN-based element extraction
performance of back-propagation neural networks: an empirical study. method for automatic mesh generation. Expert Systems with Applications, 29,
Environmental Modelling & Software, 13, 179–191. 193–206.