Online Scheduling On Parallel Batch Machine(s)

Online scheduling is an important component part of modern scheduling. In classical off-line scheduling, we always assume that all jobs' information are available before schedulers making decision. In reality and practical production, schedulers cannot get all information of jobs when they have to decide how to process the available jobs at present. So online scheduling appears. Usually, people consider the following three kinds of online scheduling.First, online-list scheduling. In online-list model, the jobs are ordered in a list or sequence. A job cannot be released until its previous ones are scheduled on a machine. We can get a job's information once it is released. The assignment of a job cannot be changed once it has been made.Second, online-time scheduling. In this model, the jobs arrive over time. The arrived jobs do not influence the later jobs' arriving, no matter whether the former jobs have been scheduled or not. A job's information is available at its arrival time. The future jobs cannot be scheduled and the assignment of a job cannot be changed once it has been made.Third, online-time-nclv scheduling. In this model, jobs arrive over time, but the scheduler is given no information about the processing time of a job at its arrival time. So we call it nonclairvoyance. The processing time is known once it is completed.In this thesis, we study online-time scheduling. We consider a single parallel batch machine or two parallel batch machines. Parallel batch scheduling is motivated by semiconductor manufacturing industry, shoes manufacturing industry, mental industry etc., which will be explained in detail later. A parallel batch machine can process several jobs not more than the batch capacity. The processing time of a batch is given by the longest job in this batch. Jobs in a common batch have the same starting time and the same completion time. In the models we study here, we assume that the batch capacity is unbounded, which implies that we can process simultaneously as many jobs as possible. In our models, we also assume that there exist several incompatible job families or assume that a batch is allowed to limited restart.Incompatible job families means that jobs may belong to different families. Each family is incompatible with other families. That is, jobs from different families cannot be scheduled in a common batch, since chemical property or different operations.We propose limited restart since that restart may be a scarce resource or restart may bring in bad influence. A batch is allowed to limited restart means that each job is allowed to restart only once. A batch could be restarted if it contains no restarted jobs. Jobs in the restarted batch are released and become independent unscheduled ones. When we process a batch containing restarted jobs, we must start from scratch, and the process cannot be preempted until it is completed.Restart is different from preemption. We start to process a preempted job following its scheduled part, but when we process a restarted job, we have to do it from beginning. The finished work on this job is wasted. Restart is meaningful only in online scheduling problems, but not in off-line problems. In the off-line case, we can wait and do not process a waiting job (or batch) until the time is appropriate, without doing useless work. Online scheduling is lack of future jobs' information, so restart can help schedulers to get better possible online algorithm.We use competitive ratio to measure the quality of an online algorithm. To a minimization online scheduling problem, we say an online algorithm A isρ-competitive (ρ> 1) if for any instance L, we have A(L)≤ρ·opt(L), where A(L) is the objective value given by algorithm A and opt(L) is the objective value given by an optimal off-line algorithm. (To a maximization online scheduling problem, algorithm A isρ-competitive (ρ< 1) means that A(L)≥ρ·opt(L).) It can be observed that the value ofρis more closely to 1, the algorithm is more better. For an online scheduling problem, if the competitive ratio of an algorithm matches the lower bound of competitive ratio, we say the algorithm is best possible. This implies that the problem is solved thoroughly.In this thesis, we consider six problems. In Chapter 2 and Chapter 3, we study online scheduling on a single parallel batch machine to minimize makespan with incompatible job families; in Chapter 4 and Chapter 5, we study two parallel batch machines; in the last two chapters, we investigate online scheduling on parallel machine(s) using limited restart. In detail, the main results are as follows.1. In Chapter 2, we study an online scheduling problem on a single parallel batch machine to minimize makespan with two incompatible families. We first prove that the lower bound of competitive ratio of any online algorithm is (?)≈1.7808. Then we provide a best possible online algorithm with competitive ratio (?).2. In Chapter 3, based on the research of Chapter 2, we extend the known result. We assume that the number of families f is an input data. We propose a best possible online algorithm with competitive ratio expression on f, which is 1 + (?). When f≤2, the result matches the known results. Note that we propose a new best possible online algorithm, which is different with other known algorithm.3. In Chapter 4, for online scheduling on two parallel batch machines to minimize makespan, we first prove the lower bound of competitive ratio is (?). Then we propose a best possible online algorithm with competitive ratio matching the lower bound.4. In Chapter 5, we investigate an online scheduling problem on two parallel batch machines to minimize makespan with two incompatible job families, we use adversary strategy to prove that the lower bound of competitive ratio is (?)≈1.618. Then we provide a best possible online algorithm with competitive ratio (?).5. In Chapter 6, we study an online scheduling problem on a single machine to minimize makespan with limited restart. We prove the lower bound of competitive ratio is 3/2. Then we propose a best possible online algorithm. Without limited restart, the best possible online algorithm is (?)-competitive. So restart helps us to get a better online algorithm.6. In Chapter 7, we consider online scheduling on two parallel batch machines to minimize makespan using limited restart. Without limited restart, we have proved in Chapter 3 that the best possible online algorithm is (?)-competitive. Here we first prove that the lower bound of competitive ratio is 1.298. Under second-restart assumption (we use restart at these points that two machines are busy and we only restart the batch with later starting time), the lower bound is (?)≈1.366. We provide an online algorithm with competitive ratio (?), which is best possible under the second-restart assumption.