研究生: |
簡尚彬 Shang-bin Chien |
---|---|
論文名稱: |
應用改良式基因演算法求解鋼筋裁切最佳化問題 Improved Constraint Handling in Optimization of Steel Bar Cutting Plan |
指導教授: |
楊亦東
I-Tung Yang |
口試委員: |
楊智斌
Jyh-Bin Yang 謝佑明 Y.M. Hsieh |
學位類別: |
碩士 Master |
系所名稱: |
工程學院 - 營建工程系 Department of Civil and Construction Engineering |
論文出版年: | 2009 |
畢業學年度: | 97 |
語文別: | 中文 |
論文頁數: | 110 |
中文關鍵詞: | 基因演算法 、鋼筋裁切 、限制式處理 、成本最佳化 |
外文關鍵詞: | Genetic Algorithm, Steel Bar Cutting, Constrained Handling, Cost Optimization |
相關次數: | 點閱:239 下載:10 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
長久以來,營造產業被視為台灣的主要發展工業。近年來,營造市場景氣不佳,多數的營造公司因成本控制沒有做好妥善的規劃,造成利潤不斷下滑。因此較為積極的公司,早將成本控制視為重要的一環。而隨著科技日新月異,在工程領域裡,期望藉由最佳化演算法技術的提升,使得成本管控更佳完善。
本研究規劃的目標為降低鋼筋裁切之總成本,亦即增加已使用原料鋼筋的剩料退回價值、與未使用的原料鋼筋退回價值,並減少裁切次數所花費的成本。
以往模式在求解過程中,常會遇到違背限制式的裁切計畫,而浪費計算資源。本研究首先提出改良式基因演算法以減少限制式之數目。為妥善處理不可行解,改良式基因演算法將鋼筋裁切之染色體的編碼方式進行改變,並提出二套鋼筋裁切問題的求解模式,第一套模式則以前測式迴圈持續搜尋可行解;第二套模式中以懲罰值策略處理不可行解。兩套模式皆採用競爭式選擇理論。為驗證求解品質與效率,提出之演算法針對實際案例進行測試。結果證明提出之求解模式確實能夠正確且更有效率的求解出品質良好的裁切計畫。且在有限的時間內,求得最佳的解,節省人力資源,提升工程品質,滿足施工作業需求。
For many years, the construction industry has been regarded as one of the main developed industries in Taiwan. Since the construction market has been under recession in recent years, many construction companies face a decrease in profit due to not well-planned cost control. Therefore, contractors have seen the cost control as an important task. As the technology changes day by day, it is desired that the cost control may be improved using advanced optimization techniques.
The purpose of this research is to minimize the total cost of cutting steel bar, in other words, to increase the return value of used and unused raw steel bar, and reduce the cost by cutting frequency reduction.
For existing of the past algorithms , a cutting plan that violates the constraints was often encountered, and this resulted in waste of calculation resources. An improved Genetic Algorithm was firstly presented in this research so as to minimize the number of constraints. In order to handle infeasible solutions properly, the coded system of chromosome of steel bar cutting will be changed, and two models of solutions of cutting steel bar will also be brought up in this research. One model is to continuously search until the feasible solutions are found, and the other one is to apply the penalty strategy to handle the non-feasible solutions. Both models adopted the theory of tournament selection. As to verify the quality and efficiency of the solutions, the proposed models were tested in practical cases, and the results indicated that they are able to produce good cutting plans correctly and efficiently. Moreover, the models are also able to meet the requirements of construction operations because they generate the best solutions within the time constraints, and then retrench the human resource and upgrade the construction quality.
1.楊秉蒼,「營建鋼筋裁切規劃系統實作與應用」,詹氏書局,高雄(2002)。
2.楊秉蒼,「營建管理科學」,詹氏書局,高雄(2003)。
3.李之源,「應用基因演算法進行背壓式汽電共生廠電力代輸之經濟調度」,中原大學電機工程系,中壢(2000)。
4.吳昭慧、張鎮盛,「鋼筋混凝土」,全華科技圖書,中壢(2001)。
5.楊世清,「營建管理技術手冊」,地景出版社,台北(2000年)。
6.沈宇晟,「鋼筋裁切問題之啟發式解法」,國立成功大學土木工程研究所碩士論文,台南(2005)。
7.張瀚文,「鋼筋裁切順序最佳化模式」,國立成功大學土木工程研究所碩士論文,台南(2005)。
8.李冠廷,「質群演算法運用於鋼筋裁切問題之研究」,淡江大學土木工程研究所碩士班論文,台北(2007)。
9.施欣宜,「改良式基因演算法求解複雜限制式之組裝規劃探討」,大葉大學工業工程與科技管理學研究所碩士班論文,彰化(2004)。
10.張浚銘,「改良式基因演算法求解複雜限制式之組裝規劃探討」,大葉大學工業工程與科技管理學研究所碩士班論文,彰化(2004)。
11.蔡英豪,「用基因演算法探討熱交換器設計之研究」,大葉大學機械工程系碩士班碩士論文,彰化(2006)。
12.汪書帆,「基因演算法於預鑄工廠排程最佳化之研究」,大葉大學工業工程與科技管理學研究所碩士班論文,彰化(2006)。
13.鄭文忠,「基因演算法在被動式減振設計的最佳化研究」,大葉大學機電自動化研究所碩士班論文,彰化(2008)。
14.工商時報,http://www.yi123.com.tw/forum_37827.html,(2009)。
15.經濟部標準檢驗局,http://www.bsmi.gov.tw/page/pagetype8_sub.jsp?pageno=635&groupid=26&no=185&type_no=0,(2007/3/26摘錄)。
16.http://140.114.42.11/job/campintro/company/007/960308a.html,經濟日報(2007)。
17.http://udn.com/NEWS/notfound_BIG5.html聯合晚報(2007)。
18.胡曉輝,「粒子群優化算法介紹」,
http://icdweb.cc.purdue.edu/~hux,(2002)。
19.單明楊、楊秉蒼,「不同進貨模式對營建鋼筋殘料生成影響之研究」,第六屆營建工程與管理研究成果聯合發表會,(1998)。
20.楊秉蒼、呂淑鈴、葉怡成,「最適鋼筋裁切問題之研究」,第九屆大地工程學術研討會論文集,(2001)。
21.Michalewicz, ``Genetic algorithms + data structures = evolution program'', Springer, (1996)。
22.Gilmore,P.C., and Gomory, R.E., “A Linear Programming approach to the cutting stock problem,” Operational Research, Vol. 9, pp. 849-859 (1961).
23.Dyckhoff, H., “A typology of cutting and packing problems,” European Journal of Operational Research, Vol. 44, pp. 145-159 (1990).
24.Schilling, G., and Georgiadis, M.C., “An algorithm for the determination of optimal cutting patterns,” Computers and Operations Research, Vol.29,No.8,pp.1041-1058(2002).
25.Eberhart, R.C. and Kennedy, J.“A new optimizer using particle swarm theory. Proc. Sixth International Symposium on Micro Machine and Human Science”, Nagoya, Japan, pp.39-43. (1995)
26.Shi, Y. and R. Eberhart ,”A modified Particle Swarm Optimizer,” IEEE International Conference on Evolutionary Computation, May 1998, Anchorage,Alaska,USA.(1998).
27.Shi, Y. and R. Eberhart ,”Particle swarm optimization: developments applications and resources,”Proc. IEEE Int.conf.On Evolutionary Computation, pp.81-86.(2001).
28.Eberhart R. C. and Shi Y. “Comparison between genetic algorithms and particle swarm optimization, ” Evolutionary Programming VII: The 7th Ann. Conf. on Evolutionary Programming, pp.181-184(1998).
29.Shi, Y. and Eberhart R., ”Parameter selection in particle swarm optimization,” Evolutionary Programming VII: Proc. EP 98 pp.591-600.Springer-Verlag, New York(1998).
30.Deb, K.. An efficient constraint handling method for genetic algorithms(2000).
31.Schmitt, L. M. Fundamental Study Theory of genetic algorithms(2001).
32.Mitra, K. and Gopinath, R. Multiobjective optimization of an industrial grinding operation using elitist nondominated sorting genetic algorithm(2004).