On-line Scheduling And Ring Loading Problem

This dissertation is concerned with parallel batch scheduling problems under on-line setting and ring loading problems.In parallel batch scheduling models, the given machine is a parallel batch processing system which can process up to b (b≥2) jobs simultaneously as a batch. All jobs in a common batch start and complete at the same time. The processing time of a batch is equal to the maximum processing time among the jobs in the batch. For any special job list, batches eventually formed are required to be a partition of the set of all jobs given. We first consider the single machine parallel batch scheduling problem with family jobs under on-line setting in the sense that we construct our schedule irrevocably as time proceeds and do not know of the existence of any job until its arrival. Our objective is to minimize the maximum completion time of the jobs(makespan). We deal with two variants: the unbounded model where the machine can handle infinite number of jobs simultaneously and the bounded model. For the unbounded case, we provide an on-line algorithm with competitive ratio 2 and prove that the result is the best possible. For the bounded case, we also present an on-line algorithm with competitive ratio 2 and show that, from a worst-case point of view, the best on-line algorithm for the problem considered cannot act much better than this algorithm when the capacity of the machine is larger than 100.We then consider the on-line scheduling problem of jobs with release dates on a single parallelbatching machine which can process infinite jobs at a time. The scheduling problem involves assigning all jobs to batches and determining the starting times of the resulted batches in such a way that the maximum completion time of the jobs (makespan) is minimized. In [G. Zhang, X. Cai and C. K. Wong, On-line algorithms for minimizing makespan on batch processing machines, Naval Research Logistics, 48(2001), 241-258] and [X. Deng and Y. Z. Zhang, Approximation algorithms in batch processing, Journal of Combinatorial Optimization, 7(2003), 247-257], the two groups of authors independently gave a same on-line algorithm with competitive ratio (5^1/2+1)/2 and proved that the on-line algorithm is the best possible. In their algorithm, a job(which has the maximum processing time in a batch) with release date r and processing time p will be delayed until time (1+α)r+αp if possible, whereα=(5^1/2-1)/2. In this dissertation, we derive a modified on-line algorithm for the same problem in which a job with processing time p will be delayed only until timeαp if possible. We show that the modified on-line algorithm still has competitive ratio (5^1/2+1)/2, and is asymptotically optimal in a weakened version.Thirdly, we consider on-line scheduling problem of jobs with precedence constraints, unit processing times and release dates on a single parallel batch machine. The release dates and precedence relations of jobs remain unknown until their arrivals. Our objective is to minimize the maximum completion time of the jobs. We first deal with the case in which the capacity of the machine is bounded and the precedence constraints are chains. We provide an on-line algorithm with a competitive ratio not greater than 3^1/2 for this case. We then deal with the case in which the precedence constraints are arbitrary. For the unbounded model, we derive an optimal on-line algorith with competitive ratio (5^1/2+1)/2 to minimize the maximun weighted completion time or the total weighted completion time; for the bounded model, we develop an on-line algorithm with a competitive ratio not greater than 2 to minimize the makespan and show that the competitive ratio of any on-line algorithm for this model is not smaller than (5^1/2+1)/2.Finally, we deal with the weighted link ring loading problems. In these problems, we are given an n-node undirected ring network each of whose links is associated with a weight; traffic demands d_i,j are given for each pair of nodes in the ring. The load of a link is the sum of the flows routed through the link and the weighted load of it is the product of its weight and the upper integer of its load. The objective of the problem is to find a routing scheme such that the maximum weighted load on the ring is minimized. We consider three variants: i) demands may be sent in either directions, clockwise or counterclockwise, with demand splitting; ii) demands are allowed to be sent in either routes but restricted to be integrally split; iii) each demand must be entirely routed in either of the two directions. We prove that the first two variants are polynomially solvable. For the third one, whose NP-hardness can be drawn from the result in [S. Cosares and I. Saniee, An optimization problem related to balancing loads on SONET rings, Telecommunication Systems, 3(1994), 165-181], we derive a polynomial-time approximation scheme(PTAS).