A Unified Approach for Designing a Cellular Manufacturing System by Specifying Number of Cells

International Journal of Applied Mathematics & Statistics, Int. J. Appl. Math. Stat.; Vol. 27; Issue No. 3; Year 2012, ISSN 0973-1377 (Print), ISSN 0973-7545 (Online) Copyright © 2011-12 by IJAMAS, CESER Publications A Unified Approach for Designing a Cellular Manufacturing System by Specifying Number of Cells A. M. Mukattash1, K. K. Tahboub2, R. H. Fouad1* and A. A. Al-Bashir1 1 Industrial Engineering Department, Hashemite University *Email: rhfouad@yahoo.co.uk Industrial Engineering Department, University of Jordan 2 ABSTRACT Cellular manufacturing has received increasing attention during the past years. The main problem in designing cellular manufacturing systems is cell formation, in other words; grouping parts with similar processing requirements into part families and their relevant machines into machine cells. In the process of forming such manufacturing cells, the designer is faced with the constraint of limited number of cells, therefore the designer needs to specify the number of cells in the design in advance. A number of heuristic methods were developed in the literature to come up with acceptable but not optimal results due to the complexity of these optimization problems. The high performance of computers can be utilized to come up with exact solutions for small batch manufacturing where the number of machines is no more than ten machines. The main objective of this paper is to develop an approach that not only specifies the number of cells in advance but also determines all the possible ways to form p-cells from n-machines. The evolved algorithm will lead to a minimum number of voids and exceptional elements in cells in grouping machines and parts will dedicated for cellular manufacturing. Keywords: Cellular Manufacturing systems, Cell Formation, Minimum Number of Voids & Exceptions, and optimal Solution. Mathematics Subject Classification Number: 68Q80, 49K30 1. INTRODUCTION Group technology (GT) is manufacturing philosophy whose main idea is to capitalize on similar, recurrent activities. It is a philosophy with broad applicability, potentially affecting all areas of manufacturing organization [1].The main idea of group technology is to identify similar manufacturing processes and features, machines are grouped into machine cells based on their contribution to the production process [2]. Cellular Manufacturing (CM) is an application of group technology concept 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 [3].The input to the GT problem is a zero-one matrix A where aij = 1 indicates the visit of component j to machine i, and aij = 0 otherwise. Grouping of components into families and machines into cells results 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. The ideal situation is one in which all the ones are in the diagonal blocks and all the zeros, off the diagonal blocks [4]. However, this situation is rarely accomplished in practice. Therefore, the most desirable solution of cellular manufacturing systems is that which gives minimum number of zeros entries inside a diagonal block [known as voids] and minimum number of ones entries outside the diagonal blocks [known as the exceptional elements],[5]. Voids and exceptional elements have advance implications in terms of system operations (for more details see [6]. Specifying the number of cells in advance is a managerial decision. This decision is generally based on several factors such as total number of machines to be assigned to cells (cell size), physical constraints on the shop floor, and labor relation issues [7]. www.ceser.in/ijamas.html www.ceserp.com/cp-jour www.ceserpublications.com International Journal of Applied Mathematics and Statistics The first step in Cellular Manufacturing (CM) is the cell formation (CF).The goal of cell formation is to create separable machine clusters and part families. CF aims at the creation of cells (machine groups), where parts in each cell are processed with minimum interaction with other cells [8]. Many of the cell formation techniques proposed to date configure cells in such a way to minimize the number of exceptional parts or parts requiring processing outside their cells [9]. A void indicates that a machine assigned to a cell is not required for the processing of a part in the cell. The exceptional element is created when a part requires processing on a machine that is not available in the allocated cell of the part. Exceptional elements and voids are the first two problems which will face the designer. A researcher can find several algorithms in literature to generate cell formation [10 , 11,12]. They are used to obtain block diagonal forms to achieve minimum inter-cell movements. The main theme of these algorithms is to re-arrange rows (machines) and / or columns (parts) of the incidence matrix to form a matrix with block diagonal form.The output of any of these algorithms (procedures) with bounded and unbounded cell size are groups of machines. The inputs to the above algorithms come from companies technological experience and knowledge specified in route-sheets. This knowledge is presented in the literature in the form of a zero-one matrix, where the elements of the matrix are defined as: a ij ­1, if part j visit machine i . ® ¯0, otherwise Recently, new techniques have been used to solve the cell formation problem. The Bees Algorithm has been used in [13]. In [14] a methodology for forming machine cells based on materials flow has been presented. An evolutionary approach to forming manufacturing cells was presented [15]. A feature-based algorithm using fuzzy sets has been used by [16] to facilitate the formation of manufacturing cells. Researchers in [17] utilized a genetic algorithm approach to the cell formation problem. The main objective of this paper is to develop an approach that not only specifies the number of cells in advance but also determines all the possible ways to form p-cells from n-machines. The evolved algorithm will lead to a minimum number of voids and exceptional elements in cells in grouping machines and parts will dedicated for cellular manufacturing. The approach is based on Stirling number which is the number of ways to distribute n-distinguishable items into p-indistinguishable cells with no cell empty [18]. The general recursion formula of Stirling number is given below: A np A np --11  PA np -1 Where, n: is the number of machines p: is the number of cells. 2. DERIVATION OF THE FIVE – CELL FORMATION ALGORITHM 3. Notation and definitions A: the incidence matrix of zero-one element; the rows represent the machines and the columns represent the parts. aij: elements of matrix A. n: number of machines m: number of parts C1: represents the first cell C2: represents the second cell C3: represents the third cell C4: represents the fourth cell C5: represents the fifth cell 40 International Journal of Applied Mathematics and Statistics n P5 : number of all possible ways to form 5-cells from n-machines. |C1|: number of machines in the first cell |C2|: number of machines in the second cell |C3|: number of machines in the third cell |C4|: number of machines in the fourth cell |C5|: number of machines in the fifth cell M i : the ith machine S: All possible states for C1 which contains M 1 . ( M 1 ), ( M 1 M 2 ),.........( M 1 M n ), ( M 1 M 2 M 3 ),...( M 1 M n 1 M n ),... ...., ( M 1 M 2 M 3 ....M n 5 ),......( M 1 ......M n 1 M n ) | C i : number of machines in the ith cell §n· n S j : Group of elements, the number of these elements ¨ ¸ , each element contains j machines. ¨ ¸ © j¹ q : number of equivalent states n-4: maximum number of machines in each cell. i: the ith machine 2.1 Derivation of the number of states Assumptions: 1. C1:contain always M 1 2. |C1|+|C2|+|C3|+ C4+|C5| = n 3. No cell empty Since C1 contain always M 1 , then all possible states for C1is defined as: Lemma: 2 2 n 1  ( n 1)( n 6 2 n  6 )  1 S Proof: Since the first state is to put M 1 only in C1 , and the other (n-1) machines will be put in the other four cells, with no cell empty, then the type of machines distribution for the first state can be done by § n 1 · ¸ ¨ ¸ from n-1 machines. © 0¹ The second state is to put M 1 with the other machine in C1 and the remainder of the machines will be choosing ¨ assigned to the other four cells, with no cell empty. The type of machines distribution for the second § n 1 · ¸ ¨ ¸ from n-1 machines. ©1¹ state can be done by choosing ¨ The third state is to put M 1 with other two machines in C1 and the remainder of the machines will be assigned to the other four cells, such that there is no cell empty. The type of machines distribution for § n 1 · ¸ ¨ ¸ from n-1 machines. © 2¹ the third state can be done by choosing ¨ 41 International Journal of Applied Mathematics and Statistics The last state is to put M 1 with the other (n-5) machines in C1 and the remainder of the machines will be assigned to the other four cells, such that there is no cell empty. The type of machines distribution § n 1 · ¸ ¨ ¸ from n-1 machines. © n 5 ¹ for the last state can be done by choosing ¨ From the above discussion S can be written as follows: § n 1 · § n 1 · § n 1 · § n 1 · ¨ ¸  ¨ ¸  ¨ ¸  ....  ¨ ¸ ¨ ¸ ¨ ¸ ¨ ¸ ¨ ¸ © n 5 ¹ © 0¹ ©1¹ © 2¹ S But 2 n 1 (1  1) n 1 …….(1) § n 1 · § n 1 · § n 1 · ¨ ¸  ¨ ¸  .....  ¨ ¸ ¨ ¸ ¨ ¸ ¨ ¸ © n 1 ¹ ©0¹ ©1¹ …….(2) So, from equation 1 and 2 , equation 2 can be rewritten as: 2 n 1 § n 1 · ¸ ¨ ¸ ©k ¹ Moreover, ¨ S § n 1 · § n 1 · § n 1 · § n 1 · S  ¨¨ ¸¸  ¨¨ ¸¸  ¨¨ ¸¸  ¨¨ ¸¸ © n  4 ¹ © n 3 ¹ © n  2 ¹ © n 1 ¹ ……(3) § n 1 · ¸ , then we can rewrite equation 3 as follows: ¨ ¸ ¨ © n 1 k ¹ § n 1 · § n 1 · § n 1 · § n 1 · S 2 n 1  ¨¨ ¸¸  ¨¨ ¸¸  ¨¨ ¸¸  ¨¨ ¸¸ © 3¹ © 2¹ ©1¹ © 0¹ 2 n 1  ( n 1)( n  2 )( n  3 ) 3! 2 n 1  ( n 1)( n S 2  ( n 1)( n  2 ) 2! 5 n  6  3 n ) 6 1  …….(4) ( n 1) 1! 1 …….(5) ………(6) 2 2 n 1  ( n 1)( n 6 2 n  6)  1 ?S ………(7) To illustrate the above lemma, let's assume that we have seven machines, and these machines have to be distributed to the five cells. The total number of the type of machines distribution can be calculated using Equation (7) with n=7 as follows: S 2 2 7 1  ( 7 1)( 7 6 2u7  6 )  1 22 State one: C1: contains always M 1 , then we have only one type of machines distribution, because this type can § 7 1 · § n 1 · ¸ from (n-1) machines. ¨ ¸ 1 ¨ ¸ ¨ ¸ ©0¹ ©0¹ be calculated by choosing ¨ State two: 42 International Journal of Applied Mathematics and Statistics Put M 1 with the other machine in C1.We have six types of machines distribution, ( ( M 1 M 2 ), ( M 1 M 3 ), ( M 1 M 4 ), ( M 1 M 5 ), ( M 1 M 6 ) and (M 1 M 7 ) . The type of machines distribution § n 1 · ¸ ¨ ¸ from n-1 machines. ©1¹ for the second state can be done by choosing ¨ § 7 1 · ¨ ¸ ¨ ¸ ©1¹ 6 State three: Put M 1 with other two machine in C1 . We have 15 types of machine distribution. ( M 1 M 2 M 3 )...( M 1 M 2 M 7 ), ( M 1 M 3 M 4 )....( M 1 M 3 M 7 ), ( M 1 M 4 M 5 )....( M 1 M 4 M 7 ), ( M 1 M 5 M 6 )..( M 1 M 5 M 7 ) and (M 1 M 6 M 7 ) § n 1 · ¸ ¨ ¸ from n-1 © 2¹ The type of machines distribution for the third state can be done by choosing ¨ § 7 1 · ¸ ¨ ¸ 15 © 2¹ machines. ¨ Since the maximum number of machines in each cell is equal to (n-4)=3, this means that we have 3 states with 22 types of machines' distribution. 2.2 Derivation of all possible ways to form 5-cells from n-machines Since we have five cells, then we will choose the cell(s), which contain the first machine. In the case the first cell contains only the first machine ( M 1 ), and the other (n-1) machines will be put in the other four cells (State one). According to Stirling number, the number of all possible types of machines distribution is given by: P4 n 1 …(8) The second state is to put M 1 with the other machine in C1 and the remainder (n-2) machines will be assigned to the other four cells. According to Stirling number, the number of all possible types of machines distribution is given by: P4 n2 ……..(9) In general, the first cell contains the first machine with other j machines and the remainder (n-j-1) machines will be assigned to the other four cells. So according to Stirling number, the number of all possible types of machines distribution is given by: P4 n  j 1 ….(10) The summation of all the above states with its corresponding, the type of machines distribution will give all possible ways to form five cells from n machines and is given by: P5 n § n 1 · n 1 § n 1 · n  2 § n 1 · ¨ ¸ P4  ¨ ¸ P4  .....  ¨ ¸ P4 4 ¨ ¸ ¨ ¸ ¨ ¸ © 0¹ © 1¹ © n 5 ¹ Equation 11 can be written as: 43 ……(11) International Journal of Applied Mathematics and Statistics P5 n § n 1 · n  j 1 ¸P4 ¸ 0© j ¹ n 5 ¦ ¨¨ j …….(12) Applying equation 12 with n=7 will give140 possible ways to form five cells from seven machines. 2-3 Steps of the 5-cell Algorithm Step 1: Input the number of machines n J1=-1 Step 2: j1=j1+1 Step 3: If j1> n-5 then stop Step 4: Choose machines from group § n -1 · which have ¨ ¸ elements ¨j ¸ © 1¹ every element has j1 machines S j1 n 1 1 j2 Step 5: j2=j2+1 Step 6: If j2 >n-j1-5 then return to step 2 Step 7: Choose machines from group S j2 j3 n - j1  2 , where every element has j2 machines 1 Step 8: J3=j3+1 Step 9: If j3>n-j1-j2-5 then return to step 5 Step 10: Choose machines from group S j3 j4 n - j1  j 2 3 where every element has j3 machines 1 Step 11: J4=j4+1 Step 12: If j4>n-j1-j2-j3-5 then return to step 8 Step 13: Choose machines from group S j4 n - j1  j2  j3  4 where every element has j4 machines 44 International Journal of Applied Mathematics and Statistics Step 14: Select the residual group Step 15: Test the state Step 16: Return to step 11 3. NUMERICAL EXAMPLE To illustrate and test the proposed approach of 5-cell algorithm, we will apply it on an industry problem with six machines and 10 parts, shown below in Fig (1). MACHINES MACHINES MACHINES The result of applying the 5-cell algorithm steps, gave two optimal solutions with minimum inter-cell movements. Then part assignment is done with minimum sum of voids and exceptions. Fig (2) presents the first optimal solution, while Fig (3) represents the second optimal solution. Both solutions have minimum sum of voids and exceptions equal to 2. The detailed solution of the numerical example is shown in the appendix. 1 2 3 4 5 6 1 0 1 0 0 0 0 PARTS 2 3 4 5 6 7 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 0 0 0 Figure 1. Machine-part matrix for the numerical example. 8 0 0 0 1 0 0 9 1 0 0 0 1 0 10 0 0 0 0 1 0 2 3 4 6 1 5 1 1 0 0 0 0 0 PARTS 5 6 8 7 2 3 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 Figure 2. First optimal solution for the proposed approach. 4 0 0 0 1 0 0 9 0 0 0 0 1 1 10 0 0 0 0 0 1 PARTS 1 5 6 8 7 2 3 4 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 Figure 3. Second optimal solution for the proposed approach. 9 0 0 0 1 0 1 10 0 0 0 0 0 1 2 3 4 1 6 5 45 International Journal of Applied Mathematics and Statistics 4. SUMMARY AND CONCLUDING REMARKS Cellular manufacturing is a production strategy for solving certain problems in batch production. The main problem in cellular manufacturing is the formation of product families and machine cells. Particularly, cell formation is an important, critical and difficult step in Cellular Manufacturing. This paper has presented a special case algorithm for the generation of a 5-cell manufacturing system. The developed algorithm is practical for small sized manufacturing settings where the number of machines available is not more than ten machines. The algorithm provides the optimal solution (including alternative solutions) since it enumerates all possible solutions. Since the cell size is not restricted, the facility designer has the ability to control the cell size and is offered three choices of part assignment to cells, i.e., minimum sum of voids and/or exceptions. This assignment allows for the formation of loose cells with a large number of machines and/or tight cells with a limited number of machines. The proposed approach can also be used for systems with alternative process plans for the parts. 5. REFERENCES [1] Surjit, A. , Rakesh,S. and Samsudeen, Z., Cellular manufacturing – A time-based analysis to the layout problem. International Journal of Production Economics, 112, p427-438, 2008. [2] Iraj ,M.,Babak , j. ,Kaveh ,F. and Jannes , S. , Designing a new mathematical model for cellular manufacturing system based on cell utilization . Applied Mathematics and Computation , 190 , p 662-670, 2007. [3] Poornachandra R.and Vira C. ,design of cellular manufacturing systems with considerations , Computers & Industrial Engineering, 48 ,pp. 449– 469, 2005. assembly [4] Nair, G.J., and Narendran, T.T., CASE: A Clustering algorithm for cell formation with sequence data. International Journal of Production Research, 36(1), 157- 199 ,1998. [5] Kumar, C.S., and Chandrasekharan, M.P., Grouping efficacy: a quantitative criterion for goodness of block diagonal forms of binary matrices in group technology. International Journal of Production Research, 28(2), 233-243,1990. [6] Adil, G.K., Rajamani, D., and Strong, D., Cell formation considering alternate routings. International Journal of Production Research, 34(5), 1361 – 1380 ,1996. [7] Gupta, Y.P., Gupta, M.C., Kumar, A., and Sundram, C., Minimizing total intercell and intracell moves in cellular manufacturing : a genetic algorithm approach. International Journal of Computer Integrated Manufacturing, 8(2), 92-101,1995. [8] G. K. Adil, D. Rajamani, and D. Strong. Cell formation considering alternate routings, International Journal of Production Research., vol. 34, no. 5, 1361-1380 (1996). [9] N. E. Dahel. Design of cellular manufacturing systems in tandem configuration. International Journal of Production Research., vol. 33, no. 8, 2079-2095 (1995). [10] B. Arvindh and S. A. Irani. Principal component analysis for evaluating the feasibility of cellular manufacturing without initial machine-part matrix clustering. Int. J. Prod. Res. vol.32, no. 8, 19091938 (1994). 46 International Journal of Applied Mathematics and Statistics [11] R. G. Askin and K. S. Chiu. A graph partitioning procedure or machine assignment and cell formation in group technology. Int. J. Prod. Res., vol.28, no.8, 1555-1572 (1990). [12] Mukattash, A. M. and Khaldoun K.Tahboub, Generation of four-cell formation algorithm with minimum sum of voids and exceptions. Dirasat, Engineering Sciences, 31(2), p270-280, 2004. [13] Pham DT, Otri S, Afify AA, Mahmuddin M and Al-Jabbouli H. Data clustering using the bees algorithm. Proceedings of the 40th CIRP Int. Manufacturing Systems Seminar, Liverpool, UK, 2007. [14] Yong Yin, Kazuhiko Yasuda, Lan Hu, Formation of manufacturing cells based on material flows, Int J Adv Manuf Technol, 27, p159–165, 2005. [15] Jose´ Fernando Goncalvesa and Mauricio G.C. Resende, An evolutionary algorithm for manufacturing cell formation, Computers & Industrial Engineering, 47, p247–273, 2004. [16] Bernard Mutel and Egon Ostrosi, Feature-based manufacturing cell formation using a fuzzy-set approach, Int. J. Computer Integrated Manufacturing, Vol. 15, No. 2, p152–167, 2002. 17] Iraj Mahdavi, Mohammad Mahdi Paydar, Maghsud Solimanpur, and Armaghan Heidarzade, Genetic algorithm approach for solving a cell formation problem in cellular manufacturing, Expert Systems with Applications, 36, p6598–6604, 2009. [18] Roberts, F.S.,1984. Applied combinatorics.Prentice-Hall, Inc., Englewood Cliffs, 47 NJ. International Journal of Applied Mathematics and Statistics Appendix Complete solution of the numerical example n=6 , m=10 Using the recursion formula of Stirling number with p=5 , n=6 we get: P5 n j P5 n 15 , which represents all § n 1 · n  j 1 ¸P4 ¸ 0© j ¹ n 5 ¦ ¨¨ the possible ways of distributing 6-machines to 5-cells. The total number of the type of machines distribution can be calculated using Equation (7) with n=6 as follows: 2 S 261  (61)(6 62u66) 1 6 State one: C1: contains always M 1 , then we have only one type of machines distribution , because this type can § 61 · § n 1 · ¸ ¨ ¸ ¨ ¸ from (n-1) machines. ¨ ¸ 1 ©0¹ ©0¹ be calculated by choosing ¨ (m1)(m2)(m3)(m4)(m5m6) (m1)(m2)(m3)(m4m5)( m6) (m1)(m2)(m3)(m4 m6)(m5) (m1)(m2)(m3 m4)(m5)( m6) (m1)(m2)(m3 m5)(m4)( m6) (m1)(m2)(m3 m6)(m4)(m5) (m1)(m2 m3)( m4)(m5)( m6) (m1)(m2 m4)(m3)(m5)( m6) (m1)(m2 m5)(m3)(m4)( m6) (m1)(m2 m6)(m3)(m4)(m5) State two: M 1 with the other machine in C1.We have five types of machines distribution. ( ( M 1 M 2 ), ( M 1 M 3 ), ( M 1 M 4 ), ( M 1 M 5 ) and ( M 1 M 6 ).) . The type of machines' distribution for the Put § n 1 · ¸ ¨ ¸ from n-1 machines. ©1¹ second state can be done by choosing ¨ § 61 · ¨ ¸ ¨ ¸ ©1¹ 5 (m1 m2)(m3)(m4)(m5)(m6) (m1 m3)(m2)(m4)(m5)(m6) (m1 m4)(m2)(m3)(m5)(m6) (m1 m5)(m2)(m3)(m4)(m6) (m1 m6)(m2)(m3)(m4)(m5) Since the maximum number of machines in each cell is equal to (n-4) = 2, this means that we have 2 states with 6 type of machines distribution. A n4 ? A 64 4A n4 1  A 3n 1 65 , Then we find After that part assignment will be done with minimum sum of voids and exceptions. It is found that there are two optimal solutions, with minimum sum of voids and exceptions equal to 2.The first optimal solution is (m1 m5)(m2)(m3)(m4)(m6).The second optimal solution is (m1 m4)(m2)(m3)(m5)(m6)..The two optimal solutions are shown in Fig (2) and Fig (3), respectively. 48