Applying Metaheuristics in the Generalized Cell Formation Problem Considering Machine Reliability

應用通用啓發式演算法於考慮機器可靠度之一般化單元形成問題

10.29977/JCIIE.200807.0001

Mohammad Saeed Jabalameli；Jamal Arkat；Morad Shoresh Sakri

單元形成 ； 可替代的途程路徑 ； 機器可靠度 ； 記憶式演算法 ； 基因演算法 ； 模擬退火法 ； Cell Formation ； Alternative Process Routings ； Machines Reliability ； Memetic Algorithm ； Genetic Algorithm ； Simulated Annealing

工業工程學刊

25卷4期（2008 / 07 / 01）

261 - 274

英文

機器是單元製造系統中主要元件。通常，它要快速處理因應生產需要的機器停工是極爲困難的。因此，可靠度對於單元製造系統的整理績效扮演一個重要的角色。我們呈現一個具有可替代的途程路徑和機器可靠度考量的單元形成問題之數學模型並建議之嘗試同時考慮極小化單元間的移動成本及極大化製造系統的可靠度。除此之外，我們發展出三種稱爲模擬退火法、基因演算法和記憶式演算法的通用啟發式演算法來求解這個問題。我們使用了一些數學範例，並應用一種稱爲分支界限化的最佳化演算法來比較所發展的演算法之效率。結果顯示，與分支界限法相比較，所發展出來的通用啟發式演算法可以使用較少的計算時間，並得到不錯的目標函數值。

Machines are the major component of the cellular manufacturing systems (CMS). Usually, it is difficult to handle machine breakdowns as quickly as the production requirement dictates and therefore, the reliability consideration plays an important role in the overall performance of the CMS. We present a mathematical model of the cell formation problem with alternative process routings (APR) and machine reliability consideration. The proposed model tries to simultaneously minimize the intercellular movement costs and to maximize the reliability of the manufacturing system. In addition, we develop three sets of metaheuristics, namely simulated annealing, genetic algorithm and memetic algorithm to solve the proposed model. Using some numerical examples, we compare the performance of the proposed algorithms with an optimum algorithm, namely the branch and bound algorithm. The results show that in comparison with the branch and bound algorithm, the proposed metaheuristics can obtain better objective function values in less computational time.

1. Adil, G. K.,D. Rajamani,D. Strong(1996).Cell formation considering alternate routings.International Journal of Production Research,34,1361-1380.
2. Agarwal, A.,J. A. Sarkis(1998).Review and analysis of comparative performance studies of functional and cellular manufacturing layouts.Computers and Industrial Engineering,34,77-89.
3. Akturk, M. S.(1996).A note on the whiten-cell layout problem based on operation sequences.Production Planning & Control,7,99-103.
4. Arkat, J.,M. Saidi,B. Abbasi(2006).Applying simulated annealing to cellular manufacturing system design.International Journal of Advanced Manufacturing Technology,32,531-536.
5. Askin, R. G.,S. Estrada,S. A. Irani (eds)(1999).Handbook of Cellular Manufacturing Systems.New York:John Wiley.
6. Boughton, N. J.,I. C. Arokiam(2000).The application of the cellular manufacturing: a regional small to medium enterprise perspective.Proceedings of the Institution of the Mechanical Engineers,214,751-754.
7. Caux, C.,R. Bruniaux,H. Pierreval(2000).Cell formation with alternative process plans and machine capacity constraints: a new combined approach.International Journal of Production Economics,64,279-284.
8. Cerny, V.(1985).A thermodynamical approach to the travelling salesman problem: an efficient simulation algorithm.Journal of Optimization Theory and Applications,45,41-51.
9. Choobineh, F. A.(1988).Framework for the design of cellular manufacturing systems.International Journal of Production Research,26,1161-1172.
10. Das, K.,R. S. Lashkari,S. Sengupta(2005).Reliability consideration in the design and analysis of cellular manufacturing systems.International Journal of Production Economics,105,243-262.
11. Dawkins, R.(1976).The Selfish Gene.Oxford:Clarendon Press.
12. Diaz, B. A.,S. Lozano,J. Racero,F. Guerrero(2001).Machine cell formation in generalized group technology.Computers and Industrial Engineering,41,227-240.
13. Eid Moussa, S.,M. Kamel(1998).A part-machine assignment algorithm for cellular manufacturing with machine capacity constraints.Computers and Industrial Engineering,35,483-486.
14. Felix, T. S. C.,K. W. Lau,P. L. Y. Chan,K. L. Choy(2006).Two-stage approach for machine-part grouping and cell layout problems.Robotics and Computer Integrated Manufacturing,22,217-238.
15. Ferreira Ribeiro, J. F.,B. Pradin(1993).A methodology for cellular manufacturing design.International Journal of Production Research,31,235-250.
16. Flynn, B. B.,F. R. Jacobs(1986).A simulation comparison of group technology with traditional job shop manufacturing.International Journal of Production Research,24,1171-1192.
17. Goldberg, D. E(2002).The Design of Innovation: Lessons from and for Competent Genetic Algorithms.Reading, MA:Addison-Wesley.
18. Goldberg, D. E.(1989).Genetic Algorithms in Search, Optimization and Machine Learning.Boston, MA:Kluwer Academic.
19. Gupta T.,H. Seifoddini(1990).Production data based similarity coefficient for machine-component grouping decision in the design of a cellular manufacturing system.International Journal of Production Research,28,1247-1269.
20. Gupta, T.(1993).Design of manufacturing cells for flexible environment considering alternative routings.International Journal of Production Research,31,1259-1273.
21. Hwang, H.,P. Ree(1996).Routes selection for the cell formation problem with alternative part process plans.Computers and Industrial Engineering,30,423-431.
22. Jayakrishnan Nair, G.,T. T. Narendran(1998).CASE: a clustering algorithm for cell formation with sequence data.International Journal of Production Research,36,157-179.
23. Jayakrishnan Nair, G.,T. T. Narendran(1999).ACCORD: a bicriterion algorithm for cell formation using ordinal and ratio-level data.International Journal of Production Research,37,539-556.
24. Kazerooni, M.,H. S. Luong,K. Abhary(1997).A genetic algorithm based cell design considering alternative routing.Computer Integrated Manufacturing System,10,93-107.
25. Kim, C. O.,J. G. Baek,J. K. Baek(2004).A two-phase heuristic algorithm for cell formation problems considering alternative part routes and machine sequences.International Journal of Production Research,42,3911-3927.
26. Kirkpatrick, S.,C. D. Gelatt,M. P. Vecchi(1983).Optimization by Simulated Annealing.Science,220,671-680.
27. Kitaoka, M.,R. Nakamura,S. Serizawa,J. Usuki(1999).Multivariate analysis model for machine-part cell formation problem in group technology.International Journal of Production Economics,60,433-438.
28. Kusiak, A.(1987).The generalized group technology concept.International Journal of Production Research,25,561-569.
29. Logendran, R.,D. Talkington(1997).Analysis of cellular and functional manufacturing systems in the presence of machine breakdown.International Journal of Production Economics,53,239-256.
30. Lozano, S.,F. Guerrero,I. Eguia,L. Onieva(1999).Cell design and loading in the presence of alternative routing.International Journal of Production Research,37,3289-3304.
31. Morris, S. J.,R. J. Tersine(1990).A simulation analysis of factors influencing the attractiveness of group technology cellular layouts.Management Science,36,1567-1578.
32. Nagi, R.,G. Harhalakis,J. M. Proth(1990).Multiple routings and capacity considerations in group technology application.International Journal of Production Research,28,2243-2257.
33. Pablo Moscato.(2001).Brazil,Universidade Estadual de Campinas.
34. Reisman, A.,A. Kumar,J. Motwani,C. Cheng(1997).Cellular manufacturing: a statistical review of the literature.Operations Research,45,508-520.
35. Sarker, B. R.,Y. Xu(2000).Designing multi-product lines: job routing in cellular manufacturing systems.IIE Transactions,32,219-235.
36. Sarker, B. R.,Z. Li(1998).Measuring matrix-based cell formation with alternative routings.Journal of Operational Research Society,49,953-965.
37. Selim, H. M.,R. G. Askin,A. J. Vakharia(1998).Cell formation in group technology: review evaluation and directions for future research.Computers and Industrial Engineering,34,3-20.
38. Sofianopoulou, S.(1999).Manufacturing cells design with alternative process plans and or replicate machines.International Journal of Production Research,37,707-720.
39. Steudel, H. J.,A. Ballakur(1987).A dynamic programming based heuristic for machine grouping in manufacturing cell formation.Computers and Industrial Engineering,12,215-222.
40. Sule, D. R.(1991).Machine capacity planning in group technology.International Journal of Production Research,29,1909-1922.
41. Suresh, N. C.,J. R. Meredith(1994).Coping with the Loss of pooling synergy in cellular manufacturing Systems.Management Science,40,466-483.
42. Venugopal, V.,T. T. Narendran(1992).A genetic algorithm approach to the machine-component grouping problem with multiple objectives.Computers and Industrial Engineering,22,469-480.
43. Waghodekar, P. H.,S. Sahu(1984).Machine-component cell formation in group technology: MACE.International Journal of Production Research,22,937-948.
44. Wemmerlov, U.,N. L. Hyer(1986).Procedures for the part family/machine group identification problem in cellular manufacturing.Journal of Operations Management,6,125-147.
45. Wemmerlov, U.,N. L. Hyer(1989).Cellular manufacturing in the U.S. industry: a survey of users.International Journal of Production Research,27,1511-1530.
46. Won, Y.(2000).New p-median approach to cell formation with alternative process plans.International Journal of Production Research,38,229-240.
47. Yin, Y.,K. Yasuda(2005).Similarity coefficient methods applied to the cell formation problem: a taxonomy and review.International Journal of Production Economics,101,329-352.
48. Yin, Y.,K. Yasuda,L. Hu(2005).Formation of manufacturing cells based on material flows.International Journal of Advanced Manufacturing Technology,27,159-165.
49. Zakarian, A.,A. Kusiak(1997).Modeling manufacturing dependability.IEEE Transactions on Robotics and Automation,13,161-168.
50. Zhao, C.,Z. A. Wu(2000).Genetic algorithm for manufacturing cell formation with multiple routes and multiple objectives.International Journal of Production Research,38,385-395.