跳到主要內容

臺灣博碩士論文加值系統

(100.28.231.85) 您好!臺灣時間:2024/11/06 15:31
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:張緯強
研究生(外文):Chang,Weichieng
論文名稱:結合單元形成之開放型排程問題研究
論文名稱(外文):An Approach of Combination for Cell Forming and Open Shop Scheduling Problem
指導教授:駱景堯駱景堯引用關係
指導教授(外文):Low,Ghinyao
學位類別:碩士
校院名稱:大葉大學
系所名稱:工業工程與科技管理學系
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2006
畢業學年度:94
語文別:中文
論文頁數:137
中文關鍵詞:群組技術開放型排程群組效率基因演算法
外文關鍵詞:group technologyopen shop schedulinggrouping efficacygenetic algorithm
相關次數:
  • 被引用被引用:1
  • 點閱點閱:169
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
近幾年,如何在競爭激烈的製造業環境中脫穎而出,客製化與低成本的生產流程儼然而成為最受矚目的焦點。群組技術更是在現行生產需求上越來越受到重視的一環,其目的可達成生產型態上精簡且符合低成本的實務應用。且勢必需將關鍵的群組技術後之結果,與生產排程的思考邏輯相互結合,這樣的整體思考架構才算漸趨完備,而在現今的研究領域上似乎在相關兩者結合的議題上,並無相互結合的應用,往往只是對單一領域提出研究而已。
本研究旨在將單元形成與其對應的生產排程問題,做一系統性的研究探討,針對兩者利用基因演算法觀念開發一啟發式演算法求解相關問題,尤其在分群效應與開放性排程的例外單元處理問題上,加以改善其求解品質,皆可獲得不錯的成效。
Recently, the method that how to be superior in the competitive manufacturing industry environments obsiously focuses on the processes of “Customization” and “Low Cost”. The concept of “Group Technology” is also more the production procedures and more important in modern productive demands, because it can simplify and reduce cost in the manufacturing industry. On the other hand, the whole framework must be gradually completed by combing the result of “Group Technology” to the thinking logic of “Product Scheduling”. But until now, the present research doesn’t combine or apply these issues yet, because they just study in every single realm.
Therefore, this research is to explore a series of problem form cell forming and its corresponding productive procedures. I solute some related problems from taking advantage of genetic algorithm and heuristic algorithm; especially improve its quality and get good result of the exceptant cell formation problem in the realm of group effect and open shop scheduling.
封面內頁
簽名頁
授權書 iii
中文摘要 vi
ABSTRACT vi
誌 謝 vii
目 錄 viii
圖目錄 xi
表目錄 xiii
第一章 緒論 1
1.1 研究動機與目的 1
1.2 研究範圍及假設 4
1.3 研究方法及流程 6
第二章 文獻探討 9
2.1 單元製造系統問題方面 9
2.1.1 早期文獻探討 9
2.1.2 近期文獻探討 11
2.1.3 單元製造系統 16
2.2 開放型排程問題方面 23
2.2.1 早期文獻探討 23
2.2.2 近期文獻探討 24
2.3 基因演算法(Genetic Algorithms) 25
第三章 標準單元形成問題之求解 32
3.1 標準單元形成問題演算法介紹 32
3.1.1 標準單元形成問題演算法之建立 33
3.2 零件分派問題起始解 35
3.3 自動切割群組觀念 38
3.4 機器分派問題的啟發式解 39
3.5 區域搜尋改善階段(零件移步法) 44
第四章 開放型排程問題之求解 47
4.1 考量開放型排程問題之演算法介紹 47
4.2 OSP問題之編碼方式 48
4.3 處理OSP之基因演算法 49
4.3.1 編碼(Encoding) 50
4.3.2 初始族群(Initial Population) 51
4.3.3 適合度函數(Fitness Function) 52
4.3.4 複製(Reproduction) 53
4.3.5 交配(Crossover) 54
4.3.6 突變(Mutation) 56
4.4 例外加工元素的處理 57
4.5 單元形成後之開放型排程演算範例說明 58
4.5.1 產生初始母體 60
4.5.2 主架構基因演算法結果 61
第五章 演算結果與分析 64
5.1 標準單元形成問題測試例題 64
5.2 標準單元形成問題演算法參數選擇、結果和比較 66
5.3 開放型排程問題測試例題 69
5.3.1 開放型排程資料之產生與選擇參數之說明 69
5.3.2 演算結果分析 70
5.3.3 各種問題規模下之分析 71
第六章 結論與建議 79
6.1 結論 79
6.2 建議 80
參考文獻 82
附錄一 各開放型排程問題規模下之ANOVA求解品質分析表 90
附錄二 各問題模式下與各因子水準間之完工時間求解品質關係圖 106
附錄三 各問題模式下與各因子水準間之延遲時間求解品質關係圖 114
[1]許惇旭,民國86年,結合禁忌搜尋法(TS)與模擬退火法(SA)在彈性製造系統(FMS)排程之應用,大葉大學碩士學位論文。
[2]吳佳璋,民國86年,禁忌搜尋法在彈性製造系統排程問題之應用,大葉大學碩士學位論文。
[3]呂紹煌,民國88年,以塔布搜尋法求解開放工廠排程問題,朝陽大學碩士學位論文。
[4]吳文田,民國89年,製造單元形成問題解法之研究,大葉大學碩士學位論文。
[5]賴彥銘,民國89年,應用群聚技術求解製造單元形成問題,大葉大學碩士學位論文。
[6]林安祥,民國89年,開放工廠加權延遲最小化排程問題之研究,朝陽大學碩士學位論文。
[7]賴崇瑋,民國90,二機開放工廠具有工作連接性限制之排程演算法效率比較,東海大學碩士學位論文。
[8]駱芳梧,民國91年,以考量整備及拆卸時間之開放型工廠排程問題研究,大葉大學碩士學位論文。
[9]李師尹,民國91年,應用基因演算法於求解模糊環境下之單元製造系統問題,大葉大學碩士學位論文。
[10]尤冠斌,民國92年,混合基因演算法於開放型排程問題探討,大葉大學碩士學位論文。

[11]楊鎰銘,「製造單元形成之啟發式求解研究」,大葉大學碩士學位論文,民國93年。
[12]Achugbue, J.O., and Chin, F.Y., 1982, “Scheduling the open shop to minimize mean flow time,”SIAMJ. Comput., 11, pp.709-720.
[13]Adam, S., 2006, “Evolutionary strategy for manufacturing cell design ,”Omega., 34, pp.1-18.
[14]Ankerst, M., Breuning M., Kriegel H.P., and Sander J., 1999, “OPTICS:Ordering point to identify the clustering structure,” In Proc. 1999 ACM-SIGMOD Int. Conf.Management of Data(SIGMOD’99), pp.49-66, Philadelphia, PA.
[15]Askin, R.G., Cresswell, S.H., Goldberg, J.B., and Vakharia, A.J., 1991, “A Hamiltonian path approach to reordering the part-machine matrix for cellular manufacturing,” International Journal of Production Research, 29, pp.1081-1100.
[16]Askin, R.G., and Subramanian, S., 1987, “A cost-based heuristic for group technology configuration.” International Journal of Production Research, 25, pp.101–113.
[17]Asoo, J.Vakharia., and Urban, Wemmerlőv., 1995, “A comparative investigation of hierarchical clustering techniques and dissimilarity measures applied to the cell formation problem,” Joumal of Operations Management 13, pp.117-138.
[18]Balakrishnan, J., and Jog, P.D., 1995, “Manufacturing cell formation using similarity coefficients and a parallel genetic TSP algorithm formulation and comparison,” Mathematical & Computer Modeling, 21, pp.61-73.
[19]Boctor, F., 1991, “A linear formulation of the machine-part cell formation problem.” International Journal of Production Research, 29(2), pp.343-356.
[20]Boe, W., and Cheng, C.H., 1991, “A close neighbor algorithm for designing cellular manufacturing systems.” International Journal of Production Research, 29(10), pp.2097–2116.
[21]Chan, F.T.S., Mak, K.L., Luong, L.H.S., and Ming, X.G., 1998, “Machine-component grouping using genetic algorithm,” Robotics & Computer-Integrated Manufacturing, 14, pp.339-346.
[22]Chan, H.M., and Milner, D.A., 1982, “Direct clustering algorithm for group formation in cellular manufacture.” Journal of Manufacturing System, 1, pp.65–75.
[23]Carrie, S., 1973, “Numerical taxonomy applied to group technology and plant layout.” International Journal of Production Research, 11, pp.399–416.
[24]Chandrashekharan, M.P., and Rajagopalan, R., 1986a, “An ideal seed non-hierarchical clustering algorithm for cellular manufacturing.” International Journal of Production Research, 24(2), pp.451–464.
[25]Chandrashekharan, M.P., and Rajagopalan, R., 1986b, “MODROC: An extension of rank order clustering for group technology.” International Journal of Production Research, 24(5), 1221–1233.
[26]Chandrasekharan, M.P., and Rajagopalan, R., 1987, “ZODIAC-an algorithm for concurrent formation of part-families and machine-cells,” International Journal of Production Research, 25, pp.835-850.
[27]Chandrasekharan, M.P., and Rajagopalan, R., 1989, “GROUPABILITY:an analysis of the properties of binary data matrices for group technology,” International Journal of Production Research, 27, pp.1035-1052.
[28]Cheng, C.H., Gupta, Y.P., Lee, W.H., and Wong, K.F., 1998, “A TSP-based heuristic for forming machine groups and part families,” International Journal of Production Research, 36, pp.1325-1337.
[29]Cheng, C.H., Goh, C.H., and Lee, A., 2001, “Design group technology manufacturing systems using heuristics branching rules,” Computers & Industrial Engineering, 40, pp.117-131.
[30]Ester, M., Kriegle, H.P., Sander, J., and Xu., 1996, “Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise,” In Proc. 1996 Int. conf. Knowledge Discovery and Data Mining(KDD’96), pp.226-231, Portland, OR, Aug.
[31]Felix, T.S.Chan., Lau, K.W., Chan, P.L.Y., and Choy K.L., 2006, “Two-stage approach for machine-part grouping and cell layout problems,” Robotics and Computer-Integrated Manufacturing, 22, pp.217-238.
[32]Gonzalez, T., and Sahni, S., 1976, “Open shop scheduling to minimize finish time,” Journal of The Association for Computing Machinery, 23(4), pp.665-679.
[33]Gonçalves, José.Fernando., Resende Mauricio.G.C., 2004, “An evolutionary algorithm for manufacturing cell formation,” Compuers & Industrial Engineering, 47, pp.247-273.
[34]Gursel, A.Suer., and Angel, A.Cede o., 1996, “A Configuration-Based Clustering Algorithm For Family Formation,” Computers ind. Engen Vol. 31. No.1/2 pp.147-150.
[35]Harhalakis, G., Nagi R., and Proth, J.M., 1990, “An efficient heuristic in manufacturing cell formation for group technology applications,” Int J. Prod. Res., Vol. 28, no. 1, pp.185-198.
[36]Han, J., and Kamber, M., 2000, “Data Mining:Concepts and Techniques,”Morgan Kaufmann.
[37]Hiroshi, Ohta., Masaeru, Nakamura., 2002, “Cell formation with reduction in setup time,” Compuers & Industrial Engineering, 42, pp.317-327.
[38]Kaufam, L., and Rousseeuw, P.J., 1990, “Finding Groups in Data:an Introduction to Cluster Analysis,” John Wiley & Sons.
[39]Kitaoka, M., Nakamura, R., Serizawa, S., and Usuki, J., 1999, “Multivariate analysis model for machine-part cell formation problem ingroup technology,” International Journal of Production Economics, 60-61, pp.433-438.
[40]King, J.R., 1980, “Machine-component grouping in production flow analysis: An approach using a rank order clustering algorithm.” International Journal of Production Research, 18(2), pp.213–232.
[41]King, J.R., and Nakornchai, V., 1982, “Machine-component group formation in group technology: Review and extension.” International Journal of Production Research, 20(2), pp.117–133.
[42]Kumar, C.S., and Chandrasekharan, M.P., 1990, “Grouping efficacy: a quantitative criterion for goodness of block diagonal forms of binary matrices in group technology,” International Journal of Production Research, 28, pp.233-243.
[43]Kumar, K.R., Kusiak, A., and Vannelli, A., 1986, “Grouping of parts and components in flexible manufacturing systems.” European Journal of Operations Research, 24, pp.387–397.
[44]Kumar, K.R., and Vannelli, A., 1987, “Strategic subcontracting for efficient disaggregated manufacturing.” International Journal of Production Research, 25(12), pp.1715–17281.
[45]Kusiak, A., and Cho, M., 1992, “A sililarity coefficient algorithms for solving the group technology problem,” International Journal of Production Research, 30, pp.2633-2646.
[46]Kusiak, A., and Chow, W., 1987, “Efficient solving of the group technology problem.” Journal of Manufacturing Systems, 6(2), pp.117–124.
[47]Kyparisis, G.J., and Koulamas, C., 2000, “Open shop scheduling with makespan and total completion time criteria,” Computers & Operations Research, 27(1), pp.15-27.
[48]Liang, M., and Zolfaghri, S., 1999, “Machine cell formation considering processing times and machine capacities: an ortho-synapse Hopfield neural network approach,” Journal of Intelligent Manufacturing, 10, pp.437-477.
[49]Liaw, C., 1999, “An iterative improvement approach for the nonpreemptive open shop scheduling problem,” European Journal of Operational Research, 111(3), pp.509-517.
[50]Liaw, C., 1999, “A tabu search algorithm for the open shop scheduling problem,” Computers & Operations Research, 262(2), pp.109-126.
[51]Liaw, C., 2000, “A hybrid genetic algorithm for the open shop scheduling problem,” European Journal of Operational Research, 124(1), pp.28-42.
[52]Lin, H.F., Liu, C.Y., and Liu, P.Y., 1995, “A heuristics approach to the total tardiness in nonpreemptive open shop scheduling, ” International Journal of Industrial Engineering, 2(1), pp.25-33.
[53]Lin, H.F., 1995, “A heuristics solution to the total tardiness and earliness penalties of an m-machine nonpreemptive scheduling,” Journal of The Chinese Institue of Industrial Engineering, 15(2), pp.159-167.
[54]Lin, H.F., 1995, “A heuristic solution to the total tardy cost of an machine non-preemptive open shop scheduling,” Sun Yat Sen Management Review, 3(4), pp.122-143.
[55]MacQueen, J., 1967, “Some Methods for Classification and Analysis of Multivariate Observation,” In Proc. 5 Berkeley Symp. Math Stat. and Prob., Vol 1, pp.281-297.
[56]Mak, K.L., Wong, Y.S., and Wang, X.X., 2000, “An adaptive genetic algorithm for manufacturing cell formation,” International Journal of Advanced Manufacturing Technology, 16, pp.491-497.
[57]Menouar, B., and Karim, A., 2006, “A new branch-&-bound-enhanced genetic algorithm for the manufacturing cell formation roblem,” Computers & Operations Research, 33, pp.2219-2245.
[58]Mosier, C.T., and Taube, L., 1985a, “The facets of group technology and their impact on implementation,” OMEGA, 13(6), pp.381–391.
[59]McCormick, W.T., Schweitzer, P.J., and White, T.W., 1972, “Problem decomposition and data reorganization by a clustering technique.” Operations Research, 20, pp.993-1009.
[60]Nair, G.J., and Narendran, T.T., 1997, “Cluster goodness: a new measure of performance for cluster formation in design of cellular manufacturing system,” International Journal of Production Economics, 48, pp.49-61.
[61]Onwubolu, G.C., and Songore, V., 2000, “A tabu search approach to cellular manufacturing systems,” Production Planning & Control, 11, pp.153-164.
[62]Onwubulo, G.C., and Mutingi, M., 2001, “A genetic algorithm approach to cellular manufacturing systems,” Computers & Industrial Engineering, 39, pp.125-144.
[63]Pinedo, M., 1995, Scheduling: Theory, Algorithm and Systems, Prentice-Hall, Englewood Cliffs, NJ.
[64]Sarker, B.R., 2001, “Measure of grouping efficiency in cellular manufacturing systems,” European Journal of Operational Research, 130, pp.588-611.
[65]Seifoddini, H., and Wolfe, P.M., 1989, “Application of the similarity coefficient method in group technology.” IIE Transactions, 18, 3, pp.266-270.
[66]Seifoddini, H., 1989, “Single linkage versus average linkage clustering in machine cells formation applications.” Computers and Industrial Engineering, 16(3), pp.419–426.
[67]Srinivasan, G., Narendran, T., and Mahadevan, B., 1990, “An assignment model for the part-families problem in group technology.” International Journal of Production Research, 28, pp.145–152.
[68]Stanfel, L., 1985, “Machine clustering for economic production.” Engineering Costs and Production Economics, pp.73-89.
[69]Vila, Gonçalves.Filho., Eduardó, José.Tiberti., Alexandre., 2006, “A group genetic algorithm for the machine cell formation problem,” International Journal of Production Economics, 102, pp.1–21.
[70]Waghodekar, P.H., and Sahu, S., 1984, “Machine-component cell formation in group technology MACE.” International Journal of Production Research 22, pp.937-948.
[71]Wemmerlov, U., and Hyer, N.L., 1987, “Research issues in Cellular Manufacturing,”International Journal of Production Research, 25, pp.413-431.
[72]Yasuda, K., and Yin, Y., 2001, “A dissimilarity measure for solving the cell formation problem in cellular manufacturing,” Computer & Industrial Engineering, 39, pp.1-17.
[73]Zahir, A., Hamdi, A., and Mingyuan, C., 2005, “A mathematical approach for the formation of manufacturing cells,” Computer & Industrial Engineering, 48, pp.3-12.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top