Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines
---
paper_title: Optimal scheduling for two-processor systems

paper_content:

Despite the recognized potential of multiprocessing little is known concerning the general problem of finding efficient algorithms which compute minimallength schedules for given computations and m?2 processors. In this paper we formulate a general model of computation structures and exhibit an efficient algorithm for finding optimal nonpreemptive schedules for these structures on two-processor systems. We prove that the algorithm gives optimal solutions and discuss its application to preemptive scheduling disciplines.
---
paper_title: Scheduling identical jobs with unequal ready times on uniform parallel machines to minimize the maximum lateness

paper_content:

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.
---
paper_title: Solving Parallel Machine Scheduling Problems by Column Generation

paper_content:

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.
---
paper_title: Approximation algorithms for precedence-constrained scheduling problems on parallel machines that run at different speeds

paper_content:

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.
---
paper_title: Efficient scheduling of tasks without full use of processor resources

paper_content:

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.
---
paper_title: Scheduling uniform parallel machines subject to a secondary resource to minimize the number of tardy jobs

paper_content:

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.
---
paper_title: Scheduling identical jobs on uniform parallel machines with random processing times

paper_content:

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.
---
paper_title: Scheduling on uniform parallel machines to minimize maximum lateness

paper_content:

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.
---
paper_title: Preemptive Scheduling of Uniform Machines by Ordinary Network Flow Techniques

paper_content:

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.
---
paper_title: Scheduling independent jobs on uniform parallel machines to minimize tardiness criteria

paper_content:

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.
---
paper_title: On the minimization of total weighted flow time with identical and uniform parallel machines

paper_content:

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.
---
paper_title: A note on “minimizing the maximum deviation of job completion time about a common due-date”

paper_content:

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 σ.
---
paper_title: Exact and Approximate Algorithms for Scheduling Nonidentical Processors

paper_content:

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 ).
---
paper_title: Due-date assignment on uniform machines

paper_content:

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.
---
paper_title: Scheduling with parallel machines to minimize total job tardiness

paper_content:

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.
---
paper_title: Minimizing total tardiness in parallel machine scheduling with setup times: An adaptive memory-based GRASP approach

paper_content:

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.
---
paper_title: Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors

paper_content:

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 .
---
paper_title: Tardiness minimization on parallel machines

paper_content:

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.
---
paper_title: SCHEDULING TO MINIMIZE MAKESPAN ON UNEQUAL PARALLEL PROCESSORS

paper_content:

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.
---
paper_title: Approximation Schemes for Scheduling on Uniformly Related and Identical Parallel Machines

paper_content:

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.
---
paper_title: Scheduling independent tasks on uniform processors

paper_content:

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.
---
paper_title: PARAMETRIC BOUNDS FOR LPT SCHEDULING ON UNIFORM PROCESSORS

paper_content:

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
---
paper_title: A note on MULTIFIT scheduling for uniform machines

paper_content:

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 .
---
paper_title: Efficient scheduling of tasks without full use of processor resources

paper_content:

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.
---
paper_title: Makespan minimization for two uniform parallel machines

paper_content:

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.
---
paper_title: Uniform machine scheduling of unit-time jobs subject to resource constraints

paper_content:

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.
---
paper_title: A comment on scheduling on uniform machines under chain-type precedence constraints

paper_content:

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.
---
paper_title: Scheduling Jobs on Two Facilities to Minimize Makespan

paper_content:

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.
---
paper_title: Makespan minimization on uniform parallel machines with release times

paper_content:

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.
---
paper_title: Makespan minimization for multiple uniform machines

paper_content:

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.
---
paper_title: Tighter bounds for LPT scheduling on uniform processors

paper_content:

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).
---
paper_title: A POLYNOMIAL APPROXIMATION SCHEME FOR SCHEDULING ON UNIFORM PROCESSORS: USING THE DUAL APPROXIMATION APPROACH*

paper_content:

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.
---
paper_title: Bounds for multifit scheduling on uniform processors

paper_content:

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.
---
paper_title: A linear compound algorithm for uniform machine scheduling

paper_content:

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.
---
paper_title: A parametric worst case analysis of the LPT heuristic for two uniform machines

paper_content:

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..
---
paper_title: An Efficient Approximation Algorithm for Minimizing Makespan on Uniformly Related Machines

paper_content:

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.
---
paper_title: Heuristics and augmented neural networks for task scheduling with non-identical machines

paper_content:

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.
---
paper_title: Approximations and auctions for scheduling batches on related machines

paper_content:

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.
---
paper_title: A parallel algorithm for preemptive scheduling of uniform machines

paper_content:

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.
---
paper_title: Minimizing total completion time on uniform machines with deadline constraints

paper_content:

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.
---
paper_title: Exact and Approximate Algorithms for Scheduling Nonidentical Processors

paper_content:

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 ).
---
paper_title: Minimizing Makespan and Preemption Costs on a System of Uniform Machines

paper_content:

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.
---
paper_title: Minimizing total weighted completion time when scheduling orders in a flexible environment with uniform machines

paper_content:

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.
---
paper_title: Scheduling n Independent Jobs on m Uniform Machines with both Flowtime and Makespan Objectives: A Parametric Analysis

paper_content:

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.
---
paper_title: Preemptive Scheduling of Two Uniform Machines to Minimize the Number of Late Jobs

paper_content:

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.
---
paper_title: A Lower Bound for On-Line Scheduling on Uniformly Related Machines

paper_content:

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.
---
paper_title: A new algorithm for online uniform-machine scheduling to minimize the makespan

paper_content:

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.
---
paper_title: Semi-online scheduling on two uniform processors

paper_content:

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.
---
paper_title: Approximation Schemes for Covering and Scheduling on Related Machines

paper_content:

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].
---
paper_title: Optimal non-preemptive semi-online scheduling on two related machines

paper_content:

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.
---
paper_title: Optimal on-line algorithms for the uniform machine scheduling problem with ordinal data

paper_content:

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.
---
paper_title: An On-Line Algorithm for Some Uniform Processor Scheduling

paper_content:

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.
---
paper_title: On-Line Scheduling of Parallel Machines

paper_content:

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.
---
paper_title: Semi-on-line scheduling with ordinal data on two uniform machines

paper_content:

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.
---
paper_title: Optimal preemptive semi-online scheduling to minimize makespan on two related machines

paper_content:

Abstract We study a preemptive semi-online scheduling problem. Jobs with non-increasing sizes arrive one by one to be scheduled on two uniformly related machines. We analyze the algorithms as a function of the speed ratio (q⩾1) between the two machines. We design algorithms of optimal competitive ratio for all values of q, and show that for q>2, idle time needs to be introduced. This is the first preemptive scheduling problem over list, where idle time is provably required.
---
paper_title: Optimal preemptive semi-online scheduling on two uniform processors

paper_content:

We investigate a preemptive semi-online scheduling problem. Jobs with sizes within a certain range [1, r] (r≥1 ) arrive one by one to be scheduled on two uniform parallel processors with speed 1 and s≥1, respectively. The objective is to minimize makespan. We characterize the optimal competitive ratio as a function of both s and r by devising a deterministic on-line scheduling algorithm along with a matching lower bound, which also holds for randomized algorithms.
---
paper_title: Preemptive on-line scheduling for two uniform processors

paper_content:

This paper considers the problem of preemptive on-line scheduling for two uniform processors in which one of the processors has speed 1 and the other has speed s>=1. The objective is to minimize the makespan. A best possible algorithm with competitive ratio of (1+s)^2/(1+s+s^2) is proposed for this problem.
---
paper_title: Optimal Preemptive Scheduling on Uniform Processors with Non-decreasing Speed Ratios

paper_content:

We study preemptive scheduling on uniformly related processors, where jobs are arriving one by one in an on-line fashion. We consider the class of machine sets where the speed ratios are non-decreasing as speed increases. For each set of machines in this class, we design an algorithm of optimal competitive ratio. This generalizes the known result for identical machines, and solves other interesting cases.
---
paper_title: Optimal semi-online preemptive algorithms for machine covering on two uniform machines

paper_content:

In this paper, we consider the semi-online preemptive scheduling problem with decreasing job sizes on two uniform machines. Our goal is to maximize the continuous period of time (starting from time zero) when both machines are busy, which is equivalent to maximizing the minimum machine completion time if idle time is not introduced before all the jobs are completed. We design optimal deterministic semi-online algorithms for every machine speed ratio s ∈ [1, ∞), and show that idle time is required during the assignment procedure of algorithms for any s > √6/2. The competitive ratios of the algorithms match the randomized lower bound for every 1 ≤ s ≤ 3. The problem of whether randomization still does not help for the discussed preemptive scheduling problem remains open.
---
paper_title: Optimal preemptive on-line scheduling on uniform processors with non-decreasing speed ratios

paper_content:

We study preemptive scheduling on uniformly related processors, where jobs are arriving one by one in an on-line fashion. We consider the class of machine sets where the speed ratios are non-decreasing as speed increases. For each set of machines in this class, we design an algorithm of optimal competitive ratio. This generalizes the known result for identical machines, and solves other interesting cases.
---
paper_title: Early/tardy scheduling with sequence dependent setups on uniform parallel machines

paper_content:

We consider the problem of scheduling N jobs on M parallel machines that operate at different speeds (known as uniform parallel machines), to minimize the sum of earliness and tardiness costs. Jobs are assumed to arrive in a dynamic albeit deterministic manner, and have nonidentical due dates. Violations of due dates result in earliness or tardiness penalties that may be different for different jobs. Setup times are job-sequence dependent and may be different on different machines based on the characteristics of the machines. For this problem, we present a mixed integer formulation that has substantially fewer zero–one variables than typical formulations for scheduling problems of this type. We present our computational experience in using this model to solve small sized problems, and discuss solution approaches for solving larger problems. ::: ::: ::: Scope and purpose ::: ::: In JIT environments, firms face the need to complete jobs as close to their due dates as possible. Failure to do so would result in earliness and/or tardiness costs and the optimum schedule would seek to minimize functions of these costs. In many real-world situations, the problem is greatly complicated by the presence of disparate issues such as: (i) uniform parallel machines that are capable of processing these jobs at different speeds; (ii) sequence-dependent setup times; (iii) distinct job due dates; (iv) distinct job ready dates; and (v) distinct earliness and/or tardiness costs for each job. For this complex problem, we present a compact mathematical model and describe our computational experience in using this model to solve small sized problems.
---
paper_title: Operational fixed interval scheduling problem on uniform parallel machines

paper_content:

In this study, we address an operational fixed interval scheduling problem on uniform parallel machines. Our objective is to maximize the total weight of the jobs processed. We show that the problem is NP-hard in the strong sense and develop polynomial time algorithms for some special cases. We propose a branch and bound algorithm that employs dominance conditions and tight bounds. The results of our computational tests have revealed that the algorithm returns optimal solutions for problem instances with up to 70 jobs very quickly.
---
paper_title: On-Line Uniform Machine Scheduling with Rejection

paper_content:

Abstract In this paper, we consider the problem of on-line uniform machine scheduling with rejection. For the two machine case and a special three machine case, we present the best possible on-line algorithms for certain values of speed ratio s.
---
paper_title: Two parallel machine sequencing problems involving controllable job processing times

paper_content:

In this note we consider a problem of scheduling n single-operation jobs on m non-identical machines where the sequencing of the jobs and their processing times are decision variables. It is assumed that the cost of performing a job is a linear function of its processing time. The scheduling cost to be minimized is: (A) the total processing cost plus total flow time, (B) the total processing cost plus total weighted earliness and weighted tardiness. We reduce each problem to a transportation problem that can be solved by a polynomial time algorithm.
---
paper_title: Scheduling on a single processor with variable speed

paper_content:

In this paper a single machine scheduling problem with varying processing times is considered. The scheduling objectives are makespan, total flow time, and sum of deviations of jobs completion times from a common due date. Polynomial time algorithms for optimal solutions of the problems are given.
---
paper_title: A Generalized Uniform Processor System

paper_content:

This paper considers a scheduling problem whose objective is to determine both the optimal speeds of processors and an optimal schedule in a preemptive multiprocessor environment. The jobs are independent and each processor can be assigned any speed; however, the cost associated with each processor is a function of the processor's speed. Polynomial algorithms are presented to find optimal speed assignments for a variety of cost functions.
---
paper_title: Minimizing Mean Weighted Execution Time Loss on Identical and Uniform Processors

paper_content:

Abstract The problem of minimizing mean weighted execution time loss was formulated by the present author in 1984; there the preemptive case for identical as well as for a fixed number of uniform processors was solved via a linear programming approach. In this paper, we propose a strongly polynomial algorithm based on a network flow technique, which minimizes the above criterion for an arbitrary number of identical as well as uniform processors. The upper bounds on the number of preemptions in both cases are also given.
---
paper_title: Scheduling complete intrees on two uniform processors with communication delays

paper_content:

We present an optimal algorithm for scheduling a complete k-ary tree on two uniform processors of different speeds in order to minimize schedule length. We consider the basic case of unit standard execution times and unit communication times.
---
paper_title: Scheduling chains on uniform processors with communication delays

paper_content:

We show that the problem of scheduling chains of unit execution time (UET) jobs on uniform processors with communication delays to minimize makespan is NP-hard in the strong sense. We also give a heuristic that generates solutions with known, and relatively small, absolute error for this problem. The NP-hardness result holds even for the case without communication delays, and complements the earlier result of Gonzalez and Sahni who gave a polynomial time algorithm for preemptive jobs of arbitrary length. ::: ::: ::: ::: We also study the structure of optimal solutions for the two processor problem of scheduling chains of UET jobs with communication delays, where one processor is a (integer) times faster than the other. This investigation leads to a linear time optimization algorithm for this case. Copyright © 2002 John Wiley & Sons, Ltd.
---
paper_title: Preemptive Scheduling on Uniform Parallel Machines with Controllable Job Processing Times

paper_content:

In this paper, we provide a unified approach to solving preemptive scheduling problems with uniform parallel machines and controllable processing times. We demonstrate that a single criterion problem of minimizing total compression cost subject to the constraint that all due dates should be met can be formulated in terms of maximizing a linear function over a generalized polymatroid. This justifies applicability of the greedy approach and allows us to develop fast algorithms for solving the problem with arbitrary release and due dates as well as its special case with zero release dates and a common due date. For the bicriteria counterpart of the latter problem we develop an efficient algorithm that constructs the trade-off curve for minimizing the compression cost and the makespan.
---
paper_title: Scheduling periodic tasks on uniform multiprocessors

paper_content:

Abstract A uniform multiprocessor machine is comprised of an integer number of processors. Each processor P is characterized by a computing capacity P . c with the interpretation that a job executing on processor P for t time units completes ( P . c × t ) units of execution. The scheduling of systems of periodic tasks on uniform multiprocessor systems is considered.
---
paper_title: Rate-monotonic scheduling on uniform multiprocessors

paper_content:

Each processor in a uniform multiprocessor machine is characterized by a speed or computing capacity, with the interpretation that a job executing on a processor with speed s for t time units completes (s /spl times/ t) units of execution. The scheduling of systems of periodic tasks on uniform multiprocessor platforms using the rate-monotonic scheduling algorithm is considered here. A simple, sufficient test is presented for determining whether a given periodic task system will be successfully scheduled by algorithm upon a particular uniform multiprocessor platform-this test generalizes earlier results concerning rate-monotonic scheduling upon identical multiprocessor platforms.
---

Title: Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines

Section 1: Introduction
Description 1: Write about the importance of production scheduling in companies and categorize different types of production scheduling.

Section 2: Single Machine Scheduling with Single Processor
Description 2: Describe the single machine scheduling problem with a single processor, explain the difference between independent and dependent jobs, and measures of performance.

Section 3: Single Machine Scheduling with Parallel Machines
Description 3: Define single machine scheduling problem with parallel machines, classify the types of parallel machine scheduling problems, and discuss the measures of performance.

Section 4: Uniform Parallel Machines Scheduling
Description 4: List the essential characteristics of uniform parallel machines scheduling, including the operations on jobs and machine speeds.

Section 5: Basic Measures of Performance
Description 5: Detail the basic measures of performance specific to the single machine scheduling problem with uniform parallel machines.

Section 6: Offline Scheduling vs. Online Scheduling
Description 6: Explain the distinction between offline and online scheduling problems and types of online scheduling.

Section 7: Classification of Uniform Parallel Machines Scheduling Problems
Description 7: Categorize the uniform parallel machines scheduling problems based on offline/online features, preemptive/non-preemptive jobs, and measures of performance.

Section 8: Review of Literature
Description 8: Discuss the literature review of identical parallel machines scheduling and its relationship with uniform parallel machines scheduling.

Section 9: Offline Uniform Parallel Machines Scheduling
Description 9: Detail the research and literature on various offline scheduling problems, including non-preemptive and preemptive cases.

Section 10: Review of Online Uniform Parallel Machines Scheduling
Description 10: Discuss the literature review of online scheduling problems by listing different objectives and competitive ratios.

Section 11: Miscellaneous Uniform Parallel Machines Scheduling
Description 11: Review articles dealing with miscellaneous uniform parallel machines scheduling problems, including those with non-preemptive, preemptive jobs, and periodic tasks.

Section 12: Conclusions
Description 12: Summarize the literature review, classify the reviewed literature into categories, and suggest directions for future research.

Section 13: Acknowledgements
Description 13: Acknowledge the contributions and suggestions from referees and other contributors who helped improve the paper.

Section 14: References
Description 14: List all the references cited in the paper.