Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Offline Scheduling of Preemptive Jobs to <s> Exact and approximate algorithms are presented for scheduling independent tasks in a multiprocessor environment in which the processors have different speeds. Dynamic programming type algorithms are presented which minimize finish time and weighted mean flow time on two processors. The generalization to m processors is direct. These algorithms have a worst-case complexity which is exponential in the number of tasks. Therefore approximation algorithms of low polynomial complexity are also obtained for the above problems. These algorithms are guaranteed to obtain solutions that are close to the optimal. For the case of minimizing mean flow time on m -processors an algorithm is given whose complexity is O( n log mn ). <s> BIB001 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Offline Scheduling of Preemptive Jobs to <s> Abstract In this paper we describe a fast parallel algorithm for preemptive scheduling of n independent jobs on m uniform machines. Each job has a processing requirement, and each machine processes jobs at a different rate. The goal of the scheduling algorithm is to find a schedule which minimizes the time at which the last job is completed. T. Gonzalez and S. Sahni have developed a sequential algorithm which solves this problem in O(n + m log m) time. We develop a parallel version of this algorithm for a Concurrent Read Exclusive Write (CREW) shared memory computer. The algorithm runs in O(log n + log3m) time using n processors. <s> BIB002 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Offline Scheduling of Preemptive Jobs to <s> Suppose that n jobs, each with a specified processing requirement and due date, are to be preemptively scheduled for processing by a number of parallel machines, with the objective of maximizing the number of jobs that are completed by their due dates. It is known that this scheduling problem is NP-hard, even for identical machines, if the number of machines is variable, that is, specified as part of the problem instance. However, if the machine environment consists of a fixed set of uniform machines, the problem can be solved in polynomial time. An O ( n 3 ) algorithm is presented for the special case of two uniform machines. The running time of this algorithm becomes O ( Wn 2 ), where W is the sum of the job weights, for the more general problem in which it is desired to minimize the weighted number of late jobs. A fully polynomial approximation scheme is also presented for the weighted case. <s> BIB003 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Offline Scheduling of Preemptive Jobs to <s> We consider the problem of scheduling n jobs without precedence constraints on m uniform machines (i.e., the machines are identical except for speed), with preemptions allowed at no cost. We are interested in generating the entire tradeoff curve of schedules which are Pareto-optimal (undominated) for the flowtime and makespan objectives. To achieve this, we first develop an O(mn) algorithm that produces a schedule with minimum flowtime, subject to a fixed makespan deadline. This algorithm alternates between the Shortest Processing Time on Fastest Machine (SPT-FM) rule and the Longest Remaining Processing Time on Fastest Machine (LRPT-FM) rule. We then investigate how the behavior of the algorithm changes as the deadline is varied parametrically. Our knowledge of the structure of optimal schedules allows us to characterize breakpoints on the (piecewise linear) tradeoff curve, and then to compute all of the O(mn) breakpoints in O(m 3 n) time. Our analysis yields various useful sensitivity results as a by-product. INFORMS Journal on Computing , ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499. <s> BIB004 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Offline Scheduling of Preemptive Jobs to <s> It is well known that for preemptive scheduling on uniform machines there exist polynomial time exact algorithms, whereas for nonpreemptive scheduling there are probably no such algorithms. However, it is not clear how many preemptions (in total, or per job) suffice in order to guarantee an optimal polynomial time algorithm. In this paper we investigate exactly this hardness gap, formalized as two variants of the classic preemptive scheduling problem. In generalized multiprocessor scheduling (GMS), we have job-wise or total bound on the number of preemptions throughout a feasible schedule. We need to find a schedule that satisfies the preemption constraints, such that the maximum job completion time is minimized. In minimum preemptions scheduling (MPS), the only feasible schedules are preemptive schedules with smallest possible makespan. The goal is to find a feasible schedule that minimizes the overall number of preemptions. Both problems are NP-hard, even for two machines and zero preemptions.For GMS, we develop polynomial time approximation schemes, distinguishing between the cases where the number of machines is fixed, or given as part of the input. For MPS, we derive matching lower and upper bounds on the number of preemptions required by any optimal schedule. <s> BIB005 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Offline Scheduling of Preemptive Jobs to <s> Consider n independent jobs and m uniform machines in parallel. Each job has a processing requirement and a deadline. All jobs are available for processing at time t e 0. Job j must complete its processing before or at its deadline and preemptions are allowed. A set of jobs is said to be feasible if there exists a schedule that meets all the deadlines. We present a polynomial-time algorithm that given a feasible set of jobs, constructs a schedule that minimizes the total completion time ∑Cj. In the classical α v β v γ scheduling notation, this problem is referred to as Qm v prmt, dj v ∑Cj. It is well known that a generalization of this problem with regard to its machine environment results in an NP-hard problem. <s> BIB006 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Offline Scheduling of Preemptive Jobs to <s> We consider the scheduling of orders in an environment with m uniform machines in parallel. Each order requests certain amounts of k different product types. Each product type can be produced by any one of the m machines. No setup is required if a machine switches over from one product type to another. Different product types intended for the same order can be produced at the same time (concurrently) on different machines. Each order is released at time zero and has a positive weight. Preemptions are allowed. The completion time of an order is the finish time of the product type that is completed last for that order. The objective is to minimize the total weighted completion time. We propose heuristics for the non-preemptive as well as the preemptive case and obtain worst case bounds that are a function of the number of machines as well as the differences in the speeds of the machines. Even though the worst-case bounds we showed for the two heuristics are not very tight, our experimental results show that they yield solutions that are very close to optimal. <s> BIB007
Minimize Makespan McCormic and Pinedo BIB004 have considered the uniform parallel machines scheduling problem with preemption at no cost. They have generated the entire tradeoff curve of schedules which are Pareto-optimal (undominated) for the flow time and makespan objectives. To achieve this, they first developed an O(mn) algorithm that produces a schedule with minimum flow time, subject to a fixed makespan deadline. This algorithm alternates between the Shortest Processing Time on Fastest Machine (SPT-FM) rule and the Longest Remaining Processing Time on Fastest Machine (LRPT-FM) rule. Their knowledge of the structure of optimal schedules allows them to characterize breakpoints on the tradeoff curve, and then to compute all of the O(mn) breakpoints in O(m 3 n) time. Martel BIB002 describes a fast parallel algorithm for preemptive scheduling of independent jobs on uniform machines to minimize the makepsan. Gonzalez and Sahni  have developed a sequential algorithm which solves this problem in O(n + m log m) time. Martel BIB002 has developed a parallel version of this algorithm for a concurrent Read Exclusive Write (CREW) shared memory computer. This algorithm runs in O(log n + log 3 m) time using n processors. Shachnai, Tamir and Woeginger BIB005 studied the problem of minimizing the makespan with preemption costs on a system of uniform machines scheduling. Pandelis  has considered the problem of scheduling independent jobs on uniform parallel machines. Each job has a deterministic processing time and a weight associated with it. In this research, the objective is to minimize the sum of the discounted flow time of the jobs. The author has shown that for scheduling on uniform machines, assigning the job with the shortest remaining time to the fastest available machine (SRPT-FM rule) is optimal in the case preemptive schedules. The author's straightforward extension of this result is that if jobs are assigned weights that satisfy a certain agreeability condition (shortest processing time corresponds to largest weight, second shortest processing time corresponds to second largest weight, and so on), the SRPT-FM rule minimizes discounted weighted flow time. Though the researchers have used Pareto-optimal planes and other heuristics, only limited researches are carried out in this category of scheduling problem. So, the researchers may concentrate on using the advanced algorithms to the problems with single as well as multiobjective function. Minimize Sum of Total Completion Times Gonzalez, Leung and Pinedo BIB006 have analyzed n independent jobs and m uniform machines in parallel. Each job has a processing time and a due date. Job j may complete its processing before or after its due date and preemptions are allowed. A set of jobs is said to be feasible if there exists a schedule that meets all the due dates. They presented a polynomial-time algorithm that given a feasible set of jobs, which constructs a schedule that minimizes the total completion time of the jobs. Leung, Li, Pinedo and Jiawei Zhang BIB007 researched the scheduling of orders in an environment with m uniform machines in parallel. Each order requests certain amounts of k different product types. Each product type can be produced by any one of the m machines. No setup is required if a machine switches over from one product type to another. Different product types intended for the same order can be produced at the same time (concurrently) on different machines. Each order is released at time zero and has a positive weight. The completion time of an order is the finish time of the product type that is completed last for that order. The objective of this research is to minimize the total weighted completion time of orders. They proposed heuristics for the non-preemptive as well as preemptive case and obtained worstcase bounds that are functions of the number of machines as well as the difference in the speeds of the machines. As discussed in the previous section, the indirect objective of this problem is to minimize the mean flow time. Since, this is less complex problem, when compared to the non-preemptive type, the researchers may try to develop mathematical models for different cases of the problem. In turn, the optimal solutions through a model for small or moderate size problems may be used for bench marking purpose while developing heuristics. Minimize Maximum Lateness Drozdowski, Blazewicz, Formanowicz, Kubiak and Schmidt  have studied the problem of scheduling n preemptive tasks with ready times and due-dates on m uniform processors available in q time windows for minimizing maximum lateness criterion. The problem is reduced to a sequence of network flow problems. The complexity of the algorithm is O(n+q) BIB001 (log n + log q + log m + log max{b i }), where b i is speed of the processor i. Only few researchers have concentrated on this problem. The researchers may extend the contributions made in the non-preemptive case to this problem. Minimize Number of Tardy Jobs Lawler and Martel BIB003 have considered the problem of scheduling n preemptive jobs on uniform parallel machines. In this research, they formed a schedule such that the number of tardy jobs is minimized. They presented an algorithm with the complexity of O(n 3 ) for the special case of two uniform machines. Also, they gave a fully polynomial scheme for the weighted case. A very few researches have been carried out in this problem. So, there is a scope for further work in this problem with the guidelines as given in the previous section.