進階搜尋


 
系統識別號 U0026-0107201414545900
論文名稱(中文) 以基因演算法求解工件族群批件處理機台之多目標流程式生產排程問題
論文名稱(英文) Solving Multi-objective Scheduling Problem of Incompatible Families on Batch Processing Machines by Genetic Algorithm
校院名稱 成功大學
系所名稱(中) 工業與資訊管理學系
系所名稱(英) Department of Industrial and Information Management
學年度 102
學期 2
出版年 103
研究生(中文) 蕭涵謙
研究生(英文) Han-Chien Hsiao
學號 R36011042
學位類別 碩士
語文別 中文
論文頁數 57頁
口試委員 指導教授-張秀雲
口試委員-葉丁鴻
口試委員-陳明德
中文關鍵字 流程式生產  多目標基因演算法  不相容族群  批件處理機台 
英文關鍵字 flow shop scheduling  multi-objective genetic algorithm  incompatible job families  batch-processing machine 
學科別分類
中文摘要 本研究考慮批件處理機台(Batch processing machines)之流程式生產排程問題,並考量不相容工件族群(incompatible families)之情形,目標是找出最小化最大完工時間(makespan)以及最小化總權重延遲時間(total weighted tardiness time)。本研究首先針對此問題建立數學規劃模式,由於此為一個NP-complete的問題,因此若是當工件數或機台數量增加,便很難利用數學模型來求解。故此本研究修改多目標基因演算法以求得近似最佳解,使演算法更能適用在批件處理機台,或是應用到考量不相容工件族群的情形,並在演算法中使用菁英策略結合柏拉圖前緣解的概念以處理多目標問題之情形,提供生產線上決策者進行決策;並以數組隨機產生之問題進行求解,得到本研究之演算方法再求解規模較大的問題時,可以得到較完整的柏拉圖前緣解;而後續再以本研究所建立之數學模型求解較小規模之問題的每一目標最佳解,與本研究之多目標基因演算法求解進行比較,得出本研究之演算方法在求解小型問題時同樣可以得到最佳解,而求解效率相較模形求解亦隨著問題規模上升而提高;最後以演算法計算結果分析本研究問題計算結果所發生的情形,並提供未來研究方向的建議。
英文摘要 In this paper, we propose a modified multi-objective genetic algorithm and apply it to the flow shop scheduling problem with batch-processing machine (BPM) and incompatible job families. The processing time of each batch is the longest processing time among all the jobs in that batch. We construct a mathematical model for the problem. Since the mathematical model is hard to solve, we modify the multi-objective genetic algorithm (MOGA) for this problem. The characteristics of our algorithm are its coding/decoding procedure and elite preserve strategy. The performance of our multi-objective genetic algorithm is examined by applying it to random instances of the flow shop scheduling problem with two objectives: to minimize the makespan and to minimize the total weighted tardiness. The results obtained from MOGA of two small problems are compared with the single objective optimal solutions of these two problems solved by LINGO to verify the effectiveness of the proposed approaches.
論文目次 摘要 i
Extended Abstract ii
致謝 vi
目錄 1
圖目錄 3
表目錄 5
第一章 緒論 6
1.1 研究動機與目的 6
1.2 研究範圍 7
1.3 研究架構與流程 8
第二章 文獻探討 10
2.1 流程式生產排程 10
2.2 啟發式演算法 11
2.2.1 基因演算法 12
2.2.2 其他演算法 14
2.3 不相容工件族群 17
2.4 多目標之流程式生產排程 17
2.5 小結 18
第三章 研究方法 20
3.1 問題描述與假設 20
3.2 模型建立 21
3.3 基因演算法基本流程 24
3.3.1 編碼與解碼 26
3.3.2 產生初始解 27
3.3.3 計算適配值 27
3.3.4 選擇 29
3.3.5 交配 29
3.3.6 突變 30
3.4 小結 31
第四章 數據分析與評估 32
4.1 模式資料設定與作業環境 32
4.2 演算法參數分析 33
4.3 問題計算 40
4.4 小結 51
第五章 結論與建議 52
5.1 研究結論 52
5.2 未來研究建議 53
參考文獻 55
參考文獻 廖麗滿, 黃敬仁, & 林志諭. (2011). 穩健多目標基因演算法應用於流程型工廠之排程研究. Journal of Technology, 26(1), 65-71.
柯惠雯.(2001).結合模擬退火法與禁忌搜尋法在流程式生產排程之應用,大葉大學工業工程研究所碩士論文.
Allouche, M. A., Aouni, B., Martel, J. M., Loukil, T., & Rebaï, A. (2009). Solving multi-criteria scheduling flow shop problem through compromise programming and satisfaction functions. European journal of operational research, 192(2), 460-467.
Ben-Daya, M., & Al-Fawzan, M. (1998). A tabu search approach for the flow shop scheduling problem. European Journal of Operational Research, 109(1), 88-95.
Choi, H. S., & Lee, D. H. (2009). Scheduling algorithms to minimize the number of tardy jobs in two-stage hybrid flow shops. Computers & Industrial Engineering, 56(1), 113-120.
Damodaran, P., Kumar Manjeshwar, P., & Srihari, K. (2006). Minimizing makespan on a batch-processing machine with non-identical job sizes using genetic algorithms. International journal of production economics, 103(2), 882-891.
Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of operations research, 1(2), 117-129.
Gary, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman & Company. New York.
Iyer, S. K., & Saxena, B. (2004). Improved genetic algorithm for the permutation flowshop scheduling problem. Computers & Operations Research, 31(4), 593-606.
Johnson, S. M. (1954). Optimal two‐and three‐stage production schedules with setup times included. Naval research logistics quarterly, 1(1), 61-68.
Kahraman, C., Engin, O., Kaya, İ., & Öztürk, R. E. (2010). Multiprocessor task scheduling in multistage hybrid flow-shops: a parallel greedy algorithm approach. Applied Soft Computing, 10(4), 1293-1300.
Kumar Manjeshwar, P., Damodaran, P., & Srihari, K. (2009). Minimizing makespan in a flow shop with two batch-processing machines using simulated annealing. Robotics and Computer-Integrated Manufacturing, 25(3), 667-679.
Lei, D. (2008). A Pareto archive particle swarm optimization for multi-objective job shop scheduling. Computers & Industrial Engineering, 54(4), 960-971.
Lei, D., & Wang, T. (2011). An effective neighborhood search algorithm for scheduling a flow shop of batch processing machines. Computers & Industrial Engineering, 61(3), 739-743.
Mönch, L., Balasubramanian, H., Fowler, J. W., & Pfund, M. E. (2005). Heuristic scheduling of jobs on parallel batch machines with incompatible job families and unequal ready times. Computers & Operations Research, 32(11), 2731-2750.
Moore, J. M. (1968). An n job, one machine sequencing algorithm for minimizing the number of late jobs. Management Science, 15(1), 102-109.
Moslehi, G., & Mahnam, M. (2011). A Pareto approach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search. International Journal of Production Economics, 129(1), 14-22.
Murata, T., Ishibuchi, H., & Tanaka, H. (1996). Multi-objective genetic algorithm and its applications to flowshop scheduling. Computers & Industrial Engineering, 30(4), 957-968.
Pinedo, M. (2012). Scheduling: theory, algorithms, and systems. Springer.
Pour, N., Tavakkoli-Moghaddam, R., & Asadi, H. (2013). 5. Optimizing a multi-objectives flow shop scheduling problem by a novel genetic algorithm. International Journal of Industrial Engineering Computations, 4(3), 345-354.
Qing-dao-er-ji, R., & Wang, Y. (2012). A new hybrid genetic algorithm for job shop scheduling problem. Computers & Operations Research, 39(10), 2291-2299.
Reeves, C. R. (1995). A genetic algorithm for flowshop sequencing. Computers & operations research, 22(1), 5-13.
Ruiz, R., Maroto, C., & Alcaraz, J. (2006). Two new robust genetic algorithms for the flowshop scheduling problem. Omega, 34(5), 461-476.
Yagmahan, B., & Yenisey, M. M. (2008). Ant colony optimization for multi-objective flow shop scheduling problem. Computers & Industrial Engineering, 54(3), 411-420.
Yagmahan, B., & Yenisey, M. M. (2010). A multi-objective ant colony system algorithm for flow shop scheduling problem. Expert Systems with Applications, 37(2), 1361-1368.
Yan L. (2000). Isolation niche genetic algorithm. Journal of Systems Engineering, 15(1), 86–91.
http://jjcommons.csie.isu.edu.tw/research/research/download/PSO
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2019-07-11起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2019-07-11起公開。


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