Some Single Machine Scheduling Problems Of Variable Processing Time

In this paper, we study two kinds of scheduling problems:one is the scheduling problem on a single machine with increasing processing time; the other is the single-machine scheduling problem with effects of learning and deterioration. The thesis consists of four chapters.In chapter 1, Introduction. We give some basic concepts, knowledge and background information of scheduling problems.In chapter 2, we discuss two scheduling problems with increasing processing time. For problem 1|pi(t)(t0,P,T)| Lmax, we investigate its property, and give a heuristic algorithm and a worst-case error supper-bound. This problem is polynomially solvable under a special case. For problem 1|pj(t) (t0, T1,T2)|Cmax, a polynomial algorithm is proposed.In chapter 3, we discuss the scheduling problems with effects of learning and deterioration, single machine makespan and sum of completion times minimization problems remain polynomially solvable, respectively. But for the following objective functions:the weighted sum of completion times and the maximum lateness, this paper proves that the WSPT rule and the EDD rule can construct the optimal sequence under a special case, respectively.In chapter 4, we summarize the thesis and propose some problems for future research.