FUZZY SUBTRACTIVE CLUSTERING FOR DETERMINING OF THE NEW FACILITIES LOCATION

FUZZY SUBTRACTIVE CLUSTERING
FOR DETERMINING OF THE NEW FACILITIES LOCATION
by Yogi Yogaswara
 
Master Program of Industrial Engineering, Pasundan University, Bandung, Indonesia
yogi@magister-ti-unpas.org

ABSTRACT  
Efforts are made to improve the smoothness of production activity in the manufacturing had been felt still less than optimal. One effort that can be done is by adding a new facility that is expected to help increase the productivity that has a material relationship process. The problem that often occurs is how to put the location of new facilities without increasing the material handling cost.  The algorithm proposed in this paper is fuzzy subtractive clustering that has the ability to determine the regions in a variable that has a high density of points in
the vicinity . 
Key words : Fuzzy Subtractive Clustering, facilities location, material handling cost.

1. INTRODUCTION  

The first step of the facilities planning is the determination of the facility location. The problem of facility location is faced by both new and existing businesses, and its solution is critical to a company’s eventual success. The many problems faced in various companies focusing on the smoothness problem of production activity. One of the efforts made by adding new facilities to the production facilities layout. The problem that often occurs is how to determine the location of facilities in the optimal production process flow based on the relationship of material from old facilities to new facilities. Fuzzy subtractive clustering model used to solve the problem in this paper, which is based on the size of the potential density of the points in a variable space.

2. FACILITIES LOCATION MODELS 
2.1. Fuzzy C-Means (FCM)

Fuzzy C-means is a method to perform clustering of the data where the presence of each data point in a cluster is determined by the degree of membership. This method was first introduced by Jim Bezdek in 1981. FCM basic concept is to determine the cluster center, which will mark the location of the average for each cluster. At the beginning, the center of the cluster is still not accurate.

Each data point has a degree of membership for each cluster. By way of improving the center of the cluster and the degree of membership of each point repeatedly, it will show that the cluster center will move to the correct location. This iteration is based on the minimization of the objective function that describes the distance from a given data point to the nearest cluster that has been weighted by the degree of membership of data points. The output of the FCM is not a fuzzy inference system, but a row of cluster centers and some degree of membership for each data point. This information can be used to build fuzzy inference system.

2.2. Fuzzy Subtractive Clustering (FSC)

FSC is based on the size of the density (potential) of each data point in a space (variable). The basic concept of subtractive clustering is to determine the regions in a variable that has a high density of points in the vicinity. Point with the largest number of neighbors will be selected as cluster centers. The point that has been chosen as the center of the cluster was then reduced density. Then the algorithm will choose another point which has the largest neighbor to be the center of another cluster. This will be repeated until all points tested. If there are N pieces of data: X ₁ , X ₂ , ... X_N and by assuming that these data are in normal circumstances, that is by doing the translation of data before going into the next calculation, the density of point X_k can be calculated as :

Distance represented by ||X_k - X_j ||   is distance between X_k and X_j , and r is positive constanta of the radius of each attribute data, a vector derived from the distance between the locations to determine the effect of cluster centers on each variable. Thus, one data point will have a greater density if it has many close neighbors.

For example X_cl is chosen as the center point of the cluster, while D_cI is a measure of its density, the density of the points in the vicinity will be reduced to :

With r_b = r_j is a positive constant. with rb = rj is a positive constant. This means that the point are located on the U_cl cluster center will have a massive reduction in density. This will lead to that point will be very hard to become the next cluster center. Value of rb indicates an environment that resulted in reduced size of the point density. Score of r_b greater than the r , r_b = q * r_a , where r_a is the radius of initial attributes (usually, squash factor (q ) = 1.5). After the density of each point is fixed, it will look for a second cluster center is X_{c 2} . After X_{c 2} obtained, then measure the density of each data point will be repaired again, then will do the calculation as the first step until no more candidates at the center of the cluster.

In implementation, two fractions can be used as a comparison factor, namely Accept Ratio and Reject Ratio which has a fraction is 0 to 1. Accept Ratio is a lower limit to which a data point that a candidate cluster centers are allowed to be the center of the cluster. While Reject Ratio is an upper limit to which a data point which becomes a candidate cluster centers are not allowed into the center of the cluster. In an iteration, when it found a data point with highest potential (e.g. X_k with D_k potential), then will proceed by finding the ratio of the potential of these data points with the highest potential of a data point in the early iterations (e.g. X_h with D_h potential), then the division results between D_k with D_h is then called by the ratio (ratio = D_k / D_h ). There are 3 conditions that can occur in an iteration (Figure 1).

• If ratio > accept ratio, then the data point is accepted as a new cluster center.
• If Rejected ratio < ratio < accept ratio, then the new data point will be accepted as a new cluster center if the data points are located at a considerable distance to the center of another cluster (the sum of the ratio with the longest distance the data point with other cluster centers is ≥ 1). Otherwise, their potential is set equal to zero, vice versa.
• If ratio ≤ reject ratio, then there is no more data points are considered to be the center of the cluster, the iteration is stopped

Figure 1 Ratio, Accept Ratio and Reject Ratio

 

3.    RESEARCH METHOD

3.1.   Data Collection

The data collected is the result of observation of one mattress and spring bed manufacturing company in Indonesia. The data required are as follows:

1. Data of the locations number or departments that use. This data represents the number of locations or departments that will be associated with the location of the facility to be built.
2. Initial layout of the old facility location. This layout is used as input for the location of new facilities. Floor plan layout shows information about the location of each department or area and coordinates the following facilities located.

3.2.  Fuzzy Subtractive Clustering Algo-rithm Procedure

Steps in the subtractive fuzzy clustering algorithm as follows :

1. Determine the centroid of each department in the initial layout. For example, the coordinates of the points is corner of the department a (40;50), b (40;0), c (120;50), and d (120;0), then the centroid of the department is (80, 25).
2. Enter data to be in clusters : X_ij , with i = 1,2 ,..., n , and j = 1,2, .., m .
3. Set values :

• r (the radius of each data attribute); j =1,2,…m;
• q (squash factor)
• Accept ratio
• Reject ratio
• X _min (allowed data minimum)
• X _max (allowed data maximum)

     4. Normalization

      i = 1,2,...n ;   j =1,2,…m

5.   Specify the initial potential of each data point.

1. i =1
2. calculate until i =n

• T_j = X_ij , j = 1,2,…,m .
• Calculate :

        

          j = 1,2,…,m ; k   = 1,2,…,n

• Initial Potential :

          If m = 1, then

         

          If m > 1, then

         

• I = i + 1

6.   Find the point with highest potential

1. M = max [D_i , i =1,2,…n ];
2. h = I, such that D_i = M ;

7.   Specify a cluster center and reducing potential of the surrounding points

1. Center = [ ]
2. V_j = X_hj ; j = 1,2,…m ; 
3. C = 0 (number of clusters);
4. Condition = 1;
5. Z = m
6. If (condition ≠ 0) and (Z ≠ 0) then :

• Condition = 0 (there are no any candidates for new cluster center.
• Ratio = Z/M .
• If Ratio > Accept Ratio, then

          Md = -1;

          for i = 1 to i = C :

         

          

       If (Md > 0) or (Sd < 0), then Md = Sd

• Smd = √Md ;
• If  (Ratio + Smd ) ≥ 1, then condition = 1; (data accepted as cluster center);
• If (Ratio + Smd ) < 1, then condition = 2; (data will not be considered again as a central cluster).

     g.  If condition = 1 (candidate of the new cluster center accepted as cluster center), 

          then :

• C = C +1;
• Center_C = V ;
• Reduce the potential points near the cluster center

      

        

• D = D – Dc;
• If  D ≤ 0, then D_i = 0; i = 1,2,…,n .
• Z = max[D_i ]; i = 1,2,…,n ;
• Select h = i , such that D_i = Z;

      h.   If condition=2 , then

• D_h = 0;
• Z = max[D_i ]; i = 1,2,…,n ;
• Select h = i, such that D_i = Z ;

8.   Return the normalized cluster center into original form.

              

9.   Calculate cluster sigma value :

    

with the results of the gauss curve, the degree of a data point membership X_i in k cluster  is :

4.    RESULT AND DISCUSSION

Case study derived from spring bed factory, there are 12 facilities available. The company plans to add new facilities, i.e. embroidery facility which will provide an additional feature on spring products.

Coordinates data of each location of the facilities shown in Table 1.

Some assumption used are :

·         Radius (r_j )                    =  0.8

·         Accept ratio                 =  0.6

·         Reject ratio                  =  0.2

·         Squash factor (q )        =  1.25

·         Lower limit                   =  [3; 5]

·         Upper limit                   =  [47;12.5]

 

Using all the steps in the procedure of fuzzy subtractive clustering algorithm, starting from the calculation of normalization to obtain the value of membership degree, then the results shown in Table 2.  

The information in Table 2 describes the tendency of a facility to enter the cluster that has a certain degree of membership.

Greatest degree of membership indicates the highest propensity of a facility to become a member clusters.

Figure 2 shows the position of each location facilities in the coordinates. Coordinates facility based on the initial layout of the old facilities that are used as input for the location of new facilities. The location of the new facility will be located in the vicinity of the old facility which has a membership degree equal to 1, i.e. at the point coordinates into facility-8, and has the most neighbors are at the point coordinates into facility 7, 4, and 6 respectively. The location of new facilities are marked with [●].

Figure 2. The New Facilities Location Coordinates

The 8^th facility (D8) has a minimum distance proximity with minimum membership degree to the cluster center (centroid) which has a membership equal to 1 which became the location of new facilities near the old facilities.

5.    CONCLUSION

Subtractive fuzzy clustering algorithm determines only the points that have the facility of points high density in the vicinity . Calculation process stops at 5 iterations, because there are no more candidates, the center of the cluster to be the center of the cluster or clusters are in a condition where ratio ≤ reject ratio.  

Cluster obtained based on the calculations result are 4 clusters. Cluster selected to serve as a new facility located in the 4^th cluster that has a greater membership degree value of 1 compared to other clusters value are 0.969 .  

The result of the calculation of fuzzy subtractive clustering algorithm indicate the location of new facilities were selected to be near the 8^th facilities, and has the most consecutive neighbors respectively D6 (μ = 0.981), D7 (μ = 0.973), D4 (μ = 0.964).  

Simak

Baca secara fonetik

The The results of this study is expected to reduce material handling costs, because the effect of proximity between the old facilities with new facilities would reduce the impact of increased material handling costs incurred by the company. The closer the material flow from one another, it will further reduce material handling costs generated.

6.    REFERENCES

1.   Apple, J.M., (1977), Plant Layout and Material Handling , 3^rd edition, Wiley, New York, NY.  
2. Francis, R.L., and White, J.A., (1992), Facility Layout and Location An Analytical Approach , 2^nd edition, Prentice Hall, Inc., Englewood Cliffs, New Jersey, NJ.
3. Heragu, S., (2006), Facilities Design , 2^nd edition, iUniverse, Inc., New York, NY.
4. Kusumadewi S., and Purnomo, H., (2004), Aplikasi Logika Fuzzy Untuk Pendukung Keputusan , Graha Ilmu, Yogyakarta.
5. Love, R.F., Morris, J.G., Wesolowsky, G.O., (1988), Facilities Location: Models and Methods , North Holland, New York, NY.
6. Purnomo, H., (2004), Perencanaan dan Perancangan Fasilitas , Graha Ilmu, Yogyakarta.

Download Artikel ini