| Online scheduling research has important theoretical interest and also great relevance to applications. In the recent two decades, online scheduling has received extensive attention and deep-going research from the domestic and overseas scholars, which leads online scheduling to one of the fastest growing direction in modern scheduling. In this thesis, online means that jobs arrive online over time. That is, the information of each job is unknown in advance. An algorithm which is provided for an online problem is called an online algorithm. The quality of an online algorithm is usually measured by its competitive ratio. For a minimization problem, the competitive ratio ρAof an online algorithm A is defined to beρA= sup{A(I)/OPT(I) : I is an instance with OPT(I) > 0}.The closer the competitive ratio approaches 1, the better the online algorithm we have.An online algorithm A is best possible if no online algorithm has a competitive ratio less than ρA.The total weighted completion time of jobs is one of the most important objective criteria to be optimized in scheduling. We study in this thesis some online scheduling problems related to the minimization of the total weighted completion time. The thesis consists of six chapters:In Chapter 1, we first introduce some preliminary concepts and necessary knowledge about combinatorial optimization and scheduling problems. We then give a review for the achievements of online scheduling especially for minimizing the total weighted completion time.In Chapter 2, we consider online scheduling with job rejection, where each job Jj is either rejected, in which case a rejection penalty ejhas to be paid, or accepted and processed(scheduled) on the machine(s). The objective is to minimize the total weighted completion time of the scheduled jobs plus the sum of the penalties of the rejected jobs.? On a single machine, under an agreeable condition on the processing times and rejection penalties of the jobs, we provide an online algorithm DSPTR with a best possiblecompetitive ratio of 2.? For the general model on a single machine, we provide online algorithm DSWPTR with a best possible competitive ratio of 2 which generalizes the contribution of Anderson and Potts(Mathematics of Operations Research, 2004). This result also generalizes the previous one in this chapter, but the deduction techniques are completely di?erent.We first pour into the online algorithm some flexibilities and then using the technique“instance-reduction” for the deduction.? We provide an online algorithm with a competitive ratio of at most 4 + on identical machines and an online algorithm with a competitive ratio of at most 8 on unrelated machines, respectively.In Chapter 3, we consider the online tradeo? scheduling to minimize makespan and total weighted completion time on a single machine. We introduce the concept of online tradeo? scheduling to minimize two objective functions f1 and f2simultaneously. An online algorithm A is called(ρ1, ρ2)-competitive for minimizing f1 and f2if A is ρ1-competitive for minimizing f1 and ρ2-competitive for minimizing f2. A(ρ1, ρ2)-competitive online algorithm A is called nondominated if there is no other(ρ 1, ρ 2)-competitive online algorithm A such that(ρ 1, ρ 2) ≤(ρ1, ρ2) and either ρ 1< ρ1or ρ 2< ρ2.? We provide a parametric online algorithm. By using two distinct methods, we respectively show that the algorithm is a nondominated(1 + α, 1 + 1/α)-competitive online algorithm for each α with 0 < α ≤ 1. Our work generalizes the contribution of Anderson and Potts(Mathematics of Operations Research, 2004).In Chapter 4, we consider the online bounded-batch scheduling to minimize total weighted completion time on parallel machines.? For the model on m uniform machines with m being fixed, we present a 4(1 +)-competitive online algorithm.? For the model on m identical machines with m being arbitrary, we present a 4(1+)-competitive online algorithm. The result improves the online algorithm with competitive ratio of at most 8 provided by Zhang et al.(Journal of Industrial and Management Optimization, 2007) from the worst-case prospective.In Chapter 5, we study the online scheduling of linear deteriorating jobs to minimizethe total weighted completion time on a single machine. In this problem, the processing time of a job Jjis given by pj= αj(A + Bsj), where A and B are nonnegative with A + B > 0, αj≥ 0 is the deterioration rate of Jj, and sjis the starting time of Jj.? We provide a best possible online algorithm with a competitive ratio of 1 + λ(A) +αmaxB, where αmax= max1≤j≤nαjand λ(A) = 0 or λ(A) = 1 depending on A = 0 or A > 0. Our work generalizes the contribution of Liu et al.(Theoretical Computer Science,2012) from simple linear deteriorating and identical weights to linear deteriorating and nonidentical weights.In Chapter 6, we summarize the main contents and results of this dissertation, point out some problems occurred in this dissertation, and give some interesting and challenging topics for future research. |
PDF Full Text Request