跳到主要內容

臺灣博碩士論文加值系統

(44.192.22.242) 您好!臺灣時間:2021/08/03 19:45
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:吳憲明
研究生(外文):wu hsien ming
論文名稱:不等候條件考量下具非等效平行機台之流程型排程問題研究
論文名稱(外文):An Approach of No Wait Flow Shop Scheduling with Unrelated Parallel Machine
指導教授:柯千禾柯千禾引用關係駱景堯駱景堯引用關係
學位類別:碩士
校院名稱:大葉大學
系所名稱:工業工程與科技管理學系
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2007
畢業學年度:95
語文別:中文
中文關鍵詞:不等候條件非等效平行機獨立整備時間相依拆卸時間多階段平行機台多目標排程混合型基因演算法粒子群最佳化演算法
外文關鍵詞:no waitnon-identical parallel machineflow shopsetup timeremoval timeMultiple ObjectiveHybrid genetic algorithm (HGA)Particle swarm optimizer(PSO)
相關次數:
  • 被引用被引用:1
  • 點閱點閱:171
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
本研究針對多階段平行機台流程式工廠的排程問題,考量不等候(no wait)條件、非等效平行機台(unrelated parallel machine)、可分割整備時間(separable setup time)及相依拆卸時間(dependent removal time)等因素。並以總完工時間與總延遲時間最小化為目標,發展出粒子群最佳化演算法(PSO)與混合型基因演算法(HGA)兩種啟發式演算法。
在影響演算法執行結果之參數分析上,利用田口實驗求出最佳參數組合,來增進啟發式演算法之求解品質及效率,並比較兩啟發式演算法之成效。研究發現問題規模較小時,粒子群最佳化演算法的求解品質表現較好,當問題規模變大,則為混合型基因演算法的求解品質表現較佳,在求解時間上,卻較粒子群最佳化演算法緩慢。
In this research, no wait flow shop scheduling problem with unrelated parallel machine is considered. In order to search for Pareto optimal solutions of multi-objective optimization problems, we propose two heuristic algorithms to get a near optimal schedule in a reasonable computation time. Hybrid genetic algorithm and particle swarm optimization are performed in heuristics. In the past few years, most of research assumes setup time or removal times is even negligible or part of the processing time. However, we look the setup, processing, and removal times as separable, then take the sequence-independent setup time and dependent removal time into account.
Taguchi method has been widely applied in the practical applications for optimizing the process parameters in the manufacturing process. During the research, the parameters used in the heuristics that affect the solution quality is analyzed and designed by Taguchi method; then for the constructed heuristic, a good parameter setting is suggested. The experimental results are reported, and provided for the references for the further research.
目錄

封面內頁
簽名頁
授權書 iii
中文摘要 iv
英文摘要 v
誌謝 vi
目錄 vii
圖目錄 x
表目錄 xii

第一章 緒論 1
1.1 研究動機與背景 1
1.2 研究目的 2
1.3 研究範圍 2
1.4 研究方法與架構 3
第二章 文獻探討 5
2.1 不等候條件 5
2.2 平行機台問題 6
2.3 整備時間與拆卸時間 7
2.4 多目標規劃 9
2.5 粒子群最佳化演算法 12
2.6 基因演算法 15
2.7 總結 17
第三章 問題定義與分析 18
3.1 問題定義 18
3.2 問題模式建構 19
3.2.1 問題模式之限制與假設 19
3.2.2 符號說明 20
3.2.3 衡量目標 20
第四章 演算法之建構 23
4.1 粒子群最佳化演算法 23
4.1.1 編碼 26
4.1.2 計算適合度 26
4.1.3 更新柏拉圖最佳解 27
4.1.4 更新粒子位置與速度 28
4.1.5 局部搜尋 30
4.2 混合型基因演算法 31
4.2.1 複製 33
4.2.2 交配 34
4.2.3 突變 34
4.2.4 精華保留策略 35
4.2.5 取代 35
4.3 柏拉圖解之搜尋權重 36
4.4 柏拉圖解集合衡量方法 39
第五章 實驗設計 40
5.1 例題產生 40
5.2 參數設定 41
5.3 田口實驗 44
5.4 程式驗證 48
5.5 啟發式演算法之分析比較 51
第六章 結論與建議 53
6.1 結論 53
6.2 建議 54
參考文獻 55
附錄一 各目標之數學模式 59


圖目錄

圖1.1 研究架構圖 4
圖2.1 整備作業為(a)可分割(b)不可分割示意圖 8
圖2.2 柏拉圖最佳解集合圖 11
圖2.3 粒子群最佳化演算法流程圖 13
圖2.4 基因演算法流程圖 16
圖3.1 平行機台製造系統示意圖 18
圖4.1 DMS-PSO概念圖 24
圖4.2 粒子群最佳化演算法流程圖 25
圖4.3 編碼示意圖 26
圖4.4 任選階段工作順序更新示意圖 29
圖4.5 局部搜尋流程圖 30
圖4.6 產生鄰近解示意圖 31
圖4.7 混合型基因演算法流程圖 32
圖4.8 任一階段工作順序交配方式示意圖 34
圖4.9 任一階段工作順序突變方式示意圖 35
圖4.10 固定權重於雙目標最小化搜尋圖 37
圖4.11 搜尋方向與所搜尋解之關係圖 38
圖4.12 變動權重之搜尋方向圖 38
圖5.1 粒子群最佳化演算法之各參數因子回應圖 45
圖5.1 粒子群最佳化演算法之各參數因子回應圖(續) 46
圖5.5 混合型基因演算法之各參數因子回應圖 47
圖5.5 混合型基因演算法之各參數因子回應圖(續) 48


表目錄

表3.1 排程目標分類 21
表5.1 五組時間比例表 41
表5.2 粒子群最佳化演算法參數因子水準表 42
表5.3 混合型基因演算法參數因子水準表 43
表5.4 粒子群最佳化演算法之S/N表 45
表5.5 混合型基因演算法之S/N表 47
表5.6 總完工時間最小化驗證表 49
表5.7 總延遲時間最小化驗證表 50
表5.8 各規模問題之柏拉圖解集合衡量表 52
參考文獻

[1]王培珍,「應用遺傳演算法與模擬在動態排程問題之探討」,中原大學碩士學位論文,民國84年。
[2]洪正鴻,「非等效平行機台之多階段流程型排程求解模式建構」,大葉大學碩士學位論文,民國92年。
[3]張俊仁,「非等效平行機台之多階段流程型排程求解模式建構」,大葉大學碩士學位論文,民國86年。
[4]莊舜智,「多目標決策之應用:整備時間考量下之零工式排程問題探討」,大葉大學碩士學位論文,民國87年。
[5]許志義,「多目標決策」,五南圖書出版公司,民國83年。
[6]黃漢強,「混合式基因演算法應用於不等候零工廠問題之研究」,國立台灣科技大學碩士學位論文,民國92年。
[7]蔡碧芳,「等效平行機台考量之多階段流程型排程問題探討」,大葉大學碩士學位論文,民國92年。
[8]Allahverdi, A. and F. S. Al-Anzi, “A PSO and a Tabu search heuristics for the assembly scheduling problem of the two-stage distributed database application,” Computers and Operations Research ,Vol. 33, 1056-1080(2006).
[9]Allahverdi, A. and T. Aldowaisan, “No-wait flowshops with bicriteria of makespan and maximum lateness,” European Journal of Operational Research, Vol. 152, 132-147(2004).
[10]Allahverdi, A. and T. Aldowaisan, “No-wait and separate setup three-machine fowshop with total completion time criterion,” International Transcations in Opeartional Research, Vol.7, 245-264 (2000).
[11]Baker, R. K., “Sequence Rules and Due-Date Assignments in A Job Shop,” Management Science, Vol.30No.9, 1093-1104 (1998).
[12]Bilge, U., K. Furkan, M. Kurtulan, and P. Pelin,“A tabu search algorithm for parallel machine total tardiness problem,” Computers & Operations Research ,Vol. 31, 397–414(2004).
[13]Deb, K., P. Amrit, A. Sameer and T. Meyarivan, “A Fast Elitist Non-dominated Sorting Genetic Algorithm for Multi-Objective Genetic Algorithm: NSGA-II,” KanGAL report 200001, Indian Institute of Technology , Kanpur, India (2000).
[14]Gonzalez, B., M. Torres and J. A. Moreno,“A Hybrid Genetic Algorithm Approach for the No-wait Flowshop Scheduling Problem, ”Genetic Algorithms in Engineering Systems: Innovations and Applications, Conference Publication No. 414 (1995).
[15]Gupta, J. N. D., V. A. Strusevich, and C. M. Zwaneveld, “Two-stage no-wait scheduling models with setup and removal times separated,” Computers and Operations Research, Vol.24,No.1, 1025-1031( 1997).
[16]Hall, N. G. and C. Sriskandarajah,“A survey of machine scheduling problems with blocking and no-wait in process,” Operations Research, Vol.44,No.3, 510-525(1996).
[17]Holland, J. H., “Adaptation in Natural and Artificial Systems,” The University of Michigan Press(1975).
[18]Ishibuchi, H. and T. Murata,“Multi-Objective Genetic Local Search Algorithm,” Proceedings of IEEE International Conference on Evolutionary Computation, 119-124(1996).
[19]Jin, Z., Z. Yanga and T. Itob, “Metaheuristic algorithms for the multistage hybrid flowshop scheduling problem,” International Journal of production economics, Vol. 100, 322-334(2006).
[20]Kennedy, J. and R. Eberhart,“Particle swarm optimization,” IEEE International Conference on Neural Networks, Vol.4, 1942-1948(1995).
[21]Lian, Z., Kim, X. Gu and B. Jiao,“A similar particle swarm optimization algorithm for permutation flowshop scheduling to minimize makespan,” Applied Mathematics and Computation, Vol.175, 773-785(2006).
[22]Liang, J. J. and P. N. Suganthan, “Dynamic multi-swarm particle swarm optimizer with local search,” IEEE Congress on Evolutionary Computation, Vol. 1, 552528(2005).
[23]Liao, C. H., and C. H. Lin, “Makespan minimization for two uniform parallel machines,” International Journal of Production Economics, Vol.84,205-213(2003).
[24]Liaw, C. F., Y. K. Lin., C. Y. Cheng and M. C. Chen, “Scheduling unrelated parallel machines to minimize total weighted tardiness,” Computers and Operations Research, Vol. 30, 1777-1789 (2003).
[25]Murata, T. and H. Ishibuchi, “MOGA: multi-objective genetic algorithms,” International Conference on Evolutionary Computation, Vol.1, 289-294(1995).
[26]Nearchou, A. C., “The effect of various operators on the genetic search for large scheduling problems,” International Journal of Production Economics, Vol.88, 191-203(2004).
[27]Pranzo, M., “Batch scheduling in a two-machine flow shop with limited buffer and sequence independent setup times and removal times,” European Journal of Operational Research, Vol. 153, 581-592(2004).
[28]Ruiz, R. and C. Maroto, “A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility,” European Journal of Operational Research, Vol. 169, 781-800(2006).
[29]Tamaki, H., T. Komori and S. Abe,“A heuristic approach to parallel machine scheduling with earliness and tardiness penalties,” IEEE International Conference on Emerging Technologies and Factory Automation ,Vol.2,1367-1370(1999).
[30]Tamaki, H., E. Nishino and S. Abe,“A Genetic Algorithm Approach to Multi-Objective Scheduling Problems with Earliness and Tardiness Penalties,” Proceedings of IEEE International Conference on Evolutionary Computation, Vol.1, 46-52(1999).
[31]Wang, K. P., L. Huang, C. G. Zhou and W. Pang,“Particle swarm optimization for traveling salesman problem”, IEEE International Conference on Machine Learning and Cybernetics, Vol.3, 1583-1585(2003).
[32]Xia, W. J., Z. M. Wu, W. Zhang and G. K. Yang, “A new hybrid optimization algorithm for the job-shop scheduling problem,” Proceedings of American Control Conference, Vol.6, 5552-5557(2004).
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top