Group Technology (GT) is a manufacturing management philosophy that emphasizes
on identifying groups of products with similar design and processing characteristics.
Cellular Manufacturing (CM) is an application of GT that attempts to identify
a collection of similar parts (part families) which can be processed in a manufacturing
cell with dissimilar machines. Such an arrangement of machines facilitates complete
processing of part families within the manufacturing cell (Panchalavarapu
and Chankong, 2005).
Akturk and Balkose (1996) stated that group technology
is one of the most important aspects in the design of Cellular Manufacturing
Systems (CMS). It has been realized that GT based CMS have benefited from the
advantages of both product-based manufacturing systems and job shop manufacturing
systems (Soleymanpour et al., 2002). CM is an
effective means of efficiently producing small batches of a large variety of
part types. A key step in CM is manufacturing cell formation, i.e., grouping
parts with similar design features or processing requirements into families
and allocating associated machines, forming cells. The similarity among the
parts in each family allows for significant set-up reductions, leading to smaller
economic lot sizes and lower work-in-process inventories (Dobado
et al., 2002). Generally, the cell formation problem can be represented
in matrix format by using a machine-part incidence matrix in which
all the elements are either zero or one. A one element indicates that a specific
machine is used to process a specific part and zero element indicates the opposite
(Sarker and Islam, 2000). The problem is equivalent
to block diagonal sing a zero-one input matrix. Grouping of components into
families and machines into cells result in a transformed matrix with diagonal
blocks where ones occupy the diagonal blocks and zeros occupy the off-diagonal
blocks. The resulting diagonal blocks represent the manufacturing cells (Nair
and Narendran, 1998). The case where all the ones occupy the diagonal blocks
and all the zeros occupy the off-diagonal blocks is called perfect diagonal
blocks. But this case is rarely accomplished in practice. For that, the most
desirable solution of cellular manufacturing systems is that which gives minimum
number of zero entries inside a diagonal block (known as voids) and minimum
number of one entries outside the diagonal blocks (known as the exceptional
elements). A void indicates that a machine assigned to a cell is not required
for the processing of a part in the cell. An exceptional element is created
when a part requires processing on a machine that is not available in the allocated
cell of the part. Voids and exceptional elements have adverse implications in
terms of system operations (Adil et al., 1996).
The main objective in CM is to identify machine cells and part families such
that every part undergoes almost all of its processing in the assigned machine
cell. Cell Formation (CF) is considered to be the first step in CM design. CF
is recognized by researchers as a complex problem. The size of the engineering
problem of CM philosophy can be looked at from many important characteristics
such as: Number of cells, cell size, operation sequence, process plan and machine
loading/balancing (Srivastava and Chen, 1995). Lee
et al. (2010) suggested a heuristic approach to the machine loading
problem in order to reduce the maximum workload of the machines by partially
Many researchers mentioned that little research has been done to determine
the optimal number of cells and that it is usually left as a managerial or facility
designer decision. Several authors have developed and published solution methods
to generate cell formation. Specifying the number of cells in advance and obtaining
all the natural clustering of the input matrix, can be achieved by developing
algorithms or models that take all the possible ways of forming p-cells from
n-machines. Niknam et al. (2008) used a hybrid
evolutionary optimization algorithm based on Ant Colony Optimization (ACO) and
Simulated Annealing (SA) for optimal clustering N object into K clusters.
Since the problem of the cell formation is considered to be complex, many researchers
worked on to develop a solution using Artificial Neural Network (ANN). The ANN
is an efficient method that can be used in CF regardless the number of machines
and parts. Using ANN in cell formation will make the processing time needed
only few seconds. Sivaprakasam and Selladurai (2008)
used Memetic Algorithm (MA) with Gentic Algoritm (GA) to minimize the exceptional
Artificial Neural Networks (ANNs) have received a lot of attention in
recent years due to their attractive capabilities in forecasting, modeling of
complex nonlinear systems and control. Applications of neural networks include
many various fields among which are engineering and business. ANNs have
been used for forecasting electric load (Kalaitzakis et
al., 2002), gasoline consumption (Nasr et al.,
2003), energy (Reddy and Ranjan, 2003) and financial
indicators (Chen et al., 2003; Tkacz,
Artificial neural networks are widely used for forecasting. A large number
of successful applications have shown that neural networks can be a very useful
tool for time series modeling and forecasting (Zhang et
al., 1998). In addition, the simulation experiments of Zhang
et al. (2001) show that neural networks are valuable tools for forecasting
nonlinear time series when compared to other traditional linear methods. Even
though it may sound that ANNs are not needed for modeling and forecasting
linear time series due to the well developed linear system theory, they are
competent in Zhang (2001). The ANN model is trained with
historical time series input-output process data or observations and is then
used to predict the output in the future.
In this study, a special model for generating a three-cell formation is developed with minimum sum of voids (v) and/or exceptions (e). The computerized model is designed for the case of unbounded cell size that takes all the possible ways of forming 3-cells from n-machines by using Artificial Neural Networks (ANN). The output of the computerized model will be input to the ANN. For small number of machines the computerized model can generate all the possible ways of forming three cells from n machines and then find the optimal number of exception (e) plus voids (v) (e+v). For large number of machines the computerized model can generate only all the possible ways of forming three cells from n machines, since it is impossible to run the program to find the optimal (e+v). In this case the output of the generation of large number of machines will be input to the ANN.
The main objective of this study is to determine the exact and optimal solution (s) of forming three cells from any number of machines by using ANN. The significance of this model is that, the processing time needed to run the program (the output of the computerized model) takes only few seconds because machine cells and part families are identified and done concurrently which will decrease the computational time. Machine cells and part families are identified so as to minimize the sum of voids (v) and/or exceptions (e) according to the designer wish. Moreover, the designer will get more flexibility in choosing between different cells.
||Computerized model to compute the optimal value of exceptions
(e) plus voids (v) (e+v)
|| Computation of the e+v value
The method describes distributing the machines in three different cells in all possible way. Table 1 contains the computerized model that computes the optimal value of exceptions (e) plus voids (v) (e+v). It takes the distributions of the machines in three different cells and computes the optimal value for each case at the end we store this value in the Result parameter. The complexity of this algorithm is O (m*n) where m is the number of cases and n is the number of machines.
Calculate-e+v () algorithm presented in Table 2. The function Input Initial Matrix () in line 1 presents any matrix input by the user (according to designer) that distribute machines in three different cells. Rearranging the initial matrix according to the three input numbers by using the Rearrange Matrix () function in line 2 and the result stores in the processing- matrix.
Passing the processing- matrix and the part-no to the function Assign Part () presented in line 3 (3.1, 3.2) that responsible to assign each part in its corresponding cell based on the minimum e+v among the different cells. The function Final Rearrange () rearranges the matrix in the final form according to parts distribution among cells (line 4). Then the Get Min-e+v() (line 5) computes the minimum value of e+v for the specific distribution.
NEURAL NET MODELING
Artificial neural networks were originally inspired as being models of human
nervous system. They have been shown to exhibit many abilities, such as learning,
generalization and abstraction (Patterson 1990). Useful
information and theory about ANNs can be found by Haykin
(1999). These networks are used as models for processes that have input-output
data available. The input-output data allows the neural network to be trained
such that the error between the real output and the estimated (neural net) output
is minimized. The model is then used for different purposes among which are
estimation and control.
The Artificial Neural Net (ANN) structure is shown in Fig. 1
with a multi-input single-output. The inputs feed forward through a hidden layer
to the output. The hidden layer contains processing units called nodes or neurons.
Each neuron is described by a nonlinear sigmoid function. The inputs are linked
to the hidden layer which is in turn linked to the output. Each interconnection
is associated with a multiplicative parameter called weight. Note that the feed-forward
neural net of Fig. 1 has only one hidden layer and this is
the case that we are going to consider. A number of results have been published
showing that a feed-forward network with only a single hidden layer can well
approximate a continuous function (Cybenko, 1989; Funahashi,
1989). In practice, most of the physical processes are continuous.
An artificial neural net mathematical model that represents the structure shown in Fig. 1 is written as:
where, ynn (t + 1) is the output of the neural net model, U is a column vector of size N that contains the inputs to the ANN, Wo is a row vector of size h that contains the output weights from the hidden layer to the output with h being the number of hidden nodes, Wi is a matrix of size hxN that contains the input weights from the inputs to the hidden layer, Bi is a column vector of size h that contains the input biases and bo is the output bias. Note that tanh (Wi *U + Bi) is the activation function of the hidden layer. It is a column vector of size h.
The weights and biases of the ANN are determined by training with the historical input-output data. Backpropagation is an example of a training algorithm. For a given number of hidden neurons the network is trained to calculate the optimum values of the weights and biases that minimize the error between the real and ANN outputs. We assume that after an appropriate choice of the number of hidden neurons and a suitable training period, the network gives a good representation of the estimation system given in Eq. 1.
|| Neural net structure
To illustrate and test the proposed model, the researchers will apply it on
an industrial problem cited by Chen and Cheng (1995).
Who solved by using Adaptive Resonance Theory (ART1). Table 3
shows the machine-part matrix to the problem consisting of 6•6 machine-part.
To validate and verify the proposed model, this problem will be solved and the
result will be compared with their solution.
Since we have 6 machines, then all the possible ways to distribute 6 machines
to form 3 cells is equal to 90 ways (Mukattash, 2000).
Based on the model developed input-output data will be generated. The data contains 90 patterns. Each pattern includes data about the 3 inputs: the machines in each of the 3 cells and corresponding output e+v.
The 90 data patterns are used to train an artificial neural net model for the process. The training was done with the software package Matlab. Experiments were run for different numbers of hidden neurons.
It was observed that the quality of the results depends on the number of hidden neurons. The square error, S, is defined as:
where, M is the number of data points which is equal to 90 in our case, ynn is the neural net output and yr is the real output. Recall that the output is the e+v value.
The square error (S) is plotted as a function of the number of hidden neurons in Fig. 2. Note that this function is decreasing. The square error almost settles at a small value when the number of neurons is large enough. By inspecting Fig. 2, the neural net with 20 hidden neurons was selected as the optimum net. The corresponding square error is equal to 0.1111. For nets much larger than 20 hidden neurons the square error decreases further but makes the neural net large involving large number of parameters which causes the undesirable over-fitting of data.
||The least square error as a function of the number of hidden
neurons in the neural net
|| Part list and machines
The real output (voids + exceptions, e+v) and the optimum (20 hidden neurons) neural net approximated output are plotted in Fig. 3. Note that the two outputs are very close to each other. This indicates the accuracy of the selected neural net. Therefore, the neural net can be relied on to locate the optimum e+v value which is of great practical importance. The complete solution of this problem is shown in Table 5. Machine cells and part families are identified in this problem so as to minimize the sum of voids and exceptions.
Table 4 shows the solution of the problem in Table
3 using Adaptive Resonance Theory (ART1). It is clear that there is two
voids and two exceptions (e+v = 4) and this solution supposed to be optimal.
Table 5 shows the solution used the proposed model. Comparing
Table 4 with 5, it can be concluded that the proposed model
gives better result than ART1model since there are three exceptions and no voids.
(e+v = 3).
|| ART1 solution
|| Proposed model solution
|| The selected optimum neural net training results
Also this result (e+v = 3) is optimal since any other cell formation will not
give (e + v) less than 3.
The challenging problem of distribution of machines in a number of cells has
been solved with new techniques involving advanced programming and artificial
neural networks. A computerized model was presented to generate all the possible
distributions in the various cells and find the optimal solution (s), that is,
the ones that have minimum of value of voids and/or exceptions. The distinct
superiority of the proposed approach is that, machine cells and part families
are identified and done concurrently which will decrease the computational time.
Moreover, machine cells and part families are identified so as to minimize the
sum of voids and/or exceptions according to the designer wish which will give
the designer more flexibility in choosing between different cells. Simulation
results verified the validity of the model.