Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Miscellaneous problems Periodic tasks/ jobs <s> The problem of scheduling n independent jobs on m unequal parallel processors to minimize makespan is known to be very difficult for the nonpreemptive case. Until recently, research on this problem has consisted primarily of investigating the “worst case” behavior for simple approximation algorithms for the special cases of equal or uniform processors. Recently, Ibarra and Kim [10] have completed a similar analysis on five simple heuristics for general unequal processors. The approach in the present paper is to investigate the “average” behavior via large-scale computational testing. A new heuristic is devised. It is tested on a large number of problems (about 9,000) for both uniform and general processors, and the results are compared with the best solutions obtained from a truncated branch-and-bound procedure. It is observed that, although the heuristic takes negligible time compared to the branch-and-bound procedure, on the average it is within 5 percent of the latter in the uniform case and within 1.3 percent in the general case. It also performs better than a composite heuristic whose output, for any given problem, is the best of all previously suggested heuristics. <s> BIB001 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Miscellaneous problems Periodic tasks/ jobs <s> This paper is concerned with the problem of scheduling tasks on a system consisting of two parallel processors in order that makespan be minimized. In particular, we treat a variety of modifications to this basic theme, including the cases of identical, proportional, and unrelated processors. In addition, a heuristic scheme is suggested when precedence constraints exist where such constraints may be assignment dependent. Substantial computational experience is reported in all cases where it would appear that relatively large problems can be handled routinely. <s> BIB002 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Miscellaneous problems Periodic tasks/ jobs <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> Miscellaneous problems Periodic tasks/ jobs <s> We examine the nonpreemptive assignment of N independent tasks to a system of M uniform processors with the objective of reducing the makespan, or the time required from the start of execution until all tasks are completed. Since the problem of finding a minimal makespan has been shown to be NP-hard, and hence unlikely to permit an efficient solution procedure, near-optimal heuristic algorithms have been studied. It is known that LPT (longest processing time first) schedules are within twice the length of the optimum. We analyze a variation of the MULTIFIT algorithm derived from bin packing, and prove that its worst-case performance bound is within 1.4 of the optimum. <s> BIB004 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Miscellaneous problems Periodic tasks/ jobs <s> A worst-case analysis is given for the LPT (longest processing time) heuristic applied to the problem of scheduling independent tasks on uniform processors. A bound of $\frac{19}{12}$ is derived on the ratio of the heuristic to the optimal makespan and an example is given where the error is greater than $\frac{{3}}{{2}}$. A generalization of the classic result of Graham for the case of identical processors is given. Here tight bounds are derived for the ratio of the heuristic to the optimal makespan which depends on the ratio of the longest task to the makespan. <s> BIB005 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Miscellaneous problems Periodic tasks/ jobs <s> We examine the nonpreemptive assignment of independent tasks to a system of uniform processors with the objective of minimizing the makespan. The worst case bound for the largest processing time first algorithm for this problem is tightened to be in the interval (1.52, 1.67). <s> BIB006 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Miscellaneous problems Periodic tasks/ jobs <s> We present a polynomial approximation scheme for the minimum makespan problem on uniform parallel processors. More specifically, the problem is to find a schedule for a set of independent jobs on a collection of machines of different speeds so that the last job to finish is completed as quickly as possible. We give a family of polynomial-time algorithms $\{ {A_\varepsilon } \}$ such that $A_\varepsilon $ delivers a solution that is within a relative error $\varepsilon $ of the optimum. This is a dramatic improvement over previously known algorithms; the best performance guarantee previously proved for a polynomial-time algorithm ensured a relative error no more than 40 percent. The technique employed is the dual approximation approach, where infeasible but superoptimal solutions for a related (dual) problem are converted to the desired feasible but possibly suboptimal solution. <s> BIB007 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Miscellaneous problems Periodic tasks/ jobs <s> The nonpreemptive assignment of independent tasks to a system of m uniform processors isexamined with the objective of minimizing the makespan. Using r_m, the ratio of the fasest speed tothe slowest speed of the system, as a parameter, we assess the performance of LPT (largestprocessing time) schedule with respect to optimal schedules. It is shown thet the worst-case boundfor the ratio of the two schedule lengths is between <s> BIB008 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Miscellaneous problems Periodic tasks/ jobs <s> We consider the problem of minimizing the makespan when scheduling tasks on two uniform parallel machines, where one machine is q times as efficient on each task as is the other. We compute the maximum relative error of the LPT largest processing time first heuristic as an explicit function of q. In the special case that the two machines are identical q = 1, our problem and heuristic reduce to the problem and heuristic analyzed by Graham Graham, R. 1969. Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math.17 416-429.. <s> BIB009 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Miscellaneous problems Periodic tasks/ jobs <s> The problem of scheduling a set of unit-time jobs on m uniform machines is studied. Some jobs may require a unit of an additional single resource during their execution. The resource is renewable but the total resource consumption is limited by the same value at each time instant. The objective is to find a feasible schedule minimizing the maximum job completion time. We show that an approach suggested in the literature to solve this problem is incorrect. Then we present an O(m log m) algorithm for the problem with no machine idle times and a linear-time algorithm for the problem with identical machines. <s> BIB010 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Miscellaneous problems Periodic tasks/ jobs <s> We give a new efficient approximation algorithm for schedul- ing precedence constrained jobs on machines with different speeds. The setting is as follows. There are n jobs 1, . . ., n where job j requires p j units of processing. The jobs are to be scheduled on a set of m machines. Machine i has a speed s i; it takes p j/s i units of time for machine i to pro- cess job j. The precedence constraints on the jobs are given in the form of a partial order. If j ≺ k, processing of k cannot start until j’s execution if finished. Let C j denote the completion time of job j. The objective is to find a schedule to minimize C max = maxj C j, conventionally called the makespan of the schedule. We consider non-preemptive schedules where each job is processed on a single machine with no preemptions. Recently Chudak and Shmoys [1] gave an algorithm with an approximation ra- tio of O(log m) significantly improving the earlier ratio of O(√m) due to Jaffe [7]. Their algorithm is based on solving a linear programming relaxation of the problem. Building on some of their ideas, we present a combinatorial algorithm that achieves a similar approximation ratio but runs in O(n 3) time. In the process we also obtain a constant factor approximation algorithm for the special case of precedence constraints induced by a collection of chains. Our algorithm is based on a new lower bound which we believe is of independent interest. By a general result of Shmoys, Wein, and Williamson [10] our algorithm can be extended to obtain an O(logm) approximation ratio even if jobs have release dates. <s> BIB011 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Miscellaneous problems Periodic tasks/ jobs <s> We give a polynomial approximation scheme for the problem of scheduling on uniformly related parallel machines for a large class of objective functions that depend only on the machine completion times, including minimizing the lp norm of the vector of completion times. This generalizes and simplifies many previous results in this area. <s> BIB012 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Miscellaneous problems Periodic tasks/ jobs <s> In a recent paper, Chekuri and Bender (Proceedings of IPCO'98, pp. 383-393) derive (among other results) a polynomial-time 6-approximation algorithm for makespan minimization on uniform parallel machines subject to chain-type precedence constraints. In this short note, we combine some straightforward observations and thereby derive an extremely simple 2-approximation algorithm for this problem. <s> BIB013 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Miscellaneous problems Periodic tasks/ jobs <s> Abstract We consider the two uniform parallel machine problem with the objective of minimizing makespan. The problem can be transformed into a special problem of two identical parallel machines from the viewpoint of workload instead of completion time. An optimal algorithm is developed for the transformed special problem. Although the proposed algorithm has an exponential time complexity, the results show that it can find the optimal solution for large-sized problems in a short time. <s> BIB014 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Miscellaneous problems Periodic tasks/ jobs <s> Abstract We consider the makespan minimization problem on uniform parallel machines in the presence of release times. We develop a heuristic for this NP-hard problem and derive a tight worst-case ratio bound for this heuristic independent of the machine speeds. <s> BIB015 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Miscellaneous problems Periodic tasks/ jobs <s> Abstract We propose new heuristics along with an augmented-neural-network (AugNN) formulation for solving the makespan minimization task-scheduling problem for the non-identical machine environment. We explore four task and three machine-priority rules, resulting in 12 combinations of single-pass heuristics. The task-priority rules are Highest-Level-First (HLF), Highest-Total-Remaining-Processing-Time-First (HTRPTF), Smallest-Latest-Finish-Time-First (SLFTF) and Minimum-Slack-First (MSF). For machine priority, we propose a greedy rule called Fastest-Available-Machine-First (FAMF), and two non-greedy rules: (1) Fastest-Available-Machine-First-With-Conditional-Wait-1 (FAMF-CW-1), and (2) Fastest-Available-Machine-First-With-Conditional-Wait-2 (FMF-CW-2). The AugNN approach integrates neural-network learning with domain and problem specific knowledge through heuristics, to produce good results. A single-pass heuristic is embedded in a neural network designed specifically for each problem. We give the AugNN formulation for each of the 12 heuristics and show computational results on 100 randomly generated problems of sizes ranging from 20 to 70 tasks and 2 to 5 machines. Results demonstrate that AugNN provides significant improvement over single-pass heuristics. The reduction in the gap between the obtained solution and the lower-bound due to AugNN over single-pass heuristics ranged from 24.4% to 50%. As far as heuristics, the non-greedy machine-priority rules performed significantly better than the greedy rule. The average gaps for the non-greedy rules ranged from 16.1% to 23.5% compared to 33.7% to 40.4% for greedy. For AugNN, for non-greedy rules, the gap ranged from 11.5% to 15.5% compared to 18.4% to 25.0% for greedy. The HLF and HTRPTF task priority rules performed better than the other two. The HTRPTF/FAMF-CW-1 combination gave the best results, closely followed by HLF/FAMF-CW-2 and HTRPTF/FAMF-CW-2 combinations. <s> BIB016 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Miscellaneous problems Periodic tasks/ jobs <s> In this note, we derive the tight worst case bound √6/2+(1/2) k for scheduling with the MULTIFIT heuristic on two parallel uniform machines withk calls of FFD within MULTIFIT. When MULTIFIT is combined with LPT as an incumbent algorithm the worst case bound decreases to √2+1/2+(1/2) k . <s> BIB017 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Miscellaneous problems Periodic tasks/ jobs <s> In this paper, we consider the classical two uniform machine scheduling problem. We present a compound algorithm which consists of three Greedy-like subprocedures running independently. We prove that the algorithm has a worst-case bound of 7/6 and runs in linear time. <s> BIB018 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Miscellaneous problems Periodic tasks/ jobs <s> We consider the scheduling of groups of identical jobs on related machines with sequence independent setup times. We provide a 2-approximation algorithm for minimizing the makespan. The second result is a truthful, polynomial time, randomized mechanism for the batch scheduling problem with a deterministic approximation guarantee of 4. <s> BIB019 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Miscellaneous problems Periodic tasks/ jobs <s> We consider a classical scheduling problem with makespan minimization on uniform parallel machines. From the viewpoint of workload, instead of completion time, two important theorems are developed for the problem. The first theorem provides an improved lower bound as the starting point for the search, and the second theorem further accelerates the search speed in the algorithm. Incorporating the two useful theorems, an algorithm is developed for obtaining the optimal solution. Although the developed algorithm has an exponential time complexity, extensive computational experiments demonstrate that it is quite efficient for various sizes of the problem. With the optimal algorithm, we also examine the effectiveness of the popular LPT heuristic. <s> BIB020
A periodic task T is characterized by two integer parameters -an execution requirement T.e and a period T.p with the interpretation that the task generates a job at each integer multiple of T.p and such job has an execution requirement of T.e execution units, which should be met by a deadline equal to the next integer multiple of T.p. generates a schedule having a finishing time of at most (√5 + 1)/2 of the optimal finishing time. They verified that the LPT algorithm applied to this problem gives schedules which are near optimal for larger n. Prabuddha De and Thomas E. Morton BIB001 have developed a new heuristic to schedule jobs on uniform parallel processors to minimize makespan. It is tested on a large number of problems for both uniform and identical processors. They found that the solutions given by the heuristic for the uniform parallel machines scheduling are within 5% of the solutions given by the branch and bound algorithm. Bulfin and Parker BIB002 have considered the problem of scheduling tasks on a system consisting of two parallel processors such that the makespan is minimized. In particular, they treated a variety of modifications to this basic theme, including the cases of identical processors, proportional (uniform) processors and unrelated processors. In addition, they suggested a heuristic scheme when precedence constraints exist. Friesen and Langston BIB004 examined the non-preemptive assignment of n independent tasks to a system of m uniform processors with the objective of reducing the makespan. It is known that LPT (longest processing time first) schedules are within twice the length of the optimum makespan. Graham  , they analyzed a variation of the MULTIFIT algorithm derived from the algorithm for bin packing problem and proved that its worst-case performance bound on the makespan is within 1.4 times of the optimum makepsan. Gregory Dobson BIB005 has given a worst-case analysis while applying the LPT (longest processing Time) heuristic to the problem of scheduling independent tasks on uniform processors with the minimum makepsan. In this research, a bound of 19/12 is derived on the ratio of the heuristic to the optimal makespan. Also, a generalization of the classic result of Graham  for the case of identical processors is given. The author has derived tight bounds for the ratio of the heuristic makespan to the optimal makespan which depends on the ratio of the longest task to the makespan. Friesen BIB006 examined the nonpreemptive assignment of independent tasks to a system of uniform processors with the objective of minimizing the makespan. The author showed that the worst case bound for the largest processing time first (LPT) algorithm for this problem is tightened to be in the interval (1.52 to 1.67). Hochbaum and Shmoys BIB007 devised a polynomial approximation scheme for the minimizing makespan problem on uniform parallel processors. They gave a family of polynomial-time algorithms such that each algorithm gives a solution that is within 40% relative error of the optimum. The technique employed is the dual approximation approach, where infeasible but super-optimal solutions for a related (dual) problem are converted to the desired feasible but possibly suboptimal solution. Chen BIB008 has examined the non-preemptive assignment of independent tasks to a system of m uniform processors with the objective of minimizing the makespan. The author has examined the performance of LPT (largest processing time) schedule with respect to optimal schedules, using the ratio of the fastest speed to the slowest speed of the system as a parameter. Two wellknown heuristics LPT (largest processing time first) and MULTIFIT obtains schedules having makespan with ¾ and 11/13, respectively, of the minimum possible makespan, when the m parallel processors are identical. The best known worst-case performance ratio bounds are 1.583 and 1.40, respectively. The author has tightened bound to 1.382 for MULTIFIT algorithm for the uniform parallel processors system. Mireault, Orlin, Vohra BIB009 have considered the problem of minimizing the makespan when scheduling independent tasks on two uniform parallel machines. Out of the two machines, the efficiency of one machine is q times as that of the other machine. They computed the maximum relative error of the LPT (largest processing time first) heuristic as a function of q. For the special case in which the two machines are identical (q = 1), their problem and heuristic are identical to the problem and heuristic analyzed by Graham  , respectively. Burkard and He BIB017 derived the tight worst case bound √6/2 + (1/2) k for scheduling jobs using the MUL-TIFIT heuristic on two parallel uniform machines with k calls of FFD (first fit decreasing) within MULTIFIT. As per FFD, the tasks are sorted in non-increasing order from left to right. They concluded that when MULTIFIT is combined with LPT as an incumbent algorithm, the worst case bound decreases to √2 + ½ + (1/2) k . Kovalyov and Shafransky BIB010 have studied the uniform machine scheduling of unit-time jobs subject to resource constraints. Some jobs may require a unit of an additional single resource during their execution. The resource is renewable, but the total resource consumption is limited by the same value at each time instant. They presented an O(m log m) algorithm for the problem with no machine idle times to minimize the maximum job completion time, that is the makespan. They also presented a linear time algorithm for the problem with identical machines to minimize the maximum job completion time. Burkard, He and Kellerer BIB018 have developed a linear compound algorithm for scheduling jobs on uniform parallel machines with the objective of minimizing makespan. This algorithm has three subroutines, which run independently in order to choose the best assignment among them. Panneerselvam and Kanagalingam  have presented a mathematical model for parallel machines scheduling problem with varying speeds in which the objective is to minimize the makespan. Also, they discussed industrial applications of such scheduling problem. Panneerselvam and Kanagalingam  have given a heuristic to minimize the makespan for scheduling n independent jobs on m parallel processors with different speeds. Chandra Chekuri and Michael Bender BIB011 designed a new and efficient polynomial 6 approximation algorithm for scheduling precedence-constrained jobs on uniform parallel machines. In their work, the objective is to find a non-preemptive schedule to minimize the makespan. From their work, Woeginger BIB013 combined some straightforward observations and thereby derived an extremely simple 2 approximation algorithm for this problem. Chudak and Shmoys  gave an algorithm with an approximation ratio of O(log m), significantly improving the earlier ratio of O(√m) due to Jaffe BIB003 . Their algorithm is based on solving a linear programming relaxation. Building on some of their ideas, Chandra Chekuri and Michael Bender BIB011 have presented a combinatorial algorithm that achieves a similar approximation ratio but in O(n 3 ) time. Ching-Jong Liao and Chien-Hung Lin BIB014 have considered the two uniform parallel machines problem with the objective of minimizing makespan. In this work, the two uniform parallel machines problem is converted into a special problem of two identical parallel machines from the viewpoint of workload instead of completion time. An optimal algorithm is developed for the transformed special problem. The proposed algorithm has an exponential time complexity. Inspite of this fact, the authors claim that their algorithm can find the optimal solution for large sized problems in a short time. Epstein and Sgall BIB012 BIB012 derived a polynomial approximation scheme for the problem of scheduling on uniformly related parallel machines for a large class of objective functions as listed below that depend only on the machine completion times This generalizes and simplifies many previous results in this area. 1) Minimize the sum of the completion times on all the machines. 2) Minimize the maximum of the completion times on all the machines, which amounts to minimizing the makespan. 3) Maximize the sum of the completion times on all the machines. 4) Maximize the minimum of the completion times on all the machines. Christos Koulamas and George J. Kyparisis BIB015 investigated the makespan minimization problem on uniform parallel machines in the presence of release times. They developed a heuristic for this NP-hard problem and derived a tight worst-case ratio bound for this heuristic independent of the machines speeds. Agarwal, Colak, Jacob and Pirkul BIB016 have proposed new heuristics along with an augmented-neural-netwrok (AugNN) formulation for solving the makespan minimization taskscheduling problem for the non-identical machine environment. They explored four task and three machinepriority rules, resulting in 12 combinations of single-pass heuristics. They gave the AugNN formulation for each of the 12 heuristics and showed computational results on 100 randomly generated problems of sizes ranging from 20 to 70 tasks and 2 to 5 machines. The results clearly showed that AugNN provides significant improvement over single-pass heuristics. The reduction in the gap between the obtained solution and the lower bound due to AugNN over single-pass heuristics ranges from 24.4% to 50%. Chein-Hung Lin and Ching-Jong Liao BIB020 have considered a classical scheduling problem with makespan minimization on uniform parallel machines. From the viewpoint of workload, instead of completion time, two important theorems are developed for the problem. The first theorem provides an improved lower bound as the starting point of the search and the second theorem further accelerates the search speed in the algorithm. Incorporating the two useful theorems, an algorithm is developed for obtaining the optimal solution. Although the developed algorithm has an exponential time complexity, extensive computational experiments demonstrate that it is quite efficient for various sizes of the problem. With the optimal algorithm, they also examined the effectiveness of the popular LPT heuristic. Kis and Kapolnai BIB019 researched the scheduling of groups of identical jobs on uniform machines with sequence independent setup times. They provide a 2-approximation algorithm for minimizing the makespan. The second result is truthful, polynomial time, randomized mechanism for the batch scheduling problem with a deterministic approximation guarantee of 4. For this scheduling problem, most of the authors aimed at developing dynamic programming algorithm, mathematical model, branch and bound algorithm, heuristics based on LPT ordering, etc. Since, this problem comes under combinatorial category, obtaining the optimal solution will take exponential time. But, one can try metaheuristics, viz. simulated annealing algorithm, genetic algorithm, etc., which will give better solution tending towards global optimum, when compared to the single pass heuristics. Further, the researchers may consider multi-objective function for this problem. The possible combinations of the multi-objective problems are as listed below. While investigating such problems, enough care is to be taken to fix weights for the components of the objective functions, because they have differences in terms of interpretations.