International Journal of Scientific & Engineering Research, Volume 3, Issue 10, October-2012 1
ISSN 2229-5518
P.Dharmalingam K.Kanthavel R. Sathiyamoorthy M.Sakthivel R. Krishnaraj C.Elango
ABSTRACT: Grouping the machines and parts in a cellular manufacturing system based on similarities is known as the cell formation. This paper proposes a method for design of cell layout for a manufacturing system under dynamic demand environment for automation batch production industry. The proposed method of cell layout has two phases. In the first phase, Rank Order Clustering (ROC) was used to determine the initial cell layout for first period. This Layout was considered as static layout for other periods to calculate material handling cost. The second phase employs the use of an optimization technique (Simulated Annealing algorithm) to solve the proposed model to develop a better solution. For the purpose of study, three cells are taken in which each cell holding four machines. The demand for each period doesn’t exceed ten components. This layout is applied in all the periods. Thus the entire planning horizon uses a single layout even though the demand is different in different periods of the planning horizon. The algorithm calculates better solution to the batch production industry.
Manufacturing. Group Technology, Static Layout, Optimum Layout.
1.Introduction:
HE current market is characterized by an environment where demand volumes and product
mix vary with period, hence manufacturers require well designed layouts to improve their operations and reducing costs. Cellular Manufacturing (CM) is the application of Group Technology (GT) in manufacturing systems. This measure of performance in CM could be productivity, cycle time, and logistics measure. Measures include pieces per man hour, unit cost, on-time delivery, lead time, defect rates, and percentage of parts made cell-complete. This process involves placing a cluster of carefully selected sets of functionally dissimilar machines in close proximity to each other. The realization of benefits expected from cellular manufacturing largely depends on how effectively the stages of the design have been performed Cellular Manufacturing. Major advantages, including reduction in lead times and work-in-process inventories and reduction of setup times due to similarity of part types produced.
P.Dharmalingam is currently pursuing masters degree program in Industrialr engineering in Anna University of Technology, Coimbatore.Mobile:99420 82725
K.Kanthavel, R. Sathiyamoorthy, ,
are currently working as Assistant Professor, M.Sakthivel as associate professor and R.Krishnaraj as JRF professional in Anna University of Technology, Coimbatore.
C.Elango is currently working as Assistant Professor in Tamilnadu
College of Engineering, Coimbatore.
The determination of a linear sequence that minimizes the total distance travelled by multi-items with different operation sequence was proposed by [14], This project proposes an algorithm of simulated annealing to construct a linear sequence of machines for multi products of different operation sequences with single or a limited number of machines of each type. Design of appropriate flow layout is possible using this linear sequence of machines., suggest, a new mathematical model concerning inter-cell and intra-cell cost in layout problems in cellular manufacturing systems with stochastic demands were discussed by [17]. The objective of the model is to minimize the total cost incurred by the inter-cell and intra-cell movements. The model determines the location of each machine in each cell and the location of cells on the shop floor with respect to the confidence level determined by the decision maker.
Cell formation and cellular layout design are the two main steps in designing a cellular manufacturing system (CMS). [9] An integrated methodology based on a new concept of similarity coefficients and the use of simulated annealing (SA) as an optimization tool. In comparison with the previous works, the proposed methodology takes into account relevant production data, such as alternative process routings and the production volumes of parts. The SA based optimization tool is parallel in nature and, hence, can reduce the computation time significantly,
IJSER © 2012 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 3, Issue 10, October-2012 2
ISSN 2229-5518
so it is capable of handling large-scale problems. Finally, the SA-based procedure is compared with a genetic algorithm (GA) based procedure and it will be shown that the SA-based algorithm can be as effective as a GA-based algorithm, but with less computational time and effort.
The problem of arranging and rearranging, when there are changes in product mix and demand, manufacturing facilities such that the sum of material handling and rearrangement costs is minimized. This problem is called the dynamic plant layout problem (DPLP). [4] A multi-start simulated annealing for DPLP. To compare the performance of meta- heuristics, data sets taken from literature are used in the comparison. This project investigates the layout
layout method involves development of a layout for the demand scenario for various periods.
The non linear mathematical model for the minimization of sum of total inter cell moves cost in a (CMS) cellular manufacturing system. This is modified and simplified from equation by Anan Mungwattana [2],
Minimization
problem based on multi-period planning horizons.
H P C M
Op1
between the different departments in the layout may
j 1, pmch jpmch ij
During these horizons, the material-handling flow
change. This necessitates a more sophisticated approach than the static plant layout problem (SPLP) approach. The cost incurred because of movements of the parts from machine to machine constitutes a
X
h1 p 1 c1 m1 j 1
Subjected to
H C
X d
…(1)
significant proportion in the total production cost.. A nonlinear mathematical model has been selected and its applicability validated against an industrial case by
Nmch 4 , where
h1 c 1
Nmch
is an integer ..(2)
[3],
The aim of this work is to present a new
mathematical model for inter cell layout problems in cellular manufacturing systems with Dynamic
demands. The objective is to minimize the total costs of inter cell movements. There are several objectives to measure the effectiveness of CMS such as: Minimum number of intercellular moves, Greatest proportion of part operations performed within a single cell, Maximum machine utilization, Minimal
h - Time horizon index h = 1,2 …H, p - Component index p = 1,2…P
c - Cell index c = 1,2…C
m- Machine index m = 1,2…M
j - Operation index = 1,2… Op
γ - Material handling cost per meter
dij - Cell distance matrix
total costs by reducing setup times, and WIP (work- in-process), Minimal capital investment, Minimum
Nmch
h
- Number of machines in the cell during period
number of voids in the cells, Effective facility layout including cellular operations, Throughput improvement. Equipment set-up and changeover time reduction, Reduction in inventory, Visual factory concepts, Mistake-proofing of processes.
The parameters in dynamic and deterministic production are assumed that the demand for each period doesn’t exceed ten components , the maximum number of machines in cells are three and periods are six. Each cell has four machines and number of components twenty five. This has lead to better layouts in most cases for a size of twelve machines in three cells. Distance between cells one
&two, two & three, and one & three is 300, 400 and
500meters respectively. Material handling cost Rs. 1
per meter. Within the cell there is no material
handling cost. Operator and machining cost are same
for all operations. Machining time is not considered
and Only one machine of each type is available. The
X jpmch =1, if operation ‘j’ of part type ‘p’ is performed
on machine type ‘m’ in the cell ‘c’ during period ‘h’ ,
otherwise it is 0
3.2. Solution Methodology:
There are several methods available to find an optimum solution for the above said problem. These are… Tabu search Branch and bound, Branch and cut, and Simulated annealing
Tabu search (TS) is a relatively new method. It is based on local search techniques incorporating some concepts of artificial intelligence and tries to avoid getting stuck in a local minimum. It generates and evaluates several solutions from the current solution and then chooses the best one. The TS accepts the new solution even if it is worse than the best new solution. For the implementation of TS for SCP cell placement, i.e. ordered triplets is chosen. The objective function and neighborhood operator are also the same [5]. The neighborhood operator in SA chooses two cells randomly from the sequence of cells and then interchanges their positions in the sequence. In tabu
IJSER © 2012 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 3, Issue 10, October-2012 3
ISSN 2229-5518
list therefore the pair of cells which was exchanged is stored as a record and for the next moves, the same two cells cannot be considered again. The algorithm stops when, for a given number of iterations, it has not found any improvement. This given number will be referred to as „wait for change‟. The number of neighbors to be tested is called loop-iteration and the length of tabu list is called Tabu- Maximum.
A new non-linear mixed-integer programming model is presented for the facility layout problem in a two-dimensional area to minimize the total distance traveled by the material in the shop floor. A technique is used to linearize the proposed model. An algorithm based on branch-and- bound approach is developed to optimally solve the proposed mathematical programming model [15]. An illustrative example is solved and then the obtained result is compared to the configuration obtained from the process layout with respect to the total material handling distance. It is shown that the presented model decreases the total distance traveled by the products about 41.8% for small-sized and about 44.8% for medium-sized problems as compared to the process layouts for the example problems. Since the process layouts are special cases of the general two- dimensional layout (TDL) modeled in this paper and with respect to the fact that the proposed branch-and- bound based algorithm determines the optimal solution of TDL, Since the solution approach is an exact method, The exact algorithms cannot be applied for solving large-sized combinatorial optimization problems in a reasonable time.
Branch-and-cut methods are very successful techniques for solving a wide variety of integer programming problems, and they can provide a guarantee of optimality. Many combinatorial optimization problems can be formulated as mixed integer linear programming problems. They can then be solved by branch-and-cut methods, which are exact algorithms consisting of a combination of a cutting plane method with a branch-and-bound algorithm. These methods work by solving
a sequence of linear programming relaxations of the integer programming problem. Branch-and-cut methods have proven to be a very successful approach for solving a wide variety of integer programming problems[11]. In contrast with metaheuristics, they can guarantee optimality. For a structured integer programming problem, the branch- and-cut method should be tailored to the problem with an appropriate selection of cutting planes. These methods are also useful for general
integer programming problems, where families of
general cutting planes are used.
Simulated annealing (SA) is a generic
probabilistic metaheuristic for the global optimization
problem of applied mathematics, namely locating a
good approximation to the global optimum of a given
function in a large search space. For certain problems,
simulated annealing may be more effective than
exhaustive enumeration provided that the goal is merely to find an acceptably good solution in a fixed amount of time, rather than the best possible solution. The name and inspiration come from annealing in metallurgy, a technique involving heating and controlled cooling of a material to increase the size of its crystals and reduce their defects. the slow cooling gives them more chances of finding configurations with lower internal energy than the initial one. By analogy with this physical process, each step of the SA algorithm replaces the current solution by a random "nearby" solution, chosen with a probability that depends both on the difference between the corresponding function values and also on a global parameter T (called the temperature), that is gradually decreased during the process.It is often used when the search space is discrete. Introduced by Kirkpatrick et al, as a method to solve combinatorial optimization problems.
Since the minimization model Non linear in nature, Metaheuristic and combinatorial optimization problems. So we have decided to implement the S.A. Algorithm (SAA) for extracting an optimized solution. The proposced heuritics are programmed using the C programming language.
SA begins with an initial solution (s0) and an initial temperature (to), and an iteration number (no). Temperature controls the possibility of the acceptance of a deteriorating solution, and an iteration number decides the number of repetitions until it reaches a stable state under the necessary temperature. Temperature provides a means of flexibility while at high temperatures (early in the search), there is some flexibility to the situation to deteriorate; but at lower temperatures (later in the search) less flexibility exists. A new neighborhood solution ( s ) is generated based on Temperature and iteration number through a heuristic perturbation on the existing solutions. The neighborhood solution (s) becomes the current solution ( s ) if the change of an objective function (δ = f(s)- f(so)) is improved (i.e. f(s) ≤ f(so)). Even though it is not improved, the neighborhood solution becomes a new solution with an appropriate probability based on (X < e(-δ/t) ) . The parameters X is set using random numbers on condition, 0 < X < 1.This lowers the possibility of being trapped in a local optimum. The algorithm terminates upon reaching a predetermined temperature (tf) or if there is no improvement in the objective function after repetition.
Step 1: Define an initial solution So Step 2: Set an initial temperature, to > 0, Cooling rate (α), 0< α <1,
Initial iteration (no), Step ratio (r), and Final temperature (tf)
Step 3: Do n0 times the following
Step 3.1: Pick the random neighbouring solution
Step 3.2: Compute δ = f(s) - f (s0)
Step 3.3: If δ <= 0 then set s0 = S
IJSER © 2012 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 3, Issue 10, October-2012 4
ISSN 2229-5518
Step 3.4: If δ > 0 , Generate random number, X U (0,1),calculate probability of
acceptance, e (-δ/t). If X < pacc , then set s0 =
s, If x > pacc , discard this step.
Step 4: Set t = α * to, to = t, n = no*1.1, no= n, Go to
step 3 until to reach the final temperature tf ,
otherwise go to step 5
Step 5: Return solution So
In this project, a meta-heuristic algorithm based on simulated annealing (SA) is proposed. The main steps of the proposed SA are as follows:
The initial solution is taken from existing layout (So). In addition, initial temperature (to), final temperature (tf), step ratio (r), iteration number of each temperature (n) and cooling rate (α), according to which temperature is decreased or initialized in this step.
Two neighbourhood solutions must be developed. Evaluate new solution cost and compare with existing solution cost to determine the cost difference. Take the average of the above said cost difference, then multiply by 10 to set initial temperature.
∆1 = I MHC 0 – MHC 1 I , ∆2
= I MHC 0 – MHC 2 I ,
Average = (∆1 + ∆2) / 2
Initial temperature = average X 10
1.2. SA Initial Parameters:
Initial solution (s0 ) - (Existing layout) ; Initial
temperature - t0 (Problem depended value) ; Final
temperature (tf) - (300); Cooling rate( α) = 0.85 ; Step
ratio (r) = 1.1;
Number of initial iteration (n0) = 10
In order to obtain the neighbourhood solution from the current (existing) solution, two machines are randomly chosen from two cells (one machine from each cell) and then interchanged. This is a new layout S.
The value of the cost function is evaluated after positions of machines interchanged f(s). The difference δ [= f(s)-f(so)] between new (neighbourhood) and (current) existing cost function values are calculated.
We decide whether to replace the current solution with the neighborhood solution or not. If the difference in cost is δ < 0, the new layout is accepted, and repeat the procedure till reaching the number of iteration in the particular temperature.
On the other hand, δ > 0, the parameters X is set using random numbers on condition ; 0<X<1. Next, if X < e(-δ/t) is true, the new layout is accepted, even if the cost is increased. But if X > e(-δ/t) is true, the new layout is rejected and searching process is repeated on the previous layout. Repeat the procedure till reaching the number of iteration in the particular temperature set no=10.
The temperature is decreased according to the following Equation: t = to * α, set to=t, where α is the cooling rate and is equal to 0.85.The number of iteration is increased in every temperature updating according to the following equation: n=no * r, set no= n, where r is the step ratio and is equal to 1.1. If updated temperature is not less less than final temperature tf, go to step 2 otherwise go to step 6.
The algorithm will be terminated if the current temperature reaches a predetermined temperature of tf.
1. Lathe 2. Horizontal milling machine 3. Vertical milling machine 4. Shaping machine
5. Boring machine 6. Drilling machine 7. Grinding machine 8. Slotting machine
9. Slitting saw 10.Power hacksaw machine 11. Deburing machine 12. Broaching machine
. Results and Discussion:
IJSER © 2012 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 3, Issue 10, October-2012 5
ISSN 2229-5518
12 | 2-4-5-6-8-9-1 | 25 | 9-1-5-7-8-10 |
13 | 5-6-7-8-9 |
The Component 1 requires the following machines to finish the product, 4-2-3-6-5-8. i.e. Shaping machine, Horizontal milling machine, Vertical milling machine, Drilling machine, Boring machine and Slotting machine respectively. Machine number and its details were given in the list of machines chart.
CELL 1 CELL 2
4 8 3 2
6 5 1 10
CELL 3
12 7
QC
11 9
Table 4.2 Material Handling Cost Period Wise
Table 4.3. Machine and Component Groups
Chart 4.1 Material Handling Cost Vs Itration
The new proposed layout material handling cost is lesser than the existing layout material handling cost. The cost savings 18 %. Hence, the new layout is recommended. Computer specifications: Intel (R), Pentium(R) D CPU - 3.00 GHz, Speed - 2.99
GHz, 992 MB of RAM,100 GB hard disc, was used .
Total number of iteration 3522. Average time taken to
obtain the result 2 – 3 minutes.
In this paper, a new non linear mathematical model is proposed to design the cellular layout for the dynamic demand environment in cellular manufacturing system. The proposed model determines the optimal inter cell layout material handling with aim of minimizing the total cost of the inter cell movements. SA is used to solve the
IJSER © 2012 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 3, Issue 10, October-2012 6
ISSN 2229-5518
mathematical model and it is coded by C programming language. When compare with static layout, optimum layout not only reduce the material handling cost and also reduce the number of movements. This ensures the improved quality, work in process and productivity. Maximum amount of time is taken for waiting and move the material. That is greatly reduced in optimum layout. From the above result optimum layout gives better solution. Intra cell material handling cost, batch wise component transfer and the operating time of each component can be considered in future research work.
[1] Alan R. Mckendall Jr., Jin Shang, Saravanan Kuppusamy, (2006) “Simulated Annealing Heuristics For The Dynamic Facility Layout Problem” Computers & Operations Research 33, Page No. 2431–2444.
[2] Anan Mungwattana [2000], “Design of Cellular Manufacturing Systems for Dynamic and Uncertain Production Requirements with Presence of Routing Flexibility”. Virginia Polytechnic Institute and State University,Blacksburg, Virginia.
[3] Asif Iqbal (2010) “Balancing And Simulating Inter-Cell And Intra- Cell Moves Costs In A Cellular Manufacturing” Journal Of Studies On Manufacturing (/Iss.1) / Page No. 48-53.
[4] B. Ashtiani M. B. Aryanezhad B. Farhang Moghaddam, (2007) “Multi-Start Simulated Annealing For Dynamic Plant Layout Problem ” Journal Of Industrial Engineering International Islamic Azad University, South Tehran Branch , Vol. 3, No. 4, 44-50
[5] Bunglowala, A., Singhi, B.M. et. al, (2008), “Performance Evaluation and Comparison and Improvement of Standard Cell Placement in VLSI Design”, International Conference on Emerging Trends in Engineering and Technology.
[6] T.F. Burgess, (1996), “Modelling Quality-Cost Dynamics” International Journal Of Quality & Reliability Management, Vol. 13 No. 3, Page No.
8-26.
[7] Chang-Lin Yang & Shan-Ping Chuang & Tsung-
Shing Hsu, (2010) “A Genetic Algorithm For
Dynamic Facility Planning In Job Shop
Manufacturing” Springer-Verlag London Limited,
Int J Adv Manuf Technol, DOI .10.100170/S00170-
010-2733-0
[8] Irappa Basappa Hunagunda And Madhusudanan
Pillai Vb “Design Of Robust Machine Layout For
Cellular Manufacturing Systems”, procedings of
the International Conference on Digital factory
Page No. 1398 - 1405
[9] Jamal Arkat, Mohammad Saidi &Babak Abbasi,
(2006) “Applying Simulated Annealing To
Cellular Manufacturing System Design” Springer-
Verlag London Limited Int J Adv Manuf Technol, Page No. 531 -536.
[10] Jaydeep Balakrishnan,Chun Hung Cheng (2006), “A Note On “A Hybrid Genetic Algorithm For The Dynamic Plant Layout Problem” International Journal Of Production Economics,
103, 1, , Page No. 87-89.
[11] John E. Mitchell, (1999), “Branch-and-Cut
Algorithms for Combinatorial Optimization
Problems”. The Handbook of Applied Optimization,
Oxford University.
[12] Kamran Shahanaghi , Seyed Ahmad Yazdian,
(2009), “Analyzing The Effects Of
Implementation Of Total Productive Maintenance
(Tpm) In The Manufacturing Companies: A
System Dynamics Approach” World Journal Of
Modelling And Simulation Vol. 5 No. 2, Page No.
120-129.
[13] Maghsud Solimanpur & Shahram Saeedi & Iraj
Mahdavi, (2010) “Solving Cell Formation Problem
In Cellular Manufacturing Using Ant-Colony-
Based Optimization” Springer-Verlag London
Limited, Int J Adv Manuf Technol Page No.1135 -
1144.
[14] V. Madhusudanan Pillai, Bhavani Sankar
Gudivada, (2005) National Institute Of
Technology “A Simulated Annealing Algorithm
For Linear Sequencing Of Machines For Layout
Design” Sixth Int. Conf. On Opers. And Quant.
Management, 9-11,
[15] Solimanpur, M., Jafari, A., (2008), Optimal
solution for the two-dimensional facility layout
problem using a branch-and-bound algorithm,
Computers & Industrial Engineering, doi:
10.1016/j.cie.2008.01.018
[16] Soroush Saghafian, M. Reza Akbari Jokar, (2009)
“Integrative Cell Formation And Layout Design
In Cellular Manufacturing Systems” Journal Of
Industrial And Systems Engineering Vol. 3, No. 2,
Page No. 97-115.
[17] R. Tavakoli-Moghadam B. Javadi F. Jolai And
S.M. Mirgorbani, (2006), “An Efficient Algorithm
To Inter And Intra-Cell Layout Problems In
Cellular Manufacturing Systems With Stochastic
Demands” IJE Transactions a: Basics, Vol 19, Page
No. 67-78.
[18] Tamal Ghosh, Sourav Sengupta , Manojit
Chattopadhyay and Pranab K Dan, (2011),
“Meta-Heuristics In Cellular Manufacturing: A
State-Of-The-Art Review” International Journal
Of Industrial Engineering Computations Page No.
2 87–122.
[19] Vladimir Modrak, (2009 ) “Case On
Manufacturing Cell Formation Using Production
Flow Analysis” World Academy Of Science,
Engineering And Technology, Page No. 519 -523.
[20] Xiaodan Wu , Chao-Hsien Chu, Yunfeng Wang ,
Weili Y, (2007) , “A Genetic Algorithm For
Cellular Manufacturing Design And Layout”
IJSER © 2012 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 3, Issue 10, October-2012 7
ISSN 2229-5518
European Journal Of Operational Research 181, Page No. 156–167.
[21] J.S.Yim, C.M.Kyung,(1998)_data path layout optimisation using genitic algorithm and simulated annealing, IEE Proc.-Comput. Digit. Tech., Vol. 145, No. 2,pp. 135-141
IJSER © 2012 http://www.ijser.org