For the last many years a lot of study has been done on design of Cellular Manufacturing System (CMS). Cellular Manufacturing is an application of Group Technology (GT) philosophy in which similar parts are identified and grouped together to take advantage of their similarities in design and manufacturing. The design of CMS involves three stages i) grouping of parts and production equipments into cells (Cell Formation), ii) allocation of the machine cells to the areas within the shop floor and iii) layout of the machines within each cell. In recent years non-traditional optimization algorithms/techniques have fascinated scientists and engineers all over the world. Particularly in complex dynamic environments, these algorithms/techniques are needed to explore beyond the vicinity of existing knowledge. These algorithms have the ability to think and learn from own experience. They are called Meta heuristics because they perform considerable search before terminating to provide a good solution to the problem. Popular Meta heuristics are Genetic Algorithms (GA), Simulated Annealing (SA), Tabu Search (TS), Artificial Neural Networks (ANN), Artificial Immune System (AIS), and Sheep Flock Heredity Algorithm (SFHA). In this chapter the implementation of Meta heuristics for the design of Cell Formation problem in CMS is discussed.
TopIntroduction
Cellular manufacturing system (CMS) is synonymous with terms such as group technology (GT), cell system and cellular production systems. Cellular manufacturing system is an application of group technology, which is a solution to the problems of batch manufacturing. Here, machines are divided into cells and components are divided into the same number of families in such a way that all the components in each family can be completely processed by a particular cell. The component families are formed based on their design and production characteristics. The design of CMS involves three stages i) grouping of parts and production equipments into cells, ii) allocation of the machine cells to the areas within the shop floor and iii) layout of the machines within each cell.
Group technology ideas were first systematically presented by Burbidge (1963) following the pioneering work of Mitrofanov (1959). The literature on cell formation can be broadly classified in two ways – one based on techniques used for cell formation and other one the way the cell formation problem is modeled. Crama and Oosten (1996) made a study on various models available for Cell Formation problems (CFP). The concept of production flow analysis was introduced by Burbidge (1963). The aim of the technique as stated by Burbidge (1971) is finding the families of components and associated groups of machines for group layout by a progressive analysis of the information in route cards. The main disadvantage with implementation of PFA was the manual work involved in grouping parts and machines. Burbidge (1975) introduced a holistic approach to GT called Production Flow Analysis. It discussed the production situation and recommended a systematic solution to the problems of batch production. Burbidge (1977) introduced a two dimensional representation with a tick mark used to indicate the visit of a component to a machine. The method uses hand computations, which limits its applicability.
The array-based clustering methods are based on the Part-Machine Incidence Matrix (PMIM). In the PMIM, rows and columns indicate machines and parts, respectively. Each column of PMIM is an array of “0–1” numbers, which indicates the set of machines that produce each part. The well-known array-based clustering methods are: the Bond Energy Algorithm (BEA) by McCormick et al. (1972), the Rank Order Clustering method (ROC) by King (1980) and the direct clustering algorithm (DCA) by Chan and Milner (1982). These methods, group parts and machines are regardless of the production volume, operational sequences, production cost, inventory and other limitations in the production system, which is a main problem for them.
The hierarchical clustering based methods are defined by an input data set to determine similarity or distance function and determine a hierarchy of clusters or partitions. The Single Linkage Clustering (SLC) dendogram proposed by McAuley (1972) uses measure of similarity between machines. This model, that is based on the mathematical coefficient uses the distance matrix to determine machine groups. But the major cause for drawback of SLC is the “chaining problem”. Therefore, researchers improved it by adding more inputs, such as production volumes (proposed by Seifoddini (1989) who uses Average Linkage Clustering (ALC) algorithm). Yasuda and Yin (2001) proposed a method on dissimilarity measure for solving CFP.
Graph partition approach represents the machines as vertices and the similarity between machines as the weights of the arcs. Rajagopalan and Batra (1975) suggested the use of graph theory to form machine groups. Chandrasekaran and Rajagopalan (1986a) proposed an ideal seed nonhierarchical clustering algorithm for cellular manufacturing. Ballakur and Steudel (1987) developed graph searching algorithms which select a key machine or component according to a pre-specified criterion. Vohra et al (1990) presented a non-heuristic network approach to from manufacturing cells with minimum intercellular interactions. Srinivasan (1994) presented an approach using minimum spanning tree for the machine cell formation problem. A minimum spanning tree for machines is constructed and the seeds to cluster components are generated from this tree. Veeramani and Mani (1996) described a polynomial-time algorithm based on a graph theoretic approach for optimal cluster formation called as vertex-tree graphic matrices.