臺灣博碩士論文加值系統

在這一篇論文中，我們考慮兩個單機排程問題，其工作的執行時間是一個由工作開始時間以及工作到期日所組成的非線性階段化函數。在第一個題目中，我們的目標是考慮將所有獨立工作中的最大工作完成時間最小化，而且假設每一個工作均被指定不同的到期日。對於第二個問題，所有工作共有相同的到期日，而我們期望的目標函數是將總(平均)工作完成時間最小化。
以上兩個問題的時間複雜度已在文獻中被證明為NP-hard。在此篇論文中，我們首先提出一個具有虛擬多項式時間複雜度的動態規劃演算法來證明第一個問題是NP-hard in the ordinary sense。接來下，從實用的觀點，我們設計分支界定演法以求取最佳解。而為使其達到較佳的效能，我們先會提出數個重要的性質，其包括可行性解的下界函數，優先法則以及消去法則。
最後，我們經由數據實驗來檢視所提出演算法的實際效能，實驗數據顯示我們所提出的性質的確在求解過程有效地避免不必要的搜尋，且其結合數個性質所產生的綜合效果具有足以在數秒之內求解至一百個工作的能力。

In this thesis, we study two single-machine scheduling problems. The processing time of a job is a non-linear step function of its starting time and due date. In the first problem, different due dates are assigned to the jobs and our goal is to minimize the makespan. In the second problem, a due date is common to all jobs and the objective is to minimize the total completion time.
These two problems are already known to be NP-hard in the literature. In this thesis, we first show that the makespan problem is actually NP-hard in the ordinary sense by proposing a pseudo-polynomial time dynamic programming algorithm. Besides, to derive optimal solutions from a practical perspective, we develop several properties, including lower bounds, dominance rules and elimination rules, to facilitate the design of branch-and-bound algorithms.
Through computational experiments, we show that the proposed properties are effective in curtailing unnecessary exploration during the solution finding process and that the synergy of these properties can solve problems with up to one hundred jobs in a few seconds.

Abstract i
中文摘要 ii
Acknowledgement iii
Table of Contents iv
List of Figures vi
List of Tables vi
Chapter 1 Introduction 1
1.1 Background 1
1.2 Motivation and Research Issues 2
1.3 Research Methods 4
1.4 Problem Statements and Notation 5
1.5 Structure of the Thesis 8
Chapter 2 Dynamic Programm for 1/ pi= ai or ai+ bi, di / Cmax 9
2.1 Optimality Conditions 9
2.2 DP Algorithm 10
2.3 Time Complexity 11
Chapter 3 Branch-and-Bound Algorithm for 1/ pi= ai or ai+ bi, di / Cmax 13
3.1 Enumeration Tree 13
3.2 Lower Bound 14
3.3 Elimination Rules 21
Chapter 4 Branch-and-Bound Algorithm for 1/ pi= ai or ai+ bi, di= d/ ΣCi 23
4.1 Enumeration Tree 24
4.2 Lower Bound 24
4.3 Elimination Rules 27
Chapter 5 Computational Study 34
5.1 Descriptions of Experimental Setting 34
5.2 Results and Analysis of 1/ pi= ai or ai+ bi, di / Cmax 36
5.3 Results and Analysis of 1/ pi= ai or ai+ bi, di= d / ΣCi 41
Chapter 6 Concluding Remarks and Future Research 45
6.1 Summary of Contributions 45
6.2 Future Research 46
References 48
Appendix: Derivation of ij 51

[1] B. Alidaee and N.K. Womer (1999). Scheduling with time dependent processing times: Review and extensions. Journal of the Operational Research Society, Vol. 50, pp. 711—720.
[2] Z.L. Chen (1995). A note on single-processor scheduling with time-dependent execution times. Operations Research Letters, Vol. 17, pp. 127—129.
[3] Z.L. Chen (1996). Parallel machine scheduling with time-dependent processing times. Discrete Applied Mathematics, Vol. 70, pp. 81—93.
[4] T.C.E. Cheng and Q. Ding (1998). The complexity of single machine scheduling with release times. Information Processing Letters, Vol. 65, pp. 95—100.
[5] T.C.E. Cheng and Q. Ding (2000). Single machine scheduling with deadlines and increasing rate of processing times. Acta Informatica, Vol. 36, pp. 673—692.
[6] T.C.E. Cheng and Q. Ding (2001). Single machine scheduling with step-deteriorating processing times. European Journal of Operational Research, Vol. 134, pp. 623—630.
[7] T.C.E. Cheng, B.M.T. Lin and A. Toker (2000). Makespan minimization in the two-machine flowshop batch scheduling problem. Naval Research Logistics, Vol. 47, pp. 128—134.
[8] T.C.E Cheng, Q. Ding and B.M.T. Lin (2003).A concise survey of scheduling with time-dependent processing times. To appear in European Journal of Operational Research.
[9] M.R. Garey and D.S. Johnson (1979).Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York.
[10] R.L. Graham, E.L. Lawler, J.K. Lenstra and A.H.G. Rinooy Kan (1976). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, Vol. 5, pp. 287—326.
[11] J.N.D. Gupta and S.K. Gupta (1988). Single facility scheduling with nonlinear processing time. Computers and Industrial Engineering, Vol.14, pp. 387—393.
[12] S.K. Gupta, A.S. Kunnathur and K. Dandapai (1987). Optimal repayment policies for multiple loans. Omega, Vol.15, pp. 323—330.
[13] Y.S. Hsu and B.M.T. Lin (2002).Minimization of maximum lateness under linear deterioration. Manuscript submitted for publication.
[14] A.S. Kunnathur and S.K. Gupta (1990). Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem. European Journal of Operational Research, Vol.47, pp. 56—64.
[15] W. Kubiak and S.L. van de Velde (1998). Scheduling deteriorating jobs to minimize makespan. Naval Research Logistics, Vol. 45, pp. 511—523.
[16] B.M.T. Lin and J.M. Wu (2002). A new lower bound for the minimization of total completion time in a two-machine flowshop, Proceedings of the APIEMS 2002, Taipei, Taiwan.
[17] G. Mosheiov (1991). V-shaped policies to schedule deteriorating jobs. Operations Research, Vol. 39, pp. 979—991.
[18] G. Mosheiov (1994). Scheduling jobs under simple linear deterioration. Computers and Operations Research, Vol.21, pp. 653—659.
[19] G. Mosheiov (1995). Scheduling jobs with step-deterioration: Minimizing makespan on a single and multi-machine. Computers & Industrial Engineering, Vol. 28, pp. 869—879.
[20] G. Mosheiov (1996b). Λ-shaped polices to schedule deteriorating jobs. Journal of the Operational Research Society, Vol. 47, pp. 1184—1191.
[21] P.S. Sundararaghavan and A.S. Kunnathur (1994). Single machine scheduling with start time dependent processing times: Some solvable cases. European Journal of Operational Research, Vol. 79, pp. 394—403.
[22] V.S. Tanaev, V.S. Gordon and Y.M. Shafransky (1994). Scheduling Theory, Single-stage Systems. Kluwer, Dordrecht, Germany.