臺灣博碩士論文加值系統

本研究目的為應用改良遺傳基因演算法於複雜的多製造廠區之分配與調度問題最佳化。分佈式多製造廠生產排程問題主要考量四個部分：第一部分為「工件分配於製造廠」；第二部分為「製程順序配置」；第三部分為「各製造廠排程規劃」；第四部分為「物流中心距離各製造廠之運輸時間」。生產排程指標之總完工時間為本問題目標，意指所有工件的完成時間愈小，表示提高了企業的準時交貨的能力。本研究使用改良遺傳基因演算法解決L. De Giovanni所提出小型規模問題範例，最後主要目的為提出改良式遺傳基因演算法求解最佳化多工廠彈性工作排程問題及驗證其擴大問題規模研究分析。
本研究最後以程式運算的結果來證實本研究所提出的方法在多製造廠之分配與調度問題中的收斂程度及有效性，未來期望本研究對於多個目標發展，並且能對此問題進行求解。

This research proposes a method of improved genetic algorithm to solve the multi- manufacturing plant and flexible job-shop scheduling problem. Multi-factory production scheduling problem considering four parts: the first part is “allocate job to factories "; the second part "the routing of operations "; the third part " the assignment of operations to machines in Plant"; fourth part is " delivery time of the logistics center between the factory.” The problem for production scheduling objective is total completion time (makespan), it refers to all jobs’ completed processing times smaller. In this study, the use of improved genetic algorithm to solve L. De Giovanni raised by small sample problem, its object is to provide improved genetic algorithm for solving multi-plant flexibility to optimize job scheduling problem, and verify larger problem is designed.
The results obtained in this study to demonstrate that the proposed method of the Multi manufacturing Plant and Flexible Job-shop Scheduling problem. I hope this research toward the development of multi-objective problem in the future.

摘要 i
ABSTRACT ii
誌 謝 iii
目 錄 iv
圖目錄 vi
表目錄 viii
第一章 緒論 1
1.1 前言 1
1.2 研究動機與目的 3
1.3 研究步驟與架構 4
第二章 文獻探討 5
2.1 生產排程 5
2.2 基本派工法則 10
2.3 衡量準則定義 12
第三章 智慧型演算法 14
3.1 遺傳基因演算法 14
3.2 染色體初始化 18
3.3 染色體選擇 19
3.4 交配 21
3.5 突變 27
3.6 淘汰 29
3.7 終止 30
第四章 遺傳基因演算法於多製造廠彈性工作排程 31
4.1 零工式排程 31
4.1.1 零工式排程簡介 32
4.1.2 零工式排程限制 34
4.2 多製造廠彈性工作排程 35
4.2.1 多製造廠彈性工作排程問題描述 36
4.2.2 多製造廠彈性工作排程定義 37
4.2.3 多製造廠彈性工作排程限制 38
4.3 遺傳基因演算法求解多製造廠彈性排程問題 40
4.3.1 演算流程 40
4.3.1.1 染色體初始化 42
4.3.1.2 染色體適應值 46
4.3.1.3 染色體之選擇和複製 47
4.3.1.4 交配 49
4.3.1.5 基因突變 51
第五章 研究成果討論與驗證 52
5.1 驗證資料 52
5.2 實驗結果 60
5.3 結果分析 64
第六章 結論與未來展望 65
6.1 結論 65
6.2 未來展望 65
參考文獻 66

中文引用資料：
周至宏，2011，最佳化方法課程講義，國立高雄第一科技大學，系統資訊與控制研究所，台灣。
劉東官，2007，智慧型多目標動態生產排程系統教材，工業技術研究院，台灣。
郭瑞祥，蔣明晃，陳亞男，劉基全，2004，多廠生產規劃之供應鏈決策支援模式，臺大管理論叢，第十五卷第一期，頁49-74。
陳建良，1995，排程概述，機械工業雜誌，153期，頁122-137，台灣。
黃國祐，2009， "考量相依整備時間之完工時間最小化的非等效平行機問題"，國立臺灣科技大學，碩士論文。
林麗莉，2008， "具利潤分享機制的二層級供應鏈協同生產規劃" ，朝陽科技大學，碩士論文。
劉鎮瑋, 2012， "具資源限制及非等效平行機台考量之流程型生產排程問題" ，國立雲林科技大學，碩士論文。
陳彥竹，2009， “結合共享基因演算法與區段搜尋最佳化零工工廠排程問題" ， 大同大學，碩士論文。
王治平，2003， “實際零工式生產排程問題的派工法則” ，國立政治大學，碩士論文。
英文引用資料：
A.S.Fraser, 1957, ”Simulation of genetic systems by automatic digital computers”, International Journal of Biological Sciences , vol. 10, pp. 484–491.
Arora, 1998, "Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems", Journal of the ACM (JACM) Volume 45 Issue 5.
A. Hertz, M. Widmer, 1996, "An improved tabu search approach for solving the job shop scheduling problem with tooling constraints", Discrete Applied Mathematics 65, 319-346.
Bagley, 1967, The Behavior of Adaptive Systems which Employ Genetic and Correlation Algorithms, University of Michigan, Michigan, USA, Doctoral Dissertation.
Beamon BM, 1998, “Supply chain design and analysis: models and method.Int. J. Production Economics 55 (1998) 281–94.
Conway, R. W., et al., 1967, Theory of Scheduling, Addison-Wesley.
D.R. Sule, 1999, Logistics of Facility Location and Allocation, Marcel Dekker Inc., New York, NY.
Felix T.S. Chan, S.H. Chung, L.Y. Chan, G. Finke, M.K. Tiwari, 2006, “Solving distributed FMS scheduling problems subject to maintenance: Genetic algorithms approach”, Robotics and Computer-Integrated Manufacturing 22 (2006) 493–504.
Felix T.S. Chan, S.H. Chung, P.L.Y. Chan, 2005, "An adaptive genetic algorithm with dominated genes for distributed scheduling problems", Expert Systems with Applications 29 (2005) 364–371.
Goldberg, 1989. Genetic Algorithms in Search, Optimization and Machine Learning, Wesley Longman, Boston.
Graham, 1966, “Bounds for certain multiprocessing anomalies”, Bell System Technical Journal, vol. 45, pp. 1563–1581.
Graham, R.L., et al., 1979, “Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey”, Ann. Discrete Math, 5, pp.287-326.
H.Z. Jia, J.Y.H. Fuh, A.Y.C. Nee, Y.F. Zhang, 2003, “A modified genetic algorithm for distributed scheduling problems”, Journal of Intelligent Manufacturing 15(2003) 351–362.
J.Holland, 1975, Adaptation in Natural and Artificial Systems, University of Michigan Press, Michigan.
Kawanaka, H., 2001, "Genetic algorithm with the constraints for nurse scheduling problem", Department of Electrical and Electronic Engineering, Faculty of Engineering, Mie University.
Kim, D. W., Kim, K. H., Jang, W., and Chen, F. F., 2002, ”Unrelated parallel machine scheduling with setup times using simulated annealing”, Robotics And Computer-Integrated Manufacturing, Vol.18, pp.223-231.
L. De Giovanni, F. Pezzella, 2010, ” An Improved Genetic Algorithm for the Distributed and Flexible Job-shop Scheduling problem”, European Journal of Operational Research 200 (2010) 395–408
M. Gen and R. Cheng, 1997, Genetic algorithms and engineering design, John Wiley and Sons, New York .
M. Garey, D. Johnson and R. Sethi, 1976, The complexity of flow shop and job shop scheduling, Mathematics of Operations Research 1 (2) (1976) 117-129.
Cheng, T. E. E., and Diamond, J. E., 1995, ”Scheduling Two Job Classes on Parallel Machines”, IIE Transactions, Vol.27, pp.689-693.
Pinedo, Michael, 1995, Scheduling: Theory, algorithms, and systems, Prentice Hall , Englewood Cliffs, N.J.