Study On Optimal Schedule Of Several Stochastic Scheduling Problems

Scheduling problem is a kind of combinatorial optimization problem on timeline.With deeper research in theory and specific application in real life,several different classes of stochastic scheduling models have been derived.This thesis mainly discusses several types of stochastic scheduling problems on single machine,focusing on the optimal scheduling design of these problems under different stochastic models.This thesis is divided into five chapters.In Chapter 1,we firstly introduce the relevant background and research significance of scheduling.Then we introduce basic concepts and terms of scheduling,and gives the notation of common terms.In addition,we introduce the review of research actuality and results related to this thesis from four aspects:the classical scheduling problems,the scheduling problems with deterioration effect,the scheduling problems with learning effect and the scheduling problems with both deterioration and learning effects.Finally,the main content of this thesis and the results of corresponding study are introduced.In Chapter 2,we study the stochastic scheduling problems in which the processing times and due dates follow the specific distribution.The three problems are discussed:(1)we consider a stochastic single machine scheduling problem of minimizing the expected total costs for quadratic earliness,quadratic tardiness,and early and tardy jobs under geometric distributions for both processing times and due dates.(2)we consider a maximum expected lateness stochastic minimization problem on a single machine under geometric distributions for both processing times and due dates.(3)we consider a maximum expected lateness stochastic minimization problem on a single machine by supposing exponential processing times and geometric due dates.For the first stochastic scheduling problem,we prove that the optimal schedule of the problem has V-shaped characteristic,and give the optimal V-shaped scheduling by designing a dynamic programming algorithm.For the latter two stochastic scheduling problems,utilizing job exchanged method and the basic knowledge of probability theory,we provide the corresponding optimal schedules.In Chapter 3,we study the stochastic scheduling problems with deterioration effect or learning effect.For the stochastic scheduling problems with deterioration effect,We propose two starting-time-based stochastic models in which the true processing time of a job is an increasing function of its starting time,i.e.,Pi(t)=Pi(1+βtα)and Pi(t)=Pi(1+βt)α。For the stochastic scheduling problems with learning effect,we propose a position-dependent stochastic model in which the true processing time of a job is a nonincreasing sequence of its position,i.e.,Pir=Pikr.Under the three models,three stochastic single machine scheduling problems are considered with almost surely ordered processing times and random due dates in which the objectives include the expected total completion time costs,the expected weight total tardiness costs and the maximum expected completion time costs.Then two stochastic single machine scheduling problems of minimizing the expected total weighted tardy jobs and minimizing the expected total weighted early and tardy jobs are considered with almost surely ordered processing times and exponential due dates.For the above stochastic scheduling problems,utilizing job exchanged method and the relevant knowledge of stochastic order,we provide the corresponding optimal schedules.In Chapter 4,we study the stochastic scheduling problems with both deterioration effect and learning effect.We propose four time-based and position-based stochastic models in which the true processing time of a job is a function of its starting time and position,i.e.,Pir(t)=(Pi+g(t))kr,Pir(t)=Pikr+g(t),Pir(t)=Pi(1+βtα)kr and Pir(t)=Pi(1+βt)αkr.Under the four models,we consider three single machine stochastic scheduling problems with the objectives including the expected total completion time costs,the expected total weight tardiness costs and the maximum expected completion time costs by supposing almost surely ordered processing times and random due dates.Then the expected total weighted tardy jobs minimization problem and the expected total weighted early and tardy jobs minimization problem are studied by supposing almost surely ordered processing times and exponential due dates.For the above stochastic scheduling problems,utilizing job exchanged method and the relevant knowledge of stochastic order,we provide the corresponding optimal schedules.In Chapter 5,we summary the main contents and corresponding research results of this thesis,and give the future research directions.