進階搜尋


 
系統識別號 U0026-0812200915102971
論文名稱(中文) 應用塔布基因演算法於扣件產業之多目標生產排程研究
論文名稱(英文) A Multi-objective Tabu-Genetic Algorithm applied to Scheduling Problems of Fastener Industry
校院名稱 成功大學
系所名稱(中) 工業與資訊管理學系專班
系所名稱(英) Department of Industrial and Information Management (on the job class)
學年度 97
學期 2
出版年 98
研究生(中文) 莊政霖
研究生(英文) Cheng-lin Chuang
學號 r3796118
學位類別 碩士
語文別 中文
論文頁數 133頁
口試委員 指導教授-李昇暾
口試委員-耿伯文
口試委員-林清河
口試委員-葉榮懋
中文關鍵字 田口方法  禁忌搜尋  螺帽扣件產業  基因演算法  多目標排程 
英文關鍵字 Genetic algorithm  Taguchi Method  Tabu search  Fastener industry  multi-object scheduling 
學科別分類
中文摘要 台灣素有「螺絲螺帽王國」之美譽,在2007年扣件總產值達1,076億元創下歷史新高,總產量有141萬公噸;於2008年第一季之扣件產值達247億元[43],在有如此龐大的產值及產量狀況下,思考其中要如何精益求精提昇該產業之競爭力,故需要倚靠多年來的生產經驗尋求更好的生產產能規劃,才能使生產效率持續提高,提昇整體產業發展能力,進而增加台灣在國際的競爭力。
本研究針對螺絲螺帽扣件產業中之成型製程進行排程研究,期望能改善原有排程規劃的方式,增加現有機台產量並降低機台採購成本,該製程生產機台為多部非等效平行機台(Unrelated Parallel Machine)排程,這類生產排程問題是一種非線性NP問題,而在實際生產排程問題皆非單一目標即可滿足,故本研究亦將多目標的概念納入其中,並使用基因演算法(Genetic Algorithm),輔以塔布搜尋法(Tabu Search)[18]減化重複相同取樣步驟來增加求解效率,其中利用適性函數(fitness function)針對多目標因子制定出一套適合的架構,以期能找出最適合解,本研究將此架構稱之為MOTGA(多目標塔布基因演算法)。本研究透過實驗,以最小化總工作時間(minimize makespan)及最小化機台成本(minimize mach cost)為目標,尋求較佳解,並在實驗中以田口方法(Taguchi Method)找出演算法中之最佳參數組合,以此建構一套生產排程系統來改善扣件產業之生產排程問題。
英文摘要 In recently Taiwan is famous for fastener industry in the world. In 2007,fastenter production values is up to 107.6 millions dollars, and production is up to 1410 thousands tons. In the first quarter of 2008,fastener production values is up to 24.7 millions dollars. Because it have so much production values and productions, we must think how to improve this industry. We need to find better production plans by many years experience, and let this industry to increase production efficiency, help it to improve industry ability and increase competition ability in the world.
This paper make a study of forming step in the nut and bolt fastener industry. It could improve original scheduling method to increase machine production and lower machine cost. This scheduling problems is a Unrelated Parallel Machine schedule and belongs to a non-linear NP-completed problem. In the actuality, scheduling problems have not only single objective, so this paper study multi objectives. This paper use Genetic algorithm with Tabu search to reduce evolution of repeated step and increase the solution efficiency. This algorithm use fitness function to design a multi objective structure and call it is MOTGA. In this paper finds the best solution to solve minimize make-span and minimize minimize mach cost problems. We also use Taguchi Method to find best settings, and use it for algorithms to contruct a production scheduling system,so we would improve better on this industry scheduling problem.
論文目次 摘要 I
Abstract II
誌謝 III
目錄 IV
表目錄 V
圖目錄 VII
第一章 緒論 1
第一節 研究背景與動機 1
第二節 研究目的 4
第三節 研究架構 7
第二章 文獻探討 8
第一節 排程問題探討 8
第二節 多目標問題探討 15
第三節 啟發式演算法 18
第四節 塔布基因演算法探討 39
第三章 研究方法 44
第一節 問題定義 44
第二節 限制條件 47
第三節 求解步驟及系統架構 49
第四節 目標式及符號說明 52
第五節 演算式模型建構 58
第六節 田口方法參數設計 66
第四章 實驗結果 68
第一節 實驗設定 68
第二節 基因演算法參數實驗結果 70
第三節 塔布基因演算法參數實驗結果 80
第四節 各演算法實驗結果比較 90
第五節 田口實驗結果 95
第六節 田口穩健設計實驗結果 109
第五章 結論及未來展望 123
第一節 結論 123
第二節 未來展望 126
參考文獻 128
參考文獻 [1]. Amdahl, G.M., Validity of the single-processor approach to achieving large scale computing capabilities, Proc. AFIPS Conference: p. 483-485. 1967.
[2]. Holland, J.H., Adaptation in Natural and Artificial Systems University of Michigan Press, Ann Arbor 1975.
[3]. Glover, F., Tabu Search - Part I. ORSA Journal on Computing, No.1, 1: p. 190-196. 1989.
[4]. Glover, F., Tabu Search - Part II. ORSA Journal on Computing, No.3, 2: p. 4-32. 1990.
[5]. Parunak, H.V.D., Characterizing the manufacturing scheduling problem. Journal of Manufacturing Systems, 10(3): p. 241-259. 1991.
[6]. Fang, H.L., Genetic algorithm in timetabling and scheduling. Ph. D. Department of Artificial Intelligence, University of Edinburgh. 1994.
[7]. Michalewicz, Z., Genetic Algorithms + Data Structures = Evolution Programs. 1994.
[8]. Della Croce, F., Tadei, R., and Volta, G., A genetic algorithm for the job shop problem. Computers & Operations Research, 22(1): p. 15-24. 1995.
[9]. Glover, F., Kelly, J.P., and Laguna, M., Genetic algorithms and tabu search: Hybrids for optimization. Computers & Operations Research, 22(1): p. 111-134. 1995.
[10]. Dorigo, M. and Gambardella, L.M., Ant colonies for the traveling salesman problem. BioSystems, 43: p. 73-81. 1996.
[11]. Murata, T., Ishibuchi, H., and Tanaka, H., Multi-objective genetic algorithm and its applications to flowshop scheduling. Computers & Industrial Engineering, 30(4): p. 957-968. 1996.
[12]. Ben-Daya, M. and Al-Fawzan, M., A tabu search approach for the flow shop scheduling problem. European Journal of Operational Research, 109(1): p. 88-95. 1998.
[13]. Murata, T. and Ishibuchi, H., A multi-objective genetic local search algorithm and its application to flowshop scheduling. IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS, 28(3): p. 392-403. 1998.
[14]. Mantawy, A.H., Abdel-Magid, Y.L., and Selim, S.Z., A new genetic-based tabu search algorithm for unit commitment problem. Electric Power Systems Research, 49(2): p. 71-78. 1999.
[15]. Cicirello, V. and Smith, S., Modeling GA Performance for Control Parameter Optimization. GECCO-2000: Proceedings of the Genetic and Evolutionary Computation Conference. 2000.
[16]. Cavory, G., Dupas, R., and Goncalves, G., A genetic approach to the scheduling of preventive maintenance tasks on a single product manufacturing production line. International Journal of Production Economics, 74(1-3): p. 135-146. 2001.
[17]. Deb, K., Agrawal, S., Pratap, A., and Meyarivan, T., A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. on Evolutionary Computation, 6(2): p. 182-197. 2002.
[18]. Ting, C.K., Li, S.T., and Lee, C., On the harmonious mating strategy through tabu search. Information Sciences, 156(3-4): p. 189-214. 2003.
[19]. Kalinli, A. and Karaboga, D., Training recurrent neural networks by using parallel tabu search algorithm based on crossover operation. Engineering Applications of Artificial Intelligence, 17(5): p. 529-542. 2004.
[20]. Arroyo, J.E.C. and Armentano, V.A., Genetic local search for multi-objective flowshop scheduling problems. European Journal of Operational Research, 167(3): p. 717-738. 2005.
[21]. Pasupathy, T., Rajendran, C., and Suresh, R.K., A multi-objective genetic algorithm for scheduling in flow shops to minimize the makespan and total flow time of jobs. The International Journal of Advanced Manufacturing Technology, 27(7): p. 804-815. 2006.
[22]. Sun, J.U., A Taguchi Approach to Parameter Setting in a Genetic Algorithm for General Job Shop Scheduling Problem. IEMS, 6(2): p. 119-124. 2007.
[23]. Essafi, I., Mati, Y., and Stephane, D.P., A genetic local search algorithm for minimizing total weighted tardiness in the job-shop scheduling problem. Computers & Operations Research, 35(8): p. 2599-2616. 2008.
[24]. Vilcot, G. and Billaut, J.-C., A tabu search and a genetic algorithm for solving a bicriteria general job shop scheduling problem. European Journal of Operational Research, 190(2): p. 398-411. 2008.
[25]. Manikas, A. and Chang, Y.-L., Multi-criteria sequence-dependent job shop scheduling using genetic algorithms. Computers & Industrial Engineering, 56(1): p. 179-185. 2009.
[26]. Mohanty, D., Chandra, A., and Chakraborti, N., Genetic algorithms based multi-objective optimization of an iron making rotary kiln. Computational Materials Science, 45(1): p. 181-188. 2009.
[27]. Zhou, H., Cheung, W., and Leung, L.C., Minimizing weighted tardiness of job-shop scheduling using a hybrid genetic algorithm. European Journal of Operational Research, 194(3): p. 637-649. 2009.
[28]. Tseng, L.-Y. and Lin, Y.-T., A hybrid genetic local search algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research, 198(1): p. 84-92. 2009.
[29]. 林秀英, 以螺絲螺帽緊鎖全球市場. 台灣經濟研究月刊第二十一卷第十一期,頁77-82. 1999.
[30]. 吳宗益, 台灣螺絲螺帽產業資源累積與產業分化之研究. 中山大學企業管理研究所碩士論文. 2000.
[31]. 柯惠雯, 結合模擬退火法與禁忌搜尋法在流程式生產排程之應用. 大葉大學工業工程學系研究所碩士論文. 2000.
[32]. 黃信強, 運用基因演算法於平行機器之工作排程. 淡江大學資訊管理學系碩士論文. 2000.
[33]. 李勝隆, 基因演算法於印刷電路板鑽孔排程之應用. 元智大學工業工程與管理學系研究所碩士論文. 2002.
[34]. 張鴻卿, 流程型工廠排程與接單策略研究-以型鋼業為例. 大葉大學工業工程學系研究所碩士論文. 2002.
[35]. 林純行, 多階平行機器零工式多目標排程之模式化與系統之研究. 東海大學工業工程與經營資訊研究所碩士論文. 2003.
[36]. 蔡瑜明, 半導體後段IC封裝最適排程之研究禁忌演算法之應用. 中山大學企業管理學系在職專班研究所碩士論文. 2003.
[37]. 劉盈利, 螞蟻演算法與禁忌搜尋法混合模式於配水管網設計最佳化之應用. 國立中興大學環境工程學系碩士論文. 2004.
[38]. 鄭博文、葉育典、許家豐, 應用田口實驗設計法於基因演算法參數設定-以流程式排程為例. 第一屆台灣作業研究學會學術研討會暨2004 年科技與管理學術研討會,頁603~610. 2004.
[39]. 陳貝生, 應用基因演算法於多部門多重專案選擇與排程問題. 中央大學工業管理研究所碩士論文. 2005.
[40]. 李政聰, 整合型啟發式學習法於光電產業測試機臺排程之研究. 成功大學資訊管理研究所碩士論文. 2006.
[41]. 楊棣焱, 螞蟻啟發式學習法於多目標維修排程之研究. 成功大學資訊管理研究所碩士論文. 2006.
[42]. 李輝煌, 田口方法:品質設計的原理與實務. 高立圖書有限公司出版. 2008.
[43]. 行政院主計處、工業生產統計/金屬中心, ITIS計畫整理. 2008,1997.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2014-06-24起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2014-06-24起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw