Study On Some Single-Machine On-line Scheduling Problems

Scheduling is one kind of important combinatorial optimization problem, which use some processors, machines or resources to accomplish optimally a batch of given tasks or jobs. The theory of scheduling has become a very important subject after half a century's development, and its application is very extensive.In a non-preemptive static scheduling problem, all job parameters are known. Scheduling decisions, which only the characteristics of jobs known to be in the system at a given point are called on-line optimal scheduling.Seeing the importance of single machine scheduling problem, we take it as our object and study the dynamic condition of single machine problems. We first generalize the preemption models and then study some single machine dynamic scheduling problems. We do the following jobs.Firstly, we study problems where job preemption is allowed under the generalized delay condition, i.e. delay is caused by both setup time and time of some fraction of work must be repeated if preemption occurs. We generalize the notion of job preemption by using two kinds of preempt-setup-repeat models representing these conditions. This is the fundamental for latter study. According tothe preempt-resume model, a statistic algorithm for P2 prmp Cmax is given.Secondly, we use the two models to study the dynamic single-machine scheduling problems of minimizing total flow time and of minimizing total timetable-length and develop on-line optimal dispatching rules, which consider only available information.Thirdly, we use the two models to study the dynamic single-machinescheduling problem prmp and develop on-line optimal dispatching rules, which consider only available information.Fourthly, we use the two models to study the dynamic single-machine scheduling problem prmp fmax and develop on-line optimal dispatchingrules, which consider only available information.Fifthly, we use the two models to study the dynamic single-machine scheduling problem rj, chains, prmp wj (1 - e-acj ) and develop on-line optimal dispatching rules, which consider only available information.Finally, after summarizing the contents in the thesis, we point out the further directions to study the single machine dynamic scheduling problems.