Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Online Scheduling of Non-Preemptive Jobs to <s> Abstract : We study the problem of scheduling jobs on parallel machines in an on-line fashion, where the processing requirement of a job is not known until the job is completed. Despite this lack of knowledge of the future, we wish to schedule so as minimize the completion time of the entire set of jobs. In general, the performance of an on-line algorithm is measured by its competitive ratio: the worst case ratio of its performance to that of an optimal algorithm with total prior knowledge. We study two fundamental models for this problem, that of identical machines, where all the machines run at the same speed, and uniformly related machines, where the machine run at different speeds. Our results include: (1) Matching upper and lower bounds on the competitive ratio for the case of identical machines; (2) Upper and lower bounds that differ by a constant factor for uniformly related machines; (3) A lower bound for randomized algorithms for identical machines that nearly matches the deterministic upper bound; and (4) Several upper and lower bounds for variations on these models. <s> BIB001 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Online Scheduling of Non-Preemptive Jobs to <s> This paper considers the problem of on-line scheduling a set of independent jobs on m uniform machines (M1, M2,..., Mm) in which machine Mi's processing speed is si=1 (i=1,..., m-1) and sm=s >1. List scheduling [Y. Cho and S. Sahni, SIAM J. Comput., 9 (1980), pp. 91--103] guarantees a worst-case performance of $\frac{3m-1}{m+1} (m\ge 3)$ and $\frac{1+\sqrt 5}2 (m=2)$ for this problem. We prove that this worst-case bound cannot be improved for m=2 and m=3 and for every $m\ge 4,$ an algorithm with worst-case performance at most $\frac{3m-1}{m+1}-\e$ is presented when sm=2,$ where e is a fixed positive number, and then we improve the bound for general sm=s > 1. <s> BIB002 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Online Scheduling of Non-Preemptive Jobs to <s> We consider the problem of assigning a set of jobs to m parallel related machines so as to maximize the minimum load over the machines. This situation corresponds to a case that a system which consists of the m machines is alive (i.e. productive) only when all machines are alive, and the system should be maintained alive as long as possible. The above problem is called related machines covering problem and is different from the related machines scheduling problem in which the goal is to minimize the maximum load. Our main result is a polynomial approximation scheme for this covering problem. To the best of our knowledge the previous best approximation algorithm has a performance ratio of 2. Also, an approximation scheme for the special case of identical machines was given by [14]. <s> BIB003 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Online Scheduling of Non-Preemptive Jobs to <s> We consider the problem of on-line scheduling of jobs arriving one by one on uniformly related machines, with or without preemption. We prove a lower bound of 2, both with and without preemption, for randomized algorithms working for an arbitrary number of machines. For a constant number of machines we give new lower bounds for the preemptive case. <s> BIB004 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Online Scheduling of Non-Preemptive Jobs to <s> We investigate the problem of semi-on-line scheduling of jobs on two uniform machines where the order of jobs by their processing times is known as a priori. We propose an algorithm for any machine speed ratio s>=1. We also present a comprehensive lower bound, which is a piecewise function of s. The algorithm is optimal for the majority of [email protected]?[1,~). The total length of the intervals of s where the competitive ratio does not match the lower bound is less than 0.7784 and the biggest gap between them never exceeds 0.0521. <s> BIB005 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Online Scheduling of Non-Preemptive Jobs to <s> We consider the following non-preemptive semi-online scheduling problem. Jobs with non-increasing sizes arrive one by one to be scheduled on two uniformly related machines, with the goal of minimizing the makespan. We analyze both the optimal overall competitive ratio, and the optimal competitive ratio as a function of the speed ratio (q ? 1) between the two machines. We show that the greedy algorithm LPT has optimal competitive ratio 1/4(1 +?17) ? 1.28 overall, but does not have optimal competitive ratio for every value of q. We determine the intervals of q where LPT is an algorithm of optimal competitive ratio, and design different algorithms of optimal competitive ratio for the intervals where it fails to be the best algorithm. As a result, we give a tight analysis of the competitive ratio for every speed ratio. <s> BIB006 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Online Scheduling of Non-Preemptive Jobs to <s> In this paper, we consider an ordinal on-line scheduling problem. A sequence of n independent jobs has to be assigned non-preemptively to two uniformly related machines. We study two objectives which are maximizing the minimum machine completion time, and minimizing the lp, norm of the completion times. It is assumed that the values of the processing times of jobs are unknown at the time of assignment. However it is known in advance that the processing times of arriving jobs are sorted in a non-increasing order. We are asked to construct an assignment of all jobs to the machines at time zero, by utilizing only ordinal data rather than actual magnitudes of jobs. For the problem of maximizing the minimum completion time we first present a comprehensive lower bound on the competitive ratio, which is a piecewise function of machine speed ratio s. Then, we propose an algorithm which is optimal for any s ≥ 1. For minimizing the lp norm, we study the case of identical machines (s = 1) and present tight bounds as a function of p. <s> BIB007 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Online Scheduling of Non-Preemptive Jobs to <s> We consider the online scheduling problem with m - 1, m ≥ 2, uniform machines each with a processing speed of 1, and one machine with a speed of s, 1 ≤ s ≤ 2, to minimize the makespan. The well-known list scheduling (LS) algorithm has a worst-case bound of (3m - 1)/(m + 1) [Y. Cho, S. Sahni, Bounds for list schedules on uniform processors, SIAM J. Comput. 9 (1980) 91-103]. An algorithm with a better competitive ratio was proposed in [R. Li, L. Shi, An on-line algorithm for some uniform processor scheduling, SIAM J. Comput. 27 (1998) 414-422]. It has a worst-case bound of 2.8795 for a big m and s = 2. In this note we present a 2.45-competitive algorithm for m ≥ 4 and any s, 1 ≤ s ≤ 2. <s> BIB008 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Online Scheduling of Non-Preemptive Jobs to <s> In this paper we consider the problem of semi-online scheduling on two uniform processors, in the case where the total sum of the tasks is known in advance. Tasks arrive one at a time and have to be assigned to one of the two processors before the next one arrives. The assignment cannot be changed later. The objective is the minimization of the makespan. Assume that the speed of the fast processor is s, while the speed of the slow one is normalized to 1. As a function of s, we derive general lower bounds on the competitive ratio achievable with respect to offline optimum, and design on-line algorithms with guaranteed upper bound on their competitive ratio. The algorithms presented for s>=3 are optimal, as well as for s=1 and for [email protected][email protected]?1+32. <s> BIB009
Minimize Makespan Wein and Williamson BIB001 have studied the problem of scheduling jobs on parallel machines in an online fashion in which the processing requirement of a job is not known until that job is completed. For this problem, they scheduled jobs such that the makespan is minimized. They studied the following two models, viz. scheduling on identical parallel machines and scheduling on uniform parallel machines. Their results include the following. -Matching upper and lower bounds on the competitive ratio for the case of identical machines. -Upper and lower bounds that differ by a constant factor for uniformly related machines. -A lower bound for randomized algorithms for identical machines that nearly matches the deterministic upper bound. -Several upper and lower bounds for variations on these models. A study on establishing a lower bound for makespan in on-line scheduling on uniformly related machines was done by Epstien and Sgall BIB004 . They considered the problem of on-line scheduling of jobs one by one on uniformly related machines, with or without preemption. They proved a lower bound of 2, both with and without preemption for randomized algorithms working for an arbitrary number of machines. Tan and He BIB005 have investigated the semi-online scheduling problem with ordinal data on two uniform machines where the order of jobs by their processing times is known as priori. They presented a comprehensive lower bound which is a piecewise function of the speed ratio s. The algorithm gives optimal makespan for majority of s (1, ∞). In this paper, the total length of the intervals of s where the competitive ratio does not match the lower bound is less than 0.7784 and the biggest gap between them never exceeds 0.0521. Kontogiannis  has studied the problem of assigning unit size tasks to related machines when only limited online information is provided to each task. The author has proved that the missing information for an oblivious scheduler to perform almost optimally is the amount of tasks to be inserted into the system. In particular, the author provided an oblivious scheduler that only uses O(log log n) polls along with the additional information of the size of the input sequence, in order to achieve a constant competitive ratio. Finally, this oblivious scheduler is used in an adaptive scheduler that does not demand the knowledge of the input sequence and yet achieves almost the same performance. Epstein and Favrholdt BIB006 have considered non-preemptive semi-online scheduling problem in which jobs with non-increasing sizes arrive one by one which are to be scheduled on two uniformly related machines, with the goal of minimizing the makespan. They analyzed both the optimal overall competitive ratio and the optimal competitive ratio as a function of the speed ratio (s ≥ 1) between the two machines. They showed that the greedy algorithm LPT has optimal competitive ratio of ¼(1+√17) ≈ 1.28 overall, but does not have optimal competitive ratio for every value of s. They gave a tight analysis of the competitive ratio for every speed ratio. Cheng, Ng and Vladirmir Kotov BIB008 have researched the online scheduling problem with m-1, m ≥ 2, uniform machines each with a processing speed of 1 and one machine with a speed of s, 1 ≤ s ≤ 2, to minimize the makespan. The well known list scheduling (LS) algorithm has a worst-case bound of (3m-1)/(m+1) (Sahni and Cho,  ). An algorithm with a better competitive ratio was proposed by Li and Shi BIB002 . It has a worstcase bound of 2.8795 for large value of m and n = 2. In the note by Cheng, Ng and Vladirmir Kotov BIB008 , they presented an algorithm with a competitive ratio of 2.45 for m ≥ 4 and any s, 1 ≤ s ≤ 2. Angelelli, Speranza and Tuza BIB009 have considered the problem of online scheduling on two uniform processors where the total sum of the tasks is known in advance. In this research, tasks arrive one at a time and each task is to be assigned to one of the two processors before the next task arrives. The assignment can be changed later. The objective is the minimization of the makespan. By assuming s as the speed of the fast processor and 1 as the speed of the slow processor, they derived general lower bounds on the competitive ratio achievable with respect to offline optimum and designed on-line algorithms with guaranteed upper bound on their competitive ratio. The researchers have concentrated on the analysis of lower bound for the makespan of this problem as well as on the development of heuristics with different competitive ratios. In future, researchers may aim to develop algorithms which yield better competitive ratio. Maximize Minimum Completion Time (Machine Covering Problem) Azar and Epstein   have considered the problem of scheduling a sequence of jobs on m parallel machines such that the minimum load over the machines is maximized in an online environment. Such problem is called as machine covering problem. This situation corresponds to a case that a system consists of m machines. They have given several theorems for identical parallel machines as well as for related parallel machines along with proofs. It is well known that any on-line deterministic algorithm for identical machines has a competitive ratio of at least m. In contrast they designed an on-line randomized algorithm which is O(√m) competitive and a matching lower bound of √m for any online randomized algorithm. In the case where the jobs are polynomially related, they designed an optimal O(log m) competitive randomized algorithm and a matching tight lower bound for any on-line randomized algorithm. For related machines, they showed that there is no online algorithm, whose competitive ratio is a function of the number of machines. However for the case where the value of the optimal assignment is known in advance and for the case where jobs arrive in non-increasing order, they showed that the exact competitive ratio is m. Azar and Epstein BIB003 have developed a polynomial approximation scheme for the machine covering problem. They reported that the previous best approximation algorithm has a performance ratio of 2. They provided an approximation scheme for the related machines scheduling. Their algorithm can be adapted to provide a simpler approximation scheme for the related machines scheduling too. Tan, He and Epstein BIB007 have considered the nonpreemptive ordinal on-line scheduling of n independent jobs (p 1 , p 2 , p 3 , …p n ) on two uniform related machines. They have developed optimal algorithms for maximizing the minimum machine completion time and minimizing the l p norm of the completion times. They assumed that the values of the processing times of the jobs are unknown at the time of assignment. However, it is known in advance that processing times of arriving jobs are sorted in a non-increasing order. They have constructed an assignment of all jobs to the machines at time zero by utilizing only ordinal data rather than actual magnitudes of jobs. For the problem of maximizing the minimum completion time, they first presented a comprehensive lower bound on the competitive ratio which is a piecewise function of machine speed ratio s. Then they proposed an algorithm which is optimal for any s which is greater than or equal to 1. For minimizing the l p norm, they studied the case of identical machines (s = 1) and present tight bounds as a function of p. This is special class of problem. The researchers have concentrated on the development of algorithms with different competitive ratios. In future, researchers may aim to develop algorithms which yield better competitive ratio.