Thanks to the jury members who would like to spend time on evaluation of my work and participation in my defense.

Nearly three years ago, I started my master under the supervision of Prof. Yinfeng XU. He guided me to a new area: online algorithms. At that time, this area was brand new to me. After a while, an opportunity appeared in front of me. With good luck, I also became a Ph.D. student of Prof. Chengbin CHU who is an expert in the area of scheduling. Due to the cooperation of my two excellent supervisors, my research domain has been determined coincidentally to be online scheduling.

Although only my name appears on the cover of this thesis, I am indebted to many people who contributed to my work. Therefore, I would like to express my gratitude towards them.

First of all, I thank Chengbin CHU and Yinfeng XU for giving me all the opportunities and help to successfully complete this thesis. Prof. CHU always gave me some insightful ideas to break through the difficulties. This resulted in my publications. Other than that, he carefully reads drafts of my work and corrected my faults succinctly. I will never forget his efforts to improve my work to be conspicuous.

Secondly, I would like to thank Feifeng ZHENG. The majority of my publications benefits from the cooperation with him. I also thank him for his many suggestions to improve both the style of my writing and the layout of my publication.

Next, I express my gratitude to Zhiyi

List of Figures

Introduction

This thesis is concerned with design and evaluation of algorithms for online machine scheduling problems. This chapter presents scheduling problems, shows the motivations and the relevance of this research, and summarizes the contributions of the thesis.

Scheduling

Scheduling deals with the allocation of scarce resources to activities (or tasks) over time. It is a decision-making process to optimize one or more objective functions while satisfying some constraints.

The resources and activities in an organization can take many forms. The resources may be database servers in a network, machines in a workshop, crews at a construction site, runways at an airport, CPU in a computer, and so on. The activities may be data in a network, operations in a production process, stages in a construction project, take-offs and landings at an airport, executions of computer programs, and so on. Each activities may have some parameters, such as a certain priority level, a weight, a grade of service request (GoS), a release time, a due date, and so on. The objectives can also take many forms, such as the minimization of makespan, the minimization of total completion time, the minimization of total tardiness, the maximization of early jobs, and so on.

Scheduling plays an important role in many manufacturing and production systems as well as in many information-processing environments. In transportation and distribution environments, and other types of service industries, the role of scheduling is also indispensable.

Motivations

Traditional scheduling theory assumes that complete knowledge of the problem was available when it was to be solved. However, scheduling problems in the real world face the possibility of lack of information (or knowledge). For example, no one knows the exact number of phone calls that are going to reach a switchboard during a certain period, nor do we know the exact length of each individual call. Similarly, we do not know the exact number of tasks that are going to be executed on a time-shared multi-user computer system. Based on these scenarios in reality, it is known that uncertainties frequently encountered in scheduling environments include the appearance of new jobs and unknown processing times. These reasons promote the emergence of online scheduling. Similar to classical scheduling problems, online scheduling problems also originate from allocating certain scarce resources to activities, but over time (or over list), without having full knowledge of the future.

The notion of online algorithm is intended to formalize the realistic scenario where the algorithm does not have access to the whole input instance, unlike the (offline) algorithms for classical scheduling problems. Instead, it learns the input piece by piece, and has to react to the new requests with only a partial knowledge of the input. Its applications can be found in many areas as scheduling. This thesis is devoted to such online scheduling problems with the aim of attaining the highest resource utilization.

For instance, in real world, the following online scenario may happen in electronic commerce if no a couple of jobs are allowed to share a same machine during execution due to security reasons. A system owner provides m identical parallel machines to his customers. These customers are independent from each other. They submit their jobs dynamically over time. A customers job always uses its assigned machine exclusively for its whole processing time (i.e., preemption is not allowed). The owner receives a fixed fee from a customer for each minute a job of this customer occupies a machine. The customers do not provide in advance the machine usage necessary to process their jobs. Forcing the customers to provide the processing times of their jobs in advance may be a hassle to those customers and is very unreliable.

It is reasonable to assume that the system owner primarily tries to maximize system utilization. The system owner has no information about any future request. Therefore, without additional knowledge on the jobs, no job selection strategy can guarantee a better schedule than any other. The system owner may use a strategy by immediately assigning a free machine to an open request, that is, he generates a greedy schedule. On the other hand, he postpones the assignment of a job to a machine until a machine becomes available (for feasibility). If several requests are open at the same time he may use any arbitrary policy to pick any one of them. In such a situation, he is using an online algorithm and more specifically he uses a list scheduling algorithm, which is a classical algorithm in online scheduling.

Our contributions

In this thesis, we address some online scheduling problems by designing and analyzing some algorithms. In online scheduling, any algorithm is a heuristic. The performance of such heuristics can be evaluated either by average performance or by worst-cast performance (the evaluation is done by comparing the obtained solution with offline optimal solution. The average performance evaluation needs assumptions on probability distribution of various parameters, such as arrival interval or processing times. Furthermore, the structure of the distribution function must be special to obtain analytical expressions of expected performance of both obtained solutions and optimal offline solutions.

Because of these restrictions, we focus on worst-case analysis, i.e., we provide a performance guarantee of algorithms. This thesis considers a wide range of problems. for each problem, we try to establish a lower bound of the worstcase performance and attempt to design an algorithm such that the worst-case performance is as good as possible (as close as possible to the lower bound).

The next paragraphs summarize the main features of the problems considered in the thesis and illustrate the relevance of these problems. In this thesis, we consider several scheduling models: single machine model, parallel machine model, batch processing machine model, and open shop model. Different constraints are investigated, such as bounded delivery times, grade of service (GoS), reassignment, bounded processing times and so on.

Delivery time has a great significance in modern logistics. In order to attain a high integration, decision-makers usually consider jobs' delivery times into scheduling problems. Thus, we first study an online scheduling problem with jobs' delivery times. As we all know, each job's processing time can not be infinite. We consider the case where each job's delivery time in not too larger comparing to its processing time. In this scenario, we design an optimal online algorithm.

Grade of Service (GoS) provision is an attracting research field, since it can equip manufactures to guarantee high quality products for certain customers. As the reason mentioned above, we deal with the variant with jobs' bounded processing times. Under certain conditions, we respectively give optimal algorithms for different ranges (or intervals) of jobs' processing times.

With the technological development, machine's renovation happens more and more frequently in factories. An effect of such development is reduction of time (or cost) caused by processing the task, in other words, machine's speed has been increased. Machines with different speeds may run at the same time, i.e., the scenario of uniform parallel machines. So we draw some results for two uniform machine environment. After that, we further consider the problem with reassignment, which allows us to reassign jobs in some conditions. Such research is motivated by realistic phenomenon. For example, on the assembly line, a time delay is existing between assignment and process. In the process of dealing with all the jobs assigned, some newly arrived jobs may not have been processed yet. In order to minimize the completion time, we need to reassign these jobs to gain a better effect. In other cases, such as hotel or restaurant reservation and reception, we can do some adjustment in order to gain more profits. For the two uniform machine environment with reassignment, we design and analyze some algorithms.

Everyone has a common experience: in school homework must be handed in by a given due date. Similarly, many other assignments in the business and public worlds have dates by which the task must be completed and returned to the person who assigned the task, their due dates. Therefore, in this thesis, we also consider due date constraint in online scheduling to maximize the number of early jobs. We show the performance of an classical algorithm, called SRPT or ECT, for preemption scenario.

Another kind of machine environment is batch processing machine. Batch processing machine scheduling has been motivated by burn-in operations in the final testing stage of semiconductor manufacturing. We consider two variants on a single batch processing machine with jobs' nondecreasing processing times and jobs' nonincreasing processing times, respectively. For these two special cases, we respectively develop optimal algorithms.

Open shop scheduling problems arise in several industrial situations. For example, consider a large aircraft garage with specialized work-centers. An airplane may require repairs on its engine and electrical circuit system. These two tasks may be carried out in any order but it is not possible to do these tasks on the same plane simultaneously. There are other applications of open shop scheduling problems in automobile repair, quality control centers, semiconductor manufacturing, teacher-class assignments, examination scheduling, and satellite communications. For two open machine environment with preemption, considering jobs' processing times, we obtain an optimal algorithm.

Outline of the thesis

This thesis focuses on the theory of scheduling, and deals with the detailed sequencing and scheduling of jobs. It is divided into several parts.

We first discuss some models and results on online scheduling in Chapter 2.

In Chapter 3, we consider online scheduling on a single machine with bounded delivery times. This chapter is mainly based on [START_REF] Liu | An optimal online algorithm for single machine scheduling with bounded delivery times[END_REF]. Jobs arrive over time. The objective of this problem is to minimize the makespan considering jobs' delivery times. Note that makespan means the last moment by which all jobs have been delivered to the customers. Based on the results of literature, we further consider the situation where jobs' delivery times are bounded. For this problem, we give an optimal online algorithm, which is a generalization of the results in the literature.

In Chapter 4, we deal with online scheduling on two identical parallel machines with grade of service provision (GoS). This chapter is mainly based on [START_REF] Liu | Online scheduling on two uniform machines to minimize the makespan[END_REF]. The problem under consideration is to minimize the makespan. Jobs arrive over list. By bounding jobs' processing times, we divide the problem into different subproblems. We analyze different subproblems and present some optimal online algorithms under certain conditions. Further more, we suppose that the total processing time is known. Under this assumption, we give an optimal algorithm under some conditions.

Chapter 5 addresses the problem: online scheduling on two uniform (parallel) machines to minimize the makespan. This chapter is mainly based on [START_REF] Liu | Online scheduling on two uniform machines to minimize the makespan[END_REF]. The problems considered are: online scheduling under GoS and online scheduling with reassignment. Jobs arrive over list. For the first problem, we obtain an optimal algorithm under certain conditions. For the second problem, we give some lower bounds and upper bounds.

In Chapter 6, we study the problem of online scheduling on m identical parallel machines. The objective is to maximize the number of early jobs. This chapter is mainly on the basis of [START_REF] Liu | Online scheduling parallel machines to maximize the number of early jobs[END_REF]. The problem is online in the sense that all jobs arrive over time. Each job's characteristics, such as processing time and due date, become known at its arrival time. We consider the preemption-restart model, which means that preemption is allowed and once a job is restarted it loses all the progress that has been made on this job so far. If in some schedule a job is completed before or at its due date, then it is called early (or on time). We show that an upper bound of competitive ratio is 1 -1 2m and prove that ECT (earliest completion time) algorithm is 1 2 -competitive. In Chapter 7, we consider two semi-online scheduling problems on a single batch (processing) machine with jobs' nondecreasing processing times and jobs' nonincreasing processing times, respectively. This chapter is mainly based on [START_REF] Liu | Online scheduling on two uniform machines to minimize the makespan[END_REF]. The objective is to minimize the makespan. A batch processing machine can handle up to B jobs simultaneously. We study an unbounded model where B = ∞. The jobs that are processed together construct a batch, and all jobs in a batch start and complete at the same time. The processing time of a batch is given by the longest processing time of any job in the batch. Jobs arrive over time. Let p j denote the processing time of job J j . Given job J j and its following job J j+1 , we assume that p j+1 ≥ αp j , where α ≥ 1 is a constant number, for the first problem with jobs' nondecreasing processing times. For the second problem, we assume that p j+1 ≤ αp j , where 0 < α < 1 is a constant number. We propose an optimal algorithm for both problems.

In Chapter 8, we deal with a two-machine open shop problem. This chapter is mainly based on [START_REF] Liu | Optimal online algorithm for two-machine open shop scheduling with bounded processing times[END_REF]. The objective is to minimize the makespan. Jobs arrive over time. We study preemption-resume model, i.e., the currently processed job may be preempted at any moment in time, and it may be resumed at any later moment. Let p 1,j and p 2,j denote the processing time of job J j on machines M 1 and M 2 , respectively. Bounded processing times mean that 1 ≤ p i,j ≤ α (i = 1, 2) for each job J j , where α ≥ 1 is a constant number. We obtain an optimal online algorithm.

Finally, in Chapter 9, we give some conclusions from this research and dicuss some further research directions.

Chapter 2

State of the art

In this chapter, we review the literature on machine scheduling. Scheduling problems can be distinguished into two categories: offline scheduling and online scheduling. In offline scheduling models, it is assumed that the characteristics of the activities and/or the resources are known in advance when establishing the planning. As a consequence, offline models are deterministic models.

In practice, it is not always possible to have all the data concerning the jobs and the resources. To deal with this situation, various models are developed, especially stochastic scheduling models and online models.

In stochastic models, the unknown data are represented by random variables with known probability distribution. Among stochastic scheduling models, queuing theory is widely used.

In contrast to offline deterministic models and stochastic models, online scheduling make very few assumptions about the characteristics of jobs. This thesis is focused on online scheduling models, that is why the remainder of the chapter is mainly devoted to the literature review of online scheduling models.

Scheduling models

The models in machine scheduling problems are highly standardized. In all the scheduling problems, the number of jobs and machines are assumed to be finite. The number of jobs (or tasks/activities) is denoted by n and the number of machines (or resources) by m. It is generally assumed that each machine can process no more than one job at a time, except when the machines are batch precessing machines. The aim is to optimize some objectives. Usually, the subscript j refers to a job, whereas the subscript i refers to a machine. J j denotes a job and M i denotes a machine. If a job requires a number of processing operations, then J i,j denotes the processing operation of job J j on machine M i . Some parameters (or pieces of data) are associated with job J j .

Release time (r j ): the time when the job J j arrives at the system, i.e., the earliest time at which job J j can be processed. Release time is also called release date, arrival date or arrival time.

Processing time (p i,j ): the processing time of job J j on machine M i . If the J j 's processing times on different machines are identical, we use p j instead of p i,j to denote the processing time of J j .

Due date (d j ): the committed completion date, i.e., the date the job is promised to the customer.

Delivery time (q j ): job J j needs to be delivered after its processing on the machine, which takes a certain time. This time is called delivery time.

Weight (w j ): the importance of job J j relative to the other jobs in the system.

Variety of scheduling problems

A scheduling problem is described by a triplet α|β|γ. The α field describes the machine environment and usually contains a single entry. The β field provides details of processing characteristics and constraints and may contain no entry at all or multiple entries. The γ field describes the objective to be minimized (or maximized) and usually contains a single entry. The specification of a machine scheduling model requires the description of a machine environment (α field), job characteristics (β field), and an optimality criterion (γ field).

Some possible machine environments specified in the α field are:

Single machine (1):

There is only one machine. A single machine is the simplest of all possible machine environments.

Identical parallel machines (P m):

There are m identical machines in parallel. Job J j requires a single operation and can be processed on any one of the m parallel machines.

Uniform parallel machines (Qm):

There are m machines in parallel with different speeds. The speed of machine M i is denoted by s i . The processing time p i,j that job J j spends on machine M i is equal to p j /s i (assuming job J j is not preempted). If all the machines have the same speed, then this environment becomes identical parallel machines.

Unrelated parallel machines (Rm):

This environment is a generalization of the previous one. There are m parallel machines. Machine M i can process job J j at speed s i,j . The time p i,j that job J j spends on machine M i is equal to p j /s i,j (if this job is fully processed on machine M i ).

Open shop (O m ): There are m machines. Each job has to be processed again on each one of the m machines. There are no restrictions with regard to the routing of each job through the machine environment. The decision maker is allowed to determine a route for each job.

Flow shop (F m):

There are m machines in series. Each job has to be processed on each one of the m machines. All jobs have to follow the same route. After completion on one machine, a job joins the queue at the next machine. If all queues operate under the First In First Out (FIFO) discipline, the flow shop is referred to as a permutation flow shop.

Flexible flow shop (F F c):

A flexible flow shop is a generalization of the flow shop and the parallel machine environments. Instead of m machines in series, there are c stage in series with a number of identical machines in parallel at each stage. Each job has to be processed first at Stage 1, then Stage 2, and so on. A stage functions as a bank of parallel machines; at each stage, job J j requires processing on only one machine and any machine can satisfy. The queue at a stage may or may not operate according to the First Come first Served (FCFS) discipline. This machine environment is also referred to as a hybrid flow shop, compound flow shop, or multiprocessor flow shop.

Job shop (Jm):

In a job shop with m machines, each job has its own predetermined route to follow.

Flexible job shop (F Jc): A flexible job shop is a generalization of the job shop and the parallel machine environments. Instead of m machines, there are c work centers with a number of identical machines in parallel at each work center. Each job has its own route to go through the shop. Job J j requires processing at each work center on only one machine and any machine can satisfy. If a job on its route through the shop may visit a work center more than once, then the β-field contains the entry recrc for the reason of recirculation.

The processing constraints are specified in the β field. These restrictions may be:

Release times (r j ): job J j can not be processed before this time.

Preemptions (pmpt):

The scheduler is allowed to interrupt the processing of a job at any point in time and put a different job on the machine instead. The preempted job may be continued at some time later. When a preempted job is afterward put back on the machine (or another one), it may need be processed for its remaining processing time or for its (original) processing time. The former case is called resume, and the latter case is called restart.

Precedence constraints (prec): Precedence constraints may appear in a single machine or in a parallel machine environment, requiring that one or more jobs may have to be completed before another job is allowed to start its processing. There are several special forms of precedence constraints: If each job has at most one predecessor and at most one successor, the constraints are referred to as chains. If each job has at most one successor, the constraints are referred to as an intree or "join" type. If each job has at most one predecessor, the constraints are referred to as an outtree or "fork" type.

Grade of Service (GoS): Grade of service (GoS) is a qualitative concept, and it's often translated into the level of access privilege of different service provision. For example, suppose we have 2 machines (or processors). One of them can provide high quality service (or high GoS) while the other one provides normal service (or low GoS). Some jobs which request high quality must be processed by high GoS machine, while other jobs with low quality requests can be processed by both machines. GoS is also called hierarchy.

Availability constraint (h):

There is non-availability interval [s, t] on each of the machines. During this period, the machine cannot process any job. There are two models divided by how to handle the crossover job, which is the job affected by the non-availability interval i.e., the jobs starting beforing the unavailability period but having to be completed afterward. The first is nonresumable model where the crossover job that cannot be completed by time s is restarted from scratch at time t. Under the resumable model, the crossover job is interrupted at time s and resumed from the point of interruption at time t.

Machine eligibility restrictions (M j ): The M j symbol may appear in the β field when the machine environment is m machines in parallel. When the M j present, not all m machines are capable of processing job J j . The set M j denotes the set of machines that can process job J j .

Permutation (prmu):

A constraint that may appear in the flow shop environment is that the queues in front of each machine operate according to the First In First Out (FIFO) discipline. This implies that the order in which the jobs go through the first machine is maintained throughout the system.

Blocking (block): Blocking may occur in flow shop. If a flow shop has a limited buffer between two successive machines, then it may happen that when the buffer is full the upstream machine is not allowed to release a completed job.

No-wait (nwt):

The nwt symbol may appear in flow shop. Jobs are not allowed to wait between two successive machines. This implies that the starting time of a job at the first machine has to be delayed to ensure that the job can go through the flow shop without having to wait for any machine. It is clear that under nwt constraint, the machines also operate under the FIFO discipline.

Recirculation (recrc): recrc may occur in a job shop or flexible job shop when a job may visit a machine or work center more than once.

Online environment (online): This constraint means that decision must be made without full knowledge of jobs' information (or with partial jobs' information). Jobs arrive one by one.

Nonincreasing processing times (nonincreasing): The nonincreasing symbol may appear in the β field when the machine environment is online. When this item is presented, jobs are sorted in the order of nonincreasing processing times.

Nondecreasing processing times (nondecreasing): This symbol is defined in the opposite way of the previous one.

Any other entry that appear in the β field is self-explanatory. For example, p j = p implies that all processing times are equal, and similarly d j = d means that all due dates are equal (also called common due date). If p j ≤ p j+1 appears in β field, the processing time of job J j is not greater than that of its following job.

In order to present some possible entries in the γ field to be minimized, we first give some basic functions.

The objective function is usually a function the completion times of the jobs. The time job J j exits the machine system is denoted by C j , i.e., its completion time on the last machine on which it requires processing. Given a due date d j of job J j , the lateness of J j is defined as

L j = C j -d j ,
which is positive when J j is completed late and negative when it completed early. The tardiness of J j is defined as

T j = max{L j , 0}.
The latter notation is more reasonable since the tardiness never is negative. The unit penalty of J j is defined as

U j = 1 if C j > d j 0 otherwise .
Some commonly discussed objective functions are: Makespan (C max ): The completion time of the last job completed in the system. A minimum makespan usually signifies a high utilization of the machines, or a high throughput.

Total completion time ( C j ): The sum of the completion times of all jobs. This criterion indicates the total holding or inventory cost incurred by the schedule.

Total weighted completion time ( w j C j ):

The sum of the weighted completion times of all jobs.

Total weighted tardiness ( w j T j ): This is a more general cost function than the total weighted completion time.

Weighted number of tardy jobs( w j U j ): This objective has both academic and practical values.

All the objective functions listed above are called regular performance measures. Regular performance measures are functions that are nondecreasing in C 1 , ..., C n .

Online paradigms

In reality, it is unlikely to have all the information necessary to define a problem instance beforehand. This reason prompted the emergence of research on online models. These models differ from each other with respect to the way in which the algorithm has the information, step by step. Sgall distinguished several paradigms in an excellent survey [START_REF] Sgall | On-line scheduling[END_REF]. Note that the first two models are commonly studied in the literature [START_REF] Pruhs | Online scheduling[END_REF] and will be the main focus of this thesis.

Jobs arrive over list (or in a list): In this model, the jobs are ordered in some list and are presented one by one to the algorithm. When a job appears, all its characteristics, such as its processing time, become known. The online algorithm must assign the job immediately to a time slot and a machine before the next job is seen, consistently with some restrictions given by the problem, such as GoS. We are allowed to assign the jobs to arbitrary time intervals, i.e., they can be delayed. This assignment is irrevocable, i.e., the algorithm cannot change it after it sees the next job in the list.

This model corresponds to the standard online model of request sequences. It is used for problems such as bin packing, bin stretching, load balancing, graph coloring, and paging. There is no release time in this model, the only online feature is the limited information of future requests.

Jobs arrive over time: Jobs become available to the algorithm over time at their release time. When a job arrives, all its characteristics, such as processing time, due date, delivery time, are known by the algorithm. At each time when the machine is idle, the online algorithm decides which one of the available jobs is scheduled, if any. The online features of this model are the lack of knowledge of future requests and of their arrival time. If preemptions or restarts are allowed, the online algorithm can decide to preempt or stop any job that is currently being processed.

Unknown processing times: The main online feature in this model is that the processing time of a job is unknown until the job finishes. The online algorithm only knows whether a job is still being processed or not. The jobs may become available over time according to their release times or precedence constraints, but the case where all jobs are available at the beginning plays an important role in this model. If there are other characteristics of a job other than its processing time, they are known when the job becomes available.

Interval scheduling: This model assumes that each job has to be executed in a precisely given time interval. If this is impossible it may be rejected. This scenario is very different from the previous three. For example, it is meaningless to measure the makespan or total completion time of the schedule; instead we measure the number of accepted jobs. It is also related to load balancing.

If an online algorithm is clairvoyant, the processing time of a job becomes known at its arrival. In contrast, if an online algorithm is non-clairvoyant, the processing time of each job is still unknown when the job is available; as long as the job is not finished, a non-clairvoyant online algorithm only knows whether it is still being processed or not.

Other than in offline scheduling, the option to preempt a job can be very important in the online paradigms where jobs arrive over time. It enables the scheduler to correct mistakes in a limited range. Restarts have the same effect.

In this thesis, we only consider two online models: the one where jobs arrive over list and the one where jobs arrive over time. Most of the time, we focus on clairvoyant algorithms.

Performance measures and computation

For a scheduling problem, we need an approach to measure the performance of each algorithm for its solution. In this thesis, we use the competitive analysis [START_REF] Borodin | Online Computation and Competitive Analysis[END_REF] to measure the performance of online algorithms. Precisely, we measure the quality of an online algorithm by its competitive ratio, which is an upper bound of the ratio of the objective function value given by the considered algorithm over the optimal one obtained by offline optimal algorithm (which has access to all information in advance).

In order to evaluate a competitive ratio, the online algorithm is compared to an adversary. The adversary makes a sequence of requests, which have to be processed by the online algorithm. The adversary itself also has to serve the requests, but not necessarily at the same time as it creates them. A good adversary tries to develop a sequence of request such that the cost for processing the sequence by the online algorithm is as high as possible compared to its own cost for serving the same sequence of requests.

There are three different kinds of adversaries introduced in [START_REF] Borodin | Online Computation and Competitive Analysis[END_REF]. The difference concerns the information about the online algorithm that is available to the adversary and how the adversary processes the requests.

Oblivious adversary: He constructs the request sequence in advance, based only on the description of the online algorithm, and processes the requests himself optimally. This adversary knows the algorithm's code, but does not get to know the randomized results of the algorithm.

Adaptive online adversary: He makes the next request based on the algorithm's answers to previous ones, but processes it immediately. This adversary must make its own decision before it is allowed to know the decision of the algorithm. This adversary is stronger than the previous one, since he has opportunity to change the request sequence.

Adaptive offline adversary: He makes the next request based on the algorithm's answers to previous ones and processes them optimally in the end. This adversary knows everything, even the random number generator. This adversary is so strong that randomization does not help against him.

The competitive ratio of an online algorithm is defined as follows. An online algorithm is called ρ-competitive if for every possible request sequence generated by the adversary, the objective value of the schedule obtained by the online algorithm is at most ρ times the value of the schedule produced by the adversary plus a constant. If we allow randomization, then we compare the expected objective values, where the expectation is taken over the random choices of the algorithm.

Due to lack of information in online scheduling, the quality of any online schedule is normally not as good as an (offline) optimal schedule. Specifically, for any input job sequence I, let C ON (I) denote the objective value of the schedule produced by the online algorithm A ON and C OP T (I) denote the objective value of an (offline) optimal schedule. We say that A ON is ρ-competitive if

C ON (I) ≤ ρC OP T (I) + k
where k is a constant number. This inequality is a general form. Usually, we omit the parameter k, i.e., k = 0. We also say that ρ is the competitive ratio of A ON . In other words, we measure the quality of an online algorithm A ON , one for the online scheduling problem, by its competitive ratio ρ, which is defined to be (at least) the supremum of ratio C ON (I)/C OP T (I) over each of the problem instances I.

In other words, if for each input instance the (expected) objective value of the schedule produced by this algorithm is at most ρ times the value of the optimal schedule plus a constant, then the deterministic (randomized) algorithm has a competitive ratio ρ (also called upper bound). This corresponds to the competitive ratio against an oblivious adversary. For a specific algorithm, we can give a special instance to make the algorithm perform the worst possible (i.e., the worst case). In this way, we obtain a lower bound (of competitive ratio) of this algorithm. For this algorithm, if its competitive ratio matches it lower bound, we say that this bound is tight.

If a part of information is known in advance, such as the total processing time or the biggest processing time, the problem is called semi-online. When all information is available at the beginning (before scheduling), the problem is called offline.

Note that the above definition of competitive ratio is specified for minimization problems and ρ ≥ 1. In maximization problems, for any input job sequence I, we say that A ON is ρ-competitive if

C ON (I) ≥ ρC OP T (I).
We also say that ρ is the competitive ratio of A ON . Clearly, 0 ≤ ρ ≤ 1. The closer the ratio ρ comes to 1, the better the performance of the online algorithm A ON is. Now the question is: "without future information, how well an online algorithm can reach?". This promotes the research of the (general) lower bound of competitive ratios for all online algorithms (for minimization problems). For a certain minimization problem, a lower bound of competitive ratios (also called a lower bound of the problem) implies that there exists no online algorithm with a competitive ratio less than this lower bound. Correspondingly, for a maximization problem, an upper bound of competitive ratios (or the problem) means that no online algorithm has a competitive ratio higher than it. This kind of upper bound is also referred to as a lower bound in the literature for consistency. We use a minimization problem to explain how to draw a lower bound. Usually, a lower bound of the problem is obtained by giving a specific job instance (sometimes, a set of job instances) on which no online algorithm can performance very well. In this special instance, we first give several jobs in order to detect online algorithms' decisions. Depending on their decisions, we further give jobs to make their decisions the worst possible. If after giving these two sets of jobs, some online algorithms do not achieve their worst cases, the third set of jobs arrive in the system. With the purpose to make any online algorithm the worst possible, we carefully design the special job instance step by step. At last, we will obtain a common value which can not be beaten by any online algorithm. A fundamental principle to beat greedy algorithms is to release jobs immediately after the algorithms schedule the previous jobs.

An online algorithm is considered to be best possible or optimal if its competitive ratio matches the lower bound of competitive ratios (or the problem). In this situation, we can also say that the bound is tight.

Readers should note that the difference between lower bound of the algorithm and the lower bound of competitive ratios. The lower bound of an algorithm means that for an online problem, this specific algorithm cannot have a competitive ratio less than this lower bound. It is associated with a specific algorithm. However, the lower bound of the problem is not specific for any algorithm, but related to the problem. For an online problem, it is the lower bound of all algorithms' competitive ratios. The lower bound of the algorithm is worth to research only in the case where the lower bound of the problem and the competitive ratio of this algorithm do not match. The lower bound of the algorithm can be obtained by designing a special instance for this specific algorithm such that the algorithm performs as bas as possible.

There is also a relative concept, called upper bound of the problem. For an online problem, an upper bound is determined by (or equal to) the competitive ratio of an online algorithm which is currently known to be the best. When the upper bound is equal to the lower bound of the problem, the problem is solved. Usually, there is a gap between two bounds for an online problem. Our task is to improve two bounds to decrease gap. For an online problem, if the upper bound obtained by an algorithm is tight and there is also a gap between this upper bound and the lower bound of the problem, the task is to seek new algorithms with lower competitive ratio (or upper bound), or to improve the lower bound of competitive ratio for the problem.

In order to prove the competitive ratio of an online algorithm, we usually use a technique, called minimum counter example or smallest counter example. Suppose that we want to prove that algorithm A on is φ-competitive. We first assume that there exists a smallest counter example I with the least jobs such that A on (I) > φA opt (I). Then based on this assumption, using the features of the algorithm, we derive a contradiction. So we claim that such smallest counter example does not exist. Therefore, we have the desired result.

Since this thesis is mainly concerned with the deterministic online algorithms, two adaptive adversaries are equivalent. In this thesis, we consider the competitive ratio against an adaptive (online) adversary. Competitive analysis is a worst-case analysis which differs from an average-case analysis. This measurement gives a kind of pessimistic impression.

Modeling online scheduling problems

The basic situation of online scheduling problems is the following. We have some sequence of jobs that have to be processed on the machines. In the most basic problem, each job is characterized by its processing time and has to be assigned on one of the machines. Jobs arrive with some online features. In some complex variants, there may be additional restrictions or relaxations. We usually want to schedule the jobs as efficiently as possible.

The concept of online algorithm is used to formalize the realistic scenario, where the algorithm does not have the information of the whole input instance. In contrast, the offline algorithms are assumed to have access to the whole input instance. Online algorithms learn the input piece by piece, and has to react to the new jobs with only a partial knowledge of the input.

When the theory of NP-completeness was developed, many scheduling problems have been shown to be NP-complete [START_REF] Du | Theory of Computational Complexity[END_REF]. After the completeness of 18 basic scheduling problems had been shown [START_REF] Garey | Computers and Intractability; A Guide to the Theory of NP-Completeness[END_REF], the focus shifted to designing approximation algorithms. Online algorithms are basically kinds of approximation algorithms and many natural heuristics for scheduling are in fact online algorithms.

In order to paraphrased the online models in a realistic way, we adopt some examples illustrated in [START_REF] Vestjens | On-line machine scheduling[END_REF].

Example 1: A queue of cars is standing in front of a ferry-boat waiting to be transported to the other shore. The ferry man that is standing in front of this queue is given the task to assign each of the cars to a location on the ferry-boat so as to minimize the free area of the ship. Because the view of the ferry man is partially blocked, he can only see the first car in the queue at a time. Once this car has been assigned to a position on the ship, the cars move up and he sees the next car in the queue. Due to his years of experience, the ferry man knows exactly the space needed by a car once he sees it. For obvious reasons, the assignment of a car cannot be changed once the decision has been made. To avoid chaos, the assignment of the cars to the deck of the ferry-boat is highly structured. The deck of the ferry-boat is divided into parallel lanes of equal width and equal length. Each lane is wide enough to be able to contain any of the cars. Cars can only be assigned to the prescribed lanes and must be located one after another in each of the lanes.

We can formulate this problem in terms of the online models mentioned in the above section. Look for the machine environment (α field), job characteristics (β field) and an optimality criterion (γ field). The jobs in this example are the cars, and the processing time of a job is the length which the car requires. The machines are the lanes into which the deck is partitioned. Every job can be assigned to any lane and uses an amount of space that is independent of the lane. This means that the environment corresponds to a set of identical parallel machines. The objective is to minimize the free area, which is equivalent to minimizing the total length of the cars left ashore. Define a due date and a weight for each job to be equal to the length of the lanes and the length of the car it represents, respectively. The objective hence is to minimize the weighted number of tardy jobs. The online model is the one where jobs arrive over list.

Example 2: A factory faces a continuous demand for cardboard boxes of various types. The boxes are produced by a group of machines. Every machine can make a complete box from a single cardboard sheet. This includes printing in multi-colors, cutting, folding, and gluing. Because the machines were bought over the years, they all have different processing speeds. Every order consists of a specified number of boxes of a certain type. All orders have a due date, which is the promised date of delivery. The decision makers have to decide how to assign the orders to the machines so as to minimize the number of late orders.

Similar to the analysis of previous example, we should look for the machine environment, job characteristics and an optimality criterion. The jobs in this example are the orders that have to be produced, and the machines are simply the machines in the factory. The objective is to minimize the number of tardy jobs. Every job can be processed by processed by each of the machines. Considering the fact that all machines have different speeds, this implies that the machine environment corresponds to a set of uniform parallel machines. The online model is the one where jobs arrive over time.

Example 3: A computer network of several computers is used for transmitting messages between the users of the network. Each computer has many users who want to transmit messages via this network. Before transmitting a message, a route is chosen along which the transmission should take place. Each of the links in the route has a fixed bandwidth, i.e., the number of bits per second that they can transmit is fixed. The requests for sending a message arrive online over time at the computers, and each message has a size in bits, which is unknown at the time of the request. No computer in the route can forward a message until it has been received completely. Given the transmission route, the aim is to find a protocol that regulates the communication traffic in such a way that the average waiting time is minimized. The jobs in this example are the messages. The links between the computers can be viewed as machines. All messages are traveling via a route that is known in advance, and the order in which the machines are visited is known beforehand. The objective is to minimize the average waiting time. This is the same as minimizing the total waiting time. By adding all jobs' processing times (transmission times in the network without waiting), the objective function becomes the minimization of total completion time. The problem therefore can be formulated as a job shop to minimize the total completion time. The online feature that is used is obviously the model where jobs arrive over time and only non-clairvoyant algorithms have to be considered.

Literature review of online scheduling

There are hundreds of online scheduling results associated with different online paradigms in the literature, but our work is with regard to two kinds of online paradigms: jobs arrive over list, and jobs arrive over time. Since our research does not involve randomization, we mainly present the results of deterministic algorithms. In order to organize these results, we respectively state them in different online paradigms.

Before categorizing, we show some general results. The first one is LIST algorithm, which was given by Graham [START_REF] Graham | Bounds for certain multiprocessor anomalies[END_REF]. He studied a simple greedy algorithm.

He investigated a basic model, where we have m identical machines and a sequence of jobs characterized by their processing times. The objective is to minimize the makespan. We assume that all jobs are arranged in a list according to their release times, even if some of them do not arrive. Whenever a machine is available, LIST algorithm schedules the first job in the list on this machine. The list is formed online (no matter jobs arrive over time or over list). Since LIST algorithm does not use the information of processing times, so it also hold the online feature of unknown running times. Therefore, LIST algorithm works in the first three online paradigms.

Graham showed that the competitive ratio of LIST is 2-1 m . In the following paper [START_REF] Graham | Bounds on multiprocessing timing anomalies[END_REF], Graham showed that the factor of 2 decreases if we modify the algorithm so that some number of long jobs is scheduled first using an optimal schedule, and the rest is scheduled by LIST algorithm. Clearly, this algorithm is no longer online in any of the paradigms. However, this gives an intuition to design approximation algorithms [START_REF] Koulamas | A modified lpt algorithm for the two uniform parallel machine makespan minimization problem[END_REF] and online algorithma [START_REF] Cheng | A new algorithm for online uniform-machine scheduling to minimize the makespan[END_REF].

Jobs arrive over list

This online model corresponds most closely to the standard model of request sequence in competitive analysis. In this paradigm, there is no release times and precedence constraints, since these restrictions appear to be unnatural with scheduling jobs in a list. In most variants, it is not necessary to introduce idle time on any machine.

Minimizing makespan

The basic model is that: we have m machines in parallel and a sequence of jobs characterized by their processing times. The jobs arrive one by one, and we have to schedule each job before we see the next one. The objective is to minimize the makespan. Each job is assigned to a single machine. Each machine can process at most one job at a time. There is no additional constraints. Preemption is not allowed, and all the machines are identical.

LIST algorithm [START_REF] Graham | Bounds for certain multiprocessor anomalies[END_REF] is (2 -1 m )-competitive. This algorithm is optimal for m = 2, 3, but for larger m we should develop optimal algorithms [START_REF] Faigle | On the performance of on-line algorithms for partition problems[END_REF]. We know that there is a weakness of LIST algorithm. If currently all machines have equal loads and a job with long processing time arrives, LIST algorithm obtains a schedule which is almost twice as long as the optimal one. So here is the problem: if the scheduled jobs are sufficiently small, and the optimal schedule consists of scheduling them evenly on m -1 machines in parallel with the last long job on the remaining machine. Observing this fact, to obtain a better scheme, we have to create some imbalance and keep some machines lightly loaded (for the use by long jobs).

To attain a competitive ratio σ, a natural idea is to assign the current job to any machine such that immediately after this assignment the competitive ratio is at most σ. In order to avoid the weakness of LIST algorithm, suppose we always choose the most loaded of the machines to create as large imbalance as possible. Nevertheless, it does not work. If this algorithm faces a sequence of jobs with identical processing times, it assigns them evenly on a constant fraction of the machines, with only one job scheduled on each of the remaining machines. Now a sequence of long jobs presents. The algorithm first makes the load distributed evenly on all machines, then has to force the schedule to be too long. Thus, this natural method fails again.

To design a good algorithm, two different approaches are commonly used. One is to schedule each job on one of the two currently least loaded machines [START_REF] Galambos | An on-line scheduling heuristic with better worst case ratio than graham's list scheduling[END_REF][START_REF] Chen | New lower and upper bounds for online scheduling[END_REF]. This method yields better results than LIST for any m ≥ 4 and achieves the currently best upper bounds for small m. However, the competitive ratio approaches 2 when m is large. This approach leaves at most one lightly loaded machine. In order to obtain a better upper bound for large m, it is necessary to keep some constant fraction of machines lightly loaded. Based on this idea, several algorithms were developed [START_REF] Bartal | New algorithms for an ancient scheduling problem[END_REF][START_REF] Karger | A better algorithm for an ancient scheduling problem[END_REF][START_REF] Albers | Better bounds for online scheduling[END_REF].

We know that LIST algorithm always assigns the incoming job to the least loaded machine. Based on this algorithm, Cho and Shani [START_REF] Cho | Bounds for list schedules on uniform processors[END_REF] further studied the two-uniform-machine environment (where the speeds of machines are 1 and s ≥ 1 respectively) and proved that LIST algorithm is 1+ √ 5

2 -competitive for all s and the bound is tight when s = 1+ √ 5

2 . Epstein et al. [START_REF] Epstein | Randomized on-line scheduling on two uniform machines[END_REF] provided randomized algorithms with better performance than LIST algorithm in the case where no preemption is allowed. In the same paper, for the problem with preemption, they proposed an optimal (1 + s s 2 +s+1 )-competitive algorithm for all s ≥ 1, which cannot be beaten by any randomized algorithm [START_REF] Wen | Preemptive on-line scheduling for two uniform processors[END_REF]. Angelelli et al. [START_REF] Angelelli | Semi-online scheduling on two uniform processors[END_REF] considered the semi-online scheduling on two uniform processors in the case where the total processing time of jobs is known in advance and presented algorithms which are optimal for s ≥ √ 3, s = 1 and

1+ √ 17 4 ≤ s ≤ 1+ √ 3 2 .
In that paper, they first showed that the LIST algorithm does not improve its performance when the total sum of the tasks is fixed with respect to (pure) online problem, and then they presented three different algorithms that are optimal in some intervals of the values of the speed s. The idea of these three algorithms are simple. First assign the current job to a machine and when the load of that machine exceeds a value (or function of s), then schedule this job on a specified machine. These three algorithms differ one from another each other with regard to the function of s and the specified machine.

Minimizing makespan with GoS

GoS is a qualitative concept, and it is often translated into the level of access privilege of different service provision. One simple scheme for providing differentiated service is to label machines and jobs with pre-specified grade of service (or GoS) levels and allow each job to be processed by a particular machine only when the GoS level of the job is no less than the GoS level of the machine. In effect, the processing capability of the machines labeled with high GoS levels tends to be reserved for the jobs with high GoS levels. Hence, if we label relatively higher GoS levels on the jobs from valued customers, we can ensure better service to more valued customers. In such a situation, assigning jobs to the machines becomes a parallel machine scheduling problem with a special eligibility constraint. For example, suppose that we have two machines (or processors). One of them can provide higher service quality (higher GoS) while the other one is normal (lower GoS). Some jobs which are requested to have higher quality must be processed by the higher GoS machine. While the normal jobs can be processed by both machines whenever they are available. Within an offline context, the concept of GoS was introduced and analyzed in [START_REF] Hwang | Parallel machines scheduling under a grade of service provision[END_REF]. They proposed a simple algorithm, called lowest grade-longest processing times first (LG-LPT) whose computational complexity is strongly polynomial and the worst-case makespan of the generated schedule is no more than twice the optimum. In particular, the makespan of the schedule generated by the proposed algorithm is proven to be no more than 5/4 for m = 2 and 2 -1/(m -1) for m ≥ 3 times the optimum. The idea of algorithm LG-LPT comes from a classical algorithm LPT for problem P m||C max . Considering the GoS contraint, they modified the LPT algorithm by sorting the job sequence in a order of increasing GoS where ties are broken by LPT rule. In other words, LG-LPT algorithm assigns the jobs in the order of increasing GoS and when several jobs have the same GoS, they are scheduled by LPT rule.

Park et al. [START_REF] Park | Online and semi-online scheduling of two machines under a grade of service provision[END_REF] studied the online scheduling of two machines under a grade of service (GoS) provision and its semi-online variant where the total processing time is known. They gave an optimal online algorithm whose competitive ratio is 5 3 and an optimal semi-online algorithm with a competitive ratio 3 2 . The idea of online algorithm they proposed is try to assign jobs with lower GoS as many as possible on lower-GoS machine. To be more specific, when a higher-GoS job arrives, we have to assign it to the higher-GoS machine. When a lower-GoS job is presented, we need to determine which machine should process this job. If the load of lower-GoS machine (after assigning the current lower-GoS job on that machine) is not bigger than a certain value (or a function of previous jobs' processing times), then we do schedule lower-GoS job on lower-GoS machine. Otherwise, schedule it on the higher-GoS machine. But the criterion (or function of previous jobs' processing times) is a little difficult to design. In order to prove the online algorithm is σ-competitive, they first showed a lower bound (also a function of previous jobs' processing times) of optimal value. The first principle is to assign lower-GoS jobs as many as possible on lower-GoS machines. The second principle is to prevent the makespan from exceeding σ times the optimal value (after scheduling the currently by the first principle). Thus, if this the makespan is bigger than the criterion, the algorithm has to assign this job on a higher-GoS machine. Based on the idea of this online algorithm, by slightly changing the lower bound of optimal value with the information of total processing times, Park et al. [START_REF] Park | Online and semi-online scheduling of two machines under a grade of service provision[END_REF] proposed an optimal semi-online algorithm in the same paper.

Jiang [START_REF] Jiang | Online scheduling on parallel machines with two gos levels[END_REF] extensively investigated the problem of online scheduling on parallel machines with two GoS levels. He assumed that the number of machines providing high GoS is not known before scheduling and decisions must be made without knowledge of the exact number of machines providing higher GoS. In other words, we only know that in all 10 parallel machines there are k (1 ≤ k ≤ 9) machines which can provide higher GoS. Under this consideration, he proved that 2 is a lower bound of online algorithms and proposed an online algorithm with a competitive ratio of 12+4 √ 2 7

. The online algorithm they designed is with many details. The general idea is also to use some criterion to distinguish different situations. Some criteria are chosen in a similar way as that in [START_REF] Park | Online and semi-online scheduling of two machines under a grade of service provision[END_REF].

To the best of our knowledge, the most recent results with GoS constraint are the research of online scheduling on two uniform machines [START_REF] Liu | Online scheduling on two uniform machines to minimize the makespan[END_REF][START_REF] Lee | Online scheduling on two uniform machines subject to eligibility constraints[END_REF].

Minimizing makespan plus penalties

In this variant, jobs may be rejected at a certain penalty. Each job is characterized by the processing time and the penalty. A job can either be rejected by paying its penalty or scheduled on one of the machines. The objective is to minimize the makespan of the schedule for accepted jobs plus the sum of the penalties of all rejected jobs. The purpose of an online algorithm is to balance the penalties and the increase in the makespan. (It is a little puzzling to add two different quantities together as one objective function. Given two weights on two kinds of quantities, this objective can be viewed as a multiple-objective decision.)

This problem of Multiprocessor Scheduling with Rejection (MSR) was introduced by Bartal et al. [START_REF] Bartal | Multiprocessor scheduling with rejection[END_REF]. The main goal of an algorithm designed for online MSR problem is to choose the proper balance between the penalties yielded by rejecting jobs and the increase in the makespan for the accepted jobs. At the beginning it might have to reject some jobs if the penalty for their rejections is small compared to their processing times. However, at a certain point, it would be better to schedule some of the previously rejected jobs since the increase in the makespan due to scheduling those jobs in parallel is less than the total penalty incurred. In this scenario, the online MSR problem can be seen as a nontrivial generalization of the well known Rudolph's ski rental problem. (In that problem, a skier has to choose whether to rent skis for the cost of 1 per trip, or to buy them for the cost of c without knowing the future number of trips. The best possible deterministic strategy is to rent for the first c trips and buy afterwards. In online MSR problem, rejecting jobs is analogous to renting while scheduling one job is analogous to buying.) They showed an 1 + φ ≈ 2.618competitive algorithm, where φ is the golden ratio. Their algorithm used two simple rules. First, all jobs in the set B are rejected, where B denote the set of jobs such that each jobs' penalty is smaller than its load. The second rule that a job is rejected unless its penalty added to the total penalty of the hitherto rejected jobs would be higher than some prescribed fraction of its processing time. This rule is inspired by the relation of MSR to the ski-rental problem. The algorithms of Bartal et al. [START_REF] Bartal | Multiprocessor scheduling with rejection[END_REF] consist of two parts, a rejection scheme, which decides which jobs are rejected, and a scheduling algorithm, which assigns accepted jobs to a machine. The rejection schemes are combined with Graham's LIST algorithm.

If preemption is allowed, Seiden [START_REF] Seiden | Preemptive multiprocessor scheduling with rejection[END_REF] gave an 4+ √ 10 3 ≈ 2.38743-competitive algorithm and showed a lower bound of 2.12457. The algorithms they proposed also consist of two parts, a rejection scheme and a scheduling algorithm. In fact, the rejection schemes given in [START_REF] Bartal | Multiprocessor scheduling with rejection[END_REF] can be combined with any scheduling algorithm. The general idea in [START_REF] Seiden | Preemptive multiprocessor scheduling with rejection[END_REF] is that by combining the rejection schemes with algorithms for different scheduling models, Seiden get new algorithms for scheduling with rejection.

Gyorgy an Imreh [START_REF] Gyorgy | Online scheduling with machine cost and rejection[END_REF] investigated a new scheduling model where the number of machines is not fixed, the algorithm has to purchase the used machines, and the jobs can be rejected. They presented an algorithm OPTCOPY with a competitive ratio 2.618. The basic idea behind this algorithm is to consider a relaxed version where we replace part of the cost of the schedule (purchasing cost of machines plus the makespan) with a lower bound of it. Imreh [START_REF] Imreh | Online scheduling with general machine cost functions[END_REF] further considered the problem with general machine cost functions.

Online scheduling of open shop scheduling problem was studied in [START_REF] Chen | A study of on-line scheduling two-stage shops[END_REF][START_REF] Chen | On-line scheduling of small open shops[END_REF]. There are not many results in this research field, and all this kind of research concentrates on looking for permutation algorithms, where the schedule has the same job sequence on each of the machines.

Machine covering problems

The machine covering problem deals with partitioning a sequence of jobs among a set of machines, so as to maximize the completion time of the least loaded machine, where the load of a machine is the total time required to complete all jobs assigned to it. Machine covering problem is also called the Santa Claus problem, where n indivisible goods are to be partitioned among m clients. The goal is to distribute the goods in a way that the least satisfied client is still as pleased as possible. The offline problem is strongly NP-hard. The online machine covering is associated with the online paradigm where jobs arrive one by one, since there is no need to refer to release times. The objective of online machine covering problems is to maximize the minimum load of any machine (denoted by C min ).

Maximizing the minimum machine completion time is NP-complete in the strong sense. Deuermeyer et al. [START_REF] Friesen | Scheduling to maximize the minimum processor finish time in a multiprocessor system[END_REF] examined the behavior of the Longest Processing Time (LPT) rule to approximate the optimum solution. The LPT rule sorts all jobs into a sequence of nonincreasing processing times and then sequentially assigns each job to the next machine available. They showed that the minimum completion time in the schedule produced by LPT is at least 3/4 times the minimum completion time in the optimum schedule. Csirik et al. [START_REF] Csirik | The exact lpt bound for maximizing the minimum completion time[END_REF] tightened the analysis of LPT by showing that the LPT remains within a factor of (3m -1)/(4m -2) of the optimum solution and that this bound is tight. Observe that in the online paradigm where jobs arrive list, LIST algorithm behaves like LPT, but starts with an unsorted list (partial unknown). Thus, in the research of online machine covering, LIST and LPT are the same.

For m identical machine environment, Woeginger [START_REF] Woeginger | A polynomial time approximation scheme for maximizing the minimum machine completion time[END_REF] analyzed an simple online algorithm LPT which assigns a new job to the least loaded machine and showed that LPT is best possible with a competitive ratio m. Obviously, LPT is a kind of greedy algorithm.

After that, some scholars tried to overcome high competitive ratio by using additional information, i.e., they studied semi-online variants. Azar and Regev [START_REF] Azar | On-line bin-stretching[END_REF] considered those problems whose optimal objective function value is known in advance (denoted by opt). Kellerer et al. [START_REF] Kellerer | Semi on-line algorithms for the partition problem[END_REF] considered the problem that the total processing time of all the jobs is known in advance (denoted by sum). He and Zhang [START_REF] He | Semi on-line scheduling on two identical machines[END_REF] considered the problem that the largest processing time of all jobs is known in advance (denoted by max ). In the same paper, they also considered the problem that the processing time of jobs are tightly-grouped or bounded in a interval (denoted by tightly-grouped ). Seiden et al. [START_REF] Seiden | Semi-online scheduling with decreasing job sizes[END_REF] considered the information that jobs are arriving in nonincreasing processing time order (denoted by decr ). For problem P m|online, tightly -grouped|C min , He Yong [START_REF] He | The optimal on-line parallel machine scheduling[END_REF] proved that LIST algorithm is still optimal.

Azar and Epstein [START_REF] Azar | On-line machine covering[END_REF] proposed an algorithm FILL for P m|opt|C min with a competitive ratio 2 -1/m , and it is optimal for m = 2, 3, 4. In contrast to LIST algorithm which tries to assign jobs to all the machines evenly, FILL works as follows (The optimal solution is 1.): "If there are no empty machines, assign a new job to the least loaded machine. Otherwise, if the processing time of the new job is at least m/(2m -1), assign it to an empty machine. If the processing time of the job is less than m/(2m -1)

assign it to the active machine if exists, and otherwise to an empty machine."

At first, the FILL algorithm tries to keep a certain load difference between all empty machines and non empty machines. If there exist no empty machine, FILL algorithms works as LIST.

Tan and Wu [START_REF] Tan | Optimal semi-online algorithms for machine covering[END_REF] investigated the semi-online machine covering problems on m ≥ 3 parallel identical machines. Three different semi-online versions are studied and optimal algorithms are proposed in that paper. They proved that if the total processing time of all jobs or the largest processing time of all jobs is known in advance, the competitive ratios of the optimal algorithms are both m -1. If the total processing time and the largest processing time of all jobs are both known in advance, the competitive ratios of the optimal algorithms are 3/2 when m = 3, and m -2 when m ≥ 4. Generally speaking, all these three semi-online algorithms are designed based on LIST algorithm.

Another part of semi-online research concentrates on two uniform machines. Epstein [START_REF] Epstein | Tight bounds for online bandwidth allocation on two links[END_REF] analyzed LPT algorithm with the knowledge of optimal value on two uniform machines, where the speeds of two machines are s and 1 respectively. He showed that LPT is s + 1-competitive. In the same machine environment, the case where total processing time is known in advance was studied in [START_REF] Tan | Semi-online machine covering on two uniform machines with known total size[END_REF]. Cao and Tan [START_REF] Cao | Online uniform machine covering with the known largest size[END_REF] considered the case where the size of the largest job is declared in advance.

Minimizing makespan with parallel jobs

First note that parallel jobs are also called multi-processor jobs. In practice (i.e., in parallel supercomputers) some jobs can only be processed on several processors in parallel. The online problem of parallel job scheduling can be described as follows. A job J j = (s, p) is associated with two parameters p and s, where p is the processing time of the job and s is the width (or number of machines) required for simultaneous processing. The jobs arrive over list. Preemption and reassignment are not allowed. The goal is to minimize the makespan.

It has been shown that LIST algorithm is best possible in the online models: the one where jobs arrive over time and the one with unknown processing times [START_REF] Shmoys | Scheduling parallel machines on-line[END_REF].

In general, if a job can request any number of available machines, Johannes [START_REF] Johannes | Scheduling parallel jobs to minimize the makespan[END_REF] presented an online algorithm with competitive ratio 12. She also proved that no online algorithm is better than 2.25-competitive. Johannes' algorithm consists of two parts: partition part and schedule part. In partition part, the time axis is divided into different length intervals with such that the length is doubled at each time (i.e., intervals

I i := [2 i , 2 i+1 ], i = 0, 1...)
. The purpose of this step is to contain waiting strategy in the algorithm. In the second part, the algorithm schedules the job with bigger width as late as possible and the one with smaller width as early as possible. We call it small early big late principle.

Ye and Zhang [START_REF] Ye | On-line scheduling of parallel jobs[END_REF] improved the upper bound by giving an 8-competitive on-line algorithm DW. The nature of DW algorithm is also a combination of waiting strategy and a principle of small early big late. But DW algorithm differs from Johannes' algorithm in the aspect of waiting time. There were also some results for the cases where some extra information on the jobs is known in advance, i.e., semi-online algorithms. If the jobs arrive in a non-increasing order of processing times, Ye and Zhang proved that greedy strategy works well by showing that greedy algorithm is 2-competitive [START_REF] Ye | On-line scheduling of parallel jobs[END_REF]. In this situation, there is no need to introduce waiting strategy.

Recent results of online scheduling on parallel jobs focus mostly on a special case with two machines. We know that greedy algorithm simply schedules all jobs one after another leaving no idle time between jobs. Chan et al. [START_REF] Chan | On-line scheduling of parallel jobs on two machines[END_REF] mentioned that greedy algorithm is 2-competitive and proved a lower bound 1 + 2/3. It seems that greedy algorithm works well in this machine setting. Hurink and Paulus [START_REF] Hurink | Online scheduling of parallel jobs on two machines is 2-competitive[END_REF] further revealed that the lower bound is 2, which means that greedy algorithm is the best possible in two machine environment. For two machine scheduling problem, to improve the competitive ratio, Chan et al. [START_REF] Chan | On-line scheduling of parallel jobs on two machines[END_REF] proved that greedy algorithm is optimal with a competitive ratio 3/2 in the case where jobs arrive in a non-decreasing order of processing times. In contrast, in the case where jobs arrive in a non-increasing order of processing times, greedy was shown to be 4/3-competitive [START_REF] Chan | On-line scheduling of parallel jobs on two machines[END_REF].

Minimizing total completion time plus penalties

This objective is rarely studied in the online paradigm where jobs arrive over list. Epstein et al. [START_REF] Epstein | Online scheduling of unit time jobs with rejection: minimizing the total completion time[END_REF] investigated a single machine environment to minimize the total completion time plus penalties. Even if the machine environment is relatively simple compared to those of the previous section, but the objective is more difficult. To solve such a problem, they had to appeal to a strong assumption that jobs' processing times are identical. Otherwise, they showed that there exist no online algorithm with finite competitive ratio. The main idea of their algorithm is not difficult to understand. The nature of their algorithm is to select a criterion to determine accepting or rejecting a current job, as those algorithms mentioned in the previous section. Since all jobs have identical processing times, the number of accepted jobs can denote the total completion time.

Algorithm GREEDY they proposed is a quite simple greedy-type algorithm: when deciding about job J j , it has the choice between processing the job at a cost (a function of the number of currently accepted jobs), and rejecting the job at a cost. In the function of currently accepted jobs' number, GREEDY multiplies a factor for the reason that an accepted job is more dangerous since it may increase the cost of later jobs, whereas a rejected job cannot. A benefit of this factor is easy to adjust the algorithm in order to achieve a small competitive ratio.

Semi-online scheduling problems

Some scholars tried to improve the algorithm by considering additional jobs' information. Some constraints are extensively studied in the literature. He and Dosa [START_REF] He | Semi-online scheduling jobs with tightly-grouped processing times on three identical machines[END_REF], as well as Du [START_REF] Du | Optimal preemptive semi-online scheduling on two uniform processors[END_REF], considered the constraint that jobs' processing times are bounded in a certain interval. Cheng et al. [START_REF] Cheng | Semi-online multiprocessor scheduling with given total processing time[END_REF] investigated the semi-online problems with knowledge of total processing times.

Tan and He [START_REF] Tan | Semi-online problems on two identical machines with combined partial information[END_REF] investigated the semi-on-line versions of scheduling problem with combination of two types of information which belong to five basic types. These types of information are the total processing times (sum), the largest processing time (max), non-increasing processing times (decr), the knowledge of last job arriving (sugg), the knowledge of last job with the largest processing time (LL).

Tan and He [START_REF] Tan | Semi-online scheduling problems on two identical machines with inexact partial information[END_REF] further studied semi-online scheduling problems with the assumption that some partial additional information is not exactly known in advance. Three versions were considered [START_REF] Tan | Semi-online scheduling problems on two identical machines with inexact partial information[END_REF], where we know in advance that the total size of all jobs, the optimal value, and the largest job size are in given intervals, respectively, while their exact values are unknown.

Jobs arrive over time

In this online paradigm, online features are the existence of the jobs whose release time does not pass yet and the specific release time.

Minimizing makespan

If preemption is allowed, there exists an optimal online algorithm which is 1competitive for identical machine scheduling [START_REF] Gonzales | A new algorithm for preemptive scheduling of trees[END_REF][START_REF] Hong | Online scheduling of real-time tasks[END_REF]. The idea behind the algorithm is that whenever a new job arrives, we reschedule the unfinished parts of previous jobs and all unscheduled jobs so that they are finished as early as possible. For uniformly related machines, an optimal algorithm exists if and only if the speeds of machines satisfy si-1 si ≤ si si+1 , where s i is the speed of ith fastest machine [START_REF] Vestjens | Scheduling uniform machines on-line requires nondecreasing speed ratios[END_REF].

Without preemption, the best upper bound for parallel machine scheduling was obtained for the simple algorithm which always schedules the longest job within available jobs. This algorithm is 3 2 -competitive and a lower bound of 1.3473 is shown [START_REF] Chen | Scheduling on identical machines: How good is lpt in an on-line setting?[END_REF].

If we consider jobs' delivery times, the objective function makespan shifts to the maximum time by which all jobs have been delivered. For a single machine scheduling problem, Hoogeveen and Vestjens [START_REF] Hoogeveen | Optimal on-line algorithms for single-machine scheduling[END_REF] proposed an optimal online algorithm D-LDT which is

√ 5+1 2 -competitive.
The idea of algorithm D-LDT is that if no jobs with a large processing requirement are available, then we should schedule the job with the largest delivery time; otherwise, we should decide whether to schedule the large job, the job with the largest delivery time, or no job at all. Based on this idea, the situation with bounded delivery times was further considered in [START_REF] Tian | A best on-line algorithm for single machine scheduling with small delivery times[END_REF][START_REF] Liu | An optimal online algorithm for single machine scheduling with bounded delivery times[END_REF]. For parallel machine environment, Vestjens [START_REF] Vestjens | On-line machine scheduling[END_REF] gave a lower bound 1. [START_REF] Azar | Online scheduling with precedence constraints[END_REF].

For open shop scheduling on two machines, the greedy algorithm is optimal with a competitive ratio 3 2 [START_REF] Vestjens | On-line machine scheduling[END_REF]. If preemption is considered, he developed an optimal 5 4 -competitive algorithm [START_REF] Vestjens | On-line machine scheduling[END_REF].

Minimizing makespan on batch machine environment

When the machine environment shifts to batch processing machine, the results get scarce, especially for open shop and flow shop problems. A batch processing machine can handle up to B (the capacity of a machine) jobs simultaneously. The jobs that are processed together form a batch, and all jobs in a batch start and complete at the same time. The processing time of a batch is given by the longest processing time of any job in the batch. Jobs arrive over time.

The objective is to minimize the makespan. For the unbounded case where the capacity B is sufficiently large (i.e., all jobs can be processed simultaneously in a single batch), Zhang et al. [START_REF] Zhang | On-line algorithms for minimizing makespan on batch processing machines[END_REF] designed an optimal √ 5+1 2 -competitive algorithm H ∞ . The intuition behind this algorithm is that jobs should rather wait for a while than being processed immediately after they arrive, i.e., waiting strategy. In order to show the algorithm is σ-competitive, the waiting time is determined for the purpose that the completion time of one job can not exceed σ times the optimal value, i.e., the completion time of that job in an optimal schedule.

For parallel batch machine environment, the difficulty of the problems increase dramatically. Zhang et al. [START_REF] Zhang | Optimal online algorithms for scheduling on parallel batch processing machines[END_REF] further considered the problem on m identical parallel batch machines. When the batch capacity is infinite, i.e., unbounded case, we need not only to group the jobs into batches as for the single machine problem, but also to choose a machine for an available batch. Under the assumption that jobs' processing times are identical, Zhang et al. [START_REF] Zhang | Optimal online algorithms for scheduling on parallel batch processing machines[END_REF] proposed a best possible online algorithm with competitive ratio 1 + β m , where β m is the positive solution of equation (1 + β m ) m+1 = β m + 2. The intuition behind this algorithm is similar to the algorithm H ∞ they proposed for a single batch machine environment. The main idea is also to postpone the processing of jobs. The algorithm for m batch machines contains a waiting time, which is determined in order to control the completion time of one job not greater than σ times the optimal value (i.e., the completion time of that job in an optimal schedule). When the batch capacity is finite, they provided a best possible online algorithm A b (α) with a competitive ratio α = √ 5+1

2 . For this algorithm, the basic idea is also to postpone the starting times of jobs such that their completion times can not exceed α times the optimal value. In the algorithm, we also have to make sure that the capacity of a batch does not exceed its capacity. This character is due to the machine environment, i.e., the batch capacity is finite.

Here is a question: "Does there exist an optimal algorithm for parallel batch machines without any restriction?" Nong et al. [START_REF] Nong | An improved online algorithm for scheduling on two unrestrictive parallel batch processing machines[END_REF] investigated the problem on two parallel batch machines with infinite capacity. They provided an algorithm with a competitive ratio √ 2. The idea of their algorithm is similar to Zhang's algorithm. Use waiting strategy to design the algorithm and control the completion time of a job not bigger than √ 2 times the optimal one. Tian et al. [START_REF] Tian | A best online algorithm for scheduling on two parallel batch machines[END_REF] showed a lower bound √ 2 of competitive ratio, which means that Nong's algorithm is optimal. They also proposed a new algorithm also using waiting strategy, which is more efficient than Nong's algorithm.

Considering delivery time in batch machine scheduling, Tian et al. [START_REF] Tian | Online scheduling with delivery time on a single batch machine[END_REF] provided an online algorithm H ∞ 1 with a competitive ratio 2 for infinite batch machine situation and an algorithm H B with a competitive ratio 3 for finite batch situation. The idea of algorithm H ∞ 1 is to use a forwards dynamic programming proposed in [START_REF] Brucker | Scheduling a batching machine[END_REF] as a component to schedule current arriving jobs. For algorithm H B , the idea is similar to regular one which uses a waiting strategy and controls the completion time of one job not bigger than 3 times the optimal value. The speciality of this problem is that jobs' delivery times contribute to their completion times. It is also necessary to make sure that the capacity of a batch does not exceed its capacity.

Since no optimal algorithm for the problems with delivery times had been obtained, Yuan et al. [START_REF] Yuan | A best online algorithm for the single machine parallel-batch scheduling with restricted delivery times[END_REF] considered two restricted models: (1) the jobs have small delivery times, i.e., for each job J j its delivery time q j is not bigger than its processing time, (2) the jobs have agreeable processing and delivery times, i.e., for any two jobs J i and J j , p i > p j implies q i ≥ q j . They proposed an optimal algorithm for these two restricted situation. The intuition behind this algorithm is also to postpone the starting time of batch.

There are other papers which studied batch machine scheduling models with additional constraints. Ridouard et al. [START_REF] Ridouard | Online scheduling on a batch processing machine with unbounded batch size to minimize the makespan[END_REF] also considered agreeable processing times constraint. Fu et al. [START_REF] Fu | On-line scheduling in a parallel batch processing system to minimize makespan using restarts[END_REF][START_REF] Fu | On-line scheduling on a batch machine to minimize makespan with limited restarts[END_REF] investigated the problems with restarts. Nong et al. [START_REF] Nong | The single-machine parallel-batching on-line scheduling problem with family jobs to minimize makespan[END_REF] addressed the problem with family jobs.

Minimizing total completion time

For preemptive scheduling on a single machine, it is easy to construct an optimal schedule by always scheduling the job with shortest remaining processing time. The same rule yields a 2-competitive algorithm for identical machine problem [START_REF] Philips | Minimizing average completion time in the presence of release dates[END_REF].

For single machine problem, if preemption is not allowed, 2-competitive algorithms were given and they are optimal [START_REF] Vestjens | On-line machine scheduling[END_REF][START_REF] Lu | A class of online scheduling algorithms to minimize total completion time[END_REF]. The idea behind these algorithms (such as Delayed SPT [START_REF] Vestjens | On-line machine scheduling[END_REF]) is to shift release times, then schedule them by SPT (shortest processing time) rule.

Stee and Poutre [START_REF] Stee | Minimizing the total completion time online on a single machine, using restarts[END_REF] investigated single machine variant with restarts. Allowing restarts means that the processing of a job may be interrupted, losing all the work done on it. In this case, the job must be started again later (restarted), until it is completed without interruptions. By using restarts, Stee and Poutre [START_REF] Stee | Minimizing the total completion time online on a single machine, using restarts[END_REF] designed an algorithm RSPT (restarting SPT) with a competitive ratio 3 2 . RSPT bases the decision about whether or not it will interrupt a current processing job J j for an arriving job J j solely on J j and J j . It ignores, for example, all other jobs that are waiting to be processed. RSPT only interrupts a job J j for jobs that are smaller and that can finish earlier than J j . In fact, RSPT algorithm is identical to SRPT (Shortest Remaining Processing Time) rule and ECT (Earliest Completion Time) rule. Their results showed that restarts help.

For minimizing total weighted completion time, a slight modification of Delayed-SPT also yields an optimal online algorithm with a competitive ratio 2 [START_REF] Anderson | Online scheduling of a single machine to minimize total weighted completion time[END_REF]. The intuition behind this modification Delayed SWPT is to shift the release times, then schedule them by SWPT (shortest weighted processing time) rule.

For parallel machine variants, Vestjens [START_REF] Vestjens | On-line machine scheduling[END_REF] showed a lower bound 1.309. Liu and Lu [START_REF] Liu | Online scheduling of parallel machines to minimize total completion times[END_REF] developed a slightly modified algorithm DSPT with a competitive ratio 2. Their algorithm DSPT differs from Delayed SPT in choosing one of the available machines. In the preemption-resume environment, the currently known lower bound is 22 21 given by Vestjens [START_REF] Vestjens | On-line machine scheduling[END_REF]. Chekuri et al. [START_REF] Chekuri | Approximation techniques for average completion time scheduling[END_REF] presented a relaxation technique that converts a scheduling problem of parallel machines to a preemptive scheduling problem on a single machine. Based on this technique, they gave a (3-1 m )-competitive algorithm for P |r j , online| C j . Recently, Liu and Lu [START_REF] Liu | Online scheduling of two uniform machines to minimize total completion times[END_REF] studied two uniform machine variant and presented a 2.618-competitive algorithm FCFS for Q2|r j , online| C j . They also used this relaxation technique to convert the original problem to a preemptive single machine problem, and then applied SRPT rule for this relaxation problem. FCFS algorithm uses the new schedule obtained by solving the relaxation problem to determine how to assign the current job. Since SRPT rule works online, the FCFS is an online algorithm. For two uniform machine en-vironment, they further considered the weights of jobs and preemption-resume setting, i.e., Q2|r j , online, pmtn| w j C j . Suppose two machines are M 1 with speed 1 and M 2 with speed s, respectively. They showed that WSPT (Weighted SPT) algorithm is 2-competitive. We say that one job J j with a lower value of the ratio p j /w j has a higher priority, where p j is the processing time, and w j is the weight. WSPT rule always schedules the job with the highest priority among available processing jobs on M2, then schedule the job with the highest priority among remaining available processing jobs on M 1 , if any. This algorithm is a extension of WSPT rule for parallel machine situations. Liu et al. [START_REF] Liu | Online scheduling on m uniform machines to minimize total (weighted) completion time[END_REF] further studied Q|r j , online| C j and Q|r j , online, pmtn| w j C j .

Maximization the number of early jobs

Maximization problems were rarely studied. In offline scheduling, a similar objective function, minimizing the number of late jobs (or weighted number of late jobs), was widely studied [START_REF] Baptiste | An O(n 4 ) algorithm for preemptive scheduling of a single machine to minimize the number of late jobs[END_REF][START_REF] Baptiste | On minimizing the weighted number of late jobs in unit execution time open-shops[END_REF][START_REF] Lawler | A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs[END_REF][START_REF] Moore | An n job, one machine sequencing algorithm for minimizing the number of late jobs[END_REF][START_REF] Potts | Algorithms for scheduling a single machine to minimize the weighted number of late jobs[END_REF]. Other objective functions related to earliness and tardiness were also investigated in offline framework [START_REF] Sourd | The one-machine problem with earliness and tardiness penalties[END_REF][START_REF] Sourd | Earliness-tardiness scheduling with setup considerations[END_REF][START_REF] Hendel | Efficient neighborhood search for the onemachine earliness-tardiness scheduling problem[END_REF][START_REF] Hendel | An improved earliness-tardiness timing algorithm[END_REF][START_REF] Runge | A new model for the preemptive earlinesstardiness scheduling problem[END_REF].

In online scheduling, for maximizing the number of early jobs on a single machine in the preemption-restart model, Hoogeveen et al. [START_REF] Hoogeveen | On-line scheduling on a single machine: maximizing the number of early jobs[END_REF] provided an optimal algorithm SRPT with a competitive ratio 1/2. This algorithm is based on the SRPT (shortest remaining processing time) rule or ECT (earliest completion time) rule. Further study for parallel machines were investigated by Liu et al. [START_REF] Liu | Online scheduling parallel machines to maximize the number of early jobs[END_REF].

Other constraints and objectives were also studied in the literature. Epstein and Stee [START_REF] Epstein | Lower bounds for online single-machine scheduling[END_REF] investigated the model with restarts. Azar and Epstein [START_REF] Azar | Online scheduling with precedence constraints[END_REF], as well as Huo et al. [START_REF] Huo | Online scheduling of equalprocessing-time task systems[END_REF], studied online scheduling with precedence constraints. Kellerer et al. dealt with the objective of minimizing total flow time. Megow and Schulz [START_REF] Megow | Online scheduling to minimize average completion time revisited[END_REF] addressed the online problem to minimize average completion time revisited. Zheng et al. [START_REF] Zheng | A tight lower bound for job scheduling with cancellation[END_REF] considered online scheduling with cancelation. Havill and Mao [START_REF] Havill | Competitive online scheduling of perfectly malleable jobs with setup times[END_REF] considered online scheduling of perfectly malleable jobs with setup times. Zheng et al. [START_REF] Zheng | How much can lookahead help in online single machine scheduling[END_REF] investigated semi-online variant with lookahead information.

Summary

Greedy and waiting strategies are often used in designing the algorithms. In parallel machine scheduling, LIST algorithm plays an important role. The golden ratio occurs in the computation of competitive ratio. (Is this a coincidence or the beauty of mathematics?)

Even if hundreds of online scheduling problems and models have been studied and analyzed in the past, there are still a lot of problems which have not been employed or perfectly solved.

Chapter 3

Single machine model

We study an online scheduling problem on a single machine with delivery times. The problem is online in the sense that all jobs arrive over time. Each job's characteristics, such as processing time and delivery time, become known at its arrival time. Preemption is not allowed and once the processing of a job is completed we delivery it to the destination by a vehicle. The objective is to minimize the time by which all jobs have been delivered. In this chapter, we assume that all jobs have bounded delivery times, which means that given a certain positive number β ≥ 1 2 , for each job J j , we have a release time r j ≥ 0 and βq j ≤ p j , where p j , q j denote the processing time and the delivery time of job J j , respectively. We use 1|online, r j , βq j ≤ p j |L max to denote the problem for short, where L max denote the time by which all jobs have been delivered. We prove a lower bound of competitive ratios for all online algorithms and propose an optimal online algorithm with a competitive ratio of 1 2 ( 5 + β 2 + 2β+1-β).

Introduction

Makespan, the completion time of last job in the schedule, is commonly researched in the literature. This is an objective in the aspect of manufacturers.

In order to consider the problems in the aspect of the clients, we focus our attention on the time when each client receive his demanded job (or product), that is the sum of completion time and delivery time of that job. In practice, a job's delivery time cannot be unlimited. These reasons motivate us to investigate online scheduling problem on a single machine with bounded delivery times.

The problem considered can be described as follows. There are n jobs, a single machine and sufficiently many vehicles. Each job has an arrival time, a processing time, and a bounded delivery time. These characteristics of a job are unknown until it arrives. Once the processing of a job is completed on a machine, we deliver it to the destination by a vehicle. No preemption is allowed. The objective is to minimize the time by which all jobs have been delivered. We use r j , p j and q j to denote the arrival time, the processing time and the delivery time of job J j , respectively. The bounded delivery time means that there is a certain positive number β ≥ 1 2 , such that βq j ≤ p j for any j such that 1 ≤ j ≤ n. Suppose that σ is a schedule of the jobs. We use S j (σ), C j (σ) and L j (σ) to denote the starting time of J j , the completion time of J j and the time by which J j has been delivered in schedule σ. The objective function of the considered problem can be expressed as follows,

L max (σ) = max{L j (σ) : L j (σ) = C j (σ) + q j , 1 ≤ j ≤ n}.
Under offline setting, there are many results about scheduling problem with the objective to minimize the time by which all jobs have been delivered. A well known algorithm called the LDT rule (largest delivery time first) is optimal for the problem 1||L max . For problem 1|r j |L max , Kise et al. [START_REF] Kise | Performance analysis of six approximation algorithms for the one-machine maximum lateness scheduling problem with ready times[END_REF] proved that the LDT rule is 2-approximate and Lawer et al. [START_REF] Lawler | Sequencing and scheduling: Algorithms and complexity[END_REF] proved that the problem is strongly NP-hard. While under online setting, Hoogeveen et al. [START_REF] Hoogeveen | A best possible deterministic online algorithm for minimizing maximum delivery time on a single machine[END_REF] provided an optimal online algorithm with a competitive ratio of

√ 5+1 2
for the problem 1|online, r j |L max . Based on these results, Tian et al. [START_REF] Tian | A best on-line algorithm for single machine scheduling with small delivery times[END_REF] showed a better online algorithm with competitive ratio of √ 2 for the problem 1|online, r j , q j ≤ p j |L max .

In this chapter, we consider the problem 1|online, r j , βq j ≤ p j |L max , where β ≥ 1 2 . The rest of this chapter is organized as follows. In Section 2, we show that no online algorithm has a competitive ratio less than 1 2 ( 5 + β 2 + 2β + 1β). In section 3, we propose an online algorithm for this problem. In Section 4, we prove the algorithm proposed in section 3 is optimal.

A lower bound of competitive ratio

In this section, we present a lower bound of competitive ratio for the problem, i.e., ϕ = 1 2 ( 5 + β 2 + 2β + 1β). Note that in the following proof, we consider the problem where β > 0. And the result is a general lower bound containing the case where β ≥ 1 2 . For simplicity of expression, let ϕ = 1 2 ( 5 + β 2 + 2β + 1β), where β > 0. We derive a simple but important equality, which will be used in the following proofs.

Lemma 1 1 ϕ+β = ϕ -1 = 1+ϕ-ϕ 2 β > 0.
Proof.

1 ϕ + β = 2 5 + β 2 + 2β + 1 + β = 2( 5 + β 2 + 2β -(1 + β)) 5 + β 2 + 2β -(1 + β) 2 = 1 2 ( 5 + β 2 + 2β -1 -β) = ϕ -1. ϕ 2 = 1 4 [5 + β 2 + 2β + 1 + β 2 -2β + 2(1 -β) 5 + β 2 + 2β] = 1 2 [3 + β 2 + (1 -β) 5 + β 2 + 2β]. 1 + ϕ -ϕ 2 β = β 5 + β 2 + 2β -β -β 2 2β = 1 2 ( 5 + β 2 + 2β -1 -β) = ϕ -1. ϕ -1 = 1 2 ( 5 + β 2 + 2β -1 -β) = 1 2 [ 4 + (1 + β) 2 -(1 + β)] > 0.
According to the above equalities and inequality, we have the desired result.

Theorem 1 For the problem 1|online, r j , βq j ≤ p j |L max , no online algorithm has a competitive ratio less than ϕ = 1 2 ( 5 + β 2 + 2β + 1β), where β > 0.

Proof. For any online algorithm A, we consider the following instance. Let π and σ denote an optimal offline schedule and the schedule produced by online algorithm A for the instance, respectively. We use J j = (p j , q j ) to denote a job J j , where p j and q j are the processing time and the delivery time of J j , respectively. The first job J 1 = (1, 0) arrives at time 0. We assume that algorithm A schedules J 1 = (1, 0) at time T A ≥ 0. From Lemma 1, we know that ϕ -1 > 0. Depending on T A , we consider two cases as follows. (Job J 1 = (1, 0) is constructed in order to avoid algorithm A schedules it too early, i.e., before time ϕ -1).

Case 1:

T A ≥ ϕ -1.
In the worst-case, no jobs arrive any more. In an optimal situation, J 1 = (1, 0) is scheduled at time 0, which gives L max (π) = 1. Then

L max (σ) L max (π) = T A + 1 1 ≥ ϕ. Case 2: 0 ≤ T A < ϕ -1.
In the worst-case, the second job J 2 = (β, 1) arrives at time T A . The optimal solution consists of scheduling J 2 then J 1 . Thus

L max (σ) L max (π) = T A + 1 + β + 1 T A + β + 1 = 1 + 1 T A + β + 1 > 1 + 1 ϕ + β .
From Lemma 1, it follows that 1 + 1 ϕ+β = 1 + ϕ -1 = ϕ. Therefore, we have

L max (σ) L max (π) > ϕ (ε → 0).
The theorem follows.

Remark 1 For the problem 1|online, r j |L max , let β → 0, then we obtain the lower bound of

√ 5+1 2
proved in [START_REF] Hoogeveen | A best possible deterministic online algorithm for minimizing maximum delivery time on a single machine[END_REF].

Remark 2 For the problem 1|online, r j , q j ≤ p j |L max , which is a special case of our model with β = 1, we obtain the lower bound of √ 2 proposed in [START_REF] Tian | A best on-line algorithm for single machine scheduling with small delivery times[END_REF].

The lower bound 1 2 ( 5 + β 2 + 2β + 1β), where β > 0, is a generalized lower bound.

An online algorithm EX-D-LDT

The idea of the algorithm is originated from D-LDT algorithm (delayed LDTrule) proposed in [START_REF] Hoogeveen | A best possible deterministic online algorithm for minimizing maximum delivery time on a single machine[END_REF]. Considering the proof of the lower bound, we know that if an algorithm wants to guarantee a better performance bound, then it needs a waiting strategy. Therefore, we modify the LDT (Largest Delivery Time) rule and add some waiting times. Since we use the same idea as for D-LDT algorithm, we must mention the idea first. The basic idea behind D-LDT algorithm is that, if no jobs with a large processing requirement are available, then we schedule the job with the largest delivery time; otherwise, we decide whether to schedule the large job, the job with the largest delivery time, or no job at all. The algorithm EX-D-LDT (Extended D-LDT) described in the following has a few differences from that in [START_REF] Hoogeveen | A best possible deterministic online algorithm for minimizing maximum delivery time on a single machine[END_REF]. For the case where β ≥ 1 2 , we have

1 < ϕ ≤ 3 2 . (3.1)
First, adopt some notations from [START_REF] Hoogeveen | A best possible deterministic online algorithm for minimizing maximum delivery time on a single machine[END_REF] and [START_REF] Tian | A best on-line algorithm for single machine scheduling with small delivery times[END_REF].

-p(S) denotes the total processing time of all jobs in the set S, i.e., p(S) = Jj ∈S p j ; -J(t) is the set containing all jobs that arrived at or before time t; -U (t) is the set containing all jobs in J(t) that have not been started at time t;

-t 1 denotes the start time of the last idle time period before time t; if there is no idle time, then define t 1 = 0; -A job J j is said to be big if p j > 1 ϕ p((J(t)\J(t 1 )) U (t 1 )); -p max (t) denotes the index of the job with the largest processing time in U (t); -q max (t) denotes the index of the job with the largest delivery time in U (t). Note that (J(t)\J(t 1 )) U (t 1 ) contains the jobs which arrive from time t 1 to t and the jobs which were not started (or completed, since t 1 is the start time of idle time) at time t 1 ; if t 1 = 0, (J(t)\J(t 1 )) U (t 1 ) = J(t) for any t. And also, from equality (3.1), we have

1 ϕ ≥ 2 3 > 1 2
. Therefore, there is at most one big job at any time t. The online algorithm runs as follows.

Algorithm EX-D-LDT Step 1: Wait until a decision point, where the machine is idle and a job is available (if all jobs have been scheduled, output the schedule). Suppose this happens at time t. Determine p max (t) and q max (t).

Step 2: If there is no big job available, then schedule J qmax(t) . Go to Step 1.

Step 3: The lower bound ϕ is a key parameter in the algorithm. In Step 1 the algorithm wait to a decision point and find the job with the largest processing time J pmax(t) and the job with the largest delivery time J qmax(t) . If all jobs in the job instance have been scheduled, the algorithm stop and output the schedule. In Step 2, we divide into two cases. If there is no big job available, schedule the job with the largest delivery time J qmax(t) ; otherwise, go to Step 3. In Step 3, we have a precondition that there is a big job J pmax(t) . If this big job is the only available job, the algorithm wait until a new decision point or time r pmax(t) + (ϕ -1)p pmax(t) . Because the algorithm cannot wait infinite time. Note that the expression r pmax(t) +(ϕ -1)p pmax(t) contains a parameter ϕ which is the lower bound we have proved. This time is chosen in order that when this job is the only one in job instance, the competitive ratio of the algorithm is

If J pmax(t
ρ ≤ r pmax(t) + (ϕ -1)p pmax(t) + p pmax(t) + q pmax(t) r pmax(t) + p pmax(t) + q pmax(t) ≤ max r pmax(t) r pmax(t) , ϕp pmax(t) p pmax(t) , q pmax(t) q pmax(t) = ϕ.
Otherwise, i.e., the big job J pmax(t) is not the only available job. We divided into cases in order that the competitive ratio of the algorithm is not greater than ϕ. In Step 3.2, J pmax(t) is chosen in order that when no job arrives in future, the competitive ratio of the algorithm is

ρ ≤ t + p pmax(t) + p(U (t)\p pmax(t) ) + q qmax(t) t + p pmax(t) + p(U (t)\p pmax(t) ) ≤ p pmax(t) + q qmax(t) p pmax(t) ≤ ϕ.
This is an example. The purpose of Step 3 is to guarantee the competitive ratio of the algorithm not more than ϕ. Readers can find more details in Theorem 2.

In order to prove that algorithm EX-D-LDT has a competitive ratio of ϕ by contradiction in the next section, we assume that there exists a smallest counterexample consisting of a minimum number of jobs. For this smallest counterexample (like for all other counterexample), the competitive ratio of EX-D-LDT algorithm is greater than ϕ.

In the following, we will show several properties of this smallest counterexample, denoted by I. Let σ and π be the schedules produced by EX-D-LDT and offline optimal schedule, respectively. Let S j (σ) denote the start time of job J j in σ. Let J l denote the first job in σ that assumes (or determines) the value L max (σ), i.e., L l (σ) = L max (σ). Similar to the lemmas proved in [START_REF] Hoogeveen | A best possible deterministic online algorithm for minimizing maximum delivery time on a single machine[END_REF] and [START_REF] Tian | A best on-line algorithm for single machine scheduling with small delivery times[END_REF], we obtain several structural properties that schedule σ satisfies.

Lemma 2

The schedule σ consists of a single block: it starts at a nonnegative time and after that all jobs are processed contiguously.

Proof. By contradiction. Suppose that σ consists of more than one block (see Fig. 3.1). Let B be the block that contains job J l , L l (σ) = L max (σ).

(3.2)

(1) The first step is to reduce the jobs' number of the smallest counterexample by its definition. Consider any block that precedes B. Since the algorithm bases its choices on the set (J(t)\J(t 1 )) U (t 1 ) (considering the definition of the big job), the existence of the jobs that are completed before the start of block B does not influence the start time of B and the order in which the jobs are executed. Therefore, we delete all jobs completed before the start of block B without changing the value L max (σ) and increasing L max (π). Similarly, we can remove all jobs from I that are released after the start time S l (σ) of J l in σ.

(2) The second step is to form a new counterexample.

From the minimization of I, we assume that our counterexample consists of the jobs which arrives before time S l (σ) from block B, which form a new block B , and the jobs that are available at the start time S l (σ) of J l in σ but that are scheduled in another block. We keep these jobs in the counterexample since they result in the start time S l (σ) of job J l by the algorithm. Note that there indeed exists the jobs which are available at the start time S l (σ) of J l in σ but are scheduled in another block. B must be a continuous block, since the algorithm always starts a job if more than one job is available and the machine is idle (by Step 1 of the algorithm). For the same reason, there is at most one job that is available at time S l (σ) and does not belong to B and this job must exist, otherwise the lemma holds. Moreover, this job, denoted by J i , must be marked as big (by Step 2 of the algorithm). Otherwise, J i must be scheduled following the last job in B . Therefore, we have the new counterexample formed by B and J i (See Fig. 3.2).

(3) The third step is to prove that there is a contradiction if J i exists.

Let S(B ) and C(B ) denote the start time of the first job and the completion time of the last job in B . We know that C(B ) ≥ S l (σ) + p l .

Since J i is big and the only job at time C(B ), by Step 3 of the algorithm, we know that S i (σ) > C(B ) ≥ S l (σ) + p l . Then, L i (σ) = S i (σ) + p i + q i > S l (σ) + p l + p i + q i > S l (σ) + p l + p i . From equality (3.2), we have L max (σ) = S l (σ) + p l + q l . Therefore, L max (σ) -L i (σ) < q lp i . Since J i is a big job, p i > 1 ϕ p(I) > 1 ϕ (p i +p l ). Then, we have p l < (ϕ-1)p i . Since βq l ≤ p l , it follows that L max (σ)

-L i (σ) < q l -p i ≤ 1 β p l -p i < 1 β (ϕ -1)p i -p i = ( ϕ-1 β -1)p i .
Since β ≥ 1 2 , considering inequality (3.1), we have that

ϕ -1 β -1 ≤ 1 2β -1 ≤ 0.
Therefore, L max (σ) -L i (σ) < 0. This contradicts the assumption that J l is the first job in σ assuming the value L max (σ). Therefore, The schedule σ consists of a single block B (see Fig. 3.3) and the lemma follows.

From now on, let J 0 be the job that arrives first in I. Without loss of generality, we assume that r 0 = 0.

Lemma 3

In the optimal schedule π, (a) if J 0 is the first scheduled job, we have

L max (σ) -L max (π) ≤ (ϕ - 1)p 0 + q l ; (b) if J 0 is not the first scheduled job, we have L max (σ) -L max (π) ≤ q l .
Proof. By lemma 2, σ consists of a single block B . Since J l is the first job in σ that assumes the value L max (σ), then L max (σ) = C l (σ) + q l ≤ C(B ) + q l = S(B ) + p(I) + q l . By the algorithm, we have

S(B ) = min{(ϕ -1)p 0 , r 1 }, ( 3.3)
where r 1 is the arrival time of the second available job. This equality will be used in the following lemmas. If J 0 is the first scheduled job in π, we have L max (π) ≥ p(I). Hence, it follows that L max (σ) -L max (π) ≤ S(B ) + q l ≤ (ϕ -1)p 0 + q l . Therefore, (a) follows. If J 0 is not the first scheduled job in π, we have L max (π) ≥ r 1 + p(I) ≥ S(B ) + p(I). Hence, it follows that L max (σ) -L max (π) ≤ q l . Thus, (b) holds.

As in [START_REF] Hoogeveen | A best possible deterministic online algorithm for minimizing maximum delivery time on a single machine[END_REF] and [START_REF] Tian | A best on-line algorithm for single machine scheduling with small delivery times[END_REF], let J k be the last job scheduled in σ before J l with a delivery time smaller than q l , if any. If J k exists, let G(l) denote the set of all jobs between J k and J l in σ, including J l . Note that each job in G(l) has a delivery time greater than or equal to q l . We name J k as the interference job for schedule.

The purpose of the following lemma is to prove there there exists an interference job in σ. This job will be used in the proof of Theorem 2.

Lemma 4 Schedule σ contains an interference job J k scheduled before J l such that q k ≤ q l . Proof. By contradiction. We assume that this interference job J k does not exist in σ. We also use G(l) denote all jobs scheduling J l , including J l . Note that each job in G(l) has a delivery time greater than or equal to q l since J k does not exist. We know that in the smallest counterexample I, the competitive ratio of the algorithm is greater than ϕ.

Since each job in G(l) has a delivery time greater than or equal to q l , we have

L max (π) ≥ p(G(l)) + q l .
That is to say, in set G(l), job J l must be the last job in σ according to their positions (or completion times); otherwise, the objective value must increase. By the algorithm, the first job in the block starts at time (ϕ -1)p 0 at the latest, considering equality (3.3). Therefore, it follows that

L max (σ) = C l (σ) + q l ≤ (ϕ -1)p 0 + p(G(l)) + q l .
Therefore, L max (σ)-L max (π) ≤ (ϕ-1)p 0 ≤ (ϕ-1)L max (π). That is to say, the competitive ratio of the algorithm is not greater than ϕ. Thus, this contradicts to the fact that we consider a counterexample where the competitive ratio of the algorithm is greater than ϕ. Therefore, the lemma follows.

Lemma 5 p k > (ϕ -1)p(I).

Proof. By contradiction. We assume that p k ≤ (ϕ -1)p(I). There are two possibilities for the algorithm to select J k and not one of the jobs from G(l).

(1) All jobs in G(l) have a release date larger than S k (σ).

(2) There is one job from G(l) available, which we denote by J 1 , that is marked as big and cannot be started yet. Note that since J 1 cannot be started yet, corresponding to Step 3.4 of the algorithm, we must have that S k (σ)+p k ≤ r 1 + (ϕ -1)p 1 .

For case (1), we have that

L max (π) ≥ min Jj ∈G(l) r j + p(G(l)) + q l > S k (σ) + p(G(l)) + q l . Since L max (σ) = C l (σ) + q l = S k (σ) + p k + p(G(l)) + q l , it follows that L max (σ) -L max (π) < p k ≤ (ϕ -1)p(I) ≤ (ϕ -1)L max (π).
This contradicts to the fact that we consider a counterexample. Considering case (2), we have that

L max (π) ≥ min Jj ∈G(l) r j + p(G(l)) + q l > r 1 + p(G(l)) + q l .
Since L max (σ) = C l (σ) + q l = S k (σ) + p k + p(G(l)) + q l , it follows that

L max (σ) -L max (π) < S k (σ) + p k -r 1 ≤ r 1 + (ϕ -1)p 1 -r 1 = (ϕ -1)p 1 ≤ (ϕ -1)L max (π).
This also contradicts to the fact that we consider a counterexample. Therefore, the lemma follows.

Lemma 6 For all J j ∈ I\{J 0 }, we have p j ≤ 1 ϕ p(I).

Proof. By contradiction. We assume that there exists at least one job J i with r i ≥ r 0 , which satisfies that p i > 1 ϕ p(I). Then we know that p i is the only big job at any time after its arrival (by the definition of big job). We divide set J(t) into two independent parts: J(t)\U (t) and U (t).

Suppose that at time t such that t ∈ [S(B ), S(B ) + p(J(I))], since p i > 1 ϕ p(I) ≥ 1 ϕ p(J(t)), we have ϕp i > p(J(t)\U (t)) + p(U (t)). Note that J(t)\U (t) denotes the set of jobs which have been scheduled at time t. By the algorithm, we have S(B ) ≤ r i , considering equality (3.3). We know that the schedule σ consists of a single block. By the construction of this block, we know that t = S(B ) + p(J(t)\U (t)). Therefore, t+p(U (t)) = S(B )+p(J(t)\U (t))+p(U (t)) ≤ r i +p(J(t)) ≤ r i +p(I) < r i +ϕp i .

Note that among Step 3.1, 3.2, 3.3 and 3.4, the big job can be scheduled only in Step 3.2. Since t + p(U (t)) < r i + ϕp i always holds, Step 3.2 can not execute.

Thus, the big job can be scheduled only in the case where time t ≥ r i +(ϕ -1)p i (by Step 3). That is to say, J i cannot be scheduled before time r i + (ϕ -1)p i .

Thus, C i (σ) ≥ r i + (ϕ -1)p i + p i = r i + ϕp i . Since C i (σ) ≤ S(B ) + p(I) < S(B ) + ϕp i , we have r i + ϕp i < S(B ) + ϕp i . Therefore, r i < S(B ). This is a contradiction to S(B ) ≤ r i . So the lemma follows.

Lemma 7

In the case where each job in G(l) arrives after time S k (σ) and J k is a big job at time S k (σ), we have S k (σ) ≥ r k + (ϕ -1)p k .

Proof. By contradiction. Assume that job J k 's start time S k (σ) < r k + (ϕ -1)p k . We discuss the following two cases.

Case 1: J k is the only available job at time S k (σ).

From Step 3 of the algorithm, we know that J k cannot be scheduled before a new job arrives or r k + (ϕ -1)p k . Since S k (σ) < r k + (ϕ -1)p k , J k cannot be scheduled at time S k (σ). There is a contradiction.

Case 2: J k is not the only available job at time S k (σ). It follows that set U (S k (σ))\{J k } = ∅ and the jobs in this set are scheduled after job J l . We can delete these jobs in I without decreasing L max (σ) and increasing L max (π). Because J l should be scheduled at last in G(l); otherwise, L max (σ) increases. This contradicts to the minimization of the smallest counterexample I.

Therefore, the lemma follows.

The proof of optimality of EX-D-LDT

By the lemmas proved in the above section, we can show the following theorem.

The idea of proof of the following theorem originated from [START_REF] Tian | A best on-line algorithm for single machine scheduling with small delivery times[END_REF]. The idea is that we discuss three different possibilities which result in that algorithm EX-D-LDT select interface job J k instead of one of the jobs from G(l) at time S k (σ).

The method is to prove that there are contradictions.

Theorem 2 The online algorithm EX-D-LDT has an optimal competitive ratio of

ϕ = 1 2 ( 5 + β 2 + 2β + 1 -β), when β ≥ 1 2 .
Proof. We assume that there exists a smallest counterexample I such that L max (σ) > ϕL max (π), where σ and π denote the schedule obtained by algorithm EX-D-LDT for instance I and the offline optimal schedule, respectively. Due to Lemma 2 and Lemma 4, we know that σ consists of a single block and contains an interference job J k . In order to show that such a counterexample does not exist, we need to prove that

L max (σ) ≤ ϕL max (π) or L max (σ) -L max (π) ≤ (ϕ -1)L max (π).
Considering the interference job J k , we have

L max (σ) = S k (σ) + p k + p(G(l)) + q l . (3.4)
There are three possible reasons that algorithm EX-D-LDT selected J k instead of one of the jobs from G(l) at time S k (σ).

(1) No jobs in G(l) is available at time S k (σ).

(2) There is a big job J i ∈ G(l) available at time S k (σ), and algorithm EX-D-LDT is not allowed to schedule it at time S k (σ). This corresponds to Step 3.4.

(J k is not a big job.) (3) J k is a big job at time S k (σ), and all jobs from G(l) that are available at time S k (σ) have a delivery time of at most (ϕ -1)p k . This corresponds to Step 3.2.

In the following, we discuss these three cases, respectively. Case 1: No jobs in G(l) is available at time S k (σ). Since all jobs in G(l) arrive after time S k (σ), we have

L max (π) > S k (σ) + p(G(l)) + q l . (3.5)
From equality (3.4), we have L max (σ) -L max (π) < p k . From Lemma 5, we have p k > (ϕ -1)p(I).

(3.6)

In the following, considering whether J k is or not a big job at time S k (σ), we consider two subcases. Case 1.1: J k is not a big job at time S k (σ).

We have

p k ≤ 1 ϕ p(J(S k (σ))). It follows that p(J(S k (σ))) ≥ ϕp k . (3.7)
It can be observed that

L max (π) ≥ p(I) ≥ p(J(S k (σ))) + p(G(l)) (3.8)
Therefore, from inequalities (3.6), (3.7) and (3.8), we must have that

p k > (ϕ -1)[p(J(S k (σ))) + p(G(l)] ≥ (ϕ -1)[ϕp k + p(G(l)]. (3.9)
Therefore, it follows that

p(G(l)) < 1 + ϕ -ϕ 2 ϕ -1 p k . (3.10)
Note that βq l ≤ p l and p l ≤ p(G(l)). From inequality (3.10) and Lemma 1, we have

q l ≤ 1 β p l ≤ 1 β p(G(l)) < 1 + ϕ -ϕ 2 β(ϕ -1) p k = p k . ( 3.11)
We distinguish two possibilities according to where J 0 is scheduled in π. Case 1.1.1: J 0 is not the first scheduled job in π. By lemma 3, we have L max (σ)-L max (π) ≤ q l . From inequalities (3.7), (3.8) and (3.11) and Lemma 1, it follows that

L max (σ) -L max (π) L max (π) ≤ q l p(J((S k (σ))) + p(G(l)) ≤ q l ϕp k + βq l < 1 ϕ + β = ϕ -1.
Case 1.1.2: J 0 is the first scheduled job in π.

We use B k (σ) to denote the set of jobs which arrive at or before time S k (σ) and are scheduled before job J k in σ. Let A l (σ) denote the set of jobs which arrive at or before time S k (σ) and are scheduled after job J l in σ. Then we can divide J(S k (σ)) into 3 parts, B k (σ), p k , A l (σ). Therefore, we know

S k (σ) = S(B ) + p(B k (σ)).
(3.12)

and J(S k (σ)) = B k (σ) J k A l (σ), which deduces that

p(J k (σ)) = p(B k (σ)) + p k + p(A l (σ)). (3.13)
Note that B k (σ) and A l (σ) may be empty. Then p(B k (σ)) ≥ 0 and P (A l (σ)) ≥ 0. We will consider two subcases divided by whether J k is scheduled after all jobs in G(l) in π or not. Case 1.1.2.1: J k is not scheduled after all jobs in G(l) in π.

Considering that S(B ) = {(ϕ -1)p 0 , r 1 }, where r 1 is the arrival time of the second available job, we have

S(B ) ≤ (ϕ -1)p 0 . (3.14)
Since it is possible that J k ≡ J 0 , we further discuss the following two subcases.

Subcase 1:

J k = J 0 . It follows that B k (σ) must contain J 0 . Therefore, p(B k (σ)) ≥ p 0 . Then we have L max (π) ≥ p 0 + p k + p(G(l)) + q l ≥ p 0 + p k + p l + q l . (3.15)
Considering equality (3.4) and inequality (3.8), we have

L max (σ) -L max (π) ≤ S k (σ) + p k + q l -p(J k (σ)).
From equalities (3.12) and (3.13), it follows that

L max (σ) -L max (π) ≤ S(B ) + q l -p(A l (σ)) ≤ S(B ) + q l . ( 3.16)
Therefore, from inequalities (3.16) and (3.14), we have

L max (σ) -L max (π) ≤ (ϕ -1)p 0 + q l .
(3.17)

Considering inequalities (3.15), we have

L max (σ) -L max (π) L max (π) ≤ (ϕ -1)p 0 + q l p 0 + p k + p l + q l ≤ max ϕ -1, q l p k + p l + q l .
From inequalities (3.1) and (3.11) and Lemma 1, it follows that

q l p k + p l + q l < 1 2 + β < 1 ϕ + β = ϕ -1.
Therefore, we have

L max (σ) -L max (π) L max (π) ≤ ϕ -1.
Subcase 2: J k = J 0 . In this case J k is the first job in σ, we have B k (σ) = ∅ and S k (σ) = S(B ). Considering inequality (3.14), it follows that S k (σ) ≤ (ϕ -1)p 0 . From equality (3.4) and L max (π) ≥ p k + p(G(l)) + q l , we have

L max (σ) -L max (π) ≤ S k (σ) ≤ (ϕ -1)p 0 < (ϕ -1)L max (π).
Case 1.1.2.2: J k is scheduled after all jobs in G(l) in π.

We have

L max (π) > S k (σ) + p(G(l)) + p k + q k . (3.18)
Since J k is not a big job, we have

p(J(S k (σ))) ≥ ϕp k . (3.19)
Considering equality (3.4) and inequality (3.18), we have

L max (σ) -L max (π) < q l -q k ≤ q l . ( 3
L max (σ) -L max (π) L max (π) < q l p(J(S k (σ))) + p(G(l)) < q l ϕp k + βq l < 1 ϕ + β = ϕ -1.
Case 1.2: J k is a big job at time S k (σ). From Lemma 7, we have

S k (σ) ≥ r k + (ϕ -1)p k ≥ (ϕ -1)p k . (3.21)
We consider the following two subcases divided by whether J k is scheduled after all jobs in G(l) in π or not.

Case 1.2.1: J k is scheduled after all jobs in G(l) in π.

If q l ≥ p k , from inequality (3.5), we have

L max (π) > S k (σ) + p(G(l)) + q l ≥ S k (σ) + p l + q l = S k (σ) + (β + 1)q l ≥ S k (σ) + (β + 1)p k . ( 3
L max (σ) -L max (π) L max (π) < p k S k (σ) + (β + 1)p k ≤ p k (ϕ + β)p k = ϕ -1.
Otherwise, i.e., q l < p k . Then we have

L max (π) > S k (σ) + p(G(l)) + p k + q k . ( 3
L max (σ) -L max (π) L max (π) < q l -q k S k (σ) + p(G(l)) + p k + q k ≤ q l S k (σ) + p l + p k < q l ϕp k + p l < 1 ϕ + β = ϕ -1.
Case 1.2.2: J k is not scheduled after all jobs in G(l) in π.

Recall the definition of B k (σ), we have

B k (σ) {J k } = U (J(S k (σ))). We know that L max (π) ≥ p k + p(G(l)) + q l . (3.24) If B k (σ) = ∅, we know S k (σ) = r k + (ϕ -1)p k . (3.25)
Considering that J k is not scheduled after all jobs in G(l) in π, we know that J l must be scheduled at last in the set G(l) J k in π.

If J k is scheduled before all jobs in G(l) in π, we have L max (π) ≥ r k + p k + p(G(l)) + q l . Otherwise, i.e., if J k is not scheduled before all jobs in G(l) in π, there must be L max (π) > r k + p k + p(G(l)) + q l .

Considering above two situations, we have

L max (π) > r k + p k + p(G(l)) + q l . ( 3
L max (σ) -L max (π) ≤ S k (σ) -r k = (ϕ -1)p k < (ϕ -1)L max (π).
Then, we suppose that B k (σ) = ∅. So we have that J k = J 0 . Let J i be the job completed at time S k (σ) in σ. So we have

S k (σ) = S i (σ) + p i . (3.27)
It follows that

L max (σ) = S i (σ) + p i + p k + p(G(l)) + q l . (3.28)
Since J k is big, from equality (3.13), we have

ϕp k > p(B k (σ)) + p k + p(A l (σ)). It follows that p(B k (σ)) < (ϕ -1)p k -p(A l (σ)) ≤ (ϕ -1)p k . ( 3.29)
We consider two possibilities distinguished by whether r k ≤ S i (σ) or not.

L max (σ) -L max (π) L max (π) ≤ S k (σ) -r k r k + p k + p(G(l)) + q l < (ϕ -1)p k p k = ϕ -1.
Then we consider the case where S k (σ) > r k + (ϕ -1)p k . By the algorithm, Step 3.1 must occur at time S i (σ). Therefore, we have

q i > (ϕ -1)p k . (3.30)
Then we consider the following two subcases divided by whether J i is scheduled after all jobs in G(l) in π or not.

Subcase 1: J i is scheduled after all jobs in G(l) in π.

Since B k (σ) = ∅, we know that J 0 = J k . It follows that r k ≥ S(B ) (3.31)
and that S k (σ) = S(B ) + p(B k (σ)). (3.32) In this subcase, J i is scheduled after all jobs in the set G(l) J k in π. Considering that J k is not scheduled after all jobs in G(l) in π, we know that J l must be scheduled at last in the set G(l) J k in π. If p i + q i ≥ q l , we have

L max (π) ≥ r k + p k + p(G(l)) + p i + q i .
Otherwise, if p i + q i < q l , we have L max (π) ≥ r k + p k + p(G(l)) + q l . Therefore, we have

L max (π) ≥ r k + p k + p(G(l)) + max{p i + q i , q l }. (3.33)
From equalities (3.4) and (3.32), we know

L max (σ) = S(B ) + p(B k (σ)) + p k + p(G(l)) + q l . ( 3
L max (σ) -L max (π) ≤ p(B k (σ)) + q l -p i -q i + (S(B ) -r k ) ≤ p(B k (σ)) + q l -p i -q i . ( 3
L max (σ) -L max (π) < (ϕ -1)p k + q l -β(ϕ -1)p k -(ϕ -1)p k = q l -β(ϕ -1)p k < q l .
From inequality (3.24), we know

L max (π) ≥ p k + p(G(l)) + q l ≥ p k + p l + q l ≥ p k + (β + 1)q l .
Since I is a counterexample, we must have

q l > (ϕ -1)L max (π) ≥ (ϕ -1)p k + (ϕ -1)(β + 1)q l . (3.37)
Therefore, Considering Lemma 1, we have

p k < 1 ϕ -1 -β -1 q l = (ϕ + β -β -1)q l = (ϕ -1)q l . (3.38)
From equality (3.4) and inequalities (3.5) and (3.38), we have

L max (σ) -L max (π) < p k < (ϕ -1)q l < (ϕ -1)L max (π).
Subcase 2: J i is not scheduled after all job in G(l) in π.

We have

L max (π) ≥ p k + p i + p(G(l)) + q l . (3.39) Since B k (σ) = ∅, we know that J 0 = J k . It follows that L max (σ) = S(B ) + p(B k (σ)) + p k + p(G(l)) + q l (3.
L max (σ)-L max (π) < (ϕ-1)p 0 +(ϕ-1)p k < (ϕ-1)(p 0 +p k ) < (ϕ-1)L max (π). Case 1.2.2.2: r k > S i (σ). We know that L max (π) ≥ r k + p k + p(G(l)) + q l . (3.44)
From equality (3.28) and inequality (3.44), we have

L max (σ) -L max (π) ≤ S i (σ) + p i -r k < p i ≤ p(B k (σ)). (3.45)
From inequalities (3.29) and (3.45), it follows that

L max (σ) -L max (π) < p(B k (σ)) < (ϕ -1)p k < (ϕ -1)L max (π).
Case 2: There is a big job J i ∈ G(l) available at time S k (σ) and algorithm EX-D-LDT is not allowed to schedule it at time S k (σ). This corresponds to Step 3.4. (J k is not a big job.)

We claim that J i must be the only job from G(l) available at time S k (σ). Suppose to the contrary that there is another job J j from G(l) except J i available at time S k (σ). According to the definition of G(l), we have q k < min{q i , q j }. By Step 3.3 and 3.4 of the algorithm, J k must not be selected to schedule at time S k (σ). There is a contradiction.

Therefore, we have that

L max (π) ≥ r i + p(G(l)) + q l . (3.46)
By the above claim, we know that J i is both the job with largest delivery time and the job with largest processing time at time S k (σ). So, we know the index p max (S k (σ)) = q max (S k (σ)). Therefore, Step 3.4 of the algorithm must occur at time S k (σ). This implies that S k (σ) + p k + p i ≤ r i + ϕp i . Therefore, we have

S k (σ) + p k ≤ r i + (ϕ -1)p i . ( 3.47)
From equality (3.4) and inequalities (3.46) and (3.47) we have

L max (σ) -L max (π) ≤ S k (σ) + p k -r i ≤ r i + (ϕ -1)p i -r i = (ϕ -1)p i ≤ (ϕ -1)L max (π).
Case 3: J k is a big job at time S k (σ), and all of the jobs from G(l) that are available at time S k (σ) have a delivery time of at most (ϕ -1)p k . This corresponds to Step 3.2. Since J l is the job with minimum delivery time in G(l), we have

q l ≤ (ϕ -1)p k . (3.48)
Consider the following two cases. Case 3.1: J 0 is not the first job in π.

From Lemma 3 and inequality (3.48), we have that

L max (σ) -L max (π) ≤ q l ≤ (ϕ -1)p k < (ϕ -1)L max (π).
Case 3.2: J 0 is the first job in π.

From Lemma 3 and inequality (3.48), we have

L max (σ) -L max (π) ≤ (ϕ -1)p 0 + q l ≤ (ϕ -1)(p 0 + p k ). (3.49) If J 0 = J k , we have L max (π) > p 0 + p k .
Therefore, from inequality (3.49), it follows that

L max (σ) -L max (π) ≤ (ϕ -1)(p 0 + p k ) < (ϕ -1)L max (π).
If J 0 = J k , then J k is the first job in π. therefore, we have

L max (π) ≥ p k + p(G(l)) + q l . (3.50)
Therefore, from equality (3.4), we have and Q G(l) = ∅. Since J k is a big job and the jobs in Q are scheduled before J k in σ, from Step 3.1, we have that each job in Q has a delivery time more than (ϕ -1)p k . From inequality (3.48), q l ≤ (ϕ -1)p k , we know that each job in Q G(l) has a delivery time at least q l . Therefore, we have

L max (σ) -L max (π) ≤ S k (σ). ( 3
L max (π) ≥ p k +p(Q)+p(G(l))+ min Jj ∈Q G(l) q j = p k +p(Q)+p(G(l))+q l . (3.53)
We also know that

L max (σ) = T + p(Q) + p k + p(G(l)) + q l . (3.54)
From equalities (3.52), (3.53) and (3.54), it follows that

L max (σ) -L max (π) ≤ T ≤ (ϕ -1)p k < (ϕ -1)L max (π).
The theorem follows.

Chapter 4

Two identical parallel machine model

We study the problem of semi-online scheduling on 2 machines under a grade of service (GoS). GoS means that some jobs have to be processed by some machines to be guaranteed a high quality. The problem is online in the sense that jobs are presented one by one, and each job shall be assigned to a time slot on its arrival. Assume that the processing time p i of every job J i is bounded by an interval [a, αa], where a > 0 and α > 1 are two constant numbers. By knowing the bound of jobs' processing times, we denote it by semi-online problem. We deal with two semi-online problems. The first one concerns about bounded processing time constraint. First, we show that a lower bound of competitive ratio is: (1) 1+α 2 in the case where 1 < α < 2; (2) 3 2 in the case where 2 ≤ α < 5; and (3) 4+α 6 in the case where 5 ≤ α < 6. We further propose an algorithm, called B-ONLINE, and prove that in the case where 25 14 ≤ α and the optimal makespan C OP T ≥ 20a, B-ONLINE algorithm is optimal.

For the second problem, we further know the sum of jobs' processing times Σ in advance. We first show a lower bound 1+α 2 in the case where 1 < α < 2, then we propose an algorithm B-SUM-ONLINE which is optimal in the case where Σ ≥ 2α α-1 a and 1 < α < 2.

Introduction

Grade of service (GoS) is a qualitative concept, and it's often translated into the level of access privilege of different service provision. For example, suppose we have 2 machines (or processors). One of them can provide high quality service (or high GoS) while the other one provides normal service (or low GoS). Some jobs which request high quality must be processed by high GoS machine, while other jobs with low quality requests can be processed by both machines whenever they are available. For more recent development on GoS, see [START_REF] Hwang | Parallel machines scheduling under a grade of service provision[END_REF].

The problem is online in the sense that when receiving a job and before the next job is presented, we must irrevocably assign the job to a time slot of the schedule. The assignment of each job shall be made on its arrival and the next job arrives immediately after the assignment, i.e., the difference of arrival times of two continual jobs is ignorable. Preemption and re-assignment are not allowed. The objective is to minimize the makespan, that is the completion time of the last job in the schedule. When all information is available at one time before scheduling, the problem is called offline. We call a problem semi-online if we know some information of jobs in advance, i.e., jobs' total processing time.

Hwang et al. [START_REF] Hwang | Parallel machines scheduling under a grade of service provision[END_REF] first study the (offline) problem of parallel machine scheduling with GoS eligibility. They proposed an approximation algorithm LG-LPT, and proved that its makespan is not greater than 5 4 times the optimal makespan for m = 2 and not greater than 2 -1 m-1 times the optimal makespan for m ≥ 3. However, online scheduling under GoS eligibility was first studied by Park et al. [START_REF] Park | Online and semi-online scheduling of two machines under a grade of service provision[END_REF] and Jiang et al. [?]. For the problem of online scheduling on 2 machines with GoS constraint, they respectively proposed an optimal algorithm with a competitive ratio of 5 3 . Jiang [START_REF] Jiang | Online scheduling on parallel machines with two gos levels[END_REF] further investigated the problem of online scheduling on parallel machines with two GoS levels. He assumed that the number of machines providing high GoS is not known before scheduling and decisions must be made without knowledge of the exact number of machines providing high GoS. I.e., we only know that in 10 parallel machines there are k (1 ≤ k ≤ 9) machines which can provide high GoS. Under this consideration, he proved that 2 is a lower bound of online algorithms and proposed an online algorithm with a competitive ratio of 12+4 √ 2 7

. He et al. [START_REF] He | Semi on-line scheduling on two identical machines[END_REF] investigated two different semi on-line scheduling problems on a two-machine system. In the first problem, they assumed that all jobs have their processing times in between p and rp (p > 0, r ≥ 1). They showed that LS is optimal with a competitive ratio (r + 1)/2 in the case where 1 ≤ r < 2 and 3/2 in the case where r ≥ 2. In the second problem, they supposed that the largest processing time is known in advance. They showed that PLS algorithm is optimal with a competitive ratio 4/3.

In this chapter we will consider semi-online scheduling on two machines under a grade of service provision with jobs' processing times bounded by an interval [a, αa], where a > 0 and α > 1 are two constant numbers. For simplicity, we use online algorithm to denote semi-algorithm in the remainder.

The rest of this chapter is organized as follows. In Section 2.1, we will describe the problem and introduce some basic notations. Section 2.2 will show some lower bounds of competitive ratio considering different values of α. In section 2.3, we will propose an algorithm B-ONLINE, and prove that in the case where 25 14 ≤ α and the optimal makespan C OP T ≥ 20a, B-ONLINE is optimal. In section 3.1, we will give some problem definitions and notations. Section 3.2 will present a lower bound of competitive ratio. In section 3.3, we will show an algorithm B-SUM-ONLINE and prove that it is optimal in the case Σ ≥ 2α α-1 a and 1 < α < 2.

Online scheduling on 2 machines with GoS and bounded processing times

In this section, we study the problem of online scheduling on 2 machines under a grade of service provision with bounded processing times.

Problem definitions and notations

We are given 2 machines with speed of 1. Without loss of generality, we denote the one that can provide both high and low GoSs by M 1 , and the other one that only provides low GoS by M 2 . We denote each job by J i = (p i , g i ), where p i is the processing time of J i and g i ∈ {1, 2} is the GoS of the job. g i = 1 if J i must be processed by M 1 and g i = 2 if it can be processed by either of the two machines. p i and g i are not known unless J i arrives. A sequence of jobs σ = {J 1 , J 2 , ..., J n } which arrive online have to be scheduled irrevocably on one of the two machines on their arrivals. Each job J i is presented immediately after J i-1 is scheduled. The schedule can be seen as a partition of job sequence σ into two subsequences, denoted by S 1 and S 2 , where S 1 and S 2 consist of jobs assigned to M 1 and M 2 , respectively. Let L 1 = t(S 1 ) = Ji∈S1 p i and L 2 = t(S 2 ) = Ji∈S2 p i denote the loads (or total processing times) of M 1 and M 2 , respectively. Hence, the makespan of one schedule is max{L 1 , L 2 }. The online problem can be written as: Given σ, find S 1 and S 2 to minimize max{L 1 , L 2 }.

Let C ON and C OP T denote the makespan of online algorithm and offline optimal algorithm (for short, offline algorithm), respectively.

Lower bounds of competitive ratio

In this section, we will show some lower bounds of the competitive ratio of online algorithms for different values of α. If α = 1, online algorithms can reach the optimal makespan. An algorithm is optimal if it assigns the jobs as many as possible on M 2 when the difference of the loads of two machines is not greater than 1. Moreover, for the case where α ≥ 6, the lower bound of 5 3 has been proved in [START_REF] Park | Online and semi-online scheduling of two machines under a grade of service provision[END_REF]. So, we will focus on the case where 1 < α < 6.

Theorem 3 For the problem of online scheduling on two machines under GoS constraint with jobs' processing times bounded within interval [a, αa], there exists no algorithm with a competitive ratio less than: (1) 1+α

2 in the case where 1 < α < 2; (2) 3 2 in the case where 2 ≤ α < 5; and (3) 4+α 6 in the case where 5 ≤ α < 6.

Proof.

Without loss of generality, let a = 1. We will discuss the three cases of α in the following.

Case 1. 1 < α < 2. Let ϕ = 1+α 2 . We will generate a job sequence ρ consisting of at most 3 jobs, which arrive one by one. Once the ratio of makespans between online and offline algorithms is at least ϕ after some job is assigned, no more jobs will be presented and we stop. We begin with job J 1 = (1, 2). If online algorithm assigns J 1 to M 1 , we further generate job J 2 = (1, 1). Since offline algorithm will assign J 1 to M 2 , C ON COP T = 2 > ϕ and we stop. Otherwise if online algorithm assigns J 1 to M 2 , we generate job J 2 = (1, 2). If J 2 is assigned to M 2 , we have

C ON C OP T = 2 > ϕ. Otherwise if J 2 is assigned to M 1 , we generate job J 3 = (α, 1). We have C ON C OP T = 1+α 2 = ϕ in this case. Case 2. 2 ≤ α < 5.
Similar to the analysis in Case 1, we begin with jobs J 1 = J 2 = (1, 2). If online algorithm assigns both of them to one of the two machines, we have

C ON C OP T = 2 > 3 2
. Otherwise, we further generate job J 3 = (2, 1). Then we have C ON = 3 and C OP T = 2, since the optimal solution consists of scheduling J 1 , J 2 on M 2 and J 3 on M 1 . It follows that C ON C OP T = 3 2 . Case 3. 5 ≤ α < 6. Let ϕ = 4+α 6 . We will generate a job sequence which consists of at most 5 jobs in this case. Similarly, we begin with jobs J 1 = J 2 = (1, 2) and observe the behavior of online algorithm. If both of them are assigned to one of the two machines, C ON COP T = 2 > ϕ and we stop. Otherwise, we further generate job J 3 = (1, 2). If J 3 is assigned to M 1 , we give job J 4 = (3, 1) and then

C ON C OP T = 1+1+3 3 = 5 3 > ϕ. Otherwise if J 3 is assigned to M 2 , we further generate job J 4 = (3, 2). If J 4 is assigned to M 2 , it follows that C ON C OP T = 1+1+3 3 = 5 3 > ϕ.
Otherwise if J 4 is assigned to M 1 , we give the last job J 5 = (α, 1), and then

C ON COP T = 1+3+α 6 = 4+α 6 = ϕ.
Therefore, the theorem follows.

Remark 3

In the case where α ≥ 6, the tight lower bound of competitive ratio is 5 3 (see [START_REF] Park | Online and semi-online scheduling of two machines under a grade of service provision[END_REF]).

B-ONLINE algorithm

Combining the ONLINE algorithm proposed in [START_REF] Park | Online and semi-online scheduling of two machines under a grade of service provision[END_REF] with bounded jobs' processing time of job, we will give a modified algorithm called B-ONLINE. Before describing the algorithm, we give some notations on B-ONLINE 's schedules as follows.

At the arrival of each job, P and T are updated to become the maximum processing time and a half of total processing times of all arrived jobs, respectively. D is updated to be the total processing time of all arrived jobs with g i = 1. Let L = max{T, P, D}. Thus, we have C OP T ≥ L. For analysis convenience, we define P i , T i , D i , L i , S i 1 and S i 2 to be the P, T, D, L, S 1 and S 2 respectively immediately after job J i is assigned, and let P 0 = T 0 = D 0 = L 0 = 0 and S 0 1 = S 0 2 = ∅. According to Theorem 1 on lower bounds, we define various values of parameter ϕ as follows. (1) ϕ = 1+α 2 in the case where 25 14 ≤ α ≤ 2; (2) ϕ = 3 2 in the case where 2 ≤ α ≤ 5; (3) ϕ = 4+α 6 in the case where 5 ≤ α < 6; and (4) ϕ = 5 3 in the case where α ≥ 6.

B-ONLINE behaves as follows:

Step 1: Let S 1 = ∅, S 2 = ∅, P = 0, T = 0, D = 0;

Step 2: Receive job J i = (p i , g i ). P = max{P, p i } and T = T + pi 2 ; Step 3:

If g i = 1, let S 1 = S 1 {J i } and D = D + p i . Go to Step 5; Step 4: Let L = max{T, D, P }, if t(S 2 ) + p i ≤ ϕL, let S 2 = S 2 {J i }; else , let S 1 = S 1 {J i };
Step 5: If no more jobs arrive, stop and output S 1 and S 2 ; Else, let i = i + 1 and go to Step 2.

B-ONLINE has the same performance in competitiveness as ONLINE in the case where α ≥ 6, i.e., both of them have a competitive ratio of 5 3 in the case (please refer to [START_REF] Park | Online and semi-online scheduling of two machines under a grade of service provision[END_REF] for details). So, we will focus our attention on the case where 25 14 ≤ α < 6 later on.

Lemma 8 Given a constant number a, in the case where 25 14 ≤ α < 6, if job

J i = (p i , 2) is scheduled on M 1 by B-ONLINE algorithm, there must be t(S i 1 ) < 2-ϕ ϕ t(S i 2 ) + 2αa ϕ , where (1) ϕ = 1+α 2
in the case where 25 14 ≤ α ≤ 2;

(2) ϕ = 3 2 in the case where 2 ≤ α ≤ 5;

(3) ϕ = 4+α 6 in the case where 5 ≤ α < 6.

Proof.

If J i = (p i , 2) is scheduled on M 1 , there must be t(S i-1 2 ) + p i > ϕL i . Since t(S i 2 ) = t(S i-1 2 ) and p i ∈ [a, αa], we have t(S i 2 ) = t(S i-1 2 ) > ϕL i -αa. In another aspect, because L i ≥ T i = 1 2 [t(S i 1 ) + t(S i 2 )], we have t(S i 2 ) > ϕ 2 [t(S i 1 ) + t(S i 2 )] -αa. (4.1)
It follows that t(S i 1 ) < 2-ϕ ϕ t(S i 2 ) + 2αa ϕ . The lemma follows.

Theorem 4 Given a constant number a, in the case where 25 14 ≤ α < 6 and C OP T ≥ 20a , B-ONLINE is optimal with a competitive ratio ϕ such that (1) ϕ = 1+α 2 in the case where 25 14 ≤ α ≤ 2;

(2) ϕ = 3 2 in the case where 2 ≤ α ≤ 5;

(3) ϕ = 4+α
6 in the case where 5 ≤ α < 6.

Proof. We define C i ON and C i OP T to be C ON and C OP T respectively immediately after job J i is scheduled. Thus, C i OP T ≥ C i-1 OP T for i ≥ 1. We first assume that the theorem is false, implying that there must exist at least one instance, called counter example, which derives C ON C OP T > ϕ. Among all such counter examples, let ς be the one with the least number n of jobs, called minimal counter example. By the definition of minimal counter example, the makespan of ς is not determined until the arrival of job J n . Therefore,

C n ON = max{t(S n 1 ), t(S n 2 )} > ϕC n OP T ; (4.2) max{t(S n-1 1 ), t(S n-1 2 )} ≤ ϕC n-1 OP T . (4.3) Case 1. g n = 2. If J n = (p n , 2) is scheduled on M 2 , then t(S n-1 2 ) + p n ≤ ϕL n ≤ ϕC n OP T . This implies that ϕC n OP T < C n ON = t(S n 1 ) = t(S n-1 1 ) ≤ ϕC n-1 OP T . Since C n OP T ≥ C n-1
OP T , There is a contradiction. Therefore, J n must be assigned to M 1 and we have t(S n-1

2

) + p n > ϕL n . (4.4) Since T n = 1 2 [t(S n-1 1 ) + t(S n-1 2 ) + p n ] ≤ L n , together with inequality (4.4), we have t(S n-1 1 ) < (2 -ϕ)L n . Since L n ≤ C n OP T , we have t(S n-1 1 ) < (2 -ϕ)C n OP T . Considering p n ∈ [a, αa], it follows C n ON = t(S n 1 ) = t(S n-1 1 ) + p n < (2 - ϕ)C n OP T + αa. Since C n OP T ≥ 20a, we have C n ON C n OP T = (2 -ϕ) + αa C n OP T ≤ 2 -ϕ + α 20 .
To prove the theorem, we need to derive a contradiction to the assumption, i.e., to prove 25 14 ≤ α ≤ 2. In this subcase, ϕ = 1+α 2 , and then

C n ON C n OP T ≤ ϕ. That means 2 -ϕ + α 20 ≤ ϕ or 2 + α 20 -2ϕ ≤ 0. Case 1.1.
2 + α 20 -2ϕ = 2 + α 20 -1 -α = 1 - 19α 20 < 0.
It contradicts to the assumption.

Case 1.2. 2 ≤ α ≤ 5. In this subcase, ϕ = 3 2 and then

2 + α 20 -2ϕ = 2 + α 20 -3 = α 20 -1 < - 3 4 < 0.
Again, there is a contradiction to the assumption. Case 1.3. 5 ≤ α < 6. In this subcase, ϕ = 4+α 6 .

2 + α 20

-2ϕ = 2 + α 20 - 4 + α 3 = 40 -17α 60 ≤ - 3 4 < 0.
Again, there is a contradiction. Case 2. g n = 1. According to the definition of minimal counter example,

C n ON = t(S n 1 ) > ϕC n OP T (4.5)
Since C n OP T is at least the sum of processing times of jobs with g i = 1, inequality (4.5) means that S 1 must contain at least one job, named J k , with g k = 2. Let J K be the last job with g K = 2 assigned to M 1 . Let A K (S 1 ) be the set of jobs assigned to M 1 after J K has been assigned to M 1 . Thus, t(S n 1 ) = t(S k 1 ) + t(A K (S 1 )). Since C n OP T cannot be less than the sum of processing times of jobs with

g i = 1, we have t(A K (S 1 )) ≤ C n OP T . Therefore, t(S n 1 ) ≤ t(S k 1 ) + C n OP T . Together with Lemma 8, t(S n 1 ) ≤ 2 -ϕ ϕ t(S k 2 ) + 2αa ϕ + C n OP T (4.6)
Since the total processing time of jobs doesn't vary among different algorithms, we have t(S n 1 ) + t(S n 2 ) ≤ 2C n OP T . Considering inequality (4.5), we have

t(S n 2 ) < (2 -ϕ)C n OP T . Since t(S k 2 ) ≤ t(S n
2 ), together with inequality (4.6), we have

t(S n 1 ) < (2 -ϕ) 2 ϕ + 1 C n OP T + 2αa ϕ Therefore, C n ON C n OP T < (2 -ϕ) 2 ϕ + 1 + 2αa ϕC n OP T ≤ (2 -ϕ) 2 ϕ + 1 + α 10ϕ .
Similar to Case 1, we need to derive a contradiction to the assumption to prove the theorem, i.e., to prove

C n ON C n OP T ≤ ϕ. That means (2-ϕ) 2 ϕ + 1 + α 10ϕ ≤ ϕ or 4 + α 10 -3ϕ ≤ 0. Case 2.1. 25 14 ≤ α ≤ 2. In this subcase, ϕ = 1+α 2 . Therefore, 4 + α 10 -3ϕ = 4 + α 10 - 3(1 + α) 2 = 25 -14α 10 ≤ 0.
It contradicts to the assumption.

not greater than 1. Moreover, for the case where α ≥ 2, the lower bound of 3 2 has been proved in [START_REF] Park | Online and semi-online scheduling of two machines under a grade of service provision[END_REF]. So, we will focus on the case where 1 < α < 2.

Theorem 5 For the problem of online scheduling on two machines under GoS constraint with (1) knowledge of total processing time and (2) jobs' processing times bounded within interval [a, αa], there exists no online algorithm with a competitive ratio less than 1+α 2 in the case where 1 < α < 2.

Proof. Without loss of generality, let a = 1 and the sum of jobs' processing times be 2 + α. We will generate a job sequence which consists of at most 3 jobs, which arrive one by one. Once the ratio of makespans between online and offline algorithms is at least 1 + 1 α after some job is assigned, no more jobs will be presented and we stop. We begin with job J 1 = (1, 2). If online algorithm assigns J 1 to M 1 , we further generate job J 2 = (α, 1) and J 3 = (1, 2). Since offline algorithm will assign J 1 , J 3 to M 2 and

J 2 to M 1 , it follows C ON C OP T ≥ 1+α 2
and we stop. Otherwise if online algorithm assigns J 1 to M 2 , we generate job J 2 = (α, 2) and J 3 = (1, 1). If J 2 is assigned to M 2 , since offline algorithm will scheduling J 1 , J 3 on M 1 and J 2 on M 2 , we have CON C OP T ≥ 1+α 2 . Otherwise if J 2 is assigned to M 1 , we also generate job J 3 = (1, 1). We have C ON C OP T = 1+α 2 in this case, since offline algorithm will assign J 1 , J 3 on M 1 and J 2 on M 2 .

Remark 4

In the case where α ≥ 2, the tight lower bound of competitive ratio is 3 2 (see [START_REF] Park | Online and semi-online scheduling of two machines under a grade of service provision[END_REF]).

B-SUM-ONLINE algorithm

Combining the SEMI-ONLINE algorithm proposed in [START_REF] Park | Online and semi-online scheduling of two machines under a grade of service provision[END_REF] with bounded jobs' processing times, we will give a modified algorithm called B-SUM-ONLINE. Before describing the algorithm, we give some notations on B-SUM-ONLINE 's schedules as follows.

Let Σ be the sum of jobs' processing times. Let L = Σ 2 . Thus, we have C OP T ≥ L. B-SUM-ONLINE behaves as follows:

Step 1:

Let S 1 = ∅, S 2 = ∅; Step 2: Receive job J i = (p i , g i ); Step 3: If g i = 1, let S 1 = S 1 {J i }. Go to Step 5; Step 4: If t(S 2 ) + p i ≤ 1+α 2 L, let S 2 = S 2 {J i }; else , let S 1 = S 1 {J i };
Step 5: If no more jobs arrive, stop and output S 1 and S 2 ; Else, let i = i + 1 and go to Step 2.

B-SUM-ONLINE has the same performance in competitiveness as SEMI-ONLINE in the case where α ≥ 2, i.e., both of them have competitive ratio of 3 2 in the case (please refer to [START_REF] Park | Online and semi-online scheduling of two machines under a grade of service provision[END_REF] for details). So, we will focus our attention on the case where 1 < α < 2 later on.

The proof of the competitive ratio of B-SUM-ONLINE algorithm is by contradiction. We assume that there exists a job instance, called counter example, for which B-SUM-ONLINE algorithm yields a schedule with makespan greater than 1+α 2 times of the optimum. We further define the counter example with the least number of jobs as minimal counter example. For a minimal counter example I, let J 1 = {J i |g i = 1, J i ∈ I} and J 2 = {J i |g i = 2, J i ∈ I}. We use σ to denote the schedule generated by B-SUM-ONLINE algorithm for I. Let C S-ON and C OP T denote the makespan of B-SUM-ONLINE algorithm and the optimal algorithm for I, respectively. We define S j 1 and S j 2 to be S 1 and S 2 that we have immediately after we schedule job J j . S 0 1 = S 0 2 = ∅.

Lemma 9 t(J 2 ) > 1+α 2 L.
Proof. Suppose t(J 2 ) ≤ 1+α 2 L. For any job J j = (p j , 2), since t(S j-1

2

) + p j ≤ t(J 2 ) and t(J 2 ) ≤ 1+α

2 L, we have t(S j-1

2

) + p j ≤ 1+α 2 L. From Step 4 of the algorithm, we get

S 1 = J 1 and S 2 = J 2 . Since t(S 1 ) = t(J 1 ) ≤ C OP T , we know C S-ON = t(S 1 ). Therefore, C S-ON = t(S 2 ) = t(J 2 ) ≤ 1+α 2 L ≤ 1+α 2 C OP T .
There exists a contradiction.

Theorem 6 Given Σ ≥ 2α

α-1 a, B-SUM-ONLINE algorithm is optimal with a competitive ratio of 1+α 2 in the case 1 < α < 2.

Proof. Let ϕ = 1+α 2 . We assume that the theorem is false and there exists a minimal counter example I = {J 1 , ..., J n }. Therefore, we have

C n S-ON = max{t(S n 1 ), t(S n 2 )} > ϕC n OP T , (4.7) max{t(S n-1 1 ), t(S n-1 2 )} ≤ ϕC n-1 OP T . ( 4.8)
Our aim is to prove for this instance,

C n S-ON C n OP T ≤ ϕ holds. Case 1. g n = 2. If J n is assigned to M 2 , we have t(S n-1 2 ) + p n ≤ ϕL ≤ ϕC n OP T and t(S n-1 1 ) = t(S n 1 )
. By inequality (4.7), it follows that t(S n-1

1

) > ϕC n OP T ≥ ϕC n-1 OP T . This contradicts inequality (4.8).

So J n must be assigned to M 1 , which implies t(S n-1

2

) + p n > ϕL, C n S-ON = t(S n 1 ) > ϕC n OP T and t(S n 2 ) = t(S n-1 2 ). Since t(S n 1 )+t(S n 2 ) = 2L and C n OP T ≥ L, C n S-ON -C n OP T ≤ t(S n 1 ) -L = L -t(S n 2 ) = L -t(S n-1 2
). (4.9)

Since t(S n-1

2

) + p n > ϕL, together with the above inequality,

C n S-ON -C n OP T < L -(ϕL -p n ) = p n -(ϕ -1)L. (4.10) If p n > (α -1)L, considering p n ∈ [a, αa], it follows αa > (α -1)L. This implies L < α α-1 a. Since Σ = 2L, we have Σ < 2α α-1 a. This contradicts the assumption Σ ≥ 2α α-1 . So p n ≤ (α -1)L. (4.11)
Together with inequality (4.10), it follows that

C n S-ON -C n OP T < (α -1)L -(ϕ -1)L < α -1 2 L = (ϕ -1)L < (ϕ -1)C n OP T .
Therefore,

C n S-ON C n OP T
< ϕ, there exists a contradiction. Case 2. g n = 1. From the minimality, we have C n S-ON = t(S n 1 ). By Lemma 9, we know that there is at least one job in J 2 scheduled on M 1 . Otherwise, we have

C n S-ON C n OP T
< ϕ and there exists a contradiction. Let J k = (p k , 2) denote the last job with g i = 2 in I scheduled on M 1 , i.e., I = {J 1 , ..., J k-1 , J k , J k+1 ..., J n }. In this case, by Chapter 5

Two uniform parallel machine models

We consider two problems of online scheduling on two uniform machines: online scheduling under a grade of service (GoS) and online scheduling with reassignment. These problems are online in the sense that when a job presents, we have to irrevocably assign it to one of the machines before the next job is seen. The objective is to minimize the makespan.

In the first problem, GoS means that some jobs have to be processed by some machine so that they can be guaranteed a higher quality. Assume that the speed of the higher GoS machine is normalized to 1, while the speed of the other one is s. We show that a lower bound of competitive ratio is 1+ 2s s+2 in the case 0 < s ≤ 1 and 1 + s+1 s(2s+1) in the case s > 1. Then we propose and analyze an online algorithms HSF. HSF is optimal in the case where s > 1 and Σ 1 ≥ Σ2 s , where Σ 1 and Σ 2 denote the total processing time of jobs which request higher GoS machine and the total processing time of jobs which request the normal one, respectively.

In the second problem, we study two subproblems P L and P A proposed in [START_REF] Tan | Online scheduling with reassignment[END_REF]. Assume that the speeds of 2 uniform machines are 1 and s ≥ 1, respectively. For P L where we can reassign the last k jobs of the sequence, we show a lower bound of competitive ratio 1 + 1 1+s . For P A where we can reassign arbitrary k jobs, we show a lower bound of competitive ratio (s+1) 2 s 2 +s+1 . We propose a s+1 s -competitive algorithm HSF-1 for both P L and P A . For P A , we propose a (s+1) 2 s+2 -competitive algorithm EX-RA, which is superior to HSF-1 when 1 ≤ s ≤ √ 2.

Introduction

In the classical uniform machine scheduling problem, there are m ≥ 2 machines with different speeds. A list of n independent jobs with nonnegative processing times has to be scheduled non-preemptively on these machines with the objective of minimizing the makespan, which is the completion time of the last job in the schedule. This chapter studies the online version of this problem with two uniform machines. We are given a sequence of independent jobs which arrive in a list. We have to assign a job to one of the two uniform machines before the next job shows up.

In the first problem, we deal with online scheduling under a grade of service (GoS). Within an offline context, the concept of GoS was introduced and analyzed in [START_REF] Hwang | Parallel machines scheduling under a grade of service provision[END_REF]. For the online problem, the well-known List algorithm introduced by Graham [START_REF] Graham | Bounds for certain multiprocessor anomalies[END_REF] has been proved to be the best possible for the case of identical machines. The List algorithm assigns the incoming job to the least loaded machine. Cho and Shani [START_REF] Cho | Bounds for list schedules on uniform processors[END_REF] proved that List algorithm is 1+ √ 5

2 -competitive for all s and the bound is tight when s = 1+ √ 5

2 . Epstein et al. [START_REF] Epstein | Randomized on-line scheduling on two uniform machines[END_REF] provided randomized algorithms with better performance than List algorithm in the case where no preemption is allowed. In the same paper, for the problem with preemption, they proposed an optimal (1 + s s 2 +s+1 )-competitive algorithm for all s ≥ 1, which cannot be beaten by any randomized algorithm [START_REF] Wen | Preemptive on-line scheduling for two uniform processors[END_REF]. Angelelli et al. [START_REF] Angelelli | Semi-online scheduling on two uniform processors[END_REF] considered the semi-online scheduling on two uniform processors in the case where the total processing time of jobs is known in advance and presented algorithms which are optimal for s ≥ √ 3, s = 1 and

1+ √ 17 4 ≤ s ≤ 1+ √ 3
2 . Jongho Park et al. [START_REF] Park | Online and semi-online scheduling of two machines under a grade of service provision[END_REF] studied the online scheduling of two machines under a grade of service (GoS) provision and its semi-online variant where the total processing time is known. They gave an optimal online algorithm whose competitive ratio is 5 3 and an optimal semi-online algorithm with a competitive ratio 3 2 . In the second problem, we consider online scheduling with reassignment. In the classical online scheduling problem, jobs cannot be reassigned after they have been assigned to machines. However, it may not be the case in the real world, such as hotel or restaurant reservation and reception. In order to minimize the makespan, we need to reassign some jobs to gain a better effect. Three problems of online scheduling with reassignment have been proposed in [START_REF] Tan | Online scheduling with reassignment[END_REF]. In the first problem P L , we can reassign the last k jobs of the sequence. Tan et al. [START_REF] Tan | Online scheduling with reassignment[END_REF] proved that List algorithm [START_REF] Graham | Bounds for certain multiprocessor anomalies[END_REF] is optimal with a competitive ratio of 3 2 . In the second problem P E where we can reassign the last job of each machine, they proposed an optimal algorithm RE with a competitive ratio of √ 2. In the third problem P A , we can reassign arbitrary k jobs. They obtained lower bound 4 3 and presented an optimal algorithm RA. Kellerer et al. [START_REF] Kellerer | Semi on-line algorithms for the partition problem[END_REF] studied two models. In one of them, a buffer is available to maintain those arrived but unassigned jobs. In the other, there exists two parallel processors and we need to choose the better one as output. They obtained two optimal algorithms which are 4 3competitive. Sanders et al. [START_REF] Sanders | Online scheduling with bounded migration[END_REF] discussed another kind of reassignment model. When a new job is arriving, we are allowed to migrate some pervious jobs to other machines provided that the total processing time of migrated jobs is not greater than β times of the processing of the new job. They gave an algorithm with a competitive ratio 3 2 for β = 4 3 on m machines, and an algorithm with a competitive ratio 7 6 for β = 1 on two machines. Moreover, they also gave a family of algorithms with competitive ratio 1 + ε for a constant β(ε) on m machines for any fixed ε.

The rest of this chapter is organized as follows. In Section 2, we deal with the problem of online scheduling under a grade of service. In subsection 2.1, we describe the problem and introduce some notations. In subsection 2.2, we show that 1 + 2s s+2 is a lower bound of competitive ratio in the case where 0 < s ≤ 1 and 1 + s+1 s(2s+1) in the case where s > 1. In subsection 2.3, we show some upper bounds of competitive ratio by proposing and analyzing an online algorithms HSF algorithm. In section 3, we deal with the problem of online scheduling with reassignment. In subsection 3.1, we show that a lower bound of competitive ratio for P L is 1 + 1 1+s . In subsection 3.2, we show that a lower bound of competitive ratio for P A is (s+1) 2 s 2 +s+1 . In subsection 3.3, we give an upper bound of competitive ratio for both P L and P A by proposing and analyzing HSF-1 algorithm. In subsection 3.4, we prove that EX-RA algorithm is (s+1) 2 s+2 -competitive.

Online scheduling under GoS

In this section we consider the problem of online scheduling on two uniform machines under GoS.

Problem definition and notations

We are given two uniform machines. Without loss of generality, we denote the one which can provide higher GoS and whose speed is 1 by M 1 , while the other one with lower GoS and speed s by M s . Note that M 1 can also provide lower GoS, instead of M s , whenever it is available. A sequence of jobs I = {J 1 , J 2 , ..., J n } which arrive online have to be scheduled irrevocably on one of the machines at the time of their arrivals. The new job shows up only after the current job is scheduled. We denote a job by J i = (p i , g i ), where the first item p i is the processing time of job J i and the second item g i ∈ {1, 2} denotes the GoS assigned to the job J i , which is 1 if the job must be processed only by M 1 and 2 if it can be processed by either of two machines. p i and g i are not known until the previous job J i-1 has been scheduled, except job J 1 . The schedule can be seen as a partition of job sequence I into two subsets, denote by S 1 and S 2 , where S 1 and S 2 consist of jobs assigned to M 1 and M s , respectively.

Let L 1 = Ji∈S1 p i and L 2 = 1 s Ji∈S2 p i denote the workload of M 1 and M s , respectively. The makespan of the schedule is max{L 1 , L 2 }. The online problem can be written as:

Given I, find S 1 and S 2 to minimize max{L 1 , L 2 }.

Lower bounds of competitive ratio

In this subsection, we show some lower bounds of competitive ratio in different cases.

Theorem 7

For the problem of scheduling two uniform machines(with different speeds, s and 1) under GoS, there is no online algorithm with competitive ratio less than: (1) 1 + 2s s+2 in the case where 0 < s ≤ 1;

(2) 1 + s+1 s(2s+1) in the case where s > 1.

Proof. We discuss two cases in the theorem according to the value of s.

(1) 0 < s ≤ 1.

For simplicity of expression, let ϕ = 1 + 2s s+2 and θ = 1 s . It follows θ ≥ 1. The problem is then converted to that the speeds of M 1 and M s are θ and 1, respectively. The desired lower bound is ϕ = 1 + 2 2θ+1 . We give a job input sequence to show that there is no online algorithm whose competitive ratio is less than ϕ. The job sequence consists of at most 5 jobs which arrive in the order {J 1 , J 2 , J 3 , J 4 , J 5 }.

Let J 1 = (θ, 2). Case 1. J 1 is scheduled on M 1 . Let J 2 = (θ 2 , 1). Therefore, C ON ≥ 1 θ (θ + θ 2 ) = 1 + θ.
An optimal solution consists of assigning J 1 and J 2 to M s and M 1 , respectively. Thus,

C OP T = θ and C ON C OP T ≥ 1+θ θ > ϕ. Case 2. J 1 is scheduled on M s . Then we further generate J 2 = (θ 2 , 2). Case 2.1. J 2 is assigned to M s . It follows C ON ≥ θ + θ 2 .
In an optimal solution, J 1 and J 2 are scheduled on M s and M 1 , respectively. Thus,

C OP T = θ and C ON C OP T ≥ θ+θ 2 θ = 1 + θ > ϕ. Case 2.2. J 2 is assigned to M 1 . We generate J 3 = (θ 2 , 2). Case 2.2.1. J 3 is scheduled on M 1 . Let J 4 = (2θ 3 + θ 2 , 1). Therefore, C ON ≥ 1 θ (θ 2 + θ 2 + 2θ 3 + θ 2 ) = 3θ + 2θ 2 .
An optimal schedule consists of assigning J 1 , J 2 , J 3 to M s and J 4 to M 1 . Thus, 3 . An optimal solution can assign J 1 , J 2 , J 3 to M s and J 4 to M 1 . Therefore, it follows that

C OP T = 1 θ (2θ 3 + θ 2 ) = 2θ 2 + θ. It follows C ON C OP T ≥ 3θ + 2θ 2 2θ 2 + θ = 1 + 2 2θ + 1 = ϕ. Case 2.2.2. J 3 is scheduled on M s . We further generate J 4 = (2θ 3 + θ 2 , 2). Case 2.2.2.1. J 4 is assigned to M s . It follows C ON ≥ θ + θ 2 + 2θ 3 + θ 2 = θ + 2θ 2 + 2θ
C OP T = 1 θ (2θ 3 + θ 2 ) = 2θ 2 + θ. Then C ON C OP T ≥ θ + 2θ 2 + 2θ 3 2θ 2 + θ = 1 + 2θ 2 2θ + 1 ≥ ϕ.
Case 2.2.2.2. J 4 is assigned to M 1 . Let J 5 = (2θ 4 +3θ 3 +θ 2 , 1). It follows C ON ≥ 1 θ (θ 2 +2θ 3 +θ 2 +2θ 4 +3θ 3 +θ 2 ) = 2θ 3 + 5θ 2 + 3θ. An optimal schedule can assign J 1 , J 2 , J 3 , J 4 to M s and J 5 to M 1 . Thus,

C OP T = 1 θ (2θ 4 + 3θ 3 + θ 2 ) = 2θ 3 + 3θ 2 + θ. It follows C ON C OP T ≥ 2θ 3 + 5θ 2 + 3θ 2θ 3 + 3θ 2 + θ = 1 + 2 2θ + 1 = ϕ.
(2) s > 1.

In this case, we also give a job sequence which consists of at most 5 jobs to show that the competitive ratio of any online algorithm cannot be less than 1 + s+1 s(2s+1) . Let ϕ = 1 + s+1 s(2s+1) . We begin with J 1 = (s, 2). Case 1. J 1 is assigned to M 1 . Let J 2 = (1, 1). It follows C ON ≥ s + 1. An optimal schedule can assign J 1 to M s and J 2 to M 1 . Thus, C OP T = 1 and

(s + s + 2 + 1 s ) = 2 + 2 s + 1 s 2 .
An optimal schedule can assign J 1 , J 2 , J 3 to M s and J 4 to M 1 . Thus, C OP T = 2 + 1 s , and

C ON C OP T ≥ 2 + 2 s + 1 s 2 2 + 1 s = 1 + s + 1 s(2s + 1) = ϕ. Case 2.2.2.2. J 4 is scheduled on M 1 . We further generate J 5 = (2+ 3 s + 1 s 2 , 1). Therefore C ON ≥ 1+2+ 1 s +2+ 3 s + 1 s 2 = 5 + 4 s + 1 s 2 .
An optimal solution can assign J 1 , J 2 , J 3 , J 4 to M s and J 5 to M 1 . Thus,

C OP T = 2 + 3 s + 1 s 2 . Since s > 1, C ON C OP T ≥ 5 + 4 s + 1 s 2 2 + 3 s + 1 s 2 = 1 + s(3s + 1) (2s + 1)(s + 1) > 1 + s + 1 s(2s + 1) = ϕ.
The theorem follows.

Remark 5

In the case where s = 1, a lower bound of competitive ratio for all online algorithms is 5 3 .

This is the lower bound proved in [START_REF] Park | Online and semi-online scheduling of two machines under a grade of service provision[END_REF]. When s = 1, our online problem reduces to the one in [START_REF] Park | Online and semi-online scheduling of two machines under a grade of service provision[END_REF].

Upper bounds of competitive ratio

In this subsection we show an upper bound of competitive ratio by giving an algorithms HSF. Let Σ 1 and Σ 2 denote the total processing time of jobs with g i = 1 and with g i = 2, respectively. We first prove that in the case where s > 1 and Σ 1 ≥ Σ2 s , HSF is optimal.

HSF algorithm

There is a straightforward algorithm called HSF algorithm (higher speed machine first). HSF algorithm schedules jobs as many as possible on higher speed machine. I.e., if 0 < s ≤ 1, HSF algorithm schedules all the jobs on M 1 ; else, HSF algorithm schedules all jobs with g i = 2 on M s , and the others on M 1 .

Lemma 10

In the case 0 < s ≤ 1, HSF is (s + 1)-competitive.

Proof. By the definition of HSF algorithm, C ON = Σ 1 + Σ 2 . On the other hand, the offline adversary can generate a job sequence which can be perfectly distributed to both machines in order to maintain a load balance between two machines; i.e., Σ 1 = Σ2 s . Therefore,

C ON C OP T ≤ (Σ 1 + Σ 2 ) Σ1+Σ2 s+1 = s + 1.

Lemma 11

In the case where s > 1, if Σ 1 ≥ Σ2 s , HSF is optimal.

Proof. Since C OP T = max{Σ 1 , Σ2 s } = Σ 1 and C ON = max{Σ 1 , Σ2 s } = Σ 1 , the lemma follows.

Lemma 12 In the case where

s > 1, if Σ 1 < Σ2 s , HSF is s+1 s -competitive. Proof. Since Σ 1 < Σ2 s , C ON = max{Σ 1 , Σ2 s } = Σ2 s .
On the other hand, the offline adversary can generate a job sequence which can be perfectly distributed to both machines. Let Σ1 Σ2 = (0

< < 1 s ). Then C ON C OP T ≤ Σ 2 s • s + 1 Σ 1 + Σ 2 = s + 1 s(1 + ) .
Let → 0, we have the desired result.

Online scheduling with reassignment

In this section we consider the problem of online scheduling on two uniform machines with reassignment. Without loss of generality, we denote the machine with speed 1 by M 1 and the other one with speed s by M s , where s ≥ 1. We use C ON and C OP T to denote the makespan of an online algorithm and that of offline optimal algorithm (after reassignment), respectively.

Lower bound of competitive ratio for P L (last k jobs can be reassigned)

In this subsection, we show a lower bound 1 + 1 1+s of competitive ratio. Theorem 8 For P L , there is no online algorithm with a competitive ratio less than 1 + 1 1+s . Proof. Let ε be a sufficiently small positive number. For simplicity of expression, let ϕ = 1 + 1 1+s . We generate job J 1 with p 1 = s, and discuss two cases according to the assignment of J 1 by the online algorithm in below.

Case 1: J 1 is assigned to M 1 . We generate J 2 with p 2 = s 2 . If J 2 is assigned to M 1 , we further generate last k jobs with processing time ε. It follows C ON ≥ s + s 2 . The offline algorithm may assign jobs to the two machines with equivalent workload, i.e., C OP T = s+s 2 +kε 1+s = s + kε 1+s < s + kε. So,

C ON C OP T > s + s 2 s + kε → 1 + s ≥ ϕ. (ε → 0)
Otherwise if J 2 is assigned to M s , we generate job J 3 with p 3 = s 2 (s+1) and further generate last k jobs with processing time ε. J 3 is assigned to either M 1 or M s . In either case, C ON ≥ 1 s (s 2 +s 2 (s+1)) = s 2 +2s. The offline algorithm can make the two machines have equal workload, i.e., C OP T = s+s 2 +s 2 (s+1)+kε 1+s < s + s 2 + kε. Hence,

C ON C OP T > s 2 + 2s s + s 2 + kε → 1 + 1 1 + s = ϕ. (ε → 0)
Case 2: J 1 is assigned to M s . We generate job J 2 with p 2 = 1. If J 2 is assigned to M s , we further generate last k jobs with processing time ε. It follows C ON ≥ 1 + 1 s . On the other hand,

C OP T = s+1+kε 1+s < 1 + kε. C ON C OP T > 1 + 1 s 1 + kε → 1 + 1 s > ϕ. (ε → 0)
If job J 2 is assigned to M 1 , we generate job J 3 with p 3 = s + s 2 and then further generate last k jobs with processing time ε. Therefore, C ON ≥ 1 s (s + s + s 2 ) = 2 + s. On the other hand, C OP T = s+1+(s+s 2 )+kε 1+s

< 1 + s + kε. C ON C OP T > 2 + s 1 + s + kε → 1 + 1 1 + s = ϕ. (ε → 0)
The theorem follows.

Remark 6 For P L , if the speeds of two machines are identical, a lower bound of competitive ratio is 3 2 .

The result in [START_REF] Tan | Online scheduling with reassignment[END_REF] is a special case of Theorem 8. Note that when s = 1, List algorithm is optimal [START_REF] Cho | Bounds for list schedules on uniform processors[END_REF].

Lower bound of competitive ratio for P A (we can reassign arbitrary k jobs)

In this subsection, we show a lower bound (s+1) 2 s 2 +s+1 of competitive ratio for P A . For an arbitrary online algorithm A ON , let L 1 = Ji∈S1 p i and L 2 = 1 s Ji∈S2 p i denote the workloads of M 1 and M s before reassignment, respectively.

Theorem 9 For P A , there is no online algorithm with competitive ratio less than (s+1) 2 s 2 +s+1 .

Proof. We begin with Mn jobs with processing time 1, where M and n are two positive integers. Since the total processing time of the Mn jobs is Mn, L 1 + sL 2 = Mn. For simplicity, let x = L1 Mn and y = L2 Mn . Thus,

x + sy = 1.

(5.1)

Let ϕ = (s+1) 2 s 2 +s+1 . Consider the following two cases.

Case 1: 0 ≤ L 2 ≤ L 1 . It follows 0 ≤ y ≤ x ≤ 1. (5.2)
By equation (5.1) and inequality (5.2), x is bounded such that 1 s+1 ≤ x ≤ 1. Since s ≥ 1, 1 s+1 < 1+s s 2 +s+1 < 1. In below we further discuss two subcases according to the bound of x.

Case 1.1: 1+s s 2 +s+1 < x ≤ 1. No more jobs arrive. C ON > L 1k since A ON can at most move k jobs from M 1 to M s during reassignment, while C OP T = Mn 1+s . So,

C ON C OP T ≥ L 1 -k Mn 1+s → (1 + s)x > (s + 1) 2 s 2 + s + 1 = ϕ. (n → ∞) Case 1.2: 1 1+s ≤ x ≤ 1+s s 2 +s+1
. We further generate the last job with processing time sM n. With similar reasoning as that in Case 1.1,

C ON C OP T ≥ L 2 + Mn -k s Mn → y + 1 = 1 -x s + 1 ≥ (1 + s) 2 s 2 + s + 1 = ϕ. (n → ∞) Case 2: 0 ≤ L 1 ≤ L 2 . Together with equation (7), 0 ≤ x ≤ y ≤ 1 s . ( 5.3)
By equation (5.1) and inequality (5.3), x is bounded such that 0 ≤ x ≤ 1 s+1 . We divide the case into two subcases according to the bound of s in below.

Case 2.1: s > √ 5+1

2 . We further generate the last job with processing time sM n. Since s > √ 5+1

2 , 1 + ss 2 < 0. Together with 0 ≤ x ≤ 1 s+1 , we have x + s > y + 1. As n → ∞,

C ON C OP T ≥ min{L 1 + sM n, L 2 + Mn} -k Mn → min {x + s, y + 1} = y + 1 = 1 -x s + 1 ≥ s + 2 s + 1 > ϕ. Case 2.2: 1 ≤ s ≤ √ 5+1 2 . It follows 0 ≤ 1+s-s 2 s+1 ≤ 1 s+1 . Case 2.2.1: 0 ≤ x ≤ 1+s-s 2
2s+1 . No more jobs arrive. C ON > L 2 -k s with similar reasoning as that in Case 1.1. So,

C ON C OP T ≥ L 2 -k s Mn 1+s → (1 + s)y = (1 + s)(1 -x) s ≥ (1 + s) 2 2s + 1 ≥ ϕ. (n → ∞)
Case 2.2.2: 1+s-s 2 2s+1 < x ≤ 1+s-s 2 s+1 . We further generate the last job with processing time sM n. x + s ≤ y + 1 due to x ≤ 1+s-s 2 s+1 . It follows

C ON C OP T ≥ min{L 1 + sM n, L 2 + Mn} -k s Mn → min {x + s, y + 1} = x + s > (1 + s) 2 2s + 1 ≥ ϕ. (n → ∞)
Case 2.2.3: 1+s-s 2 s+1 < x ≤ 1 s+1 . We further generate the last job with processing time sM n. Since 1+s-s 2 s+1 < x, x + s > y + 1. Therefore,

C ON C OP T ≥ min{L 1 + sM n, L 2 + Mn} -k s Mn → min {x + s, y + 1} = y + 1 ≥ s + 2 s + 1 > ϕ. (n → ∞)
The theorem follows.

Remark 7

For P A , there is no online algorithm with a competitive ratio less than 4 3 .

The result analyzed in [START_REF] Tan | Online scheduling with reassignment[END_REF] is a special case of Theorem 9.

Upper bound of competitive ratio for P L and P A

In this subsection, we propose a straightforward algorithm named HSF-1(higher speed machine first). HSF-1 schedules all the jobs on M s (s ≥ 1). Given a job sequence I, let Σ = Ji∈I p i be the total processing time of jobs in I.

Lemma 13 HSF-1 is s+1

s -competitive for P L and P A .

Proof. By the definition of HSF algorithm, C ON = Σ s . While, the offline adversary can generate a job sequence which can be perfectly distributed to both machines to maintain a load balance between two machines. Therefore,

C ON C OP T ≤ Σ s Σ s+1 = s + 1 s .

EX-RA algorithm for P A

In this subsection, we propose another online algorithm called EX-RA, which is superior to HSF in competitiveness when 1 ≤ s ≤ √ 2. We define L 1 and L 2 to be the workloads of M 1 and M s (after reassignment), respectively. In the following we first give a lemma.

Lemma 14 Given that r ≥ 1, for any online algorithm

A ON , if L 2 ≤ L 1 ≤ rL 2 or L 1 ≤ L 2 ≤ rL 1 ,
then the competitive ratio of A ON is at most r(s+1) r+s .

Proof. Let ϕ = (s+1) 2 s+2 . If there is only one job, it is trivial that CON C OP T ≤ s < ϕ. If there are only two jobs J 1 and J 2 , without loss of generality, let p 1 ≤ p 2 . Thus,

C ON ≤ p 2 and C OP T ≥ max{p 1 , p2 s }. If p 2 ≤ sp 1 , C ON C OP T ≤ p 2 max{p 1 , p2 s } = p 2 p 1 < s < ϕ. Otherwise if p 2 > sp 1 , C ON C OP T ≤ p 2 max{p 1 , p2 s } = p 2 p2 s = s < ϕ.
In the rest proof, we assume that there are more than two jobs in the job input sequence.

Case 1:

M θ 1 ≥ M θ 2 . It follows M θ 2 ≤ (s + 1)M θ 1 . By Step 5, M π 1 = M θ 1 , M π 2 = M θ 2 .
(5.4)

If no job is assigned to M 1 in Step 3, let J k with processing time p k denote the job assigned to M 1 . Therefore,

C ON = M π 1 = p k . Since C OP T ≥ p k s , C ON C OP T ≤ p k p k s = s < ϕ.
Otherwise if some jobs are assigned to M 1 in Step 3, M θ 1 ≤ (s + 1)M θ 2 . By equation (5.4), it follows M π 2 ≤ M π 1 ≤ (s + 1)M π 2 . By Lemma 14, EX-RA algorithm is ϕ-competitive.

Case 2:

M θ 1 < M θ 2 . If M θ 2 ≤ (s + 1)M θ 1 , EX-RA algorithm is ϕ-competitive due to
Step 5 and Lemma 14. Therefore, in the following we focus on the case where M θ 2 > (s + 1)M θ 1 , which implies that at least two jobs are assigned to M 2 . Let J y and J x be the last two jobs on M 2 before reassignment such that J y arrives before J x . Let B be the total processing time of jobs arriving between J y and J x (except J y and J x ). Let A be the total processing time of jobs coming after J x . These jobs are assigned to M 1 .

Case 2.1: M 1 denotes M 1 . Considering jobs J x and J y , we have

M y 1 + p y > (s + 1)M y 2 , ( 5.5
)

M y 1 + B + p x > (s + 1) M y 2 + p y s . (5.6) By M θ 2 > (s + 1)M θ 1 and
Step 5, the reassignment consists of moving J y from M s to M 1 . Before reassignment,

M θ 1 = M y 1 + B + A, M θ 2 = M y 2 + p y s + p x s . (5.7) Since M θ 2 > (s + 1)M θ 1 , M y 2 + p y s + p x s > (s + 1)(M y 1 + B + A).
(5.8)

After reassignment,

M π 1 = M y 1 + B + A + p y , M π 2 = M y 2 + p x s .
(5.9)

Case 2.1.1:

M π 2 > (s + 1)M π 1 . It follows C OP T = M π 2 .
By inequality (5.5) and equation (5.9),

p x > s[(s + 1)(M y 1 + B + A + p y ) -M y 2 ] ≥ s[(s + 1)(M y 1 + p y ) -M y 2 ] ≥ s 2 (s + 2)M y 2 .
Since

C OP T ≥ p x /s, C ON C OP T ≤ M π 2 px s = M y 2 + px s px s < 1 s(s + 2) + 1 ≤ ϕ. Case 2.1.2: M π 1 ≤ M π 2 ≤ (s + 1)M π 1 . It follows C ON /C OP T ≤ ϕ by Lemma 14. Case 2.1.3: M π 2 < M π 1 . It follows C ON = M π 1 .
Let both sides of inequality (5.6) multiply a factor s 2 +s+1 2s+1 and add to both sides of inequality (5.8), considering equation (5.9), it follows that

M π 2 < M π 1 = M y 1 + B + A + p y < s 3 + s 2 + 3s + 1 s 2 (s + 2) p x ≤ s 3 + s 2 + 3s + 1 s(s + 2) M π 2 ≤ (s + 1)M π 2 .
It

P x > [(s+1)(M y 1 + B s + A s + p y s )-M y 2 ] ≥ [(s+1)(M y 1 + p y s )-M y 2 ] ≥ s(s+2)M y 2 .
Since C OP T ≥ px s ,

C ON C OP T ≤ M π 2 Px s = M y 2 + P x Px s < s 1 s(s + 2) + 1 = (s + 1) 2 s + 2 = ϕ. Case 2.2.2: M π 1 ≤ M π 2 ≤ (s + 1)M π 1 . It follows C ON /C OP T ≤ ϕ by Lemma 14.
Case 2.2.3: M π 2 < M π 1 . Let both sides of inequality (5.13) multiply a factor s 2 +s+1 2s+1 and add to both sides of inequality (5.11), considering equation (5.14),

M π 2 < M π 1 = M y 1 + B s + A s + p y s < s 3 + s 2 + 3s + 1 s 3 (s + 2) p x ≤ s 3 + s 2 + 3s + 1 s 3 (s + 2) M π 2 ≤ (s + 1)M π 2 .
It follows C ON /C OP T ≤ ϕ by Lemma 14. According to the above discussion, the theorem follows.

Remark 8 EX-RA algorithm is superior to HSF algorithm in the case where

1 ≤ s ≤ √ 2.
Remark 9 EX-RA algorithm is optimal in the case where s = 1.

As a consequence, Theorem 10 generalizes the result in [START_REF] Tan | Online scheduling with reassignment[END_REF].

The theorem follows.

Remark 11

The Theorem 3 in [START_REF] Angelelli | Semi-online scheduling on two uniform processors[END_REF] is a special case of Theorem 1 such that m = 1.

ECT algorithm

In this section, we describe and analyze online algorithm ECT, which is based on the shortest remaining processing time (SRPT) or ECT rule. Algorithm ECT constructs a schedule of early jobs only, since any tardy jobs can be appended to this schedule in an arbitrary order. Given a job instance I, algorithm ECT runs as follows.

Step 1: Wait until a decision point t, at which a new job is released or at least one of m identical machines becomes available (idle).

Step 2: At any decision point, if there is no idle machine, schedule job J i such that

p i = min{p k |J k ∈ I, r k ≤ t, p k > 0, t + p k ≤ d k } (shortest
remaining processing time) to process on the machine with the least current workload; otherwise, schedule job J i on one of idle machines. Ties are broken by alphabetic order.

Step 3: If at some decision point t, no jobs are subsequently released and t + p k > d k for all jobs J k with r k ≤ t and p k > 0, stop; else, go to Step 1.

Note that ECT algorithm is based on the earliest completion time (ECT) policy, i.e., when ECT algorithm makes a decision to schedule a job J j with the shortest remaining processing time among available jobs, then if it is not preempted, J j completes no later than if any other available job were to be processed next. Therefore, a job is preempted only if a newly released job can complete earlier.

Without loss of generality, we assume that the machines are reindexed in increasing order of the job scheduled at the first position. Let N (S) be the number of jobs scheduled in S. Let -→ S and S * be the (feasible) schedule obtained by ECT algorithm and an optimal (feasible) schedule, respectively. Let J k (S) be the job with the kth smallest completion time in schedule S. If two jobs are completed at the same time, the job completed on the smallest indexed machine is considered to be completed earlier.

Note that -→ S only contains early jobs and algorithm ECT terminates at time t when all unscheduled jobs in I cannot meet their respective due dates (i.e., any job J j ∈ I\J( -→ S ) satisfies the conditions that t + p j > d j and p j > 0). That is to say, once algorithm ECT stops, no job in I\J( -→ S ) can be scheduled to be early (by any algorithm).

Theorem 12 Algorithm ECT is 1 2 -competitive.

Proof. If S * = -→ S , the theorem follows. Therefore, in the following proof, we assume that S * = -→ S . In order to prove the theorem, it is sufficient to prove that N ( -→ S ) ≥ N (S * ) 2 . For this purpose, we construct a series of feasible schedules S 0 , S 1 , ..., S h = -→ S such that S 0 = S * and S 1 , ..., S h-1 are different from -→ S . Schedule S q is obtained from S q-1 for q = 1, ..., h as follows.

Let k (q) be the smallest k such that J k (S q-1 ) = J k ( -→ S ) for 1 ≤ k ≤ N ( -→ S ). Such a k necessarily exists, since S q-1 is different from -→ S . From the notation, we have either k (q) = 1 or

J k (S q-1 ) = J k ( -→ S ), k ∈ {1, ..., k (q) -1}. (6.1)
S q is obtained by ( i) Deleting job J k (q) (S q-1 ) from S q-1 ; (ii) Moving or adding job J k (q) ( -→ S ) to the place of J k (q) (S q-1 ) depending on whether the job appears in S q-1 .

By construction, S q is necessarily feasible since J k (q) ( -→ S ) is the job that can be completed the earliest among all remaining jobs at that time (ECT policy). Furthermore, for q = 1, ..., h, we have either S q = -→ S or k (q) > k (q -1), (6.2)

N (S q ) ≥ N (S q-1 ) -1. ( 6.3)
From inequality (6.2), we obtain

h ≤ N ( -→ S ). (6.4)
From inequalities (6.3) and (6.4), we obtain

N ( -→ S ) = N (S h ) ≥ N (S h-1 ) -1 ≥ N (S h-2 ) -2 ≥ ... ≥ N (S 0 ) -h = N (S * ) -h ≥ N (S * ) -N ( -→ S ).
As a consequence, N ( -→ S ) ≥ N (S * )

Chapter 7

Single batch processing machine model

We consider two semi-online scheduling problems on a single batch (processing) machine with jobs' nondecreasing processing times and jobs' nonincreasing processing times, respectively. Our objective is to minimize the makespan. A batch processing machine can handle up to B jobs simultaneously. We study an unbounded model where B = ∞. The jobs that are processed together construct a batch, and all jobs in a batch start and complete at the same time. The processing time of a batch is given by the longest processing time of any job in the batch. Jobs arrive over time. Let p j denote the processing time of job J j . Given job J j and its following job J j+1 , we assume that p j+1 ≥ αp j , where α ≥ 1 is a constant number, for the first problem with jobs' nondecreasing processing times. For the second problem, we assume that p j+1 ≤ αp j , where 0 < α < 1 is a constant number. We propose an optimal algorithm for both problems with a competitive ratio √ α 2 +4-α 2

+ 1 for the first problem and

√ 4α+1+1 2
for the second problem.

Introduction

Batch processing machine scheduling has been motivated by burn-in operations in the final testing stage of semiconductor manufacturing in [START_REF] Lee | Efficient algorithms for scheduling semiconductor burn-in operations[END_REF] and [START_REF] Lee | Minimizing makespan on a single batch processing machine with dynamic job arrivals[END_REF]. Batch scheduling means that a machine can process up to B jobs simultaneously as a batch, and the processing time of a batch is equal to the longest processing time of the jobs assigned to it. Unbounded model means that B is sufficiently large and the bounded model means that B is a constant positive integer.

In this chapter, we consider the third model where jobs arrive over time. Zhang et al. [START_REF] Zhang | On-line algorithms for minimizing makespan on batch processing machines[END_REF] considered the problem of online scheduling on a batch processing machine. They provided an optimal online algorithm with a competitive ratio √ 5+1

2 . Based on their results, we study the semi-online problems by using additional jobs' information. We present an optimal semi-online algorithm with a competitive ratio no more than √ 5+1

2 . Let p j denote the processing time of job J j . Given job J j and its following job J j+1 , we assume that p j+1 ≥ αp j , α ≥ 1 is a constant number, in the first problem with jobs' nondecreasing processing times. For the second problem, we assume that p j+1 ≤ αp j , 0 < α < 1 is a constant number.

Online scheduling on a (parallel) batch processing machine has been studied in the last decade. In the unbounded model, for the problem of online scheduling on a single batch machine to minimize the makespan, Zhang et al. [START_REF] Zhang | On-line algorithms for minimizing makespan on batch processing machines[END_REF] and Deng et al. [START_REF] Deng | Approximation algorithms in batch processing[END_REF] independently provided an online algorithm with a competitive ratio √ 5+1

2 . Poon et al. [START_REF] Poon | Online scheduling algorithms for a batch machine with finite capacity[END_REF] showed that for the same problem in the bounded model, any FBLPT-based (Full Batch Longest Processing Time) algorithm is 2-competitive. Moreover, they presented an algorithm with a competitive ratio 7 4 for batch size B = 2. If a batch is allowed to restart, Fu et al. [START_REF] Fu | On-line scheduling in a parallel batch processing system to minimize makespan using restarts[END_REF] showed that for minimizing makespan on an unbounded batch machine there is no algorithm with a competitive ratio less than 5- √ 5

2 . Further, they provided an online algorithm with a competitive ratio 3 2 . For this problem, Fu et al. [START_REF] Fu | On-line scheduling on a batch machine to minimize makespan with limited restarts[END_REF] further considered limited restarts which means that any batch containing a job has already been restarted once cannot be restarted any more. They present an optimal algorithm with a competitive ratio 3 2 . Recently, Nong et al. [START_REF] Nong | The single-machine parallel-batching on-line scheduling problem with family jobs to minimize makespan[END_REF] considered family jobs constraint in the single batch machine scheduling problem. For the unbounded case, they provided an optimal online algorithm with a competitive ratio 2. For the bounded case, they gave a 2-competitive algorithm.

For convenience, we use online algorithm to denote semi-online algorithm in the remainder. The rest of this chapter is organized as follows. In section 2, we give the problem definitions and some notations. In section 3, we present a lower bound ϕ = (0 < α < 1) for the second problem, respectively. In section 4, we use the lower bounds obtained in the above section to design algorithm H ∞ α . After that, we prove that this algorithm is optimal for both problems.

Problem definitions and notations

We are given a job instance I = {J 1 , ..., J n } (n ≥ 2) where each job J j is associated with a release time r j and a processing time p j . The jobs are to be processed by a batch processing machine of capacity B = ∞, i.e., we study unbounded model. The processing time of a batch is the longest processing time of any job in the batch. Jobs arrive over time, i.e., each job's character, such as processing time, becomes known at its arrival. Let p j denote the processing time of job J j . Let J i+1 denote the following job of J i . In the first problem with jobs' nondecreasing processing times, we assume that p j+1 ≥ αp j , where α ≥ 1 is a constant number. For the second problem, we assume that p j+1 ≤ αp j , where 0 < α < 1 is a constant number. Our objective is to minimize the makespan. Using three field notations, our problems can be denoted by 1|online, r j , B = ∞, nondecreasing|C max and 1|online, r j , B = ∞, nonincreasing|C max , respectively.

We use U (t) to denote the set of unscheduled jobs available at time t.

Lower bounds for both problems

In this section, we deal with the problems of online scheduling on a batch machine with jobs' nondecreasing processing times and jobs' nonincreasing processing times, respectively. We study unbounded model, i.e., the batch's size is sufficiently large. We first respectively give a lower bound of competitive ratio for each problem, then we provide an optimal algorithm for both problems. Let

ϕ = √ α 2 +4-α 2 + 1 when α ≥ 1 and ϕ = √ 4α+1+1 2 when 0 < α < 1. Note that 1 < ϕ ≤ √ 5+1 2
and we will use it in the remainder for simplicity. Given an job instance I, let C ON and C OP T denote the makespan obtained by an online algorithm A ON and the value of an optimal (offline) schedule, respectively.

Lemma 16 For 1|online, r j , B = ∞, nondecreasing|C max , there is no algorithm with a competitive ratio less than

√ α 2 +4-α 2 + 1, where α ≥ 1.
Proof. For any online algorithm A ON , we construct a special job instance I such that C ON /C OP T is as large as possible. Let be a sufficiently small positive number. At time 0, we give the first job J 1 with p 1 = 1. We assume that A ON schedules this job at time T A . Depending on T A , we discuss the following two cases.

Case 1. T

A ≥ √ α 2 +4-α 2
. No job arrives in future. We know that C ON ≥ √ α 2 +4-α 2 + 1. An optimal scheme consists of scheduling J 1 at time 0, i.e., C OP T = 1. Therefore,

C ON C OP T ≥ √ α 2 + 4 -α 2 + 1 = ϕ. Case 2. 0 ≤ T A < √ α 2 +4-α 2
. We further generate job J 2 with p 2 = α at time T A + . We obtain C ON ≥ T A + 1 + α. An optimal schedule consists of scheduling J 1 and J 2 in a batch at time T A + . Therefore, C OP T = T A + + α due to α ≥ 1. It follows that

C ON C OP T ≥ T A + 1 + α T A + + α = 1 + 1 T A + α > 1 + 1 √ α 2 +4-α 2 + α = ϕ, → 0.
According to the above two cases, the lemma holds.

Lemma 17 For 1|online, r j , B = ∞, nonincreasing|C max , there is no algorithm with a competitive ratio less than

√ 4α+1+1 2
, where 0 < α < 1.

Proof. For any online algorithm A ON , we construct a special job instance I such that C ON /C OP T is as large as possible. Let be a sufficiently small positive number. At time 0, we give the first job J 1 with p 1 = 1. We assume that A ON scheduling this job at time T A . Depending on T A , we discuss the following two cases.

Case 1. T

A ≥ √ 4α+1-1 2
. No job arrives in future. We know that C ON ≥ √ 4α+1+1 2

. An optimal scheme consists of scheduling J 1 at time 0, i.e., C OP T = 1. Therefore,

C ON C OP T ≥ √ 4α + 1 + 1 2 = ϕ. Case 2. 0 ≤ T A < √ 4α+1-1 2
. We further give job J 2 with p 2 = α at time T A + . We obtain C ON ≥ T A + 1 + α. An optimal schedule consists of scheduling J 1 and J 2 in a batch at time T A + . Therefore, C OP T = T A + + 1 due to α < 1. It follows that

C ON C OP T ≥ T A + 1 + α T A + + 1 = 1 + α T A + 1 > 1 + α √ 4α+1-1 2 + 1 = ϕ, → 0.
According to the above cases, the lemma holds.

An optimal algorithm for both problems

Considering the proofs of two lower bounds of competitive ratios, we realize that the algorithm should wait for a while rather than scheduling the jobs immediately after their arrivals. We shift the release time of job J j to r j = ϕr j + (ϕ -1)p j in order to contain the waiting time. This equation can guarantee that if J j is scheduled at time ϕr j + (ϕ -1)p j , its completion time cannot exceed ϕ times the optimal value, i.e., ϕr j + (ϕ -1)p j + p j = ϕ(r j + p j ). This idea is used in [START_REF] Zhang | On-line algorithms for minimizing makespan on batch processing machines[END_REF]. We design the following algorithm using the same idea. Algorithm H ∞ α works as follows.

Step 1: Wait until a decision point, where the batch machine is idle and at least one job is available (If all jobs have been scheduled, output the schedule). Suppose this happens at time t. Choose a job J j with the longest processing time in U (t).

Step 2: If r j ≤ t, schedule all jobs in U (t) as a single batch; otherwise, wait until a new job arrive or until time r j , whichever happens first.

Step 3: Go to Step 1.

We adopt some notations and definitions from [START_REF] Zhang | On-line algorithms for minimizing makespan on batch processing machines[END_REF]. Given an job instance, we assume that H ∞ α generate m batches in total. We index these batches in nondecreasing order of their completion times. For convenience, in batch i, denote by J (i) the job with the longest processing time in that batch. Let p (i) and r (i) be the processing time and the release time (or arrival time) of job J (i) , respectively. Let s (i) be the starting time of batch i. Note that batch i is processed either at time ϕr (i) + (ϕ -1)p (i) or after batch i -1 is finished at time s (i-1) + p (i-1) .

If batch i starts at time ϕr (i) +(ϕ-1)p (i) , we call it a regular batch; otherwise, it is called a delayed batch.

Similar to Lemma 2 in [START_REF] Zhang | On-line algorithms for minimizing makespan on batch processing machines[END_REF], we have the following lemma.

Lemma 18

If batch i is a regular batch, then batch i + 1 or batch i + 2 is also a regular batch.

Proof. We prove this lemma for two cases: α ≥ 1 and 0 < α < 1.

(1) α ≥ 1. By contradiction. Suppose both batches i + 1 and i + 2 are delayed batches. We know that each job in batch i + 1 arrives later than the starting time of batch i. Therefore, considering job J (i+1) , we have r (i+1) > ϕr (i) + (ϕ -1)p (i) . Since batch i + 1 is a delayed batch, we obtain

ϕ(r (i) + p (i) ) > ϕr (i+1) + (ϕ -1)p (i+1) > ϕ 2 r (i) + ϕ(ϕ -1)p (i) + (ϕ -1)p (i+1) . It follows that (2ϕ -ϕ 2 )p (i) > (ϕ 2 -ϕ)r (i) + (ϕ -1)p (i+1) ≥ (ϕ -1)p (i+1) . (7.1) Considering ϕ = √ α 2 +4-α 2
+ 1 and α ≥ 1, we have

p (i+1) < 2ϕ -ϕ 2 ϕ -1 p (i) = 1 ϕ -1 -(ϕ -1) p (i) = αp (i) .
This contradicts to the assumption that p (i+1) ≥ αp (i) for 1|online, r j , B = ∞, nondecreasing|C max .

(2) 0 < α < 1. By contradiction. Suppose both batches i + 1 and i + 2 are delayed batches. We know that each job in batch i + 2 arrives later than the starting time of batch i + 1. Therefore, considering job J (i+2) , we have r (i+2) > ϕ(r (i) + p (i) ). Since batch i + 2 is a delayed batch, we obtain

ϕ(r (i) + p (i) ) + p (i+1) > ϕr (i+2) + (ϕ -1)p (i+2) > ϕ 2 (r (i) + p (i) ) + (ϕ -1)p (i+2) . It follows that p (i+1) > (ϕ 2 -ϕ)(r (i) + p (i) ) + (ϕ -1)p (i+2) ≥ (ϕ 2 -ϕ)p (i) = ϕ(ϕ -1)p (i) . (7.2) Considering ϕ = √ 4α+1+1 2
and α < 1, we have ϕ(ϕ -1) = α, which implies

p (i+1) > αp (i) .
This contradicts to the assumption that p (i+1) ≤ αp (i) for 1|online, r j , B = ∞, nonincreasing|C max . The lemma follows.

Corollary 1

In the schedule obtained by algorithm H ∞ α , there do not exist two successive delayed batches.

Proof. By the algorithm, the first batch must be a regular batch. Then we have the desired result.

Let C H and C * denote the value obtained by algorithm H ∞ α and the optimal objective value (for an instance), respectively.

Lemma 19 If the last batch is a regular batch

, i.e., s (m) = ϕr (m) + (ϕ -1)p (m) , then C H /C * ≤ ϕ. Proof. Since C H = s (m) + p (m) = ϕ(r (m) + p (m) ) and C * ≥ r (m) + p (m)
, the lemma follows.

Theorem 13 Algorithm H ∞

α is optimal for both problems: 1|online, r j , B = ∞, nondecreasing|C max and 1|online, r j , B = ∞, nonincreasing|C max . (α ≥ 1 in the first problem and 0 < α < 1 in the second problem.) Proof. By contradiction. By Lemma 19, we only need to consider the case where the last batch m is a delayed batch. By algorithm, we know that the first batches must be a regular batch. Thus, in this case, there must be some batch processed before batch m. By Corollary 1, there do not exist two successive delayed batches in the schedule obtained by algorithm H ∞ α . Therefore, batch m -1 must be a regular batch. It follows that s (m-1) = ϕr (m-1) + (ϕ -1)p (m-1) ≥ (ϕ -1)p (m-1) .

(7.3)

We know C H = s (m-1) + p (m-1) + p (m) . (7.4) Note that r (m) > s (m-1) . (7.5)

In the following, we respectively discuss two cases: α ≥ 1 and 0 < α < 1.

(1) α ≥ 1.

We further discuss two cases depending on whether J (m) and J (m-1) are in the same batch in an optimal schedule. Case 1. In an optimal schedule, J (m) and J (m-1) are in the same batch. By the assumption that p j+1 ≥ αp j , we have C * ≥ r (m) + p (m) and p (m) ≥ αp (m-1) . Note that ϕ = √ α 2 +4-α 2 + 1. Considering equation (7.4) and inequalities (7.3) and (7.5), it follows

C H C * ≤ s (m-1) + p (m-1) + p (m) r (m) + p (m) < 1 + p (m-1) s (m-1) + p (m) ≤ 1 + 1 ϕ -1 + α = ϕ.
Case 2. In an optimal schedule, J (m) and J (m-1) are in different batches. It follows that C * ≥ r (m-1) + p (m-1) + p (m) . Considering equations (7.4) and (7.3), we have

C H C * ≤ s (m-1) + p (m-1) + p (m) r (m-1) + p (m-1) + p (m) = ϕ(r (m-1) + p (m-1) ) + p (m) r (m-1) + p (m-1) + p (m) < ϕ.
(2) 0 < α < 1.

We discuss two cases depending on whether J (m) and J (m-1) are in the same batch in an optimal schedule. Case 1. In an optimal schedule, J (m) and J (m-1) are in the same batch. By the assumption that p j+1 ≤ αp j , we have C * ≥ r (m) + p (m-1) and p (m) ≤ αp (m-1) . Note that ϕ = The theorem follows.

J 1 = (α, α). We assume that A ON schedules this job at time T . Depending on T , we discuss the following two cases. Note that α -1 ≥ 0. Case 1. T ≥ α -1.

No job arrives in future. We know that C ON ≥ T +2α ≥ 3α -1. An optimal scheme consists of scheduling J 1 at time 0, i.e., C OP T = 2α. Therefore,

C ON C OP T ≥ 3α -1 2α = 1 + α -1 2α > 1 + α -1 4α = φ.
Case 2. 0 ≤ T < α -1.

We know α -T > 1. We denote by p l 1,1 and p l 2,1 the respective parts of O 1,1 and O 2,1 that have been processed by time α -1, and by p r 1,1 and p r 2,l the respective parts of O 1,1 and O 2,1 that are processed after α -1. It follows that p l 1,1 + p l 2,1 ≤ α -1 -T , which also implies that none of the operations is completed at time α -1. By symmetry, without loss of generality, we assume that p l 1,1 ≥ p l 2,1 . Therefore, p l 2,1 ≤ α-1-T

2

. Considering p l 2,1 + p r 2,1 = α, we have p r 2,1 ≥ α+1+T 2 . We further generate job J 2 = (1, α) at time α -1. Since p r 2,1 ≥ α+1+T 2 and T ≥ 0, we have C ON ≥ (α -1) + α + p r 2,1 ≥ 5α-1 2 . An optimal schedule consists of processing O 2,1 at time 0 on M 2 followed by O 2,2 and processing O 1,2 at time α -1 on M 1 followed by O 1,1 . Thus, C OP T = 2α. It follows

C ON C OP T ≥ 5α -1 4α = φ.
The theorem follows.

An optimal algorithm

In this section, we show an optimal online algorithm SLICE-α with a competitive ratio which matches the lower bound φ. Based on SLICE Algorithm proposed in [START_REF] Vestjens | On-line machine scheduling[END_REF], we develop a new algorithm for the concerning problem. Since φ ≤ 5 4 , we will show that SLICE-α algorithm outperforms SLICE algorithm under the considered circumstances.

For a job instance, let σ denote the schedule obtained by algorithm SLICEα. We first recall some notations used in [START_REF] Angelelli | Semi-online scheduling on two uniform processors[END_REF]. For any time t, define the surviving job of a job J j to be the part of J j that still needs to be processed in σ after time t. Let p 1,j (t) and p 2,j (t) denote the (remaining) processing times of this surviving job J j at time t. We denote by S(t) the set of surviving jobs at time t. We denote by P 1 (t) the total processing times of M 1 operations in S(t), i.e., P 1 (t) = Jj ∈S(t) p 1,j (t), by P 2 (t) the total processing times of M 2 operations in S(t), i.e., P 2 (t) = Jj ∈S(t) p 2,j (t). We use L(t) to denote the total processing time of the largest job J k in S(t), i.e., L(t) = p 1,k (t) + p 2,k (t) = max Jj ∈S(t) {p 1,j (t) + p 2,j (t)}. We also say that J k determines L(t). Note that, given S(t), if no more jobs are released after time t, then the optimal makespan is t + max{P 1 (t), P 2 (t), L(t)} according to Lemma 20.

Algorithm SLICE-α works as follows.

Step 1: Wait until a release time r j of job J j , compute P 1 (r j ) , P 2 (r j ) and L(r j ) (If all jobs have been scheduled, output the schedule).

Step 2: If L(r j ) > max{P 1 (r j ), P 2 (r j )}, do the following until a new job is released (and go to Step 1).

Step 2.1: If J j determines L(r j ), do the following.

Step 2.1.1: At time r j process O 1,j until time r j +min{p 1,j , (φ-1)(p 1,j +p 2,j )} on M 1 .

Step 2.1.2: if p 2,j > min{p 1,j , (φ -1)(p 1,j + p 2,j )}, process O 2,j until time r j + p 2,j on M 2 .

Step 2.1.3: Processing the remaining portion of O 1,j on M 1 , which is followed by the remaining portion of O 2,j on M 2 .

Step 2.2: If another job J l determines L(r j ), then maintain the schedule for J l determined at the previous release time.

Step 2.3: Process the other jobs in S(r j ) on both machines as much as possible, and preempt if necessary.

Step 3: If L(r j ) ≤ max{P 1 (r j ), P 2 (r j )}, do the following schedule S until a new job is released (and go to Step 1). Construct an optimal schedule S for the jobs in S(r j ), satisfying the extra condition that at the beginning both machines are busy and in the remaining part only one machine is busy. This can easily be done according to Lemma 20, and by preempting a few jobs if necessary.

The intuitive idea behind algorithm SLICE-α is similar to that of algorithm SLICE. At time r j , a busiest slice of an optimal schedule for all jobs in S(r j ) is assigned into the interval [r j , r j+1 ]. At time r j , if the largest surviving job determines the makespan of the optimal schedule for all jobs in S(r j ), this slice is scheduled in such a way that the two operations of the largest surviving job are reduced in a proper amount related to their processing times. The algorithm tries to remain the currently largest job to be largest one at the next release time r j+1 , except for possibly J j+1 . If the total processing time on one machine determines the makespan, the algorithm keeps both machines busy during [r j , r j+1 ] as long as possible.

In order to prove that algorithm SLICE-α is φ-competitive by contradiction, we assume that there exists a smallest counterexample, denoted by I, which consists of a minimum number of jobs. For this smallest counterexample I, the competitive ratio of algorithm SLICE-α is greater than φ. This idea was used in [START_REF] Vestjens | On-line machine scheduling[END_REF] to prove that SLICE algorithm is 5/4-competitive. We first show several properties of this smallest counterexample. Then we will derive a contradiction to the existence of such a counterexample. We use σ and π to denote the schedule obtained by algorithm SLICE-α and an optimal schedule for this smallest counterexample I, respectively. Thus, C max (σ) and C max (π) denote the makespan obtained by SLICE-α and that of an optimal schedule for I, respectively.

Lemma 21

In σ, there is no simultaneous idle time on both machines before time C max (σ).

Proof. By contradiction. Suppose that there exists simultaneous idle time on both machines before C max (σ). Deleting all jobs scheduled before this idle time neither decreases C max (σ) nor increases C OP T (π). This contradicts the minimality of I. Therefore, the lemma follows.

Furthermore, if we modify the smallest counterexample I by decreasing all release times such that the first job arrives (or is released) at time 0, the modified instance is a smallest counterexample too. Because this modification does not Since at time r j , the algorithm executes Step 2 and the surviving job J l = (p 1,l (r j ), p 2,l (r j )) is the largest surviving job. Then we have p 1,l (r j ) + p 2,l (r j ) > max{P 1 (r j ), P 2 (r j )}. Together with inequality (8.1), r j-1 + max{P 1 (r j-1 ), P 2 (r j-1 )} > r j + max{P 1 (r j ), P 2 (r j )}.

It follows that max{P 1 (r j-1 ), P 2 (r j-1 )} -(r jr j-1 ) > max{P 1 (r j ), P 2 (r j )}.

(8.2)

We further consider two possible cases. Case 1. P 1 (r j-1 ) ≥ P 2 (r j-1 ). By Lemma 20 and the fact that there is no idle time on M 2 throughout [0, r k ], we know M 1 is busy throughout [r j-1 , r j ]. This implies that P 1 (r j-1 ) -P 1 (r j ) = r jr j-1 .

(8.3)

Consider inequality (8.2), we have that P 1 (r j-1 ) > r jr j-1 + max{P 1 (r j ), P 2 (r j )} ≥ r jr j-1 + P 1 (r j ).

This contradicts to inequality (8.3). Case 2. P 1 (r j-1 ) < P 2 (r j-1 ). Since there is no idle time on M 2 throughout [0, r k ], we know M 2 is busy throughout [r j-1 , r j ]. This implies that P 2 (r j-1 ) -P 2 (r j ) = r jr j-1 .

(8.4)

Consider inequality (8.2), we have that P 2 (r j-1 ) > r jr j-1 + max{P 1 (r j ), P 2 (r j )} ≥ r jr j-1 + P 2 (r j ).

This contradicts to inequality (8.4). Therefore, the lemma follows.

Lemma 26

In σ, J l cannot be completed before time r k+1 .

Proof. By contradiction. Suppose that J l is completed at time C l (σ) such that r k ≤ C l (σ) < r k+1 . By Step 2 of the algorithm, all jobs in S(r k ) are completed not later than C l (σ). There exists simultaneous idle time throughout [C l (σ), r k+1 ]. This contradiction to Lemma 21. The lemma holds.

Corollary 3 J l is processed thoughout [r l , r k+1 ], either on M 1 or on M 2 .

We denote by p l 1,l and p l 2,l the respective parts of O 1,l and O 2,l that have been processed by time r k+1 , and by p r 1,l and p r 2,l the respective parts that are processed after r k+1 . We know that Recall that φ = 5α-1 4α and α ≥ 1.

Lemma 27 p l 1,l > (φ -1)C max (π) and p r 2,l > (φ -1)C max (π).

Proof. Let P 2 be the total time spent by M 2 on processing jobs other than J l from time r k+1 onwards, i.e., P 2 = C max (σ)r k+1p r 2,l ,. Because I is a counterexample, we have φC max (π) < C max (σ) = r k+1 + p r 2,l + P 2 . (8.8)

By Corollary 2, we know that all jobs that contribute to P 2 are released at time r k+1 or later. Otherwise, M 2 could not be idle sometime during [r k , r k+1 ]. Therefore, r k+1 + P 2 ≤ C max (π). Together with inequality (8.8), we have φC max (π) ≤ C max (π) + p r 2,l .

It follows that p r 2,l > (φ -1)C max (π). Due to inequality (8.8) and equations (8.7) and (8.6), we obtain φC max (π) < p l 1,l + p l 2,l + r l + p r 2,l + P 2 = r l + p l 1,l + p 2,l + P 2 . (8.9)

Since J l and all jobs that contribute to P 2 are released at time r l or later, we have r l + p 2,l + P 2 ≤ C max (π). Together with inequality (8.9), we have φC max (π) < C max (π) + p l 1,l .

This implies p l 1,l > (φ -1)C max (π). This completes the proof.

Theorem 15 For O2|online, r j , 1 ≤ p •,j ≤ α|C max , algorithm SLICE-α is optimal with a competitive ratio φ.

Proof. By contradiction. We will show that there is a contradiction to Lemma 27 in order to prove that the smallest counterexample I does not exist. We only need to prove p l 1,l ≤ (φ -1)C max (π) or p r 2,l ≤ (φ -1)C max (π). Note that if min{p 1,l , p 2,l } ≤ (φ -1)(p 1,l + p 2,l ), then min{p l 1,l , p r 2,l } ≤ (φ -1)C max (π) and the theorem follows. Therefore, we assume that the processing times of both operations are at least φ -1 of the total processing time of the job, i.e., min{p 1,l , p 2,l } > (φ -1)(p 1,l + p 2,l ). (8.10) This implies min{p 1,l , (φ -1)(p 1,l + p 2,l )} = (φ -1)(p 1,l + p 2,l ). (8.11) We know that if p l 1,l ≤ (φ -1)C max (π), the theorem follows. So we suppose that p l 1,l > (φ -1)C max (π). It follows that p l 1,l > (φ -1)(p 1,l + p 2,l ). (8.12)

By Step 2 and Lemma 25, we know that J l was first processed on M 1 from time r l . Due to inequality (8.10) and equation (8.11), we know that p 2,l > (φ -1)(p 1,l +p 2,l ) = min{p 1,l , (φ-1)(p 1,l +p 2,l )}. Considering Step 2 of the algorithm, this inequality means that O 2,l is processed sometime during [r l , r k+1 ]. By Step 2 of the algorithm and equalition (8.11), we know that J l must be processed on M 1 at time r k+1 . Otherwise, p l 1,l = (φ -1)(p 1,l + p 2,l ) and this contradicts to inequality (8.12).

By inequality (8.12) and Step 2 of the algorithm, we know that at least a portion p 2,l -(φ -1)(p 1,l + p 2,l ) of O 2,l has been processed, i.e., p l 2,l ≥ p 2,l -(φ -1)(p 1,l + p 2,l ). Together with equation (8.6), we obtain p r 2,l = p 2,lp l 2,l ≤ (φ -1)(p 1,l + p 2,l ) ≤ (φ -1)C max (π).

This completes the proof.

Remark 12 When α → ∞, we have φ = 5/4 which is the competitive ratio of algorithm SLICE proposed in [START_REF] Vestjens | On-line machine scheduling[END_REF].

Remark 13 φ = 1 when α = 1.

Chapter 9

Conclusion

The main topic of this thesis has been the evaluation of online algorithms for machine scheduling problems. We used the concept of competitive ratio to measure the performance of online algorithms. For each minimization problem, we gave a lower bound of competitive ratio to establish a bound below which there exists no online algorithm. In contrast, for the maximization problem, we showed an upper bound of competitive ratio to construct a bound over which there exists no online algorithm. By proving that the competitive ratio of an online algorithm matches the lower bound, we showed that the algorithm is optimal. This method has been commonly used in the research of online algorithm.

In this chapter, we generally summarize what we learned from studying online scheduling problems.

Approximation ratio and competitive ratio

For offline scheduling problems, the number of jobs are finite. By enumerating all possible job sequences, we can obtain an optimal solution. Since enumeration method requires a lot of time, it is impractical. Polynomial approximation algorithms are developed due to this reason.

Approximation algorithms are algorithms used to find approximate solutions to optimization problems. Approximation algorithms are often associated with NP-hard problems; since it is unlikely that there can ever be efficient polynomial time exact algorithms solving NP-hard problems, one settles for polynomial time suboptimal solutions. Unlike heuristics, which usually only find reasonably good solutions reasonably fast, one wants provable solution quality and provable run time bounds. Ideally, the approximation is optimal up to a small constant factor. Approximation algorithms are increasingly being used for problems where exact polynomial-time algorithms are known but are too expensive due to the input size.

Similarity. The performance of an approximation algorithm is measured by its approximative ratio. Similarly, the performance of an online algorithm is measured by its competitive ratio. The definitions of two ratios are similar. They are all worst-case analysis. Usually, online algorithms are polynomial as approximation algorithms.

Difference. The environment of the problem are different. An online algorithm makes decision without future information, while an approximation algorithm does with all information. The input size of job sequences are different; for an online problem, an job sequence can be infinite.

Getting a better online algorithm

First, develop some feeling for online algorithms by carefully considering the proof of the lower bound of competitive ratio. An online algorithm tries to avoid the worst-case. Note the threshold values which cause case-by-case discussion in the proof. Some times we can use the lower bound of competitive ratio to design an online algorithm.

Second, design an simple algorithm with an assumption that no new job arrive any more. Such an algorithm makes its decision purely on the basis of all available information, disregarding any possible event in the future.

Third, consider waiting strategy. This means that postponing the decision to avoid the decision too greedy. An greedy algorithm some times causes the performance drastically decreases.

Drawbacks of online scheduling problems

First, the more complex the machine environment is, the less results online algorithms have. For example, for the problem of online scheduling on two flow shop, there are scare results. Normally, an online algorithm cannot be too complex since the proof of competitive ratio could be dramatically difficult. This reason causes the limited usage of online algorithms.

Second, the input sequence of online problem could be infinite. This yields that one cannot firstly consider a simple case with several jobs in order to attack the difficult case with infinite jobs.

Third, competitive analysis is worst-case analysis. Unlike average-case analysis, it gives a rather pessimistic impression. It often yields unrealistically high competitive ratios for typical instances. An algorithm which does not consider the worst case works well in practice.

Future works

Although a lot of results have been obtained in recent years, there exist numbers of unexploited areas and some unsolved problems.

As we all know, when the machine environment gets complicated, the results of online algorithms get scare. In a decade, there are less results about online scheduling on open shop, flow shop and job shop. Considering this situation, the following problems are my future works.

3. 1

 1 Structure of a counterexample . . . . . . . . . . . . . . . . . . . . 3.2 Structure of a smaller counterexample . . . . . . . . . . . . . . . 3.3 Structure of the smallest counterexample I . . . . . . . . . . . . iii Chapter 1

Figure 3 . 1 :

 31 Figure 3.1: Structure of a counterexample

Figure 3 . 2 :

 32 Figure 3.2: Structure of a smaller counterexample

. 22 )

 22 From equality(3.4), inequalities (3.5), (3.21) and(3.22) and Lemma 1, we have

. 23 )

 23 From equation(3.4), inequalities (3.11), (3.21) and (3.23), and Lemma 1, it follows that,

. 26 )

 26 From equalities (3.4) and (3.25) and inequality(3.26), it follows that

Case 1 . 2 . 2 . 1 :

 1221 r k ≤ S i (σ). From inequality (3.21) and equality (3.27), we have S i (σ)+p i ≥ r k +(ϕ-1)p k . Therefore, S i (σ) + p i + p k ≥ r k + ϕp k . If S k (σ) = r k + (ϕ -1)p k , from equality (3.4) and inequality (3.26), we have

  [START_REF] Graham | Bounds for certain multiprocessor anomalies[END_REF] and that L max (π) > p 0 + p k .(3.41)From inequalities (3.39) and (3.40), we haveL max (σ) -L max (π) ≤ S(B ) + p(B k (σ))p i ≤ S(B ) + p(B k (σ)). (3.42)Since S(B ) = min{(ϕ -1)p 0 , r 1 }, we haveS(B ) ≤ (ϕ -1)p 0 . (3.43) From inequalities (3.29), (3.41), (3.42) and (3.43), it follows that

. 51 )

 51 Since I is a counterexample, we must have S k (σ) > (ϕ -1)p k . (Note that r k = 0.) This implies that the algorithm must run Step 3.1 at least once. Let T be the starting time of the first job completed after time (ϕ -1)p k . Let Q denote the set of jobs processed from time T to time S k (σ) in σ. So we know that T ≤ (ϕ -1)p k(3.52)

√ α 2 -α 2 + 1 (α ≥ 1 )

 2211 +4for the first problem and a lower bound ϕ = √ 4α+1+1 2

√ 4α+1+1 2 .Case 2 .

 22 Considering equation(7.4) and inequalities (7.3) and (7.5), it followsC H C * ≤ s (m-1) + p (m-1) + p (m) r (m) + p (m-1) < 1 + p (m) s (m-1) + p (m-1)In an optimal schedule, J (m) and J (m-1) are in different batches. It follows that C * ≥ r (m-1) + p (m-1) + p (m) . Considering equations (7.4) and (7.3), we haveC H C * ≤ s (m-1) + p (m-1) + p (m) r (m-1) + p (m-1) + p (m) = ϕ(r (m-1) + p (m-1) ) + p (m)r (m-1) + p (m-1) + p (m) < ϕ.

p l 1 ,l + p r 1 ,l = p 1

 111 + p l 2,l = r k+1r l .(8.7)

Problem 1 : 2 : 3 :

 123 Design a better algorithm for online scheduling on two-machine flow shop. Problem Establish a lower bound and an upper bound for online scheduling on m-machine flow shop and open shop. Problem Consider batch-machine environment in flow shop and open shop scheduling problems.

  ) is the only available job, then wait (or keep idle) until a new job arrives or until time r pmax(t) + (ϕ -1)p pmax(t) , whichever happens first;

otherwise, If t + p(U (t)) > r pmax(t) + ϕp pmax(t) , (3.1) If q qmax(t) > (ϕ -1)p pmax(t) , schedule J qmax(t) ; (3.2) otherwise, schedule J pmax(t) ; else, (3.3) If q max (t) = p max (t), then schedule J qmax(t) ; (3.4) otherwise, schedule the job with the second largest delivery time, if any. Step 4: Go to Step 1.

  An optimal solution can assign J 1 to M s and J 2 to M 1 . Therefore, C OP T = 1 andC ON COP T ≥ 1 + 1 s > ϕ. , J 2 , J 3 to M s and J 4 to M 1 . It follows C OP T = 2 + 1 s . Since s > 1, J 4 is scheduled on M s . It follows C ON ≥ 1 s

	C ON COP T ≥ s + 1 ≥ ϕ. s , 1). Thus, C ON ≥ 1 + s + 2 + 1 Case 2. J 1 is assigned to M s . We further generate J 2 = (1, 2). Case 2.1. J 2 is scheduled on M s . It follows C ON ≥ 1 s (s + 1) = 1 + 1 We further generate J 3 = (s, 2). Case 2.2.1. J 3 is assigned to M 1 . Let J 4 = (2+ 1 s = 3+s + 1 s . An optimal schedule can assign J 1 C ON C OP T ≥ 3 + s + 1 s 2 + 1 s = 1 + s(s + 1) 2s + 1 > ϕ. s . Case 2.2. J 2 is scheduled on M 1 . Case 2.2.2. J 3 is assigned to M s . Then we generate J 4 = (2 + 1 s , 2). Case 2.2.2.1.

  follows C ON /C OP T ≤ ϕ by Lemma 14.

	Case 2.2.1: M π 2 > (s + 1)M π 1 . It follows C ON = M π 2 . Considering inequality (5.10) and equation (5.14), it
	follows that
	Case 2.2: M 1 denotes M s .
	Considering jobs J x and J y , we have
		M y 1 +	p y s	> (s + 1)M y 2 ,	(5.10)
	M y 1 +	B s	+	p x s	> (s + 1) (M y 2 + P y ) .	(5.11)
	Combining M θ 2 > (s + 1)M θ 1 with Step 5, the reassignment consists of
	shifting J y from M 1 to M s . Before reassignment,
	M θ 1 = M y 1 +	B s	+	A s	,		M θ 2 = M y 2 + p y + p x .	(5.12)
	Since M θ 2 > (s + 1)M θ 1 ,
	M y 2 + p y + p x > (s + 1) M y 1 +	B s	+	A s	.	(5.13)
	After reassignment,
	M π 1 = M y 1 +	B s	+	A s	+	p y s	,	M π 2 = M y 2 + p x .	(5.14)

and the theorem follows.

Acknowledgements

Again, there is a contradiction. Case 2.3. 5 ≤ α < 6. In this subcase, ϕ = 4+α 6 and thus

There is a contradiction to the assumption.

According to the analysis in Cases 1 and 2, the theorem follows.

Online scheduling on 2 machines with the total processing time

In this section, we further know jobs' total processing time in advance. We also study the problem of online scheduling on 2 machines with GoS and bounded processing times.

Problem definitions and notations

We are given 2 machines with speed of 1 and jobs' total processing time Σ. Without loss of generality, we denote the machine that can provide both high and low GoSs by M 1 , and the other one that only provides low GoS by M 2 . We denote each job by J i = (p i , g i ), where p i is the processing time of J i and g i ∈ {1, 2} is the GoS of the job. g i = 1 if J i must be processed by M 1 and g i = 2 if it can be processed by either of the two machines. p i and g i are not known unless J i arrives. A sequence of jobs σ = {J 1 , J 2 , ..., J n } which arrive online have to be scheduled irrevocably on one of the two machines on their arrivals. Each job J i is presented immediately after J i-1 is scheduled. The schedule can be seen as a partition of job sequence σ into two subsequences, denoted by S 1 and S 2 , where S 1 and S 2 consist of jobs assigned to M 1 and M 2 , respectively. Note that Σ = t(S 1 ) + t(S 2 ). Let L 1 = t(S 1 ) = Ji∈S1 p i and L 2 = t(S 2 ) = Ji∈S2 p i denote the loads (or total processing times) of M 1 and M 2 , respectively. Hence, the makespan of one schedule is max{L 1 , L 2 }. The online problem can be written as: Given σ, find S 1 and S 2 to minimize max{L 1 , L 2 }.

Let C S-ON and C OP T denote the makespan of online algorithm and offline optimal algorithm (for short, offline algorithm), respectively.

Lower bounds of competitive ratio

In this section, we will show some lower bounds of competitive ratio of online algorithm considering difference values of α. If α = 1, online algorithms can reach the optimal makespan. I.e., one algorithm is optimal if it assigns the jobs as many as possible on M 2 when the difference of the loads of two machines is taking out J k and putting it at last position in I, we get a new instance I , i.e., I = {J 1 , ..., J k-1 , J k+1 , ..., J n , J k }. Note that for this new instance I , the performance of B-SUM-ONLINE algorithm does not become worse, by Step 4 of the algorithm. Now, we renew the indexes of jobs in I by their positions, i.e.,

Therefore, the theorem follows.

Proof. We discuss the two cases in the lemma.

The lemma follows. EX-RA algorithm is an extension from the RA algorithm proposed in [START_REF] Tan | Online scheduling with reassignment[END_REF]. Before describing EX-RA, we introduce some notations. Let L 2 1 and L 2 2 denote the workloads of M 1 and M s just after the first two jobs J 1 and J 2 (before the third job) have been scheduled, respectively. If there is only one job in the job sequence, we also use L 2 1 and L 2 2 to denote the workloads (of M 1 and M s after scheduling the only job). Let M 1 = max{L 2 1 , L 2 2 } denote higher workload machine just after scheduling the first two jobs (before scheduling the third job) and M 2 = min{L 2 1 , L 2 2 } denote the other one. Note that M 1 and M 2 are determined just after scheduling two jobs in the job sequence and in the following loops the machine which is denoted by M 1 (or M 2 ) does not change. For example, just after the first two jobs (before the third job) have been scheduled, if M s is the higher workload machine, M 1 denotes M s . When the following jobs arrive, M 1 always denotes M s . We define M i 1 and M i 2 to be M 1 and M 2 just before job J i (i ≥ 3) has been scheduled, respectively. We use s(M 1 ) to denote the speed of M 1 . I.e., if M 1 denotes M s , then s(M 1 ) = s. Let M θ 1 and M θ 2 denote the workloads of M 1 and M 2 after all jobs have been scheduled (just before reassignment), respectively. Let M π 1 and M π 2 denote the workloads of M 1 and M 2 after reassignment, respectively. It follows C ON = max{M π 1 , M π 2 }. EX-RA algorithm consists of two parts: assignment and reassignment. In assignment, the algorithm firstly assigns two jobs to different machines. Then it denote the higher workload machine with M 1 and the lower one with M 2 . It maintains the workload of M 1 not greater than (s + 1) times of the workload of M 2 . In reassignment, the EX-RA algorithm tries to maintain the workload of M 2 not greater than (s + 1) times of that of M 1 .

EX-RA algorithm works as follows:

Step 1: Assign the first two jobs to two different machines. Let M 1 = max{L 2 1 , L Chapter 6

M identical parallel machine model

We study a maximization problem: online scheduling on m identical machines to maximize the number of early jobs. The problem is online in the sense that all jobs arrive over time. Each job's characteristics, such as processing time and due date, become known at its arrival time. We consider the preemption-restart model, which means that preemption is allowed and once a job is restarted it loses all the progress that has been made on this job so far. If in some schedule a job is completed before or at its due date, then it is called early (or on time).

The objective is to maximize the number of early jobs. For m identical machines, we show that an upper bound of competitive ratio is 1-1 2m and prove that ECT (earliest completion time) algorithm is 1 2 -competitive.

Introduction

In this chapter, we consider the third model where jobs arrive over time. There are also three models for online scheduling where jobs arrive over time. The first one, called non-preemptive model, assumes that once a job is started on the machine, it must run to completion. The second one, named preemptionresume model, assume the currently processed job may be preempted at any moment in time, and it may be resumed at any later moment in time. The third one is preemption-restart model. It assumes that the currently processed job may be preempted at any moment in time. However, by preempting a job, all the progress that has been made on this job so far is lost. In this model, the finally constructed schedule is non-preemptive. In this paper, we focus on the preemption-restart model in the online setting where jobs arrive over time. Note that we investigate a maximization problem in this chapter. Correspondingly, the competitive ratio form changes. Sgall et al. [START_REF] Sgall | On-line scheduling[END_REF] gave a survey on online scheduling. There are many results in the non-preemptive and in the preemption-resume model. Shmoys et al. [START_REF] Shmoys | Scheduling parallel machines on-line[END_REF] introduced the preemption-restart model and presented several results for scheduling m parallel machines to minimize the makespan. They studied the minimization problems. Maximization problems are rarely researched in the online settings. Hoogeveen et al. [START_REF] Hoogeveen | On-line scheduling on a single machine: maximizing the number of early jobs[END_REF] studied the online scheduling on a single machine to maximize the number of early jobs in the preemption-restart model. They proved that the shortest remaining processing time(SRPT) rule yields an optimal online algorithm with competitive ratio 1 2 . Note that SRPT rule implies earliest completion time (ECT) rule. Our results in the paper are generalizations of his results.

The rest of this chapter is organized as follows. In section 2, we introduce some definitions and notations. In section 3, we show that 1 -1 2m is an upper bound of competitive ratio for all online algorithms. In section 4, we present an online algorithm ECT based on the earliest completion time (ECT) rule, and prove that it is 1 2 -competitive.

Problem definition and notations

We are given m identical machines. Without loss of generality, we denote them by M 1 , ..., M m , respectively. A sequence of jobs I = {J 1 , ..., J n } arrive over time. Each machine can process at most one job at a time. The model considered is a preemption-restart model. Preemption is allowed, and by preempting a job, all the progress that has been made on this job so far is lost. Each job has a due date. If job is completed before or at its due date, then it is called early (or on time). The objective is to maximize the number of early job. We introduce some definitions and notations as follows.

early job: a job is completed before or at its due date in some schedule. (The opposite is tardy job.) p j : the processing time of job J j . r j : the release time of job J j . d j : the due date of job J j . feasible schedule: a schedule of early jobs. current workload (of a machine): the total processing time of all jobs currently assigned to that machine.

Since the tardy jobs in a schedule cannot influence the objective value for this problem, we only consider the feasible schedule (omitting the tardy jobs). Thus, we use a feasible schedule to replace a schedule in the remainder.

At any time t, let p j denote the remaining processing time of job J j with r j ≤ t. From this definition, p j = p j it no machine processes J j immediately before time t. On the other hand, if one machine processes J j throughout some time interval [s, t], but J j is not processed immediately before time s, then p j = p j -(ts).

Upper bound of competitive ratio

In order to show the upper bound of competitive ratio for all online algorithms, we use the following lemma.

Lemma 15

In m identical machine scheduling problem, for every integer k ≥ 0 and for all real numbers r and d with r < d, there exists an adversary strategy S m = S m (k, r, d) with the following properties.

(1) S m creates (2k + 1)m jobs. The earliest release time of these jobs is r, and the latest due date of these jobs is d.

(2) There exists a feasible schedule in which all (2k +1)m jobs are early. In such a schedule, the machines are continuously busy throughout the interval [r, d].

(3) If u ∈ {0, 1, ..., m} machines are unavailable throughout the interval [r, d], the adversary strategy S m can prevent any online algorithm from scheduling more than (2k + 1)(mu) jobs to be early. [START_REF] Azar | On-line machine covering[END_REF] The adversary strategy S m can prevent any online algorithm from scheduling more than (2m -1)k + m jobs to be early. (i.e., the adversary strategy can force any online algorithm to have at least k tardy jobs.)

Proof. The proof is by induction on k. For k = 0, the adversary S m releases m jobs with processing time dr at time r. For k ≥ 1, the adversary S m proceeds as follows. Let L = d-r 8 , and note that d = r + 8L. The adversary releases 2m jobs J 1 , J 2 , ..., J 2m with processing times p i = 3L and p m+i = 4L for i = 1, 2, ..., m at time r. All these 2m jobs have due date d. Then the adversary waits until r + 2L.

Case 1. If at time r + 2L the online algorithm is processing at least one job J i for i ∈ {1, 2, ..., m} (i.e.,p i = 3L), then S m calls the sub-adversary S m (k -1, r + 4L, r + 5L). Case 2. Otherwise, S m calls the sub-adversary S m (k -1, r + 3L, r + 4L).

(1) The proof of Property [START_REF] Albers | Better bounds for online scheduling[END_REF].

When k = 0, Property (1) holds. Considering k ≥ 1. We assume that Property (1) follows for k -1. Our aim is to prove that Property (1) holds for k. Since S m creates 2m new jobs J 1 , J 2 , ..., J 2m together with the (2k -1)m jobs generated by the sub-adversary, Property (1) holds for k.

(2) The proof of Property (2).

To prove Property (2), we consider the following schedules with all jobs early. In case 1, we schedule jobs J 1 , J 2 , ..., J m at each of the m machines during the interval [r + 5L, d] respectively; we assign jobs J m+1 , J m+2 , ..., J 2m to all m machines during the interval [r, r + 4L], respectively. Then we process all jobs of the sub-adversary by induction. Similarly, in case 2, we schedule J 1 , J 2 , ..., J m at all m machines during the interval [r, r + 3L], respectively; we assign J m+1 , J m+2 , ..., J 2m to all m machines during the interval [r + 4L, d], respectively. Then we process all jobs of the sub-adversary by induction.

(3) The proof of Property (3). Assume that u ∈ {0, 1, ..., m} machines are unavailable throughout the interval [r, d]. We prove Property (3) by induction on k. For k = 0 Property (3) holds, i.e., S m can prevent any online algorithm from scheduling more than (mu) jobs to be early with the precondition that u machines are unavailable throughout the interval [r, d]. We assume that for k -1 (in k ≥ 1 case), Property (3) holds, i.e., considering the assumption that u machines are unavailable throughout the interval [r, d], S m (k -1, r, d) can prevent any online algorithm from scheduling more than (2k -1)(mu) jobs to be early. Our aim is to prove that Property (3) holds for k. Because the processing times of all 2m jobs released by S m , we know that mu machines can not schedule more than 2(mu) jobs. No matter how these 2m jobs are scheduled, at most m machines have a common available interval [r + 3L, r + 4L] or [r + 4L, r + 5L].

In case 1, by assumption that S m can prevent any online algorithm from scheduling more than (2k -1)(m-u) jobs to be early with the precondition that u machines are unavailable, Property (3) holds, since the online algorithm can schedule at most 2(mu) jobs (in 2m jobs) together with the (2k -1)(mu) jobs generated by the sub-adversary. In case 2, similarly, Property (3) holds.

Considering (2k + 1)(mu), the more machines are available, the more jobs the online algorithm can schedule to be early.

(4) The proof of Property ( 4). Now we show that Property (4) holds by induction on k. For k = 0, Property (4) holds because S m creates m jobs. We assume that for k -1 (in k ≥ 1 case), Property (4) holds, i.e., S m (k -1, r, d) can prevent any online algorithm from scheduling more than (2m -1)(k -1) + m jobs to be early. Our aim is to prove that Property (4) holds for k.

Firstly, we assume that the online algorithm schedules all 2m jobs J 1 , J 2 , ..., J 2m to be early. Then in case 1, there must be one job J j for j ∈ {m + 1, m + 2, ..., 2m} (i.e.,p j = 4L) which covers the interval [r+4L, r+5L] on one machine. That is to say, throughout the interval [r + 4L, r + 5L], at least one machine is unavailable. Then we calls sub-adversary S m = S m (k -1, r + 4L, r + 5L). By Property (3), throughout the interval [r + 4L, r + 5L] the online algorithm can schedule at most (2k -1)(m -1) jobs to be early. Therefore,

Property (4) holds.

Secondly, we assume that the online algorithm does not schedule all 2m jobs J 1 , J 2 , ...J 2m to be early, i.e., the online algorithm schedules at most 2m -1 jobs of these 2m jobs to be early. In case 1, if all m machines are available at interval [r + 4L, r + 5L], by assumption for k -1, the sub-adversary S m (k -1, r + 4L, r + 5L) can prevent any online algorithm from scheduling more than (2m -1)(k -1) + m jobs to be early in the interval [r + 4L, r + 5L]. That is to say, the online algorithm can schedule at most (2m -1)(k -1) + m jobs to be early in the interval [r + 4L, r + 5L]. Together with at most 2m -1 early jobs scheduled by the online algorithm, we know that (2m-1)+(2m-1)(k-1)+m = (2m -1)k + m. Property (4) follows. Otherwise, in Case 1, not all m machines are available at interval [r + 4L, r + 5L], i.e., u ≥ 1. By Property (3), we know that the sub-adversary S m (k -1, r + 4L, r + 5L) can prevent any online algorithm from scheduling more that (2k -1)(mu) jobs to be early in the interval [r + 4L, r + 5L]. Since u ≥ 1, we have (2k -1)(mu) ≤ (2k -1)(m -1). Together with at most 2m -1 early jobs scheduled by the online algorithm, we have

Property (4) follows. In case 2, similar to the proof of case 1, by changing the interval from [r + 4L, r + 5L] to [r + 3L, r + 4L], we show that Property (4) also holds.

Remark 10

The Lemma 2 in [START_REF] Angelelli | Semi-online scheduling on two uniform processors[END_REF] is a special case of Lemma 1 such that m = 1.

Theorem 11 For the online problem of scheduling m machines to maximize the number of early jobs, every online algorithm A has a competitive ratio ρ

Let C OP T and C ON denote the number of early jobs of an offline optimal algorithm (offline algorithm for short) and that of online algorithm, respectively. By Lemma 15, we have C OP T = (2k+1)m and C ON ≤ (2m-1)k+m. Therefore,

Chapter 8

Open shop model

This chapter deals with a two-machine open shop problem. The objective is to minimize the makespan. Jobs arrive over time. We study preemption-resume model, i.e., the currently processed job may be preempted at any moment in time, and it may be resumed at any later moment in time. Let p 1,j and p 2,j denote the processing time of job J j on machines M 1 and M 2 , respectively. Bounded processing times mean that 1 ≤ p i,j ≤ α (i = 1, 2) for each job J j , where α ≥ 1 is a constant number. We propose an optimal online algorithm with a competitive ratio 5α-1 4α .

Introduction

In this chapter, we consider the online model where jobs arrive over time. In reality, the processing time of a job could not be enormously large. So we focus on the problem with jobs' bounded processing times. In the literature, there are some results about (offline) shop scheduling problems [START_REF] Pinedo | Scheduling: Theory, Algorithms, and Systems[END_REF][START_REF] Brucker | Scheduling algorithms[END_REF]. This chapter concerns about online shop scheduling problem. Chen et al. [START_REF] Chen | On-line scheduling of small open shops[END_REF] investigated the problem of on-line scheduling open shops of two and three machines to minimize the makespan. They studied the first online model where jobs arrive one by one. They proposed a 1.848-competitive algorithm for the non-preemptive scheduling problem of two machines and showed a lower bound of 1.754. Then they developed a (27/19)-competitive algorithm for the preemptive scheduling problem of three machines. A.P.A. Vestjens [START_REF] Vestjens | On-line machine scheduling[END_REF] addressed the online two-machine open shop scheduling problem. They considered the third model where jobs arrive over time. They proposed an optimal algorithm with a competitive ratio 3/2 for non-preemptive situation. Moreover, they studied the preemptive-resume scenario, and presented a 5/4-competitive algorithm which was shown to be optimal later. Based on the results of Vestjens, we further consider the situation with jobs' bounded processing times, which is more practical. For instance, jobs' processing times are bounded in a interval [1, α] where α ≥ 1. The remainder of this chapter is organized as follows. Section 2 contains the problem definition, some notations and preliminaries. In section 3, we show a lower bound of competitive ratio 5α-1 4α . In section 4, we propose an algorithm SLICE-α and show that it is optimal with a competitive ratio 5α-1 4α .

Problem definition, notations and preliminaries

We are given two machines, denoted by M 1 and M 2 , and an job instance I = {J 1 , ..., J n }. Each job J j is released at time r j . We denote each job J j by an ordered pair (p 1,j , p 2,j ), where p 1,j and p 2,j are the processing times of two operations O 1,j and O 2,j on machines M 1 and M 2 . We study the open shop problem, i.e., job J j may be processed first on M 1 then on M 2 or vice versa; the decision maker may determine the routes. We study the preemption-resume model, which means that the currently processed job may be preempted at any moment in time, and it may be resumed at any later moment in time. Jobs arrive over time, i.e., each job's character, such as processing time, becomes known at its arrival. We assume that 1 ≤ p 1,j , p 2,j ≤ α, where α ≥ 1 is a constant number. Our objective is to minimize the makespan. Using three-field notation, the problem can be denoted by O2|online, r j , 1 ≤ p •,j ≤ α|C max . Let C max (σ) denote the makespan of the schedule σ obtained by an algorithm. For a set of jobs, say S ∈ I, let P 1 (S) = Jj ∈S p 1,j , P 2 (S) = Jj ∈S p 2,j and L(S) = max Jj ∈S {r j + p 1,j + p 2,j }. Let r(S) = min Jj ∈S r j . We define Z * = max S⊆I {r(S) + P 1 (S), r(S) + P 2 (S), L(S)}. Clearly, the minimum makespans of an optimal preemptive schedule and an optimal non-preemptive schedule π satisfy

We introduce a lemma which states some structural information of an optimal schedule. We will use these structural information to design algorithm SLICE-α and to prove the optimality of the algorithm.

Lemma 20 [START_REF] Gonzalez | Open shop scheduling to minimize finish time[END_REF] For any instance I of the two-machine open shop with all jobs being released at time 0, C max (π) ≥ C max ( ) ≥ Z * = max{P 1 (I), P 2 (I), L(I)}. Furthermore, the structure of any optimal schedule is as follows:

(1) If P 1 (I) ≥ max{P 2 (I), L(I)}, then M 1 is busy all the time.

(2) If P 2 (I) ≥ max{P 1 (I), L(I)}, then M 1 is busy all the time.

(3) If L(I) > max{P 1 (I), P 2 (I)}, then the job J j such that p 1,j + p 2,j = L(I) is processed all the time either on M 1 or on M 2 , and all other jobs are processed in the remaining available machine time.

A lower bound

In this section, we deal with the two-machine open shop problem with bounded processing times. We give the following lemma to show a lower bound of the competitive ratio.

Given a job instance I, let C ON and C OP T denote the makespan obtained by an online algorithm A ON and the makespan of an optimal (offline) schedule, respectively. Let φ = 5α-1 4α and we use this notation in the remainder for simplicity.

Theorem 14 For O2|online, r j , 1 ≤ p •j ≤ α|C max , there is no algorithm with a competitive ratio less than φ.

Proof. For any online algorithm A ON , we construct a special job instance I such that C ON /C OP T is as large as possible. At time 0, we give the first job decrease the value of C max (σ)/C max (π). Therefore, without loss of generality, we assume that the first job in I is released at time 0. By symmetry of two machines, without loss of generality, we assume that M 2 finishes last in σ.

Lemma 22

In σ, there exists idle time on M 2 .

Proof. By contradiction. Suppose that there is no idle time on M 2 . Since the first job arrives at time 0 and M 2 finishes last in σ, we know that σ is an optimal schedule. There is a contradiction and the lemma follows.

Let r k ≥ 0 be the last release time before the last idle time on M 2 finishes. We know that idle time exists at sometime during [r k , C max (σ)]. Let J k+1 be the following job of J k such that r k+1 > r k in I. We have the following lemma. Proof. By contradiction. Suppose that SLICE-α executes Step 3 (not Step 2) at time r k . Then the algorithm must create a schedule in which M 2 is contiguously busy until all jobs in S(r k ) are finished on this machine. By Corollary 2, all jobs in S(r k ) must finish earlier than r k+1 on M 2 . This implies that all jobs processed on M 2 after (or at) time r k+1 are released at time r k+1 or later. By Lemma 23, we have that σ is an optimal schedule. There is a contradiction. The lemma holds.

Let J l be the largest job in S(r k ) and hence determine L(r k ). We can observe that J l is the only job in S(r k ) that may still need processing on M 2 after time r k . The following lemma indicates that the surviving job of J l has been the largest job from its release time r l . Lemma 25 At any release time t such that r l ≤ t ≤ r k , SLICE-α executes Step 2 (not Step 3) and the surviving job of J l always determines L(t).

Proof. By induction. By Lemma 24, we know that at time r k the algorithm executes Step 2. By the definition of J l , we know that the surviving job of J l determines L(r k ). Assume that at release time r j such that r l < r j ≤ r k , the algorithm executes Step 2 and the surviving job of J l determines L(r j ). Therefore, at r j the algorithm must execute Step 2.2 since J l is released before r j . The execution of Step 2.2 implies that at the previous release time t j-1 , J l determines L(r j-1 ), i.e., L(r j-1 ) = p 1,l (r j-1 ) + p 2,l (r j-1 ). Therefore, we only need to show that at release time r j-1 , the algorithm also executes Step 2.

By contradiction. Suppose that at time r j-1 , the algorithm executes Step 3 (not Step 2). By Lemma 20, all jobs in S(r j-1 ), including the surviving job of J l at r j-1 must be scheduled in such a way that they are processed in a period of length max{P 1 (r j-1 ), P 2 (r j-1 )}. This implies that r j-1 + max{P 1 (r j-1 ), P 2 (r j-1 )} ≥ r j + p 1,l (r j ) + p 2,l (r j ).