##
Esnek imalat istemlerinde hücre oluşturma problemine 0-1 tamsayılı programlama ile modelleme yaklaşımı

Esnek imalat istemlerinde hücre oluşturma problemine 0-1 tamsayılı programlama ile modelleme yaklaşımı

##### Dosyalar

##### Tarih

1997

##### Yazarlar

Tansöker, Süleyman Ertan

##### Süreli Yayın başlığı

##### Süreli Yayın ISSN

##### Cilt Başlığı

##### Yayınevi

Fen Bilimleri Enstitüsü

##### Özet

Günümüzde mal ve hizmet pazarları artan bir oranda globalleşme eğilimi göstermektedir. Bu durum beraberinde artan rekabet koşullarını getirmekte; firmaların faaliyetlerini sürdürerek ayakta kalabilmeleri ancak bu zorlu rekabet koşullarına adapte olabilmelerine bağlı olmaktadır. Bölgesel pazarların giderek daha güçlü hale gelmesi ülkemizin de Avrupa Topluluğu' na başvurusunu zorunlu kılmıştır. Bunun sonucunda 1996 yılından itibaren başlayan tam üyelik öncesi Gümrük Birliği Anlaşması ülkemiz ve Avrupa Topluluğu ülkeleri arasında imzalanmıştır. Böylece hemen hemen tüm ürünler bazındaki gümrük tarifeleri karşılıklı olarak sıfırlanmıştır. Doğaldır ki topluluk ülkeleri özellikle sanayi ürünlerinde teknoloji ve kalite açısından ülkemizden daha ileri konumdadırlar. Bu nedenle firmalarımızın rekabet edebilmeleri için kalitede dünya standartlarını yakalamaları ve maliyet açısından daha etkin çalışmaları şarttır. Sanayi ürünlerinde hammadde ve enerji girdilerinde maliyetleri azaltmak pek kolay olmamaktadır. Dolayısıyla ancak verimliliği arttırarak mevcut girdilerle daha fazla ürün üretmek toplam maliyetleri etkilemese de birim maliyetleri azaltarak rekabet avantajı sağlayacaktır. Günümüzde pazar talepleri ürünlerin daha fazla çeşitli ve daha kısa sürelerde üretilmesini de gerektirmektedir. Grup Teknolojisi bu noktada işe yaramakta; büyük imalat sistemlerini daha küçük makina ve parça aileleri olarak gruplayarak daha etkin çalışan sistemlere ulaşılmasını sağlamaktadır. Bu çalışmada grup teknolojisi ile makina-parça aileleri oluşturma problemine tamsayılı programlama ile modelleme yaklaşımı ele alınmış ve mevcut bir sistemin bu modelle yeniden oluşturulmasına çalışılmıştır. Sistemin bilgisayar destekli çalışabilmesi için gerekli bilgisayar programlan üretilmiştir.

Product and service markets have recently tend to be global markets in an increased proportion. That is the reason of the increasing competition in market economy. Thus it is a must to adopt the strong market conditions for the firms to survive. The more competitive and strong positions of regional markets around the world had forced our country to apply for the membership to The European Union. In 1996, as a result, Customs Union Agreement had been signed between Turkey and member countries of the union. Afterwards the tariffs on almost all of the products had been decreased to zero level. Since the member countries of the union have more competitive advantages on industrial products from the point of quality and technology, our firms have to reach the worldwide standards and work much more effective to catch a competitive position. Obviously it is not easy to decrease the costs of energy and resources. Consequently the only way to acquire the competitive advantage is to increase the productivity since it provides remarkable decrease in unit costs of goods. Nowadays the changing demand of the markets requires more differentiated products with shorter production time. Thus the manufacturing systems have been forced to be organized in such a way that they will provide production with shorter time and smaller lots. The Group Technology is a powerful tool at this point to form machine-part families which work more cost and time effective. In this thesis the modeling by 0-1 integer programming approach to form the machine-part families have been studied and a present manufacturing system reorganized by the model. The required software have been written to use the computing facilities. In the first chapter the group technology and its effects upon costs in manufacturing systems, the application methods for the group technology, the general searching groups and assumptions have been studied. As stated in the chapter that the group technology is a kind of manufacturing philosophy. This philosophy forms the principles to benefit from the advantages of similarities in all stages of designing an manufacturing while gathering the similar parts or processes. The results of the researches on the factors that effect the productivity of manufacturing systems are as follows: XI 1 - The effect of the improvement in manpower quality is 15%. 2 - The effect of the force to acquire the required capital fund is 25%. 3 - The effect of the improvements in manufacturing technologies is 60%. The group technology studies take place in the last group. According to the results of a comparative productivity research including 270.000 operation selected by sampling, neither machines nor manpower can be used beneficially during 50% of the production time. That's a remarkable result. If the time of machine usage can be increased by this philosophy the processes will be more cost and time effective. The three different methods that have been based on to form the consistent machine-part families in group technology are as follows: 1 -Visual inspection method that depends on analyzing the geometrical patterns of the parts to form the part families. 2-Methods depending on part characteristics which are also referred to part coding and classifying analysis. 3-Methods depending on the production process. This is a very popular method also named as Production Flow Analysis. After gathering the initial data there are three steps respectively in applying this method. a. Forming the part packages. b. Forming the matrix of production flow analysis. c. Analyzing the matrix to form the machine-part families. In the second chapter the fundamental cell formation methods have been studied. They are called as follows: 1-Cell formation by production flow analysis. This analysis had been developed by Burbidge. Unfortunately it has two important problems. The first is that the analysis' depend on heuristic procedures. As the second, it not probable to reach a feasible solution while the machine-part matrix is to large. In the analysis a similarity coefficient is defined as Ss-VCXa+VXj) 0) Sy : The similarity coefficient Xu : The number of parts that are operated by only i. machine. Xjj : The number of parts that are operated by only j. machine. Xy : The number of parts that are operated by both i. and j.machine. The more the value of Xy the more is the similarity. According to a previously determined threshold T value the groups are formed. XII 2-Methods that forms diagonally ordered groups in machine-part matrix. The first method is the bond energy method. In essence this is a quadratic assignment problem. When the problem is large the counting time increases exponentially. Thus a heuristic method had been developed to reach secondary optimal solutions. The second is the rank order clustering algorithm. It was developed by King to form diagonally ordered groups. Techniques that will produce better solutions especially for the bottle-neck machines. The last one is the cell formation using machine and part statistics. In this approach first the machine families are formed, later the parts are assigned to these groups without forming the part families. In the third chapter 0-1 integer programming approach and The Additive Algorithm or Balas Algorithm have been explained. In this algorithm the variables can only have 0 or 1 values. There are two parts as the objective function and the constraints. In the method, the objective function must be a minimization type and the constraints must be less than or equal to zero. minZ = £CjXj j=l,.-,n 2aijXj + Si = bi i=l,..,m Xj=0orXj=l S; >0 Herein, Q : The coefficients of the objective function. Xj : The 0-1 variables. ay : The technical coefficients in the constraint matrix. bj : The values of the resources. S; : The values of the slack variables that added the model later. The transformation techniques for incompatible problem types are provided by solving an example problem. In the last chapter the 0-1 integer programming approach to machine grouping problem in cellular manufacturing systems and two different mathematical models have been studied. The objective is to assign the machines into previously formed part groups. The methods are applied depending on the tooling requirements of the parts, the present tools and the operating times. In the first formulation machines are grouped based on the compatibility index between the parts and machines. On the other hand, in the second formulation the transportation costs among the cells and the layout costs are aimed to minimize while grouping the machines. Both the number of machines of each type and the maximum number of machines in a group are assumed as parameters. The variables of the models are as follows: X1H i :Part index, i=l,..,n j : Machine index, j=l,..,m k : Cell index, k=l,..,p N, : The number of the tools required for the part i. Mj : The number of the tools available on the machine j. Ty : The number of the common tools between parts i and j Oy : The number of the operations on pan i machine j. Pi : The set of the operations that must be done on part i. Sjj : The compatibility index between part i and machine j. tu : The required time for operation 1 of part i. qi : The annual production amount of part i. fj : The annual fixed cost ratio of machine j. Li : The unit handling size of the part i. c : The average cost of transport between two cells. Aj : The available number of machine j. Bj : The max. number of machine j that can be procured. Gk : The limit of the machine number in cell k 1, if part i is in cell k a, : { } 0, otherwise The decision variable X is defined as 1, if machine j is incelik X, : { } 0, otherwise Two different compatibility index are defined in the models. XIV 1 -Compatibility index based on the tooling requirements. Sö=Tü/min{Mj,Ni} (2) This equation states the operational compatibility between a machine and a part. If there are a number of common tools between a machine and a part, that means less transportation and handling costs. 2-Compatibility index based on both the tooling requirements and operation time. SÖ = (Ş tü ) / (S w) (3) kOjj re Pi If the machine and the part are grouped together, while the operation time is as long as possible then the working rate of the machine will be that much higher. In this study two different models are proposed as mentioned before. These models are as follows: Model 1 -Reorganizing an available system. maxZi^ E E Xjk * aik * Sy- (4) i j k The fist objective function aims to maximize the sum of the compatibility index for all machine and parts in all cells. minZ2=(S Zfj*XjkM E E S Xjk * aij * Tu *C * qi/L; ) (5) j k i j k The second objective function is formed for the equilibrium between the machine assignment and handling cost among cells. The handling cost is faced when any tool of a machine in cell m is required to operate on a part in cell k. Here m =f k is assumed. The first term in the equation is the assignment cost of a machine in a cell. The second one is the total savings from intercell movement. Ty * ( q; / Lj ) is the number of movement between any couple of cells. Then Ty- * C * q; / L; means the average cost of these movements. If these parts are grouped in a common cell, that means the savings from the cost of movements. The constraints of the system are as follows: 1 Xjk < Gk for all k (6) 2 Xjk =Aj for all j (7) Xjk £(0,1) for all j and k (8) XV Model 2-Organizing a new system. The objective function of the model is given in equation 4. The cell size constraint is the same as equation 6 and 8. But equation 7 is converted as follows: Xjk £ Bj for all j (9) This constraint satisfies that the maximum number of each type of machines that can be procured will not exceed. The model does not assign a machine to a cell if it is not cost effective. It's required to invoke a constraint that at least one of each type of a machine will be assigned to any cell. Otherwise it would be impossible to do some operations on some of the parts. I Xjk >1 for all j (10) k Model 1 is applied to a manufacturing system including 10 machine and 25 different parts. The required information can be obtained from Table 5.1 and Table 5.2. The cost of an inter-cell movement is supposed TL 500.000. The unit loading size for all parts is 5. The number of machines that can be assigned to a cell is limited to 6. Meanwhile the part families are formed by a heuristic based on tooling requirements. The results are presented in Table 5.3 and Table 5.4. As the conclusion if the proposed mathematical models presented in the thesis are applied to form machine-part families in large sized integrated flexible manufacturing systems, the layout will be more cost effective. Key Words : Group Technology, Integer Programming, Production Flow Line XVI

Product and service markets have recently tend to be global markets in an increased proportion. That is the reason of the increasing competition in market economy. Thus it is a must to adopt the strong market conditions for the firms to survive. The more competitive and strong positions of regional markets around the world had forced our country to apply for the membership to The European Union. In 1996, as a result, Customs Union Agreement had been signed between Turkey and member countries of the union. Afterwards the tariffs on almost all of the products had been decreased to zero level. Since the member countries of the union have more competitive advantages on industrial products from the point of quality and technology, our firms have to reach the worldwide standards and work much more effective to catch a competitive position. Obviously it is not easy to decrease the costs of energy and resources. Consequently the only way to acquire the competitive advantage is to increase the productivity since it provides remarkable decrease in unit costs of goods. Nowadays the changing demand of the markets requires more differentiated products with shorter production time. Thus the manufacturing systems have been forced to be organized in such a way that they will provide production with shorter time and smaller lots. The Group Technology is a powerful tool at this point to form machine-part families which work more cost and time effective. In this thesis the modeling by 0-1 integer programming approach to form the machine-part families have been studied and a present manufacturing system reorganized by the model. The required software have been written to use the computing facilities. In the first chapter the group technology and its effects upon costs in manufacturing systems, the application methods for the group technology, the general searching groups and assumptions have been studied. As stated in the chapter that the group technology is a kind of manufacturing philosophy. This philosophy forms the principles to benefit from the advantages of similarities in all stages of designing an manufacturing while gathering the similar parts or processes. The results of the researches on the factors that effect the productivity of manufacturing systems are as follows: XI 1 - The effect of the improvement in manpower quality is 15%. 2 - The effect of the force to acquire the required capital fund is 25%. 3 - The effect of the improvements in manufacturing technologies is 60%. The group technology studies take place in the last group. According to the results of a comparative productivity research including 270.000 operation selected by sampling, neither machines nor manpower can be used beneficially during 50% of the production time. That's a remarkable result. If the time of machine usage can be increased by this philosophy the processes will be more cost and time effective. The three different methods that have been based on to form the consistent machine-part families in group technology are as follows: 1 -Visual inspection method that depends on analyzing the geometrical patterns of the parts to form the part families. 2-Methods depending on part characteristics which are also referred to part coding and classifying analysis. 3-Methods depending on the production process. This is a very popular method also named as Production Flow Analysis. After gathering the initial data there are three steps respectively in applying this method. a. Forming the part packages. b. Forming the matrix of production flow analysis. c. Analyzing the matrix to form the machine-part families. In the second chapter the fundamental cell formation methods have been studied. They are called as follows: 1-Cell formation by production flow analysis. This analysis had been developed by Burbidge. Unfortunately it has two important problems. The first is that the analysis' depend on heuristic procedures. As the second, it not probable to reach a feasible solution while the machine-part matrix is to large. In the analysis a similarity coefficient is defined as Ss-VCXa+VXj) 0) Sy : The similarity coefficient Xu : The number of parts that are operated by only i. machine. Xjj : The number of parts that are operated by only j. machine. Xy : The number of parts that are operated by both i. and j.machine. The more the value of Xy the more is the similarity. According to a previously determined threshold T value the groups are formed. XII 2-Methods that forms diagonally ordered groups in machine-part matrix. The first method is the bond energy method. In essence this is a quadratic assignment problem. When the problem is large the counting time increases exponentially. Thus a heuristic method had been developed to reach secondary optimal solutions. The second is the rank order clustering algorithm. It was developed by King to form diagonally ordered groups. Techniques that will produce better solutions especially for the bottle-neck machines. The last one is the cell formation using machine and part statistics. In this approach first the machine families are formed, later the parts are assigned to these groups without forming the part families. In the third chapter 0-1 integer programming approach and The Additive Algorithm or Balas Algorithm have been explained. In this algorithm the variables can only have 0 or 1 values. There are two parts as the objective function and the constraints. In the method, the objective function must be a minimization type and the constraints must be less than or equal to zero. minZ = £CjXj j=l,.-,n 2aijXj + Si = bi i=l,..,m Xj=0orXj=l S; >0 Herein, Q : The coefficients of the objective function. Xj : The 0-1 variables. ay : The technical coefficients in the constraint matrix. bj : The values of the resources. S; : The values of the slack variables that added the model later. The transformation techniques for incompatible problem types are provided by solving an example problem. In the last chapter the 0-1 integer programming approach to machine grouping problem in cellular manufacturing systems and two different mathematical models have been studied. The objective is to assign the machines into previously formed part groups. The methods are applied depending on the tooling requirements of the parts, the present tools and the operating times. In the first formulation machines are grouped based on the compatibility index between the parts and machines. On the other hand, in the second formulation the transportation costs among the cells and the layout costs are aimed to minimize while grouping the machines. Both the number of machines of each type and the maximum number of machines in a group are assumed as parameters. The variables of the models are as follows: X1H i :Part index, i=l,..,n j : Machine index, j=l,..,m k : Cell index, k=l,..,p N, : The number of the tools required for the part i. Mj : The number of the tools available on the machine j. Ty : The number of the common tools between parts i and j Oy : The number of the operations on pan i machine j. Pi : The set of the operations that must be done on part i. Sjj : The compatibility index between part i and machine j. tu : The required time for operation 1 of part i. qi : The annual production amount of part i. fj : The annual fixed cost ratio of machine j. Li : The unit handling size of the part i. c : The average cost of transport between two cells. Aj : The available number of machine j. Bj : The max. number of machine j that can be procured. Gk : The limit of the machine number in cell k 1, if part i is in cell k a, : { } 0, otherwise The decision variable X is defined as 1, if machine j is incelik X, : { } 0, otherwise Two different compatibility index are defined in the models. XIV 1 -Compatibility index based on the tooling requirements. Sö=Tü/min{Mj,Ni} (2) This equation states the operational compatibility between a machine and a part. If there are a number of common tools between a machine and a part, that means less transportation and handling costs. 2-Compatibility index based on both the tooling requirements and operation time. SÖ = (Ş tü ) / (S w) (3) kOjj re Pi If the machine and the part are grouped together, while the operation time is as long as possible then the working rate of the machine will be that much higher. In this study two different models are proposed as mentioned before. These models are as follows: Model 1 -Reorganizing an available system. maxZi^ E E Xjk * aik * Sy- (4) i j k The fist objective function aims to maximize the sum of the compatibility index for all machine and parts in all cells. minZ2=(S Zfj*XjkM E E S Xjk * aij * Tu *C * qi/L; ) (5) j k i j k The second objective function is formed for the equilibrium between the machine assignment and handling cost among cells. The handling cost is faced when any tool of a machine in cell m is required to operate on a part in cell k. Here m =f k is assumed. The first term in the equation is the assignment cost of a machine in a cell. The second one is the total savings from intercell movement. Ty * ( q; / Lj ) is the number of movement between any couple of cells. Then Ty- * C * q; / L; means the average cost of these movements. If these parts are grouped in a common cell, that means the savings from the cost of movements. The constraints of the system are as follows: 1 Xjk < Gk for all k (6) 2 Xjk =Aj for all j (7) Xjk £(0,1) for all j and k (8) XV Model 2-Organizing a new system. The objective function of the model is given in equation 4. The cell size constraint is the same as equation 6 and 8. But equation 7 is converted as follows: Xjk £ Bj for all j (9) This constraint satisfies that the maximum number of each type of machines that can be procured will not exceed. The model does not assign a machine to a cell if it is not cost effective. It's required to invoke a constraint that at least one of each type of a machine will be assigned to any cell. Otherwise it would be impossible to do some operations on some of the parts. I Xjk >1 for all j (10) k Model 1 is applied to a manufacturing system including 10 machine and 25 different parts. The required information can be obtained from Table 5.1 and Table 5.2. The cost of an inter-cell movement is supposed TL 500.000. The unit loading size for all parts is 5. The number of machines that can be assigned to a cell is limited to 6. Meanwhile the part families are formed by a heuristic based on tooling requirements. The results are presented in Table 5.3 and Table 5.4. As the conclusion if the proposed mathematical models presented in the thesis are applied to form machine-part families in large sized integrated flexible manufacturing systems, the layout will be more cost effective. Key Words : Group Technology, Integer Programming, Production Flow Line XVI

##### Açıklama

Tez (Yüksek Lisans) -- İstanbul Teknik Üniversitesi, Sosyal Bilimler Enstitüsü, 1997

##### Anahtar kelimeler

Doğrusal programlama,
Esnek üretim sistemleri,
Hücresel üretim,
Matematiksel modelleme,
Linear programming,
Flexible manufacturing systems,
Cellular manufacturing,
Mathematical modelling