A Study Of Online Scheduling And Batch Scheduling

Scheduling is one of the most important branches in combinatorial optimiza-tion.With the development of practical application and theoretical research,there has been,many different scheduling models.The article focuses on classical on-line,semi-online for parallel machines and batch scheduling problems for single machine.The whole thesis is split into five chapters.Chapter 1 gives some basic knowledge about combinational optimization,scheduling problems,algorithms and computational complexity.Results of this thesis are summarized in this chapter.In Chapter 2 and Chapter 3,we discuss classical online parallel machine scheduling problems Pm?Cmax.In Chapter 2,we present pseudo lower bounds for the online scheduling problems on parallel and identical machines,which is the infimum of the competitive ratio of an online algorithm that can be proved by using three lower bounds on the optimum makespan.And in Chapter 3,we introduce a new algorithm for Pm?Cmax,and prove that the competition ratio of this algorithm matches the pseudo lower bound given in Chapter 2,when m is no more than 11.In Chapter 4,we study semi-online problems P2|sum|Cmax,where the total processing time of all jobs are known in advance.We give a randomized algo-rithm with competitive ratio 5/4,which is better than 4/3 the lower bound of any deterministic algorithm can achieve.In Chapter 5,we concern the problem of scheduling jobs with unit processing time and nonidentical sizes on single batch machine.The objective is to minimize the total completion time of all jobs.We show that the worst-case ratio of the algorithm based on the bin-packing algorithm First Fit Increasing(FFI)lies in the interval[109/82,3/2],and the worst-case ratio of First Fit Decreasing(FFD)is unbounded.Numerical results of various approximation algorithms and heuristics are also presented.