Two Scheduling Problems On Uniform Machines With Rejection

Scheduling is an important branch of combinatorial optimization. It is extensively applied in many fields, such as management science, computer science, production of industry and agriculture, transportation et al.. On-line scheduling and the scheduling with rejection are two important aspects of it, we mainly discuss them in this thesis.This thesis has three chapters.In the first chapter, some notation, definitions and basic background information about the subject are introduced.In the second chapter, we consider an on-line scheduling of unit time jobs with rejection on uniform machines. In the standard three-field scheduling notation, the problem is denoted by Q_m|on - line,p_j =1|ΣC_j + Σe_j. (Here, the rejection penalty e_j, i.e. when job J_j arrivals, if we reject it, we would be penalized at cost e_j).In this chapter, we extend the case on one machine and arbitrary number identical parallel machines to the case on arbitrary number uniform machines. We design an on-line algorithm G1 for the latter case, and give the competitive ratio 1/2(2 + 3^1/2)≈ 1.86602. For the off-line case of this problem , we give a polynomial optimal algorithm.In the third chapter, we mainly consider the scheduling with rejction on uniform machines, which the objective is to minimize the sum of the makespan and the total penalties. We consider the on-line and the off-line cases respec-...