Received 18 February 2016; accepted 22 July 2016; published 25 July 2016
For the online scheduling on a system of m uniform parallel machines, denoted by, each machine has a speed, i.e., the time used for finishing a job with size p on is. Without loss of generality, we assume. Cho and Sahni  are the first to consider the on-line scheduling problem on m uniform machines. They showed that the LS algorithm for has competitive ratio not greater than. When and, they
proved that the algorithm LS has a competitive ratio and the bound is achieved when.
For, Epstein et al.  showed that LS has the competitive ratio and is an optimal online algorithm, where the speed ratio.
Cai and Yang  considered. Let and be two speed ratios. They showed that the algorithm LS is an optimal online algorithm when the speed ratios, where
and. Moreover, for the general speed ratios, they also presented an upper bound of the competitive ratio.
Aspnes et al.  are the first to try to design algorithms better than LS for. They presented a new algorithm that achieves the competitive ratio of 8 for the deterministic version, and 5.436 for its randomized variant. Later the previous competitive ratios are improved to 5.828 and 4.311, respectively, by Berman et al.  .
Li and Shi  proved that for LS is optimal when and and presented an online algorithm with a better competitive ratio than LS for. Besides, they also showed that the
bound could be improved when and. For and, Cheng et al.  proposed an algorithm with a competitive ratio not greater than 2.45.
A generalization of the Graham’s classical on-line scheduling problem on m identical machines was proposed by Li and Huang  -  . They describe the requests of all jobs in terms of order. For an order of the job, the scheduler is informed of a 2-tuple, where and represent the release time and the processing time of the job, respectively. The orders of request have no release time but appear on-line one by one at the very beginning time of the system. Whenever the request of an order is made, the scheduler has to assign a machine and a processing slot for it irrevocably without knowledge of any information of future job orders. In this on-line situation, the jobs’ release times are assumed to be arbitrary.
Our task is to allocate a sequence of jobs to the machines in an on-line fashion, while minimizing the maximum completion time of the machines. In the following of this paper, m parallel uniform machines which have speeds of respectively, are given. Let be any list of jobs, where job is given as order with the information of a release time and a processing size of.
The rest of the paper is organized as follows. In Section 2, some definitions are given. In Section 3, an algorithm U is addressed and its competitive ratio is analyzed.
2. Some Definitions
In this section we will give some definitions.
Definition 1. We have m parallel machines with speeds. Let be any list of jobs, where jobs arrives online one by one and each has a release time and a processing size of. Algorithm A is a heuristic algorithm. Let and be the makespan of algorithm A and the makespan of an optimal off-line algorithm respectively. We refer to
as the competitive ratio of algorithm A.
Definition 2. Suppose that is the current job to be scheduled with release time and size. We say that machine has an idle time interval for job, if there exists a time interval satisfying the following two conditions:
1) Machine is idle in interval and a job with release time is assigned on machine to start at time.
It is obvious that if machine has an idle time interval for job, then we can assign to machine in the idle interval.
In the following we consider m parallel uniform machines with speeds and a job list with information for each job, where and represent its release time and size, respectively. For convenience, we assume that the sequence of machine speeds is non-decreasing, i.e.,
3. Algorithm U and Its Performance
Now we present the algorithm U by use of the notations given in the former section in the following:
Step 0. (*start the first phase*)
Step 1. If there is a new job with release time and processing size given to the algorithm then go to Step 2. Otherwise stop.
Step 2. If there is a machine which has an idle time interval for job, then we assign to machine in the idle interval. Set and go to Step 1.
Step 3. Set. If then set, , Go to Step 1.
Step 4. (*start a new phase*)
Set, , and go to Step 3.
Now we begin to analyze the performance of algorithm U.
The following statement is obvious:
Lemma 1. Let be the stream of jobs scheduled in phase h and is the first job assigned in phase. Let be the largest load in an optimal schedule for job list. Then we have
Proof: If, let r be the fastest machine whose load does not exceed, i.e. . If there is no such machine, we set. If, then. It is
obvious that Hence we have
It means that can be assigned to the fastest machine in phase h. It is a contradiction to the fact that is the first job assigned in phase. Define, the set of machines with finishing time bigger than by the end of phase h. Since,. Denote by and the set of jobs assigned to machine by the on-line and the off-line algorithms, respectively. Since for any job the following inequalities hold
This implies that there exists a job () such that, i.e. there exists a job assigned by the on-line algorithm to a machine and assigned by the off-line algorithm to a slower machine.
By our assumptions, we have. Since, machine is at least as fast as machine, and thus. Since job was assigned before job and, we have
But this means that the on-line algorithm should have placed job on or a slower machine instead of, which is a contradiction. ¢
Theorem 2. Algorithm achieves a competitive ratio of 12.
Proof: Let denote the maximum load generated by jobs that were assigned during phase h; denote the last phase by. By the rules of our algorithm we have and
Hence the total height generated by the assignment is:
The claim of the theorem is trivially true if. For, phase h is started only if. In particular we have
Therefore we have
4. Concluding Remarks
In this paper, we consider on-line scheduling for jobs with arbitrary release times on uniform machines. An algorithm with the competitive ratio of 12 is given. It should be pointed out that more detailed consideration should be taken in order to improve the competitive ratio.
The authors would like to express their thanks to the National Natural Science Foundation of China for financially supporting under Grant No. 11471110 and No. 61271264.