Research On Some Parallel Machine Scheduling Problems With Grade Of Service Provision

In this thesis we study the problems of parallel machine scheduling under a grade of service (GoS) provision. First, we consider several semi-online scheduling problems on two uniform machines with the objective of minimizing the makespan. In the semi-online version, jobs arrive one by one, and the scheduler only know partial information of the jobs before they arrive. We respectively study the versions of foreseeing the optimal makespan, total job size, maximum job size and the bounds of job sizes. In the last two chapters, we consider the case of m uniform machines. We discuss the offline version of preemptive scheduling and the online version of fractional scheduling, respectively.In Chapter two, we consider two semi-online problems on two uniform machines under a GoS provision, where the optimal makespan (OPT) and total job size (SUM) is known in advance, respectively. Jobs are different in grade. The jobs of grade1can only be processed by the first machine, while the jobs of grade2can be processed by either of the two machines. And the second machine runs at s (s>0) times the speed of the first one. We present optimal algorithms GoS-OPT and GoS-SUM, respectively for the two semi-online problems. The competitive ratio are both min{In Chapter three, we study the semi-online problem on two uniform machines with known largest job size, where the second machine can only process partial jobs and runs s (s>0) times as fast as the first one. We design an optimal algorithm GoS-MAX for all s>0. The competitive ratio is min for0<s<1and min for s>1.In Chapter four, we investigate the semi-online problem on two uniform machines with bounded job sizes, where the second machine can only process partial jobs and runs s(s≥1) times as fast as the first one. Denote the ratio of upper and lower bound by t(t≥1). We discuss the problem for different values of (s,t). First, we prove that algorithm A1in Tan and Zhang remains optimal for most (s, t) values, which means the boundary information of job sizes is redundant. However, for the rest regions, we present another five algorithms, which produce better schedules by using the boundary information of job sizes. And these algorithms are proved to be optimal.Chapter five is a continuation of Chapter four, where we study the case of0<s≤1for the semi-online problem on two uniform machins with bounded job sizes. We prove that algorithm A2in Tan and Zhang is optimal for some (s, t) values. Then we present six improved algorithms, which are also optimal in some (s, t) region. The area of the (s,t) region failed to be optimal is about0.2.In Chapter six, we consider the offline version of preemptive scheduling on m uniform machines under a GoS provision. Jobs are different in grade. The jobs of grade1can only be processed by the first k machines, while the jobs of grade2can be processed by any machine. Denote the speed of the ith machine by si. We study the cases of1=s1=…=sk≤sk+1≤…≤sm and1=s1=…=sk≥sk+1≥…≥sm. For both cases, we present an optimal offline algorithm.In the last chapter, we discuss the online version of fractional scheduling on m uniform machines. Suppose that there are l≥2hierarchies. Denote the total speed of machines with hierarchy i and the total speed of all machines by Si and S, respectively. We prove that the lower bound is max for an arbitrary l≥2, and it could be improved to max when l=3. Then, we respectively present the optimal algorithms for l=2,3.