臺灣博碩士論文加值系統

本研究考慮在有機台限制的非等效平行機台（Unrelated Parallel Machine）下之排程問題，本研究目標為使總完工時間（Total Completion Time）最小化。本問題為NP-Hard，故本研究提出啟發式演算法與分支界限演算法；啟發式演算法主要是以能最早完工的工作進行指派，但是因為每一個排入的工作皆會對未排的工作造成影響，故本研究的啟發式演算法會利用已排與未排工作的估計總完工時間來加以判斷工作排入的位置；分支界限演算法會利用本研究所提出的改善後的下限值，來減少分支界限法所分支的節點數，加快其求解時間；經實驗後證明本研究所提出的啟發式演算法與最佳解整體平均誤差不會超過0.46%。

This article considers the problems of scheduling a given set of independent jobs on unrelated parallel machines to minimize the total completion time. The problem is known to be NP-Hard. Efficient heuristic and branch and bound algorithms are developed. Heuristic algorithm is based on the solution of an assignment problem, and assign job by the earliest completion time. Each assigning job makes a significant influence to unscheduled jobs. Therefore, the heuristic algorithm will use the total completion time of scheduled and unscheduled jobs to be estimated total completion time for the assignment. Branch and bound algorithm will use the improve lower bound to reduce its nodes and execution time. Computational experience indicates that the deviation of the heuristic and optimal is not more than 0.46%.

目錄
中文摘要 I
英文摘要 II
誌謝 III
目錄 IV
圖目錄 VI
表目錄 VII
第一章 緒論 1
1.1 研究背景與目的 1
1.2 研究範圍與內容 1
1.3 研究方法 2
第二章 文獻探討 4
2.1 非等效平行機台（Unrelated Parallel Machine）之相關文獻 4
2.2 機台限制（Machine Eligibility）之相關文獻 5
第三章 模式建構 7
3.1 本研究之基本假設 7
3.2 符號說明 8
3.3 問題定義 9
3.4 整數規劃之建立 9
3.5 啟發式演算法 11
3.5.1 啟發式演算法步驟 11
3.5.2 啟發式演算法範例步驟 12
3.5.3 特殊條件下求得最佳解 15
3.6 分支界限法（Branch and Bound, B&B） 15
3.6.1 下限值（Lower Bound） 15
3.6.2 下限值演算法的改善 18
第四章 結果分析 22
4.1 實驗參數設定 22
4.2 實驗結果與分析 23
第五章 結論與未來展望 34
5.1 結論 34
5.2 建議與未來展望 34
參考文獻 35

圖目錄
圖1.1 研究流程圖 3
圖3.1 啟發式演算法範例甘特圖 15
圖3.2 剔除重複分支示意圖 21
圖4.1 啟發式演算法、BAB*、BAB分別在作業加工時間服從U[1,10]與U[1,100]的平均求解時間比較圖 28
圖4.2 不同機台限制比例 下，BAB*與BAB在作業加工時間服從U[1,10]與U[1,100]的平均求解時間比較圖 29
圖4.3 不同機台限制比例 下，Heuristic在作業加工時間服從U[1,10]與U[1,100]的求解品質比較圖 30
圖4.4 啟發式演算法在作業加工時間服從U[1,10]與U[1,100]的求解品質比較圖 31
圖4.5 啟發式演算法在作業加工時間服從U[1,10]與U[1,100]的平均求解時間 32
圖4.6不同機台限制比例 下，Heuristic在作業加工時間服從U[1,10]與U[1,100]的求解時間比較圖 33

表目錄
表3.1 範例工作資料表 12
表3.2 列與行減後的工作資料表 13
表3.3 指派一個工作後的工作資料表 13
表3.4 工作資料表3.1的 值 19
表3.5 工作資料表3.1之對偶最佳解 20
表4.1 實驗次數彚整表 23
表4.2 不同參數下分支界限法求解時間與啟發式演算法求解品質彚整表 24
表4.3 不同參數下BAB*與BAB的求解節點數彚整表 26
表4.4 不同參數下啟發式演算法求解時間彚整表 31

參考文獻

Azizgolu M. and Kirca O., Scheduling jobs on unrelated parallel machines to minimize regular total cost functions. IIE Transactions, 31, 153–9, (1999).

Bruno J., E. G. Coffman Jr., and Sethi R., Scheduling in-dependent tasks to reduce mean finishing time. Communications of the ACM, 17, 382±387, (1974).

Ching-Fang Liaw, Yang-Kuei Lin, Chun-Yuan Cheng, Mingchin Chen, Scheduling unrelated parallel machines to minimize total weighted tardiness. Computers and Operations Research 30, 1777-1789, (2003).

Chung-Lun Li, Scheduling unit-length jobs with machine eligibility restrictions. European Journal of Operational Research 174, 1325-1328, (2006).

Conway R. W., Maxwell W. L., and Miller L. W., Theory of scheduling, Addison Wesley, Reading, Maxx., (1967).

Garey M.R., Johnson D.S., Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, (1979).

Grissele Centeno, Robert L., Armacost, Minimizing makespan on parallel machine with release time and machine eligibility restrictions. INT. J. PROD. RES. Vol. 42, No. 6, 1243-1256, (2004).

Horn W. A., Minimizing average flow time with parallel machines. Operations Research, 21, 846-847, (1973).

Michael X. Weng, John Lu, Haiying Ren, Unrelated parallel machine scheduling with setup consideration and a total weighted completion time objective. Int. J. Production Economics 70, 215-226, (2001).

Mokotoff E., P. A cutting plane algorithm for the unrelated parallel machine scheduling problem. European Journal of Operational Research 141, 515–525, (2002).

Pinedo M., Scheduling Theory, Algorithms, and Systems (Englewood Cliffs: Prentice Hall), (1995).

Safia Kedad-Sidhoum, Mounib Mekhilef, Unrelated parallel machine scheduling under constraints: stability number of an associated graph. IEEE, 436-441, (1997).

Silvano Martello, Francois Soumis, Paolo Toth. Exact and approximation algorithms for makespan minimization on unrelated parallel machines. Discrete Applied Mathematics 75, 169-188, (1997).