| Scheduling problem is a kind of important problem in the field of combinatorial optimization of operations research. Scheduling theory has important theoretical signifcance and wide practical application. The hierarchical service scheduling problem is a new combinatorial optimization model in the modern indusdtr y. In recent years,the problem has received attention of many scholars.In this paper, we mainly study online and semi-online hierarchical service scheduling problems. The paper is consisted of five chapters.In Chapter 1,we first introduce the basic concepts and theories of scheduling problem,and then give a description of the hierarchical service scheduling problem on parallel machines and the progress of the issue in recent years.In Chapter 2,we consider online and semi-online hierarchical service scheduling for 1oad balancing on m parallel uniform machines with two hierarchies. In this model,jobs arrive one by one and they are fractional.There are k(1≤k≤m-1) machines with speed s and hierarchy 1 can process all jobs,and the remaining m-k machines with speed 1 and hierarchy 2 can only process jobs with hierarchy 2.For the integral model with objective to maximize the minimum machiine completion time,we show that no online algorithm can achieve bounded competitive ratio.In order to overcome this barrier,we consider the fractional model and design a best possible algorithm with competitive ratio(?) for any 0≥1. For 0< s< 1, the competitive ratio is For s> 1, the competitive ratio is Here s1∈(0,1) is the real root of equation k2s3+k(2m-2k-l)s2+(m-k)(m-2k)s—(m-k)2=0 and s2 is the positive root of equation ks2-(2k-l)s-(m-k)= 0. Both algorithms are the best possible in the special case of k=1 and m=2. Lower bounds for some special cases are also presented.In Chapter 4, we discuss online hierarchical service scheduling on two identical machines. In this model, jobs arrive online over time. We first show that the competitive ratio of any online algorithm is at least, and then we give an online algorithm with competitive ratio 1+(?).In Chapter 5, we investigate online and semi-online scheduling problems with machine release time. In this model, jobs arrive one by one. For online scheduling problems on two identical parallel machines with reassignment and machine release time, we study two different versions, the model of we can reassign arbitrary k jobs and the model of we can reassign the last job of each machine. For both models, we propose two best possible algorithms with competitive ratio4/3 and (?), respectively. For online and semi-online hierarchical service scheduling on two identical parallel machines with machine release time, we give two modified online algorithms and show that both algorithms are the best possible.
|
PDF Full Text Request