臺灣博碩士論文加值系統

排程問題本身屬於組合最佳化問題，許多研究證實大多數排程問題都為NP-hard問題，複雜度高且不易求解的問題。本研究探討給定完工順序下允許中斷開放工廠之排程問題，其中與以往不同的是工件完工的順序必須符合C1≦C2≦…≦Cn限制，並且允許工件在處理過程中可以任意中斷。本研究經由總完工時間(ΣCi)及總延遲時間(ΣTi)最小化問題之分析，證實工件的適度延後完工是對目標函數值有所助益的。針對總延遲工件數(ΣUi)最小化問題，本研究提出HEU_F和HEU_S兩種啟發式演算法來求得近似解，並利用一致性問題和非一致性問題來測試演算法之優劣。針對一致性之問題下，HEU_F演算法整體平均誤差百分比為3.07%，以及整體非最佳解之誤差比例為8.04%；HEU_S演算法整體平均誤差百分比為1.83%，以及整體非最佳解之誤差比例為0.70%。針對非一致性之問題下，HEU_S演算法整體平均誤差百分比為為24.65%，以及整體非最佳解之誤差比例為14.95%。

Most scheduling problems are NP-hard combinational optimization problems. That is, they are extremely complex and difficult to solve. In this thesis, the preemptive open shop scheduling problem with a given job completion sequence is investigated.
Without loss of generality, we assume that the jobs must be completed in the sequence C1≦C2≦…≦Cn. We first examine the problems with the objective of minimizing total completion time (ΣCi) and total tardiness (ΣTi). Both of them can be formulated as linear programs. It is shown that in some case the unforced delay of job completion may be helpful. In other words, it is not always advantageous to complete jobs as early as possible. Then, we develop two heuristics, HEU_F and HEU_S, for the problem whose objective is minimizing number of tardy jobs (ΣUi).
To evaluate the performance of the proposed heuristics, the solutions obtained are compared with optimal solutions from LINGO software. For consistent problems, heuristic HEU_F has an average relative percentage deviation of 3.07%. Also, only 8.04% of the tested instances are not optimally solved. On the other hand, heuristic HEU_S has an average relative percentage deviation of 1.83%, and only 0.70% of the tested instances are not optimally solved. For non-consistent problems, heuristic HEU_S perfroms worse. It has an average relative percentage deviation of 24.65%, and 14.95% of the tested instances are not optimally solved.

目錄

摘要 II
Abstract III
誌謝 V
目錄 VI
表目錄 VIII
圖目錄 X
第一章 緒論 1
1.1 研究背景與動機 1
1.1.1 排程問題之機器類型 1
1.1.2 排程問題的評估準則 2
1.1.3 排程問題的求解方法 4
1.2 研究目的 5
1.3 研究問題限制 7
1.4 研究內容及架構 7
第二章 文獻探討 9
2.1 總完工時間 9
2.2 總延遲時間相關文獻 10
2.3 總延遲工件數相關文獻 12
2.4 開放工廠排程問題之相關文獻 12
2.4.1 允許中斷 12
2.4.2 不允許中斷 13
2.5 最大流量問題 14
2.6 單形法 15
第三章 研究方法 19
3.1 符號定義及數學規劃模式 19
3.1.1 符號定義 20
3.1.2 數學規劃模式 20
3.2 問題特性之分析 23
3.2.1 總完工時間最小化問題之特性 24
3.2.2 總延遲時間最小化之問題之特性 34
3.3 總延遲工件數最小化問題之啟發式演算法 35
3.3.1 HEU_F啟發式演算法 36
3.3.2 HEU_S啟發式演算法 40
第四章 實驗結果 51
4.1 測試例題產生方法及評估準則 51
74.2 一致性問題測試 54
4.2.1 HEU_F及HEU_S演算法之比較 55
4.2.2 一致性問題下HEU_S求解績效之變異數分析 58
4.3 非一致性問題測試 61
4.3.1 HEU_S演算法求解品質之分析 61
4.3.2 非一致性問題下HEU_S求解績效之變異數分析 62
第五章 結論與未來研究方向 65
參考文獻 68

表目錄
表2.1 總完工時間之相關文獻整理 15
表2.2 總延遲時間之相關文獻整理 15
表2.3 總延遲工件數之相關文獻整理 16
表2.4 開放工廠之相關文獻整理 16
表3.1 Case1各工件於機器上所需處理時間 22
表3.2 Case 1各工件最早可完工時間與最佳完工時間之比較 25
表3.3 Case 2各工件於機器上所需處理時間 25
表3.4 Case 2各工件最早可完工時間與最佳完工時間之比較 26
表3.5 例題1各工件於機器上所需處理時間 26
表3.6 例題1各工件最早可完工時間與最佳完工時間之比較 27
表3.7 例題2各工件於機器上所需處理時間及交期日 30
表3.8 例題2各工件最早完可工時間與最佳完工時間之比較 30
表3.10 例題3各工件於機器上所需處理時間及交期日 34
表3.11 例題4各工件於機器上所需處理時間及交期日 38
表3.12 例題5各工件於機器上所需處理時間及交期日 43
表4.1 一致性與非一致性問題的交期日之差異 48
表4.2 HEU_F啟發式演算法在ARPD評估準則之績效(一致性問題) 50
表4.3 HEU_F啟發式演算法在NOS評估準則之績效(一致性問題) 51
表4.4 HEU_F啟發式演算法在AAD評估準則之績效(一致性問題) 51
表4.5 HEU_S啟發式演算法在ARPD評估準則之績效(一致性問題) 52
表4.6 HEU_S啟發式演算法在NOS評估準則之績效(一致性問題) 52
表4.7 HEU_S啟發式演算法在AAD評估準則之績效(一致性問題) 52
表4.8 HEU_F與HEU_S演算法平均運算時間 53
表4.9 問題影響因子與反應變數 53
表4.10 n=m問題反應變數為ARPD之變異數分析(一致性問題) 54
表4.11 n>m問題反應變數為ARPD之變異數分析(一致性問題) 54
表4.12 n=m問題反應變數為NOS之變異數分析(一致性問題) 55
表4.13 n>m問題反應變數為NOS之變異數分析(一致性問題) 55
表4.14 Om/pmtn,GCS/ΣUi問題類型的因子與反應變數ARPD 55
表4.15 驗証兩類型問題是否有差異之變異數分析(一致性問題) 56
表4.17 HEU_S啟發式演算法在NOS評估準則之績效(非一致性問題) 57
表4.18 HEU_S啟發式演算法在AAD評估準則之績效(非一致性問題) 57
表4.19 n=m問題反應變數為ARPD之變異數分析(非一致性問題) 58
表4.20 n>m問題反應變數為ARPD之變異數分析(非一致性問題) 58
表4.21 n=m問題反應變數為NOS之變異數分析(非一致性問題) 59
表4.22 n>m問題反應變數為NOS之變異數分析(非一致性問題) 59

圖目錄
圖1.1 (a)工件1的完工時間及交期日(b)工件1將完工時間延至交期日 5
圖1.2研究內容及架構 7
圖2.1最大流量問題示意圖(Liaw 2005) 13
圖2.2單形法求解之流程圖 14
圖3.1工件儘早完工情況下之細部排程 28
圖3.2總完工時間最小化之最佳解細部排程 29
圖3.3例題2工件儘早完工情形下之細部排程 31
圖3.4例題2總延遲時間最小化之最佳解細部排程 31
圖3.5HEU_F啟發式演算法流程圖 34
圖3.6HEU_S啟發式演算法流程圖 42
圖4.1產生交期日之示意圖 47

陳哲宇，「應用塔布搜尋法求解兩部機器可分割工作開放工廠總延遲時間最小化之排程問題」，碩士論文，私立朝陽科技大學工業工程與管理研究所，台中(2002)。
高小雅，「作業處理可中斷之開放工廠加權與未加權延遲工件數最小化排程之研究」碩士論文，私立朝陽科技大學工業工程與管理研究所，台中(2007)。
Achugbue, J.O., and Chin F.Y., “Scheduling the open shop to minimize mean flow time”, SIAM J. COMPUT., Vol.11, pp.709-720, (1982).
Aksjonov.V.A. , “A polynomial-time algorithm of approximate solution of a scheduling problem”, Upravlyaemye Sistemy, Vol.28, pp.273-281,(1989).
Alidaee Bahrama, Duaneb Rosa, "Scheduling Parallel Machines To Minimize Total Weighted And Unweighted Tardiness", Computers & Operations Research, Vol. 24, No 8, pp.775-788,(1997).
Amaral Armentano, V. V., Rigao Scrich, C., "Tabu Search For Minimizing Total Tardiness In A Job Shop", International Journal Of Production Economics, Vol. 63, No. 2, pp.131-140,(2000).
Deman, V., John, M., and Baker, K.R., “Minimizing mean flow time in the flow shop with no intermediate queues”, AIIE Transactions, Vol.6, No.1, pp.28-34,(1974).
Dorit S. Hochbaum, Ron Shamir “Minimizing the number of tardy job units under release time constraints”, Discrete Applied Mathematics, Vol. 28, pp. 45-57,(1990).
Du, J., Leung, J. Y. T., “Minimizing Total Tardiness On One Processor Is NP Hard”, Mathematics Of Operations Research, Vol. 3, pp.483-495,(1990).
Du, J.Z., and Leung, Y.T., “Minimizing mean flow time in two-machine open shops and flow shops”, Journal of Algorithms, Vol.14, pp.24-44,(1993).
Elmaghraby, S.E., and Park, S.H., “Scheduling jobs on a number of identical machines”, AIIE Transactions, Vol.6, pp.1-13,(1974).
Emmett Lodree Jr, Wooseung Jang, Cerry M. Klein “A new rule for minimizing the number of tardy jobs in dynamic flow shops”, European Journal of Operational Research, Vol. 159, pp.258-263,(2004)
Emmons, H., “One Machine Sequencing To Minimize Certain Function Of Job Tardiness”, Operations Research, Vol. 17, pp.701-715,(1969).
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).
Eui-Seok Byeon, S. David Wu, Robert H. Storer, “Decomposition Heuristics For Robust Job Shop Scheduling”, IEEE Transactions On Robotics And Automation, Vol. 14, No. 2, pp.303-313,(1998).
Garey, M.R., Johnson, D.S., and Sethi, R., “Complexity of flowshop and jobshop scheduling”, Mathematics of Operations Research, Vol.1, No.2, pp.117-129,(1976).
Gonzalez, T., and Sahni, S., “Open shop scheduling to minimize finish time”, JACM, Vol.23, No.4, pp.665-679,(1976).
Graham, R.L., Lawler, E.L., Lenstra, J.K.,& Rinnooy Kan, A. H. G., “Optimization and approximation in deterministic sequencing and scheduling: a survey”, Annals of Discrete Mathematics, Vol. 5, pp.287-326,(1979).
Gursel A. Suer, Zbigniew Czajkiewicz “ A heuristic procedure to minimize number of tardy jobs and total tardiness in single machine scheduling”, Computers & Industrial Engineering, Vol. 23, pp.145-148,(1992).
He, Z., Yang, T., and Deal, D.E, “A multiple-pass heuristic rule for job shop scheduling with due dates”, International Journal of Production Research, Vol. 31, pp.2677-2692, (1993).
Hirakawa Yasuhiro, “A Quick Optimal Algorithm For Sequencing On One Machine To Minimize Total Tardiness”, International Journal Of Production Economics, Vol. 60-61, pp.549-555,(1999).
Ho, J.C., and Chang, Y.L., “New heuristic for n-job, m-machine flow shop problem”, European Journal of Operational Research, Vol.52, No.2, pp.194-202,(1991).
Holthans, O., and Rajendran, C., “Efficient dispatching rules for scheduling in a job shop”, International Journal of Production Economics, Vol.48, No.1, pp.87-105,(1997).
Johnny C. Ho, Yih-Long Chang “Minimizing the number of tardy jobs for m parallel machines”, European Journal of Operational Research, Vol. 84, pp. 343-355,(1995).
Kim Y., “A New Branch And Bound algorithm For Minimizing Mean Tardiness In Two-Machine Flowshop”, Computer & Operations Research, Vol. 20, pp.391-401,(1993).
Kim Y., “Minimizing Mean Tardiness On Flowshop”, European Journal Of Operation Research, Vol.85, pp. 541-555,(1995).
Koksalan, M., Azizoglu, M., Kondakci, and Koksalan, S., “Minimizing flowtime and maximum earliness on a single machine”, IIE Transactions (Institute of Industrial Engineerings), Vol.30, No.2, pp.192-200,(1998).
Lawler E.L., “On Scheduling With Deferral Cost”, Management Science, Vol.11, pp.280-288,(1964).
Lawler, E. L., Lenstra, J. K., and Rinnooy Ken A. H. G., “Minimizing maximum lateness in a two-machine open shop”, Math.of Operations Research, Vol.6, No.1, pp.153-158,(1981).
Lawler, E. L., Lenstra, J. K., and Rinnooy Ken A. H. G., “Minimizing maximum lateness in a two-machine open shop”, Math.of Operations Research, Vol.6, No.1, pp.153-158,(1981).
Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., and Shmoys, D.B.,“Sequencing and Scheduling: Algorithms and Complexity”, Center for Mathematics and Computer Science, P.O. Box 4079, 1009 AB Amsterdam, The Netherlands (1989).
Liaw, C., “A Tabu search algorithm for the open shop scheduling problem”, European Journal of Operational Research, Vol.26, No.2, pp.109-126,(1999).
Liaw, C., “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).
Liaw, C., “Multi-machine scheduling problems”, Master thesis, Dept. of Industrial Management, National Cheng-Kung Univ., Taiwan(1987).
Liaw, C., 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).
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).
Liu, C.Y., and Bulfin, R.L., “Scheduling ordered open shops”, Computers & Operations Research, Vol.14, No.3, pp.257-264,(1987)
Mckoy, D.H.C., and 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).
Ramudhin,A.,and Maruer,P., “The generalized shifting bottleneck procedure”, Europen Journal of Operational Research, Vol.93, pp.34-48, (1996).
Root, J. G., “Scheduling With Deadlines And Loss Functions On K Parallel Machine”, Management Science, Vol. 14, pp.460-475,(1965).
Sabuncuoglu, I., Bayiz, M., “Job Shop Scheduling With Beam Search”, European Journal Of Operations Research, Vol. 118, pp.390-412,(1999).
Sethi, R., “On the complexity of mean flow time scheduling”, Mathematics of Operations Research, Vol.2, No.4, pp.320-330,(1977).
Sun, D., and Batta, R., “Scheduling large job shop: A decomposition approach”, International Journal of Production Research, Vol.34, No.7, pp.2019-2033,(1996).
Szwarc, W., “Flow shop problem with mean completion time criterion”, IIE Transactions Institute of Industrial Engineering, Vol.15, No.2, pp.172-176,(1983).
Townsend W., “Sequencing n Jobs on m Machine to Minimize Maximum Tardiness”, Vol.23, pp.1016-1019,(1977).
Tsung-Che Chiang, Li-Chen Fu “Using a family of critical ratio-based approaches to minimize the number of tardy jobs in the job shop with sequence dependent setup times”, European Journal of Operational Research, Vol. 196, pp.78-92,(2009).
Webster, S., “Weighted flow time for scheduling identical processors”, European Journal of Operational Research, Vol.80, No.1, pp. 103-111, (1995).
Woo, H.S., and Yeh, D.S., “Heuristic algorithm for mean flowtime objective in flow shop scheduling”, Computers & Operations Research, Vol.25, No.3, pp.175-182,(1998).
Zaloom, V., and Vatz, D., “Note on optimal scheduling of two parallel processors”, Naval Research Logistics Quarterly, Vol.22, No.4, pp.823-827,(1975).