| Scheduling is an important branch of Operations Research and Combinatorial Optimization. Batch scheduling is a modern scheduling model which received much attentions.In the batch scheduling, the jobs are partitioned into and scheduled in batches. The jobs in the same batch have the same starting time and the same completion time. In the parallel-batch scheduling studied in this thesis, the processing time of a batch is equal to the largest processing time of the jobs in the batch. According to the number b of jobs limited in each batch(called the capacity of the batches), the parallel-batch scheduling is distinguished as two models of unbounded capacity and bounded capacity. Online scheduling is a hot research direction in the recent years. In the online setting of a scheduling problem, the information of the jobs is not known in advance. The decision maker has to schedule the known jobs without the information of the jobs arriving in the future.In this thesis, we study the online setting of scheduling with the jobs arriving online over time. This means that the jobs arrive over time and we do not know the information of a job until its arriving. An algorithm presented for an online optimal problem is called an online algorithm.Usually, the quality of an online algorithm is measured by its competitive ratio. For a minimization online optimization problem, an online algorithm is called ρ-competitive if for any instance, the algorithm produces a solution with an objective value no worse than ρ times the value of an optimal o?-line solution. The competitive ratio of an online algorithm A is defined to be ρA= inf{ρ : A is ρ-competitive}. It is not hard to see thatρAis always larger than or equal to 1. Because of the lack of the information, the caseρA= 1 can only occur at some very special problems. In general, the more ρAapproaches to 1, the better the online algorithm A. If there is no online algorithm with a competitive ratio less than ρA, then A is called an optimal online algorithm.To obtain better online algorithms, the jobs to be scheduled are usually allowed restart. Here, “restart” means that a running task may be interrupted, losing all the work done on it. We will schedule the interrupted job anew later. Allowing restart can help us to adjust our mistakes on decision, but too many restarts may cause waste of the resource and increase the probability of a spoiled product. Hence, in the design of an online algorithm, limited restart is also an adopted strategy. In this thesis, limited restart means that: each jobs can be restarted at most once, and so a running batch containing some restarted jobs cannot be interrupted again.In this thesis, we study the online over time scheduling on parallel batch machines(machine) with restart or limited restart. For all the four online scheduling problems studied in the thesis, we present best possible online algorithms. The thesis is organized as follows.In Chapter 1, we introduce some preliminary knowledge on scheduling theory, some useful notations and the related literature review.In Chapter 2, we study the online scheduling of equal length jobs on m identical unbounded parallel batch machines with limited restart to minimize the makespan. For this problem, we present a best possible online algorithm with a competitive ratio of1 + αm. Here, di?erent from the apparent representation of a formula as usually in the literature, 1 + αmis determined by an algorithm.In Chapter 3, we study the online scheduling of equal length jobs on a bounded parallel batch machine with a capacity b with limited restart to minimize makespan. Letα be the positive solution of the equation(1 + x)(2x~2+ 4x + 1) = 3. Let β be the positive solution of the equation x(1 + x)~2= 1. For the case of b = 2, we present a best possible online algorithm with a competitive ratio of 1 + α. For the case of b ≥ 3, we present a best possible online algorithm with a competitive ratio of 1 + β.In Chapter 4, we consider the online scheduling of equal length jobs on a bounded parallel batch machine with a capacity b to minimize makespan with restart. Let γ be the positive solution of the equation x(x + 1)(2x + 3) = 2. Let ？ be the positive solution of the equation x(x + 1)(2x + 1) = 1. For the case of b = 2, we show that the best possible online algorithm presented for the case of b = 2 with limited restart(in Chapter 3) is also best possible for the current version with restart. For the case of b = 3, we present a best possible online algorithm with a competitive ratio of 1 + γ. For the case of b ≥ 4, we present a best possible online algorithm with a competitive ratio of 1 + ？.In Chapter 5, we consider the online scheduling of equal length jobs on a bounded parallel batch machine with a capacity b with limited restart. The objective is to minimize the time by which all jobs have been delivered. Let α be the positive solution of the equation 2x(1 + x) = 1 and β be the positive solution of the equation x(1 + x)~2= 1.When b = 2, we present a best possible online algorithm with a competitive ratio of 1 + α.When b ≥ 3, we present a best possible online algorithm with a competitive ratio of 1 + β. |
PDF Full Text Request