臺灣博碩士論文加值系統

本論文將探討開放型工廠(Open Shop)在允許中斷(Preemption)限制下，最小化總完工時間(Minimize Total Completion Time)之排程問題，以排程符號表示為 問題，此問題已被證明為NP-hard問題。
本研究旨在發展一分枝界限演算法(Branch-and-Bound Algorithm)來求解上述問題。其中結合線性規劃(Linear Programming)、上限值演算法及下限值演算法等，使分枝的過程中，有效刪除無用節點數，加快求解的效率。
最後，經由電腦大量隨機產生的測試例題，評估所發展之分枝界限演算法與其他現有方法的結果進行比較，結果顯示此分枝界限演算法可有效地縮短執行時間，而且本研究所設計之上限值演算法及下限值演算法均有較佳的品質。

This paper examines the open shop scheduling problem with preemption under the objective of minimize total completion time. The problem is denoted by , and is known to be a NP-hard problem.
An improved branch-and-bound algorithm is developed to solve problems under completion. A linear programming model is used to determine the optimal job completion times when the job completion sequence is fixed. Also, both upper bound and lower bound are incorporated into the algorithm to effectively prune unpromising nodes during the search process.
The performance of the proposed branch-and-bound algorithm is evaluated through randomly generated test problems. The algorithm is compared with other existing algorithms in the literature. The results show that the proposed algorithm significantly improves other existing algorithms in terms of computation time. Moreover, the proposed upper and lower bounds can effectively cut down the search space and improve the algorithm’s efficiency.

目錄
摘要 I
Abstract II
誌謝 III
目錄 IV
表目錄 VI
圖目錄 VII
第一章 緒論 1
1.1研究背景與動機 1
1.2排程問題的種類 2
1.2.1排程之機器環境 2
1.2.2工件之加工特性與限制 3
1.2.3排程之績效指標 4
1.3排程問題的求解 5
1.3.1派工法則 5
1.3.2最佳解法 5
1.3.3近似解法 6
1.4研究目的 6
1.5研究問題描述與限制 7
1.6研究步驟與架構 8
第二章 文獻探討 10
2.1單機排程 10
2.2平行機排程 10
2.3流程型工廠 11
2.4零工型工廠 12
2.5開放型工廠 13
2.5.1不允許中斷 13
2.5.2允許中斷 14
2.6文獻彙整 15
第三章 研究方法 17
3.1符號定義 17
3.2分枝界限演算法 18
3.3分枝法則 19
3.4搜尋策略 20
3.5線性規劃 21
3.6上限演算法 23
3.7下限演算法 25
3.7.1下限值演算法一(LB1) 25
3.7.2下限值演算法二(LB2) 27
第四章 實例驗證 29
4.1產生測試例題 29
4.2驗證上、下限值演算法之績效 29
4.2.1驗證上限值 30
4.2.2驗證下限值 31
4.3與現有方法[35]之績效比較 32
4.3.1比較上限值 32
4.3.2比較下限值 33
4.3.3比較求解時間與節點數 35
4.4評估添加限制式之效益 37
第五章 結論與建議 39
5.1結論 39
5.2未來研究方向 40
參考文獻 41


表目錄
表2.1 單機、平行機、流程型、零工型文獻彙整 .......................................... 15
表2.2 開放型文獻彙整 ...................................................................................... 16
表3.1 工件在機器上的加工時間Pij ................................................................. 24
表3.2 工件之總處理時間依SPT 法則重新編列 ............................................. 24
表3.3 工件順序代入線性規劃求解所得之上限值 .......................................... 24
表3.4 每台機器上未排序工件依SPT 重新編列 ............................................. 26
表3.5 未排序工件在機器上的完工時間 .......................................................... 26
表4.1 init_UB 與opt 之績效驗證 ..................................................................... 30
表4.2 init_LB 與opt 之績效驗證 ...................................................................... 31
表4.3 UB_C 與UB_Z 之績效比較 ................................................................... 32
表4.4 LB_C 與LB_Z 之績效比較 ..................................................................... 34
表4.5 節點數與求解時間之比較績效 .............................................................. 35
表4.6 添加限制式(6)對求解時間之影響 ......................................................... 37


圖目錄
圖1.1 研究流程圖 ............................................................................................... 9
圖3.1 分枝圖 ..................................................................................................... 19
圖3.2 深度優先搜尋 ......................................................................................... 20
圖3.3 廣度優先搜尋 ......................................................................................... 20
圖3.4 添加限制式示意圖 ................................................................................. 22
圖3.5 現階段工件已排序之甘特圖 ................................................................. 28
圖3.6 所有工件皆已排序之甘特圖 ................................................................. 28
圖4.1 工件數對上限值的影響 ......................................................................... 30
圖4.2 機器數對上限值的影響 ......................................................................... 30
圖4.3 工件數對下限值的影響 ......................................................................... 31
圖4.4 機器數對下限值的影響 ......................................................................... 31
圖4.5 工件數對兩上限值差距的影響 ............................................................. 33
圖4.6 機器數對兩上限值差距的影響 ............................................................. 33
圖4.7 工件數對兩下限值差距的影響 ............................................................. 34
圖4.8 機器數對兩下限值差距的影響 ............................................................. 34
圖4.9 節點數之績效比較 ................................................................................. 36
圖4.10 求解時間之績效比較 ........................................................................... 36
圖4.11 添加限制式(6)對求解時間的影響 ...................................................... 38

參考文獻
[1]Graham, T., Lawer, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., “Optimization and approximation in eterministic sequence and scheduling a survey”, Annals of Discrete Mathematics, Vol.5, pp.287-326 (1979).
[2]Emmons, H., “One machine sequencing to minimize mean flow time with minimum number tardy”, Naval Research Logistics Quarterly, Vol.22, No.3, pp.585-592 (1975)
[3]Koksalan, M., Azizoglu, M., Kondakci, Koksalan, S., “Minimizing flowtime and maximum earliness on a single machine”, Institute of Industrial Engineerings, Vol.30, No.2, pp.192-200 (1998)
[4]Zaloom, V., Vatz, D., “A note on the optimal scheduling of two parallel processors”, Naval Research Logistics Quarterly, Vol.22, No.4, pp.823-827 (1975)
[5]Webster, S., “Weighted flow time bounds for scheduling identical processors”, European Journal of Operational Research, Vol.80, No.1, pp.103-111 (1995)
[6]Azizoglu, M., Kirca, O., “On the minimization of total weighted flow time with identical and uniform parallel machines”, European Journal of Operational Research, Vol.113, pp.91-100 (1999)
[7]Salem, A., Anagnostopoulos, G.C., Rabadi, G., “A branch-and-bound algorithm for parallel machine scheduling problems”
[8]Johnson, S. M., “Optimal two- and three-stage production schedules with setup times included”, Naval Research Logistics Quarterly, Vol.1, No.1, pp.61–68 (1954)
[9]Garey, M.R., Johnson, D.S., Sethi, R., “ The complexity of flowshop and jobshop scheduling”, Mathematics of Operations Research, Vol.1, No.2, pp.117-129 (1976)
[10]Croce, F.D., Narayan, V., Tadeia, R., “The two-machine total completion time flow shop problem”, European Journal of Operational Research, Vol.90, No.2, pp.227-237 (1996)
[11]Ravindran, D., Selvakumar, S.J., Sivaraman, R., Noorul Haq, A., “Flow shop scheduling with multiple objective of minimizing makespan and total flow time”, The International Journal of Advanced Manufacturing Technology, Vol.25, No.9-10, pp.1007-1012 (2005)
[12]Deman, V., John, M., Baker, K.R., “Minimizing mean flowtime in the flow shop with no intermediate queues”, AIIE Transactions, Vol.6, No.1, pp.28-34 (1974)
[13]Rajendran, C., Chaudhuri, D, “Heuristic algorithms for Continuous Flow-Shop Problem” Naval Research Logistics, Vol.37, No.5, pp.695-705 (1990).
[14]T’Kindt, V., Gupta, J.N.D., Billaut, J.C., ”A Branch-and-Bound algorithm to Solve a Two-Machine Bicriteria Flowshop Scheduling Problem”,ORP3, PARIS, 26-29 September (2001)
[15]Adams, J., Balas, E., Zawack, D., “The shifting bottleneck procedure for job shop scheduling”, Management Science, Vol.34, No.3, pp.391-401 (1988)
[16]Applegate, D., Cook, W., “A computational study of the job shop scheduling problem,” ORSA Journal on Computing, Vol. 3, No.2, pp.149-156 (1991)
[17]Mckoy, D.H.C., Egbelu, P.J., “Minimizing production flow time in a process and assembly job shop”, International Journal of Production Research, Vol.36, No.8, pp.2315-2332 (1998)
[18]Sun, D., Batta, R., “Scheduling large job shop: A decomposition approach”, International Journal of Production Research, Vol.34, No.7, pp.2019-2033 (1996)
[19]Brucker, P., Jurisch, B., Sievers, B., “A branch and bound algorithm for the job-shop scheduling problem”, Discrete Applied Mathematics, Vol.49, No.1-3, pp.107-127 (1994)
[20]Achugbue, J.O., Chin, F.Y., “Scheduling the open shop to minimize mean flow time”, Society for Industrial and Applied Mathematics, Vol.11, No.4, pp.709-720 (1982)
[21]Brucker, P., Johann, H., Bernd, J., Birgit, W., “A Branch & Bound Algorithm for the Open Shop Problem”, Discrete Applied Mathematics, Vol.76, No.1-3, pp. 43-59 (1997)
[22]Gueret, C., Prins, C., “Classical and new heuristics for the open-shop problem: A computational evaluation”, European Journal of Operational Research, Vol.107, No.2, pp.306-314 (1998)
[23]Gonzalez, T., Sahni, S., “Open shop scheduling to minimize finish time”, Journal of the Assooauon for Computing Machinery, Vol.23, No.4, pp.665-679 (1976)
[24]Liaw, C. F., “An iterative improvement approach for the non-preemptive open shop scheduling problem”, European Journal of Operational Research, Vol.111, No.3, pp.509-517 (1998)
[25]Liaw, C. F., Cheng C. Y., Chen, M., “The total completion time open shop scheduling problem with a given sequence of jobs on one machine”, Computers & Operations Research, Vol. 29, pp. 1251-1266 (2002)
[26]Tang, L., Bai, D., “A new heuristic for open shop total completion time problem”, Applied Mathematical Modelling, Vol.34, No.3, pp 735-743 (2010)
[27]Du, J., Leung, J.Y.T., ”Minimize mean flow time in twomachine open-shops and flow-shops”, Journal of Algorithms, Vol.14, No.1, pp.24-44 (1990)
[28]Liu, C. Y., Bulfin, R. L., “On the complexity of preemptive open-shop scheduling problems”, Operations Research Letter, Vol.4, No.2, pp.71-74 (1985)
[29]Cho, Y., Sahni, S., “Preemptive scheduling of independent jobs with release and due time on open, flow and job shop”, Operations Research, Vol.29, No.3, pp.511-522 (1981)
[30]Brasel, H., Hennes, H., “On the open-shop problem with preemption and miniminzing the average completion time”, European Journal of Operational Research, Vol.157, No.3, pp.607-619 (2004).
[31]Liu, C. Y., Bulfin, R. L., “Scheduling ordered open shops”, Computers & Operations Research, Vol. 14, No. 3, pp.257-264 (1987)
[32]Liu, C. Y., “A branch and bound algorithm for the preemptive open shop scheduling problem”, Journal of the Chinese Institute of Industrial Engineers, Vol. 12, No. 1, pp.25-31 (1995)
[33]Liaw, C. F., “Scheduling two-machine preemptive open shops to minimize total completion time”, Computers & Operations Research, Vol.31, No.8, pp.1349-1363 (2004)
[34]陳怡聲，「允許中斷之開放工廠總完工時間最小化問題之研究」，碩士論文，私立朝陽科技大學工業工程與管理研究所，台中(2002)
[35]曾佳盈，「以分枝界限法求解可中斷式開放工廠排程問題」，碩士論文，私立朝陽科技大學工業工程與管理研究所，台中(2011)