臺灣博碩士論文加值系統

在過去二十年，具有退化效果的排程問題受到極大的關注。然而，同時考慮群組技術的問題相對地很少被討論。隨著現代社會所強調的客戶服務和滿足所承諾的交貨日期，我們探討一個具有退化效果(deteriorating jobs)和前置時間(setup time)的單機排程問題，目標函數為延遲工作的總加權個數(weighted number of late jobs)最小化。我們提出一個分枝界限演算法(branch-and-bound algorithm)藉由幾個凌越性質和下界值(lower bound)來尋找最佳解。電腦模擬實驗結果印證，分枝界限法可以在合理的時間內解出高達1500個工作件的例子。我們並利用統計方法測試各參數的有效性。

Deteriorating jobs scheduling has received tremendous attention in the past two decades. However, the group technology has rarely been considered. With the current emphasis on customer service and meeting the promised delivery dates, we consider a single-machine scheduling problem to minimize the total weighted number of late jobs with deteriorating jobs and setup times. A branch-and-bound with several dominance properties and a lower bound is developed to solve this problem. Computational results show that the proposed algorithm can solve instances up to 1,500 jobs. In addition, statistical tests are conducted to investigate the impact of the parameters.

目錄
第一章 緒論 1
1.1研究架構 1
1.2 研究背景與目的 3
1.3文獻探討 4
第二章 問題描述 7
2.1 假設與符號 7
2.2 目標函數 8
第三章 分支界限法運算 11
3.1 推導凌越性質 11
3.2 下界值 21
3.3 啟發式演算法程序 24
3.4 分枝界限法 27
第四章 模擬實驗 29
4.1 模擬資料設定 29
4.2 分析模擬結果 30
第五章 結論 42
參考文獻 42

圖目錄
圖1.1 研究架構之流程圖 2
圖4.1群組數變動對平均節點數之影響(包含啟發式演算法) 32
圖4.2 群組數變動對平均節點數之影響(不含啟發式演算法) 33
圖4.3 啟發式演算法對平均枝節點數之影響(n=80,m=20) 34
圖4.4 啟發式演算法對平均枝節點數之影響(n=80,m=50) 34
圖4.5 啟發式演算法對平均枝節點數之影響(n=80,m=80) 35
圖4.6 變動對平均枝節點數之影響(n=80,m=20) 36
圖4.7 變動對平均枝節點數之影響(n=80,m=50) 36
圖4.8 變動對平均枝節點數之影響(n=80,m=80) 37
圖4.9 成對母體平均數檢定 39
圖4.10 三因子變異數分析 42
表目錄
表4.1 分枝界限法逐一加入凌越性質，和下界值之模擬結果 31
表4.2 分枝界限法和啟發式演算法之模擬結果(n= 80) 38
表4.3分枝界限法對大量工作件數之模擬結果 41

[1] B. Alidaee and N.K. Womer, Scheduling with time dependent processing times: Review and extensions, Journal of the Operational Research Society 50 (1999), 711-720.
[2] A. Allahverdi, J.N.D. Gupta and T. Aldowaisan, A review of scheduling research involving setup considerations, Omega, The International Journal of Management Sciences 27 (1999), 219-239.
[3] S. Browne and U. Yechiali, Scheduling deteriorating jobs on a single processor, Operations Research 38 (1990), 495-498.
[4] T.C.E. Cheng, Q. Ding, M.Y. Kovalyov, A. Bachman and A. Janiak, Scheduling jobs with piecewise linear decreasing processing times, Naval Research Logistics 50(6) (2003), 531-554.
[5] T.C.E. Cheng, Q. Ding and B.M.T. Lin, A concise survey of scheduling with time-dependent processing times, European Journal of Operational Research 152 (2004), 1-13.
[6] M.L. Fisher, A dual algorithm for the one-machine scheduling problem, Mathematical Programming 11 (1976), 229-251.
[7] S. French, Sequencing and Scheduling: An Introduction to the Mathematics of the Job-Shop. Ellis Horwood Ltd, 1982.
[8] S. Gawiejnowicz, Scheduling deteriorating jobs subject to job or machine availability constraints, European Journal of Operational Research 180 (2007), 472-478.
[9] S. Gawiejnowicz, Time-Dependent Scheduling, Monographs in Theoretical Computer Science, An EATCS Series, Springer, Berlin-Heidelberg 2008.
[10] J.N.D Gupta and S.K. Gupta, Single facility scheduling with nonlinear processing times, Computers and Industrial Engineering 14 (1988), 387-393.
[11] M. Ji and T.C.E. Cheng, An FPTAS for scheduling jobs with piecewise linear decreasing processing times to minimize makespan, Information Processing Letters 102 (2007), 41-47.
[12] M. Ji and T.C.E. Cheng, An FPTAS for parallel-machine scheduling under a grade of service provision to minimize makespan, Information Processing Letters 108 (2008), 171-174.
[13] R.M. Karp, Reducibility among combinatorial problems, in: RE Miller and JW Thatcher (Eds.) Complexity of Computer Computations, Plenum Press, New York, 1972.
[14] W. Kubiak and S.L. Van de Velde, Scheduling deteriorating jobs to minimize makespan, Naval Research Logistics 45 (1998), 511-523.

[15] A.S. Kunnathur and S.K. Gupta, Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem, European Journal of Operational Research 47 (1990), 56-64.
[16] W.C. Lee, C.C. Wu, Y.H. Chung and H.C. Liu, Minimizing the total completion time in permutation flow shop with machine-dependent job deterioration rates, Computers & Operations Research 36 (2009), 2111-2121.
[17] Y. Li, G. Li, L. Sun and Z. Xu, Single machine scheduling of deteriorating jobs to minimize total absolute differences in completion times, International Journal of Production Economics 118 (2009) 424-429.
[18] G. Mosheiov, -shaped policies to schedule deteriorating jobs, Journal of the Operational Research Society 47 (1996), 1184-1191.
[19] C.T. Ng, J.B. Wang, T.C.E. Cheng and L.L. Liu, A branch-and-bound algorithm for solving a two-machine flow shop problem with deteriorating jobs, Computers & Operations Research 37 (2010), 83-90.
[20] N.P. Rachaniotis and C.P. Pappis, Scheduling fire fighting tasks using the concept of deteriorating jobs, Canadian Journal of Forest Research 36 (2006), 652-658.
[21] J.B. Wang and Z.Q. Xia, Flow shop scheduling with deteriorating jobs under dominating machines, Omega, The International Journal of Management Sciences 34 (2006), 327-336.
[22] J.B. Wang JB, C.T. Ng and T.C.E. Cheng, Single-machine scheduling with deteriorating jobs under a series–parallel graph constraint, Computers & Operations Research 35 (2008), 2684-693.
[23] S. Webster and K.R. Baker, Scheduling groups of jobs on a single machine, Operations Research 43 (1995), 692-703.
[24] C.C. Wu and W.C. Lee, Single-machine group-scheduling problems with deteriorating setup times and job-processing times, International Journal of Production Economics 115 (2008), 128-133.
[25] C.C. Wu, Y.R. Shiau and W.C. Lee, Single-machine group scheduling problems with deterioration consideration, Computers and Operations Research 35 (2008), 1652-1659.
[26] W.H. Yang and S. Chand, Learning and forgetting effects on a group scheduling problem, European Journal of Operational Research 187 (2008), 1033-1044.
[27] Y. Yan, D.Z. Wang, D.W. Wang, W.H. Ip and H.F. Wang, Single machine group scheduling problems with the effects of deterioration and learning, Acta Automatica Sinica 35 (2009), 1290-1295.
[28] X. Zhang and G. Yan, Single-machine group scheduling problems with deteriorated and learning effect, Applied mathematics and Computation (2010), doi: 10.1016/j.amc.2010.02.018.
[29] T.C.E. Cheng and Q. Ding, The complexity of scheduling starting time dependent tasks with release times, Information Processing Letters 65 (1998), 75-79.