本篇論文主要研究的主題是考慮具有階段退化性工作之單機排程，而其工作之執行時間是一個由工作開始的時間 及工作到期日 所組成的非線性階段退化函數，同時假設每一個工作件具有不同的到期日。本文的目標是找出一個排程使得所有的工作件的總完工時間（total completion time）之和達到最小化。相關文獻已證實解此問題的演算複雜度(complexity)為「NP-complete」。
本篇論文將用分枝界限法(branch-and-bound method)進行搜尋最佳化之解。首先，本文將導出相關的刪除性質(dominance properties)以及下界值(lower bound)，進而發展出分枝界限法。最後，本文提出2個近似解演算法(Heuristic Algorithms)。
經由模擬數據顯示，本文所建立的分枝界限法在合理時間可解到24個工作件數的問題。另外，對於工作件的到期日具有較小變異數與平均數的排程問題，不論是在搜尋時間上或是節點數上均有良好的成效。除此之外，本文所提出的近似解其誤差非常小。由此結果更可以顯示出，近似演算法對於工作件數很大之排程問題，將是一個非常具有經濟效益的方法。

In many real situations, it is found that if certain maintenance procedures fail to be completed prior to a pre-specified deteriorating date, then the jobs will require extra time for successful completion. In this thesis, a single-machine total completion time problem with stepwise deteriorating jobs is considered. A branch-and-bound method incorporated with several dominance properties and a lower bound was developed to derive the optimal solution for this problem. In addition, a weight-combination search algorithm is proposed to search for the near-optimal solution. Computational results indicate that the branch-and-bound algorithm can solve most of the problems for up to 24 jobs in a reasonable amount of time. Moreover, the proposed heuristic algorithm is accurate with mean error percentages of less than 0.3%.

CONTENTS
1 INTRODUCTION 1
1.1 Motivation and background 1
1.2 Problem descriping and notations 3
1.3 Research objective and methods 4
1.4 Structure of the thesis 5
2 LITERATURE REVIEW 7
3 BRANCH-AND-BOUND ALGORITHM 12
3.1 The branch and bound method 12
3.2 Branching strategy 13
3.3 Lower bound 16
3.4 Dominance properties 18
3.5 Procedures of the branch-and-bound method 25
4. HEURISTIC ALGORITHMS 27
4.1 Heuristic design 27
4.2 Range of parameters and in the heuristics 30
4.3 Determine partition numbers in the heuristics 39
5 SIMULATIONS AND ANALYSIS 48
5.1 Data simulations 48
6 CONCLUSIONS AND FUTURE RESEARCH 58
REFERENCES 60




List of Figures

Figure 1.1 Research flow chart 6
Figure 3.1 Graph of depth search branching strategy 15
Figure 4.1 Errors for different weight 29
Figure 4.2 Minimal mean error percentage of different for data 1
Data 1: 38
Figure 4.3 Minimal mean error percentage of different for data 2
Data 2: 38
Figure 4.4 Minimal mean error percentage of different for data 3
Data 3: 39
Figure 5.1 Mean error percentage of heuristic algorithm without pair-wise interchange for three different intervals. 50
Figure 5.2 Mean error percentage of heuristic algorithm with pair-wise interchange for three different intervals. 50
Figure 5.3 Max error percentage of heuristic algorithm without pair-wise interchange for three different intervals. 51
Figure 5.4 Max error percentage of heuristic algorithm with pair-wise interchange for three different intervals. 51
Figure 5.5 Mean CPU time of the branch-and-bound method under different job numbers. 54


Figure 5.6 Max CPU time of the branch-and-bound method under different job numbers. 54
Figure 5.7 Mean node numbers of the branch-and-bound method under different job numbers. 55
Figure 5.8 Max node numbers of the branch-and-bound method under
different job numbers. 55




























List of Tables

Table 3.1 Data for explaining how to calculate the lower bound in a 10-job problem with two scheduled jobs. 17
Table 4.1 Illustrative examples for 10 jobs. 28
Table 4.2 Heuristic results and errors of the examples. 29
Table 4.3 Mean error percentage of different weights of for data 1
Data 1: d interval = (0, .........……………………………32
Table 4.4 Mean error percentage of different weights of for data 2
Data 2: d interval = , )...…………………………….34
Table 4.5 Mean error percentage of different weights of for data 3
Data 3: d interval = (0, ).........………………………………36
Table 4.6 Performance for both proposed heuristics under various due dates and partitions. 41
Table 4.7 Data for explaining how to calculate the near-optimal solution by in a 5-job problem. 44
Table 5.1 Performance for both proposed heuristics under various intervals. 49
Table 5.2 CPU time of finding the optimal solution by the branch-and-bound
method under different job numbers n for three d intervals. 53
Table 5.3 Nodes of finding the optimal solution by the branch-and-bound
method under different job numbers n for three d intervals. 53

Alidaee, B.,1990. A Heuristic solution procedure to minimize makespan on a single machine with non-linear cost functions. Journal of Operational Research Society 41, 1065-1068.
Alidaee, B., Womer, N.K., 1999. Scheduling with time dependent processing times: Review and extensions. Journal of the Operational Research Society 50, 711-720.
Bachman, A., Janiak, A., 2000. Minimizing maximum lateness under linear deterioration. European Journal of Operational Research 126, 557-566.
Bachman, A., Janiak, A., Kovalyov, M.Y., 2002. Minimizing the total weighted completion time of deteriorating jobs. Information Processing Letters 81(2), 81-84.
Browne, S., Yechiali, U., 1990. Scheduling deteriorating jobs on a single processor.
Operations Research 38, 495-498.
Cheng, T.C.E., Ding, Q., 1998. The complexity of single machine scheduling with
release times. Information Processing Letters 65(2), 75-79.
Cheng, T.C.E., Ding, Q., 2001. Single machine scheduling with step-deteriorating processing times. European Journal of Operational Research 134, 623-630.
Cheng, T.C.E., Ding, Q., 2003. Scheduling start time dependent tasks with deadlines and identical initial processing times on a single machine. Computers and Operations Research 30(1), 51-62.
Cheng, T.C.E., Ding, Q., Lin, B.M.T., 2004. A concise survey of scheduling with time-dependent processing times. European Journal of Operational Research 152, 1-13.

French S. 1982. Sequencing and Scheduling: An Introduction to the Mathematics of the Job-Shop. Ellis Horwood Ltd.
Gawiejnowicz, S., Pankowska, L., 1995. Scheduling jobs with varying processing times. Information Processing Letters 54(3), 175-178.
Gray, P., Hart W., Painton L., Phillips C., Trahan M., Wagner J., 1997. A Survey of Global Optimization Methods. Sandia National Laboratories. Albuquerque, NM 87185.
Guo, A.X., Wang, J.B., 2005. Single machine scheduling with deteriorating jobs under the group technology assumption. Internal Journal of Pure and Applied Mathematics 18(2), 225-231.
Gupta, S.K., Kunnathur, A.S., Dandapani, K., 1987. Optimal repayment policies for multiple loans. OMEGA 15(4), 323-330.
Gupta, J.N.D., Gupta, S.K., 1988. Single facility scheduling with nonlinear processing times. Computers and Industrial Engineering 14, 387-393.
Hsu, Y.H., Lin, B.M.T., 2003. Minimization of maximum lateness under linear deterioration. OMEGA 31(6), 459-469.
Jeng, A.A.K., Lin, B.T.M., 2004. Makespan minimization in single-machine scheduling with step-deterioration of processing times. Journal of Operational Research Society 55, 247-256.
Jeng, A.A.K., Lin, B.T.M., 2005. Minimizing the total completion time in single-machine scheduling with step-deteriorating jobs. Computers and Operations Research 32, 521-536.
Kubiak, W., Van de Velde, S.L., 1998. Scheduling deteriorating jobs to minimize makespan. Naval Research Logistics 45(5), 511-523.

Kunnathur, A.S., Gupta, S.K., 1990. Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem. European Journal of Operational Research 47(1), 56-64.
Mosheiov, G., 1991. V-shaped polices for scheduling jobs. Operation Research 39, 979-991.
Mosheiov, G., 1994. Scheduling jobs under simple linear deterioration. Computers and Operations Research 21(6), 653-659.
Mosheiov, G., 1995. Scheduling jobs with step-deterioration: Minimizing makespan on a single and multi-machine. Computers and Industrial Engineering 28(4), 869-879.
Mosheiov, G., 1996. -shaped policies to schedule deteriorating jobs. Journal of the Operational Research Society 47, 1184-1191.
Ng, C.T., Cheng, T.C.E., Bachman, A., 2002. Three scheduling problems with deteriorating jobs to minimize the total completion time. Information Processing Letters 81(6), 327-333.
Pinedo, M., 2002. Scheduling: Theory, Algorithms, and Systems, 2nd ed., Prentice Hall, Inc.
Sundararaghavan, P.S., Kunnathur, A., 1994. Single machine scheduling with start time dependent processing time: Some solvable cases. European Journal of Operational Research 78(3), 394-403.
Voutsinas, T.G., Pappis, C.P., 2002. Scheduling jobs with values exponentially deteriorating over time. International Journal of Production Economics 79, 163-169.