| Online scheduling is a central research direction in the modern scheduling theory,and are widely applied in production management, logistics transportation, goods selling,and network service. In the recent two decades, online scheduling received extensive at-tentions and deep-going researches from the domestic and overseas scholars, which leadsonline scheduling to one of the fastest growing direction in modern scheduling. In thisthesis, online means that jobs arrive over time. That is, the jobs arrive over time, andthe characteristics of each job are unknown until it is released. There are three stan-dard models for online (over time) scheduling: non-preemptive model, preemption-resumemodel, and preemption-restart model.The quality of an online algorithm is usually measured by its competitive ratio. Fora maximization online scheduling problem, an online algorithm A is ρ-competitive (ρ≥1)if for every instance I, we have A(I)≥(1/ρ)· OPT(I), where A(I) is the objective valueof the schedule obtained by algorithm A, and OPT(I) is the objective value of an of-line optimal schedule. Similarly, for a minimization online scheduling problem, an onlinealgorithm A is ρ-competitive if for every instance I, we have A(I)≤ρ· OPT(I). Themore the competitive ratio approaches to1, the better the online algorithm we have.In Chapter2, we consider the online scheduling of equal-length jobs with incompat-ible families on multiple batch machines. In the problem, only the jobs from a commonfamily can be processed in batches, where each batch has a capacity b with b=∞in theunbounded batching and b <∞in the bounded batching. Each job J has an equal-lengthintegral processing time p>0, an integral release time r(J)≥0, an integral deadlined(J)≥0, and a real weight w(J)≥0. The goal is to determine a preemptive schedulewith restart which maximizes the weighted number of early jobs.When p=1, we show that the problem has a lower bound21/b, and provide anonline algorithm of a competitive ratio2. This means that the greedy algorithm is of thebest possible for b=∞.When p is any positive integer, we provide an online algorithm of competitive ratio3+2√2. This is the first online algorithm for the problem with a constant competitiveratio. In Chapter3, we address the online scheduling of equal-length jobs with incompatiblefamilies on two (or three) batch machines. The goal is to determine a schedule whichmaximizes the (weighted) number of early jobs.For two batch machines under the non-preemptive model, we establish an lowerbound that depends on the machine capacity b, and provide an online algorithm with acompetitive ratio of b+1.For two batch machines under the preemption-restart model, we present a lowerbound2, and then provide an online algorithm with a competitive ratio of3.For three unbounded batch machines under the preemption-restart model, weprovide an online algorithm with a competitive ratio of (8+2√15)/3≈5.249.In Chapter4, we introduce a new environment of online scheduling in which jobshave kind release times (KRT). Under the KRT assumption, no jobs can be released whenall of the machines are busy.We show that, under the KRT assumption, the online version of the SWPT ruleis an optimal online algorithm for the online scheduling on a single machine to minimizethe total weighted completion time. Note that，without the KRT assumption, the onlineSWPT rule does not have a finite competitive ratio.We study the competitive ratio of the online LPT algorithm to minimize makespanon m identical parallel machines under the KRT assumption.When m=2, we show that LPT is a best possible online algorithm with a com-petitive ratio of5/4. Comparing to the known result of Chen and Vestjens (OperationsResearch Letters,1997), which establishes the3/2-competitiveness of LPT, the results inthis paper imply that the KRT assumption can help to improve the competitive ratio ofLPT for two parallel machines.For each m≥3, we show that LPT has a competitive ratio of3/2.For every m≥1, we show that LPT is a best possible online dense-algorithm.For m≥3, we show that no online algorithms have a competitive ratio less than1.3473.For the online scheduling of tight jobs with kind release times and two processing times on a single machine to determine a non-preemptive schedule which maximizes thetotal processing times of the scheduled jobs with just two processing times1and k,we establish a lower bound max{4/(2+k),1}, and provide an online algorithm with acompetitive ratio of k/k. This means that our algorithm is of the optimal in the casethat k is a positive integer.In Chapter5, we study the online preemptive scheduling of equal-length intervals ona single machine with lookahead. Let p be the length (processing time) of all intervalsin instance I. The goal is to select some intervals in I without overlap so that the totalweight of the selected interval is as large as possible. Here,“lookahead” means that atevery time point t, the online algorithms can foresee all intervals that will release in thetime segment (t, t+L) for a certain L.When L=p, we provide an online algorithm with a competitive ratio of2. Thework improves an online algorithm with a competitive ratio of3provided by Zheng et al.(Computers&Operations Research,2013). |
PDF Full Text Request