| In this paper, we consider some online batch scheduling problems, design online.algo-rithms and make competitive analysis. For classic scheduling problems, at one time the machine can process one job at most. But for the parallel batch model of batch scheduling problems, the batch machine can process up to B jobs simultaneously as a batch, where B is called the capacity of batch machine. In this paper the online setting is overtime. Every job has an arrival time, before which we do not have any information about the job. As one job arrives, we get all of its information. We need to decide whether to start the jobs or wait for more information. Once the decision is made, we can not change it.The paper consists of five parts. In Chapter 1, we introduce some concepts about combinatorial optimization and scheduling problems. A literature review of online schedul-ing and batch scheduling problems is given.In Chapter 2. we study on-line scheduling problems on a batch machine with the assumption that all jobs have their processing times in [p,(1+φ)p], where p> 0 andφ=((?)-1)/2. The objective is to minimize makespan and the time by which all jobs have been delivered, respectively. The lower bounds of the problems studied in this chapter are all 1.618, and we give the optimal algorithms, respectively.In Chapter 3, we study the online batch scheduling problem on identical machines with delivery times. Online algorithms are designed on m parallel batch machines to minimize the time by which all jobs have been delivered. When all jobs have identical processing times, we provide the optimal online algorithms for both bounded and un-bounded versions of this problem. For the general case of processing time on unbounded batch machines, an online algorithm with a competitive ratio of 2 is given when the number of machines m=2 or m=3, respectively. When m≥4 we present an online algorithm with a competitive ratio of smaller than 2, when m intends to infinity, the competitive ratio intends to 1.5.In Chapter 4, we investigate the online scheduling problems on one unbounded batch machine to minimize total weighted completion times. For the general case, there does not exist one online algorithm with competitive ratio smaller than 2. Chen et al. give a 10/3-competitive algorithm. Based on their algorithm we provide an online algorithm with a competitive ratio 3.236. When all jobs have the same processing times, a 1.618-competitive algorithm is provided, which is best possible.In Chapter 5, we consider the online batch scheduling problem on one unbounded batch machine with batch delivery. After the jobs are processed on the batch machine, they need to be transported to destination with one vehicle, the objective is to minimize the time, by which the vehicle returns to the batch machine after all jobs have been delivered. When all jobs have the same processing times, we give the lower bound. The optimal online algorithm is given for the case that the vehicle has an infinite capacity. For the finite case we provide two online algorithms IHc and MIHc, which are best possible when p≥2T etc., where p is the processing time and T is the time that the vehicle needs to deliver one batch and return to the machine. For general case of processing time, the lower bound is at least 1.618. When the vehicle has an infinite capacity, we provide the optimal online algorithm. When the vehicle has a finite capacity, a 2-competitive algorithm is given.At last, we make a summary of our paper, and discuss what we can do in the future.
|
PDF Full Text Request