臺灣博碩士論文加值系統

過去排程研究中，針對延遲成本問題大部份學者皆假設工件延遲時，產生的延遲成本是隨著時間的增加而呈線性的增加；但是在實務上，延遲成本往往是以階段式增加。在問題中，客戶會給予多個時間點，在不同時間點下各要求不同的固定延遲成本。因此本研究稱此一個新的排程準則為階段式延遲成本(stepwise tardiness cost)。
本研究將探討階段式延遲成本準則於單機排程之問題，首先，我們提出二個啟發式演算法求解此問題，兩者主要之差異為使用不同的初始解。為了得到更好解的品質，本研究發展出一個變動鄰域搜尋法。提出的變動鄰域搜尋法中，使用一個新的表示可行解之方式，並且提出三種不同的鄰域結構。特別的是，其中之一的鄰域結構是以記憶機制為基礎的結構。實驗結果顯示，提出的啟發式演算法及變動鄰域搜尋法求解此排程問題，可得到良好的績效。

Over the past scheduling study, all the studies on this subject assume that the tardiness of jobs is a linear tardiness cost function. However, the stepwise tardiness cost function usually exists in many real-life situations, i.e., buyers usually provide several late periods. At the different late periods, firms would pay the different fixed tardiness cost. In this study, the new criterion of scheduling is called stepwise tardiness cost.
We will investigate stepwise tardiness criterion in a single machine scheduling problem. First of all, we propose two heuristics to solve the problem. Two heuristics use the SPT and EDD rule as the initial solutions, respectively. In order to obtain good solutions, we also develop a variable neighborhood search (VNS). In VNS algorithm, we develop a new encoding scheme to represent a feasible solution and propose three different neighborhood structures. In particularly, one of the neighborhood structures is based on memory-based mechanism. The experimental results show that the proposed heuristics and VNS algorithm can obtain a good performance for solving this scheduling problem.

中文摘要 I
Abstract II
謝誌 III
目錄 I
圖目錄 III
表目錄 4
第一章 導論 6
1.1 研究動機 6
1.2 研究目的 7
1.3 研究流程 8
第二章 相關文獻探討 10
2.1 單機總加權延遲時間排程問題 10
2.2 單機總延遲工件數排程問題 11
2.3 階段式延遲成本準則 12
第三章 變動鄰域搜尋法 14
3.1 基本原理與起源 14
3.2 變動鄰域搜尋法演算流程 14
3.3 變動鄰域搜尋法的參數設定 16
第四章 研究方法 18
4.1 問題描述 18
4.2 啟發式演算法 21
4.2.1 S啟發式演算法 21
4.2.2 E啟發式演算 23
4.3 演算實例 25
4.3.1 S啟發式演算法 25
4.3.2 E啟發式演算 30
4.4 變動鄰域搜尋法之演算架構 35
4.4.1 編碼（encoding） 36
4.4.2 產生起始解 37
4.4.3 鄰域結構 37
4.4.4 進行震動（Shaking）機制 43
4.4.5 區域搜尋（Local Search）機制 43
4.4.6 移步 44
第五章 實驗結果與說明 45
第六章 結論與未來研究方向 49
6.1 結論 49
6.2 未來研究方向 50
參考文獻 52
圖目錄
圖11 研究流程 9
圖21 傳統線性延遲成本與階段式延遲成本的比較 12
圖22 Σ j j 1|| w U 與Σ jk jk 1|| w U 的比較 13
圖31 變動鄰域搜尋法的ㄧ般演算流程 15
圖41 解的表示方法 36
圖42 編碼範例 37
圖43 鄰域h = 1範例 38
圖44 31 x 和24 x 做交換 39
圖45 鄰域h = 2 範例 39
圖46 31 x 和24 x 做插入 40
圖47 鄰域h = 3範例 41

表目錄
表41 工件資料 25
表42 是否滿足j j3 p < d 25
表43 是否滿足d C j > 1 26
表44 SPT 排序 26
表45 SPT 排序後依j j1 C < d 分類 26
表46 S1的EDD 排序後 27
表47 計算未延遲工件的j t 27
表48 找出滿足P t* j ≤ 之工件 28
表49 重新計算所有延遲工件的j C 28
表410 重新計算所有延遲工件的j C 29
表411 S 2 放在S * 的最後位置 29
表412 結果資料 29
表414 是否滿足j j3 p < d 30
表415 是否滿足d C j > 1 30
表416 EDD 排序 31
表417 EDD 排序後依j j1 C < d 分類 31
表418 重新計算所有延遲工件的j C 32
表419 計算S1的寬鬆時間 32
表420 找出滿足P t* j ≤ 之工件 33
表421 目前S1排序 33
表422 計算S1的寬鬆時間 33
表423 S1的寬鬆時間以EDD 排序 33
表424 找出滿足p t* j ≤ 之工件 34
表425 重新計算所有延遲工件的j C 34
表426 S 2 放在S * 的最後位置 35
表427 結果資料 35
表428 記憶矩陣的表示方式 40
表429 記憶矩陣累加權重分數 42
表430 記憶矩陣依累加權重分數大小作排序 42
表 51 啟發式演算法平均值差之結果 45
表52 各演算法平均值差之結果 46

[1]李鈞，生產管理進階，第二版，前程文化，台北，民95。
[2]汪玉柏，「運用基因演算法求解流程型工廠之多目標排程」，碩士論文，台灣科技大學工業工程研究所，台北(1999)。
[3]William J. Stevenson., Operations Management, 7ed, McGraw-Hill/Irwin, Boston, (2002).
[4]Sahin, G, “New combinatorial approaches for solving railroad planning and scheduling problems,” PhD thesis, University of Florida (2006).
[5]Liang, Y.C., Tien, C.Y. and Y.S. Chen, “A variable neighborhood search algorithm for bi-objective parallel machine scheduling problems,” CIIE Conference, Taoyuan, Taiwan, (2004).
[6]Karp, R.M, “Reducibility among combinatorial algorithms,” in: Miller, R.E., J.M. Thatcher (Eds), Complexity of Computer Computations, Plenum Press, NT, 85-103 (1972).
[7]Villarreal, F.J. and R.L. Robert, “Scheduling a single machine to minimize the weighted number of tardy jobs,” IIE Transactions, 15, 337-343 (1983).
[8]M’Hallah, R. and R.L. Bulfin, “Minimizing the weighted number of tardy jobs on a single machine,” European Journal of Operational Research, 145, 45-56 (2003).
[9]Mladenović, N. and P. Hansen, “Variable neighborhood search,” Computers and Operations Research, 24, 1097-1100 (1997).
[10]Graham, R.L., Lawler, E.L., Lenstra, J.K. and A.H.G. Rinnooy Kan, “Optimization and approximation in deterministic sequencing and scheduling: A survey,” Annals of Discrete Mathematics, 5, 287-326 (1979).
[11]Marc, S. and D.P. Stéphane, “Genetic algorithms to minimize the weighted number of late jobs on a single machine,” European Journal of Operational Research, 151, 296-306 (2003).
[12]Crauwels, H.A.J., Potts, C.N., and L.N. Van Wassenhove, “Local search heuristics for the single machine total weighted tardiness scheduling problem,” Informs Journal on Computing, 10, 341-350 (1998).
[13]Meoore, J.M, “An n-job,one-machine sequencing algorithm for the minimizing the number of late jobs,” Manufacturing Sciences, 15, 102-109 (1968).
[14]Suer, G.A. and C. Zbigniew, “A heuristic procedure to minimize number of tardy jobs and total tardiness in single machine scheduling,” Computers and Industrial Engineering, 23, 145-148 (1992).
[15]Curry, J. and B. Peters, “Rescheduling parallel machines with stepwise increasing tardiness and machine assignment stability objectives,” International Journal of Production Research, 43, 3231-3246 (2005).
[16]Blum, C. and A. Roli, “Metaheristics in combinatorial optimization: Overview and conceptual comparison,” ACM Computing Surveys, 35, 268-308 (2003).
[17]Hansen, P. and N. Mladenović, “Variable neighborhood search: principles and applications,” European Journal of Operational Research, 130, 449-467 (2001).
[18]Hansen, P. and N. Mladenović, “A tutorial on variable neighborhood search,” Lee Cahiers du GERAD, G-2003-46, (2003).
[19]Wu, T.H., Yang, M.L. and C.T. Tseng, “Minimizing the total tardiness in a single machine,” CIIE Conference, Taoyuan, Taiwan, (2005).