Researches On Online Scheduling With Job Delivery

Online scheduling is a frontier research direction in scheduling theory, and has been extensively studied in last decades. In the literature, there are various models of online scheduling, but in this paper, “online scheduling” means “online-time scheduling”: the jobs arrive over time. A job’s information is known until its arrival time. In the research for online scheduling problems, schedulers should make the decision at the current time only according to the information of the arrived jobs. Therefore, for most online scheduling problems, there exist no optimal algorithms. Usually, the quality of an online algorithm is measured by its competitive ratio. For a minimization online scheduling problem, the competitive ratio of an online algorithm A, denoted by ρAis defined byρA= sup{A(I)/OPT(I) : I is an instance with OPT(I) > 0}where A(I) is the objective value of I acquired by algorithm A and OPT(I) is the objective value of I acquired by an optimal o?-line algorithm. Then we have ρA≥ 1, and the value of ρAis more closely to 1, the algorithm is more better.In this thesis, we study four kinds of online scheduling problems with delivery times:Online tradeo? scheduling; Online scheduling problem with incompatible job families and delivery times; Online scheduling with grouped processing times and delivery times;Online scheduling with deteriorating jobs and delivery times. The main results of this thesis are as follows:In Chapter 2, we study the online tradeo? scheduling problem on a single machine in which the objective is to minimizes the makespan and the maximum delivery completion time. For this problem, we present a best possible(nondominated) online algorithm with a tradeo? competitive ratio of(ρ, 1 +（1/ρ）), where 1 ≤ ρ ≤(?).In Chapter 3, we study the online scheduling problem on an unbounded parallel-batch machine with incompatible job families and delivery coordination in which the objective is to minimizes the maximum delivery completion time. Here, the job incompatibility means that the jobs from distinct families cannot be processed and transported in the same batch. We assume that the number of incompatible job families is unknown in advance, and furthermore, there is only a vehicle and its capacity is infinite. For thisproblem, we present a best possible online algorithm and the competitive ratio of this online algorithm is 2.In Chapter 4, we still study the online scheduling problem on an unbounded parallelbatch machine with incompatible job families and delivery coordination in which the objective is to minimizes the maximum delivery completion time. But we assume that the number of incompatible job families f is known in advance. There is only a vehicle and its capacity is infinite. In the case of pj= p and Ti= T, we present a best possible online algorithm with a competitive ratio of 1 +(?). For the general version, we present a best possible online algorithm and the competitive ratio of this online algorithm is 2.In Chapter 5, we study the online scheduling problem on a single machine with grouped processing times and job delivery in which the objective is to minimizes the maximum delivery completion time. Here, “grouped processing times” mean that all jobs’ processing times are in [p,(1 + α)p]. Suppose that there is one vehicle to deliver the jobs. For both of the unbounded version and the bounded version, we provide a best possible online algorithm and the competitive ratio of this online algorithm is(?).In Chapter 6, we study the online scheduling problem on a single machine with deteriorating jobs and delivery times in which the objective is to minimizes the maximum delivery completion time. Here, “the deteriorating jobs” means that the jobs’ processing times depend on their starting times, i.e., pi= ait, where ai≥ 0 and t is the starting time of Ji. When the capacity is unbounded, we provide a best possible online algorithm and the competitive ratio of this online algorithm is(?). When the capacity is bounded, we provide an online algorithm and the competitive ratio of this algorithm is 2.