Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Offline Scheduling of Non-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 Non-Preemptive Jobs to <s> The finishing time properties of several heuristic algorithms for scheduling n independent tasks on m nonidentical processors are studied. In particular, for m = 2 an n log n time-bounded algorithm is given which generates a schedule having a finishing time of at most (√5 + 1)/2 of the optimal finishing time. A simplified scheduling problem involving identical processors and restricted task sets is shown to be P-complete. However, the LPT algorithm applied to this problem yields schedules which are near optimal for large n . <s> BIB002 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Offline Scheduling of Non-Preemptive Jobs to <s> Abstract The nonpreemptive scheduling of a partially ordered set of tasks on a machine with m processors of different speeds is studied. Polynomial time algorithms are presented which benefit from selective non-use of slow processors. The performance of these heuristics is asymptotic to √ m times worse than optimal, whereas list schedules are unboundedly worse than optimal for any fixed value of m . The techniques of analyzing these schedules are used to obtain a bound on a large class of preemptive schedules. <s> BIB003 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Offline Scheduling of Non-Preemptive Jobs to <s> Abstract An integer goal programming algorithm is constructed to solve the parallel machine tardiness problem. In this problem, different machines are allowed to have different processing speeds on a job. This reflects the real-life situation that some machines may be older or of later design than others. In this paper the solution procedure is introduced beginning with the single machine problem and then extended to the general case of m machines. The computational complexity of this problem remains a major question. Currently, there is no polynomial time algorithm existing for this problem, nor a proof of NP-completeness. Due to the difficulty of this problem, future research will probably be concentrated on the development of approximate algorithms. Optimal solutions obtained from the integer goal program developed in this paper can serve as standards in evaluating the efficiency of approximate algorithms. <s> BIB004 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Offline Scheduling of Non-Preemptive Jobs to <s> We consider the problem of scheduling n jobs, each with a specific processing requirement, release time and due date on m uniform parallel machines. It is shown that a feasible schedule can be obtained by determining the maximum flow in a network, thus permitting the use of standard network flow codes. Using a specialized maximum flow procedure, the complexity reduces to Otn3 operations when t is the number of distinct machine types. Previous algorithms solve the feasibility problem in Om + log nm2n3 + n4 operations. In addition to the feasibility problem, we describe algorithms for the maximum lateness criterion. Here we develop a bound which compares even more favorably to the best previous bound. We also show how other criteria with respect to the amount of work completed on each job prior to its due date or the amount of work scheduled in each of a sequence of periods can be optimized by similar path augmenting techniques. <s> BIB005 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Offline Scheduling of Non-Preemptive Jobs to <s> Abstract A recent paper by Cheng analyzed the problem of simultaneous determination of a common due-date and a sequence of n jobs to minimize the maximum deviation of job completion time around the common due-date. It is assumed that all jobs are available at time zero and their processing times, t i 's, are known in advance. The analysis in Cheng used an LP formulation and duality results to prove the theorems. This note provides an alternate simpler proof for the same results. We also give some results for the case when splitting and preemption are allowed. A recent paper by Cheng [1] gives an optimal solution to the problem of setting a common due-date and sequence of n jobs on a single machine. All jobs are available at time zero and their processing times, t i 's, are known in advance. The objective is to determine the optimal common due-date value k ∗ , and the sequence ( σ ) to minimize the maximum deviation of job completion time about the common due-date. We here give a much simpler proof of the results derived in [1]. The notations used here are the same as in [1]. Let C [1] denote the completion time (decision variable) and t [i] denote the given processing time of a job in the i th position of sequence σ. <s> BIB006 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Offline Scheduling of Non-Preemptive Jobs to <s> We consider a class of problems of scheduling n jobs on m identical, uniform, or unrelated parallel machines with an objective of minimizing an additive criterion. We propose a decomposition approach for solving these problems exactly. The decomposition approach first formulates these problems as an integer program, and then reformulates the integer program, using Dantzig-Wolfe decomposition, as a set partitioning problem. Based on this set partitioning formulation, branch-and-bound exact solution algorithms can be designed for these problems. In such a branch-and-bound tree, each node is the linear relaxation problem of a set partitioning problem. This linear relaxation problem is solved by a column generation approach where each column represents a schedule on one machine and is generated by solving a single machine subproblem. Branching is conducted on variables in the original integer programming formulation instead of variables in the set partitioning formulation such that single machine subproblems are more tractable. We apply this decomposition approach to two particular problems: the total weighted completion time problem and the weighted number of tardy jobs problem. The computational results indicate that the decomposition approach is promising and capable of solving large problems. <s> BIB007 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Offline Scheduling of Non-Preemptive Jobs to <s> The problem of scheduling N jobs on M uniform parallel machines is studied. The objective is to minimize the mean tardiness or the weighted sum of tardiness with weights based on jobs, on periods or both. For the mean tardiness criteria in the preemptive case, this problem is NP-hard but good solutions can be calculated with a transportation problem algorithm. In the nonpreemptive case the problem is therefore NP-hard, except for the cases with equal job processing times or with job due dates equal to job processing times. No dominant heuristic is known in the general nonpreemptive case. The author has developed a heuristic to solve the nonpreemptive scheduling problem with unrelated job processing times. Initially, the algorithm calculates a basic solution. Next, it considers the interchanges of job subsets to equal processing time sum interchanging resources (i.e. a machine for a given period). This paper models the scheduling problem. It presents the heuristic and its result quality, solving 576 problems for 18 problem sizes. An application of school timetable scheduling illustrates the use of this heuristic. <s> BIB008 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Offline Scheduling of Non-Preemptive Jobs to <s> We present new approximation algorithms for the problem of scheduling precedence-constrained jobs on parallel machines that are uniformly related. That is, there arenjobs andmmachines; each jobjrequirespjunits of processing, and is to be processed on one machine without interruption; if it is assigned to machinei, which runs at a given speedsi, it takespj/sitime units. There also is a partial order ? on the jobs, wherej?kimplies that jobkmay not start processing until jobjhas been completed. We consider two objective functions:Cmax=maxjCj, whereCjdenotes the completion time of jobj, and ?jwjCj, wherewjis a weight that is given for each jobj. For the first objective, the best previously known result is anOm-approximation algorithm, which was shown by Jaffe more than 15 years ago. We give anO(logm)-approximation algorithm. We also show how to extend this result to obtain anO(logm)-approximation algorithm for the second objective, albeit with a somewhat larger constant. These results also extend to settings in which each jobjhas a release daterjbefore which the job may not begin processing. In addition, we obtain stronger performance guarantees if there are a limited number of distinct speeds. Our results are based on a new linear programming-based technique for estimating the speed at which each job should be run, and a variant of the list scheduling algorithm of Graham that can exploit this additional information. <s> BIB009 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Offline Scheduling of Non-Preemptive Jobs to <s> Abstract For the problem of scheduling identical jobs on a set of uniform parallel machines with random processing times, methods are given for optimizing the expected sum of weighted completion times and the probability of meeting a common due date. <s> BIB010 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Offline Scheduling of Non-Preemptive Jobs to <s> We consider the NP-hard problem of scheduling jobs on identical parallel machines to minimize total tardiness. We present properties that characterize the structure of an optimal schedule. We propose a branch and bound algorithm that incorporates the properties along with an efficient lower bounding scheme. We find that optimal solutions can be obtained in reasonable times for problems with up to 15 jobs. In the last part of the study we extend the results to uniform parallel machines. <s> BIB011 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Offline Scheduling of Non-Preemptive Jobs to <s> Abstract We consider the problem of scheduling n identical jobs with unequal ready times on m parallel uniform machines to minimize the maximum lateness. This paper develops a branch-and-bound procedure that optimally solves the problem and introduces six simple single-pass heuristic procedures that approximate the optimal solution. The branch-and-bound procedure uses the heuristics to establish an initial upper bound. On sample problems, the branch-and-bound procedure in most instances was able to find an optimal solution within 100,000 iterations with n ≤80 and m ≤3. For larger values of m , the heuristics provided approximate solutions close to the optimal values. <s> BIB012 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Offline Scheduling of Non-Preemptive Jobs to <s> We consider the NP-hard problem of scheduling jobs on identical parallel machines to minimize total weighted flow time. We discuss the properties that characterize the structure of an optimal solution, present a lower bound and propose a branch and bound algorithm. The algorithm is superior to prior methods presented in the literature. We also extend the algorithm to uniform parallel machines and solve medium-sized problem instances. <s> BIB013 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Offline Scheduling of Non-Preemptive Jobs to <s> We consider the uniform parallel machine scheduling problem with the objective of minimizing maximum lateness. We show that an extension of the EDD rule to a uniform parallel machine setting yields a maximum lateness value which does not exceed the optimal value by more than p"m"a"x, where p"m"a"x is the maximum job processing time. <s> BIB014 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Offline Scheduling of Non-Preemptive Jobs to <s> This paper deals with the problem of scheduling jobs in uniform parallel machines with sequence-dependent setup times in order to minimize the total tardiness relative to job due dates. We propose GRASP versions that incorporate adaptive memory principles for solving this problem. Long-term memory is used in the construction of an initial solution and in a post-optimization procedure which connects high quality local optima by means of path relinking. Computational tests are carried out on a set of benchmark instances and the proposed GRASP versions are compared with heuristic methods from the literature. <s> BIB015 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Offline Scheduling of Non-Preemptive Jobs to <s> This research investigates the problem of scheduling jobs on a set of parallel machines where the speed of the machines depends on the allocation of a secondary resource. The secondary resource is fixed in quantity and is to be allocated to the machines at the start of the schedule. The scheduling objective is to minimize the number of tardy jobs. Two versions of the problem are analyzed. The first version assumes that the jobs are pre-assigned to the machines, while the second one takes into consideration the task of assigning jobs to the machines. The paper proposes an Integer Programming formulation to solve the first case and a set of heuristics for the second. <s> BIB016 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Offline Scheduling of Non-Preemptive Jobs to <s> The classical weighted minsum scheduling and due-date assignment problem (with earliness, tardiness and due-date costs) was shown to be polynomially solvable on a single machine, more than two decades ago. Later, it was shown to have a polynomial time solution in the case of identical processing time jobs and parallel identical machines. We extend the latter setting to parallel uniform machines. We show that the two-machine case is solved in constant time. Furthermore, the problem remains polynomially solvable for a given (fixed) number of machines. <s> BIB017
Minimize Makespan Horowitz and Sahni BIB001 first presented dynamic programming algorithms for scheduling independent tasks in a multiprocessor environment in which the processors have different speeds. In this research, the objective is minimize the finish time (makespan) and weighted mean flow time on two processors. These algorithms have worst-case complexity functions which are exponential in the number of tasks. Hence, they next presented approximation algorithms of low polynomial complexity for the above problem. Ibarra and Kim BIB002 have developed a heuristic for scheduling independent tasks on nonidentical processors. In their study, particularly, for m = 2, an n log n time-bounded algorithm is given which Offline scheduling of preemptive jobs to minimize the number of tardy jobs Offline scheduling Preemptive jobs This category minimizes the number of tardy jobs in the schedule. Minimize Sum of Total Completion Times Dessouky and Marcellus BIB010 have developed methods to optimize the expected sum of weighted completion times and the probability of meeting a common due date while scheduling identical jobs on a set of uniform parallel machines with random processing times. Meral Azizoglu and Omer Kirca BIB013 have considered the NP-hard problem of scheduling jobs on identical parallel machines to minimize total weighted flow time. They also discussed the properties that characterize the structure of an optimal solution, presented a lower bound and proposed a branch and bound algorithm. They also extended the algorithm to uniform parallel machines. Zhi-Long Chen and Warren B. Powell BIB007 have considered a class of problems of scheduling n jobs on m identical, uniform, or unrelated parallel machines with an objective of minimizing an additive criterion, viz. the total weighted completion times of the jobs. They proposed a decomposition algorithm for solving there problems exactly. The decomposition algorithm first formulates these problems as an integer program, and then reformulates the integer program, using Dantzig-Wolfe decomposition, as a set partitioning problem. The  Minimize Total Earliness/Tardiness Kun-si Lin BIB004 developed an integer programming algorithm to solve the parallel machines problem with the objective of minimizing total tardiness in which different machines are allowed to have different processing speeds on a job. In this work, a solution procedure is introduced beginning with the single machine problem and then extended to the general case of m machines. Alain Guinet BIB008 considered the problem of scheduling n jobs on m uniform parallel machines with the objective of minimizing the mean tardiness or the weighted sum of tardiness with weights based on jobs, periods or both. For the mean tardiness criterion in the non-preemptive case, the problem is NP-hard, except for the cases with equal job processing times or with job due dates equal to job processing times. They have developed a heuristic to solve the non-preemptive scheduling problem with unrelated job processing times. The heuristic was experimented with 576 problems which consist of 18 problem sizes. Meral Azizoglu and Omer Kirca BIB011 have considered the NP-hard problem of scheduling jobs on identical parallel machines to minimize the total tardiness. They presented the properties that characterize the structure of an optimal schedule. They proposed a branch and bound algorithm that incorporates the properties along with an efficient lower bounding scheme. They found that optimal solutions can be obtained in reasonable times for problems with size up to 15 jobs. In the last part of the study, they extended the results to uniform parallel machines. Naofumi, Shunji and Mitsuhiko  have considered a class of problems to minimize total tardiness on uniform parallel machines with human resource constraints, in which each machine requires an operator to process a job. They constructed a branch and abound algorithm for this problem and examined the efficiency of it by numerical examples. Viniclus Amaral Armentano and Moacir Fellzardo de Franca Fllho BIB015 have considered the problem of scheduling jobs in uniform parallel machines with sequence dependent setup times in order to minimize the total tardiness of the jobs. They proposed GRASP versions that incorporate adaptive memory principles to solve the problem. Long-term memory is used in the construction of an initial solution and in a post optimization procedure which connects high quality local optima by means of path re-linking. They carried out computational tests on a set of benchmark instances and compared the proposed GRASP versions with heuristic methods from the literature. Toung, Soukhal and Jean-Charless Billaut  have developed algorithm for uniform parallel machines scheduling problem with a common due date to minimize total weighted tardiness. Gur Mosheiov and Assaf Sarig BIB017 have shown that the two machines case of the uniform parallel machines scheduling with earliness and tardiness and due-date costs is solvable in constant time. Also, they stated that the problem remains polynomially solvable for a fixed number of machines. The minimization of the total earliness/tardiness is considered to be a challenging measure of performance even in the single machine scheduling problem with single processor. This magnifies the complexity of the algorithm to obtain the optimal solution. The researchers have used integer programming technique, branch and bound technique, single pass heuristic, GRASP, etc to minimize the measures of performance of this problem. As mentioned earlier, since it is a challenging measure, which magnifies the complexity of the problem, use of any exact algorithms like integer programming, branch and bound technique, etc. will take too much computational time. So, the researchers should concentrate on the development of meta-heuristics to obtain near-optimal/global optimum solutions for this scheduling problem. Minimize Maximum Lateness Federgruen and Groenevelt BIB005 considered the problem of scheduling n jobs, each with a specific processing requirement, release time and due date on m uniform parallel machines. They have obtained a feasible schedule by using network flow technique which determines the maximum flow in network. The complexity of the procedure used by them is O(tn 3 ) operations, where t is the number of distinct machine types. Previous algorithm solves the feasibility problem in O(m + log n) (m 2 n 3 + n 4 ) operations. In this research, they further described algorithms for minimizing the maximum lateness. Dessouky BIB012 has considered the problem of scheduling n identical jobs with unequal ready times on m parallel uniform machines to minimize the maximum lateness. In this research, a branch and bound procedure and six simple single-pass heuristic procedures are presented. The branch and bound procedure uses the heuristics to establish an initial upper bound. On sample problems, the branch and bound procedure in most instances was able to find an optimal solution within 100,000 iterations when the number of jobs is less than or equal to 80 and the number of machines is less than or equal to 3. For larger values of the number of machines, this heuristics provided approximate solutions close to optimal values. Chhajed BIB006 has analyzed the problem of simultaneous determination of a common due-date and a sequence of n jobs to minimize the maximum deviation of job completion time around the common due-date. It is assumed that all the jobs are available at time zero and their processing times are known in advance. He gave some results for the case when splitting and preemption are allowed. Chudak and Shmoys BIB009 presented new approximation algorithms for the problem of scheduling precedence-constrained jobs on parallel machines that are uniformly related without preemption. Here, they considered two objective functions: C max = max j C j , where C j denotes the completion time of the job j and ∑w j C j , where w j is a weight that is given for each job j. For the first objective, the best previously known result is an O(√m)-approximation algorithm, which was shown by Jaffe BIB003 . They have given an O(log m) approximation algorithm. They also showed how to extend this result to obtain an O(log m)-approximation algorithm for the second objective. There results also extend to settings in which each job has a release date r j before which the job may not begin processing. Christos Koulamas and George J. Kyparisis BIB014 considered the uniform parallel machines scheduling problem with the objective of minimizing maximum lateness. They showed that an extension of EDD rule to a uniform parallel machines setting yields a maximum lateness value which does not exceed the optimal value by more than p max , where p max is the maximum job processing time. The researchers have used network flow technique, branch and bound technique, heuristics, etc in the past. The minimization of the maximum lateness improves the goodwill of the customers, because the maximum delay is minimized, for which there is an exact algorithm namely EDD rule in the single machine scheduling problem with single processor. The minimization of this measure under parallel machines environment makes the problem combinatorial in nature. Hence, the researchers may concentrate on the development of meta-heuristics for this problem. If one uses simulated annealing, an improved version of EDD rule may be designed as the seed generation algorithm. Minimize Number of Tardy Jobs As already stated in one of the earlier sections, Zhi-Long Chen and Warren B.Powell BIB007 have considered a class of problems of scheduling n jobs on m identical, uniform, or unrelated parallel machines with an objective of minimizing an additive criterion, viz. the total weighted completion times of the jobs. In addition to this measure, they also considered the objective of minimizing the weighted number of tardy jobs. They proposed a decomposition algorithm for solving these problems exactly. Ruiz-Torres, Lopez and Ho BIB016 investigated the uniform parallel machines scheduling problem subject to a secondary resource constraint to minimize the number of tardy jobs. The secondary resource is fixed in quantity and is to be allocated to the machines at the start of the schedule. Two versions of the problem are analyzed. The first version assumes that the jobs are pre-assigned to the machines, while the second one takes into consideration the task of assigning jobs to the machines. They proposed an integer programming formulation to solve the first case and a set of heuristics for the second case. One can use Hodgson's algorithm to optimize the number of tardy jobs in the single machine scheduling problem with single processor with un-weighted jobs. When the jobs are with weights, the optimality is not guaranteed. Since, this measure is a derived measure from tardiness, it is a challenging measure. So, the researchers may use meta-heuristics to obtain global optimal solution. Further, the seed generation algorithm for the simulated annealing algorithm may be designed using an improved version of Hodgson's algorithm.