臺灣博碩士論文加值系統

本 論 文 將 探 討 單 機 (single machine) 在 相 依 整 備 時 間 (sequence
dependent setup times)限制下，總加權延遲時間(total weighted tardiness)
之排程問題，以排程符號表示為 1|

This paper investigates a single machine total weighted tardiness problem
with sequence dependent setup times. The problem is denoted by |

中文摘要 ............................................................................................................ I
Abstract .............................................................................................................. II
致謝 .................................................................................................................. III
目錄 .................................................................................................................. IV
表目錄 .............................................................................................................. VI
圖目錄 ............................................................................................................ VIII
第一章 緒論 .................................................................................................. 1
1.1 研究背景與動機 ............................................................................................. 1
1.2 研究目的 ........................................................................................................ 4
1.3 研究流程 ........................................................................................................ 4
第二章 文獻探討 .............................................................................................. 6
2.1 易經與科學 ..................................................................................................... 6
2.2 通用啟發法 ................................................................................................... 10
2.3 單機總加權延遲時間問題 ........................................................................... 13
第三章 研究方法 ............................................................................................ 14
3.1 問題模式 ...................................................................................................... 14
3.1.1 符號說明 ......................................................................................... 14
3.1.2 問題定義 ......................................................................................... 16
3.2 易經演算法 .................................................................................................. 16
3.2.1 初始化及計算目標函數值 .............................................................. 17
3.2.2 卜卦 ................................................................................................. 18
3.2.3 下卦指引 ......................................................................................... 25
3.2.4 上卦指引 ......................................................................................... 28
3.2.5 移動 ................................................................................................. 30
3.2.6 終止條件 ......................................................................................... 30
3.2.7 演算法步驟 ...................................................................................... 31
3.3 易經演算法實際範例 .................................................................................. 32
第四章 實驗結果與說明 ................................................................................ 40
第五章 結論與未來研究方向 ........................................................................ 45
5.1 結論 .............................................................................................................. 45
5.2 未來研究方向 .............................................................................................. 46
參考文獻 ......................................................................................................... 47


表目錄
表3.13.1 八卦與二進位對照八卦與二進位對照八卦與二進位對照表 .......................................................................... 22
表3.2 工件資料表 ............................................................................................. 33
表3.3 工件整備時間表 ..................................................................................... 33
表3.4 起始工件排序表 ..................................................................................... 34
表3.5 最佳解及目標函數最佳解及目標函數最佳解及目標函數值 .......................................................................... 37
表3.6 局部搜尋最佳解及目標函數值 ............................................................. 39
表4.1 演算法參數設定 ..................................................................................... 40
表4.2 標竿例題類型 ......................................................................................... 41
表4.3 14.3 14.3 1-10題目數據題目數據 ...................................................................................... 42
表4.4 11-20題目數據 ........................................................................................ 42
表4.5 21-30題目數據..................................................................................... 42
表4.6 31-40題目數據..................................................................................... 42
表4.7 41-50題目數據 ........................................................................................ 43
表4.8 51-60題目數據..................................................................................... 43
表4.9 61-70題目數據..................................................................................... 43
表4.10 71-80題目數據 ................................................................................... 43
表4.11 81-90題目數據 ................................................................................... 44
表4.12 91-100題目數據 ................................................................................. 44
表4.13 101-110題目數據 ............................................................................... 44
表4.14 111-120題目數據 ............................................................................... 44


圖目錄
圖1.11.1 六十四卦 ................................................................................................ 2
圖1.21.2 乾卦之辭及爻乾卦之辭及爻乾卦之辭及爻辭 ................................................................................ 3
圖1.3 研究流程圖 ............................................................................................ 5
圖2.1 2.1 八卦與二項式八卦與二項式八卦與二項式原理 ................................................................................ 7
圖2.22.2 六十四卦方陣演繹六十四卦方陣演繹六十四卦方陣演繹法 ............................................................................ 9
圖2.3 LS演算法的步驟 ................................................................................. 11
圖3.1 工件順序的表示方式 ............................................................................. 17
圖3.2 大衍之數揲卦法流程 ............................................................................. 21
圖3.3 卦象二進位轉換圖 ................................................................................. 22
圖3.4 太極生成圖太極生成圖 .......................................................................................... 23
圖3.5 先天八卦圖 .......................................................................................... 23
圖3.6 後天八卦圖 .......................................................................................... 24
圖3.7 八卦方向圖 .......................................................................................... 25
圖3.8 易經最佳化演算法流程圖 ..................................................................... 32
圖3.9 卜卦流程圖 ............................................................................................. 34
圖3.10 下卦↖方向工件抽取圖(a) .................................................................. 35
圖3.11 下卦↖方向工件抽取圖方向工件抽取圖方向工件抽取圖(b) ................................................................ 36
圖3.12 抽取工件插入至工件排序搜尋最佳解(a) .......................................... 36
圖3.13 抽取工件插入至工件排序搜尋最佳解(b) ........................................ 37
圖3.14 上卦↓方向工件移動圖 ...................................................................... 38
圖3.15 上卦加工順序第一工件局部搜尋 ....................................................... 38
圖3.16 上卦加工順序第二工件局部搜 ......................................................... 39

南懷瑾，「易經雜說」，老古文化事業股份有限公司，台北市(2009)
南懷瑾，「易經繫傳別講上傳」，老古文化事業股份有限公司，台北市(1991)
黎凱旋，「易數淺說」，名山出版社，台北市(1993)
孔繁詩，「易象易數易理應用研究」，情園印刷事業有限公司，台北市(1995)
程振清,何成正，「易經與現代管理」，中天出版社，新北市(1999)
陳蒼杰，「易經讀本」，大夏出版社，台南市(1994)
林益勝，「易經與生活」，台灣商務印書館股份有限公司，台北市(2010)
陳文德，「數位易經」，遠流出版事業股份有限公司，台北市(1999)
呂淳風，「商用易經讀本」，實學社，台北市(1996)
周盈君，「變動臨域搜尋法求解單機階段式延遲問題」，碩士論文，朝陽科
技大學工業工程與管理研究所，台中(2009)
林金郎，「易經很簡單」，未來書城有限股份公司，台北市(2003)
何兆武，「中國印象︰外國名人論中國文化」，中國人民大學出版社，北京
市(2011)
郝岳才，「周易文化的科學探索」，大展出版社有限公司，台北市(2010)
Cicirello, V.A, “Weighted Tardiness Scheduling with Sequence-Dependent
Setups: A Benchmark Problem for Soft Computing”, Applications of Soft
Computing Advances in Soft Computing Conference, Richard Stockton College,
New Jersey, Vol. 52, pp 189-198 (2009)

Cicirello, V.A, “On the design of an adaptive simulated annealing algorithm” In
Proceedings of the CP 2007 First International Workshop on Autonomous
Search, (2007).

Cicirello, V.A, “Weighted tardiness scheduling with sequence-dependent setups
a benchmark library”, Technical Report of Intelligent Coordination and
Logistics Laboratory Robotics Institute, Carnegie Mellon University, USA
(2003)

Eva Vallada., Ruben Ruiz, “A genetic algorithm for the unrelated parallel
machine scheduling problem with sequence dependent setup times”, European
Journal of Operational Research, Vol.211, No3, pp 612–622 (2011)

Guohua Wan., Benjamin P.-C. Yen, “Tabu search for single machine scheduling
with distinct due windows and weighted earliness tardiness penalties”, European
Journal of Operational Research, Vol.142, No.2, pp 271 – 281 (2002)

Liao CJ, Juan HC, “An ant colony optimization for single-machine tardiness
scheduling with sequence-dependent setups” Computers & Operations Research,
Vol.34, No.7,pp, 1899–1909, (2007)
M. Fatih Tasgetiren., Yun-Chia Liang., Mehmet Sevkli., Gunes Gencyilmaz, “A
particle swarm optimization algorithm for makespan and total flowtime
minimization in the permutation flowshop sequencing problem”, European
Journal of Operational Research, vol.177, No.3, pp 1930–1947(2007)

Marco Dorigo., Gianni Di Caro, “Ant Colony Optimization: A New
Meta-Heuristic”, Evolutionary Computation, CEC 99. Proceedings of the 1999
Congress on, Vol.2, (1999)

Manuel Laguna., J. Wesley Barnes., Fred W. Glover, “Tabu search methods for a
single machine scheduling problem“, Journal of Intelligent Manufacturing,
Vol.2,No.2 , pp 63-73(1991)

Pinedo, M., Scheduling: Theory, Algorithms, and Systems, 3
rd
edition,
Prentice-Hall, (2008)

Sharif Melouk., Purushothaman Damodaran., Ping-Yu Chang, ”Minimizing
makespan for single machine batch processing with non-identical job sizes using
simulated annealing”, International Journal of Production Economics, Vol.87,
No.2, pp 141–147 (2004)