| This thesis mainly concerns design and analysis of approximation algorithms forpreemptive (semi-)online parallel machine scheduling problems. For each problemconsidered in this thesis, both lower bound and online approximation algorithm areprovided. The thesis is split up into seven chapters. We first introduce some preliminaryconcepts related to scheduling problems and then summarize the results of semi-onlinescheduling in Chapter 1.In Chapter 2, we investigate preemptive machine covering problem. We firstshow the off-line version can be solved in O(mn) time for general m-uniform-machinecase. For the online version, we present a general formula to obtain the lower boundof the problem on m uniform machines and thus show that the lower bounds ofQm|pmpt|Cmin and Pm|pmpt|Cmin are m and sum from i=1 to m 1/i, respectively. Lastly, we focuson the online algorithms for two-uniform-machine case. We first present an optimal on-line algorithm for the case that the idle time is not allowed to be introduced. We furtherpresented an optimal online algorithm when the idle time is allowed.In Chapter 3, we consider preemptive semi-online scheduling problems where alljobs have their processing times in an interval. We present respectively optimal semi-online algorithms for the problems P3|pmpt, group|Cmax, Q2|pmpt, group|Cmax andQ2|pmpt, group|Cmin.In Chapter 4, we study two preemptive semi-online scheduling problems. In thefirst semi-online problem, it is assumed that all jobs arrives one by one with non-increasing job sizes. We present an optimal algorithm for Q2|pmpt, decr|Cmin. Inthe second semi-online problem, it is assumed that the size of the largest job is knownin advance. We present optimal algorithms for the problems Q2|pmpt, max|Cmax andQ2|pmpt, max|Cmin, respectively.In Chapter 5, we investigate preemptive semi-online scheduling on parallelmachines with inexact partial information. We present respectively optimal algo-rithms for the problems Pm|pmpt, dist opt|Cmax, Q2|pmpt, dist opt|Cmax andQ2|pmpt, dist max|Cmax.In Chapter 6, we consider preemptive (semi-)online parallel scheduling with ma- chine cost. In this problem, no machines are initially provided, and when a job isrevealed the algorithm has the option to purchase new machines. The objective is tominimize the sum of the makespan and cost of machines. We present an online algo-rithrn with a competitive ratio of (2 61/2+2)/5≈1.3798 while the lower bound is 4/3.For the semi-online problem with decreasing sizes, we design an optimal algorithmwith a competitive ratio of 4/3, which does not introduce any preemption, and hence isalso an optimal algorithm for the non-preemptive semi-online problem.In Chapter 7, we deal with online parallel scheduling under a grade of service(GoS) provision, where each job and machine are labelled with the GoS levels, andeach job can be processed by a particular machine only when the GoS level of the jobis no less than that of the machine. We first propose an optimal online algorithm withcompetitive ratio 5/3 on two identical machines. Then we consider the online problemon m identical machines with two GoS levels. We show that the lower bound of theproblem is at least 2 and the greedy algorithm has a tight bound of 4-1/m. Finally,we design an improved algorithm with a competitive ratio of (12+4 21/2)/7≈2.522.
|
PDF Full Text Request