Approximation Algorithms for Precedence-Constrained Scheduling Problems on Parallel Machines that Run at Different Speeds

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 jobjrequiresp_junits of processing, and is to be processed on one machine without interruption; if it is assigned to machinei, which runs at a given speeds_i, it takesp_j/s_itime 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:C_max = max_j C_j, whereC_jdenotes the completion time of jobj, and ∑_jw_jC_j, wherew_jis a weight that is given for each jobj. For the first objective, the best previously known result is an -approximation algorithm, which was shown by Jaffe more than 15 years ago. We give anO(log m)-approximation algorithm. We also show how to extend this result to obtain anO(log m)-approximation algorithm for the second objective, albeit with a somewhat larger constant. These results also extend to settings in which each jobjhas a release dater_jbefore 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.     

Approximation algorithms for scheduling unrelated parallel machines

We consider the following scheduling problem. There arem parallel machines andn independent jobs. Each job is to be assigned to one of the machines. The processing of jobj on machinei requires timep _ij . The objective is to find a schedule that minimizes the makespan.Our main result is a polynomial algorithm which constructs a schedule that is guaranteed to be no longer than twice the optimum. We also present a polynomial approximation scheme for the case that the number of machines is fixed. Both approximation results are corollaries of a theorem about the relationship of a class of integer programming problems and their linear programming relaxations. In particular, we give a polynomial method to round the fractional extreme points of the linear program to integral points that nearly satisfy the constraints.In contrast to our main result, we prove that no polynomial algorithm can achieve a worst-case ratio less than 3/2 unlessP = NP. We finally obtain a complexity classification for all special cases with a fixed number of processing times.A preliminary version of this paper appeared in theProceedings of the 28th Annual IEEE Symposium on the Foundations of Computer Science (Computer Society Press of the IEEE, Washington, D.C., 1987) pp. 217–224.     

Induced disjoint paths problem in a planar digraph

As an extension of the disjoint paths problem, we introduce a new problem which we call the induced disjoint paths problem. In this problem we are given a graph G and a collection of vertex pairs {(s₁,t₁),…,(s_k,t_k)}. The objective is to find k paths P₁,…,P_k such that P_i is a path from s_i to t_i and P_i and P_j have neither common vertices nor adjacent vertices for any distinct i,j.The induced disjoint paths problem has several variants depending on whether k is a fixed constant or a part of the input, whether the graph is directed or undirected, and whether the graph is planar or not. We investigate the computational complexity of several variants of the induced disjoint paths problem. We show that the induced disjoint paths problem is (i) solvable in polynomial time when k is fixed and G is a directed (or undirected) planar graph, (ii) NP-hard when k=2 and G is an acyclic directed graph, (iii) NP-hard when k=2 and G is an undirected general graph.As an application of our first result, we show that we can find in polynomial time certain structures called a “hole” and a “theta” in a planar graph.     

Outsourcing and scheduling for two-machine ordered flow shop scheduling problems

This paper considers a two-machine ordered flow shop problem, where each job is processed through the in-house system or outsourced to a subcontractor. For in-house jobs, a schedule is constructed and its performance is measured by the makespan. Jobs processed by subcontractors require paying an outsourcing cost. The objective is to minimize the sum of the makespan and the total outsourcing cost. Since this problem is NP-hard, we present an approximation algorithm. Furthermore, we consider three special cases in which job j has a processing time requirement p_j, and machine i a characteristic q_i. The first case assumes the time job j occupies machine i is equal to the processing requirement divided by a characteristic value of machine i, that is, p_j/q_i. The second (third) case assumes that the time job j occupies machine i is equal to the maximum (minimum) of its processing requirement and a characteristic value of the machine, that is, max{p_j, q_i} (min{p_j, q_i}). We show that the first and the second cases are NP-hard and the third case is polynomially solvable.     

Scheduling uniform machines on-line requires nondecreasing speed ratios

We consider the following on-line scheduling problem. We have to schedulen independent jobs, wheren is unknown, onm uniform parallel machines so as to minimize the makespan; preemption is allowed. Each job becomes available at its release date, and this release date is not known beforehand; its processing requirement becomes known at its arrival. We show that if only a finite number of preemptions is allowed, there exists an algorithm that solves the problem if and only ifs _i–1/s_i s_i/s_i+1 for alli = 2,,m – 1, wheres _i denotes theith largest machine speed. We also show that if this condition is satisfied, then O(mn) preemptions are necessary, and we provide an example to show that this bound is tight. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

Competitive online scheduling of perfectly malleable jobs with setup times

We study how to efficiently schedule online perfectly malleable parallel jobs with arbitrary arrival times on m ? 2 processors. We take into account both the linear speedup of such jobs and their setup time, i.e., the time to create, dispatch, and destroy multiple processes. Specifically, we define the execution time of a job with length p_j running on k_j processors to be p_j/k_j + (k_j − 1)c, where c > 0 is a constant setup time associated with each processor that is used to parallelize the computation. This formulation accurately models data parallelism in scientific computations and realistically asserts a relationship between job length and the maximum useful degree of parallelism. When the goal is to minimize makespan, we show that the online algorithm that simply assigns k_j so that the execution time of each job is minimized and starts jobs as early as possible has competitive ratio 4(m − 1)/m for even m ? 2 and 4m/(m + 1) for odd m ? 3. This algorithm is much simpler than previous offline algorithms for scheduling malleable jobs that require more than a constant number of passes through the job list.     

Preemptive scheduling of two uniform parallel machines to minimize total tardiness

We consider the problem of preemptive scheduling n jobs on two uniform parallel machines. All jobs have equal processing requirements. For each job we are given its due date. The objective is to find a schedule minimizing total tardiness ∑T_i. We suggest an O(n log n) algorithm to solve this problem.     

Scheduling jobs with time-resource tradeoff via nonlinear programming

We consider a scheduling problem where the processing time of any job is dependent on the usage of a discrete renewable resource, e.g. personnel. An amount of k units of that resource can be allocated to the jobs at any time, and the more of that resource is allocated to a job, the smaller its processing time. The objective is to find a resource allocation and a schedule that minimizes the makespan. We explicitly allow for succinctly encodable time-resource tradeoff functions, which calls for mathematical programming techniques other than those that have been used before. Utilizing a (nonlinear) integer mathematical program, we obtain the first polynomial time approximation algorithm for the scheduling problem, with performance bound (3+ε) for any ε>0. Our approach relies on a fully polynomial time approximation scheme to solve the nonlinear mathematical programming relaxation. We also derive lower bounds for the approximation.     

An approximation algorithm for the generalized assignment problem

The generalized assignment problem can be viewed as the following problem of scheduling parallel machines with costs. Each job is to be processed by exactly one machine; processing jobj on machinei requires timep _ij and incurs a cost ofc _ij ; each machinei is available forT _i time units, and the objective is to minimize the total cost incurred. Our main result is as follows. There is a polynomial-time algorithm that, given a valueC, either proves that no feasible schedule of costC exists, or else finds a schedule of cost at mostC where each machinei is used for at most 2T _i time units.We also extend this result to a variant of the problem where, instead of a fixed processing timep _ij , there is a range of possible processing times for each machine—job pair, and the cost linearly increases as the processing time decreases. We show that these results imply a polynomial-time 2-approximation algorithm to minimize a weighted sum of the cost and the makespan, i.e., the maximum job completion time. We also consider the objective of minimizing the mean job completion time. We show that there is a polynomial-time algorithm that, given valuesM andT, either proves that no schedule of mean job completion timeM and makespanT exists, or else finds a schedule of mean job completion time at mostM and makespan at most 2T. Research partially supported by an NSF PYI award CCR-89-96272 with matching support from UPS, and Sun Microsystems, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.Research supported in part by a Packard Fellowship, a Sloan Fellowship, an NSF PYI award, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.     

Approximation schemes for parallel machine scheduling with availability constraints

We investigate the problems of scheduling n weighted jobs to m parallel machines with availability constraints. We consider two different models of availability constraints: the preventive model, in which the unavailability is due to preventive machine maintenance, and the fixed job model, in which the unavailability is due to a priori assignment of some of the n jobs to certain machines at certain times. Both models have applications such as turnaround scheduling or overlay computing. In both models, the objective is to minimize the total weighted completion time. We assume that m is a constant, and that the jobs are non-resumable.For the preventive model, it has been shown that there is no approximation algorithm if all machines have unavailable intervals even if w_i=p_i for all jobs. In this paper, we assume that there is one machine that is permanently available and that the processing time of each job is equal to its weight for all jobs. We develop the first polynomial-time approximation scheme (PTAS) when there is a constant number of unavailable intervals. One main feature of our algorithm is that the classification of large and small jobs is with respect to each individual interval, and thus not fixed. This classification allows us (1) to enumerate the assignments of large jobs efficiently; and (2) to move small jobs around without increasing the objective value too much, and thus derive our PTAS. Next, we show that there is no fully polynomial-time approximation scheme (FPTAS) in this case unless P=NP.For the fixed job model, it has been shown that if job weights are arbitrary then there is no constant approximation for a single machine with 2 fixed jobs or for two machines with one fixed job on each machine, unless P=NP. In this paper, we assume that the weight of a job is the same as its processing time for all jobs. We show that the PTAS for the preventive model can be extended to solve this problem when the number of fixed jobs and the number of machines are both constants.     

Complexity results for scheduling tasks with discrete starting times

Suppose that n independent tasks are to be scheduled without preemption on a set of identical parallel processors. Each task T_i requires a given execution time τ_i and it may be started for execution on any processor at any of its prescribed starting times s_i1, s_i2, …, s_iki, with k_i ≤ k for some fixed integer k. We first prove that the problem of finding a feasible schedule on a single processor is NP-complete in the strong sense even when τ_i ε {τ, τ′} and k_i ≤ 3 for 1 ≤ i ≤ n. The same problem is, however, shown to be solvable in O(n log n) time, provided s_iki − s_i1 < τ_i for 1 ≤ i ≤ n. We then show that the problem of finding a feasible schedule on an arbitrary number of processors is strongly NP-complete even when τ_i ε {τ, τ′}, k_i = 2 and s_i2 − s_i1 = δ < τ_i for 1 ≤ i ≤ n. Finally a special case with k_i = 2 and s_i2 − s_i1 = 1, 1 ≤ i ≤ n, of the above multiprocessor scheduling problem is shown to be solvable in polynomial time.     

Selection in Monotone Matrices and Computingkth Nearest Neighbors

Anm×nmatrix =(a_{i, j}), 1≤i≤mand 1≤j≤n, is called atotally monotonematrix if for alli₁, i₂, j₁, j₂, satisfying 1≤i₁<i₂≤m, 1≤j₁<j₂≤n.[formula]We present an[formula]time algorithm to select thekth smallest item from anm×ntotally monotone matrix for anyk≤mn. This is the first subquadratic algorithm for selecting an item from a totally monotone matrix. Our method also yields an algorithm of the same time complexity for ageneralized row-selection problemin monotone matrices. Given a setS={p₁,…, p_n} ofnpoints in convex position and a vectork={k₁,…, k_n}, we also present anO(n^4/3log^c n) algorithm to compute thek_ith nearest neighbor ofp_ifor everyi≤n; herecis an appropriate constant. This algorithm is considerably faster than the one based on a row-selection algorithm for monotone matrices. If the points ofSare arbitrary, then thek_ith nearest neighbor ofp_i, for alli≤n, can be computed in timeO(n^7/5 log^c n), which also improves upon the previously best-known result.     

Disjoint skolem sequences and related disjoint structures

A Skolem sequence of order n is a sequence S = (s₁, s₂…, s²ⁿ) of 2n integers satisfying the following conditions: (1) for every k ∈ {1, 2,… n} there exist exactly two elements s_i,S_j such that S_i = S_j = k; (2) If s_i = s_j = k,i < j then j ? i = k. In this article we show the existence of disjoint Skolem, disjoint hooked Skolem, and disjoint near-Skolem sequences. Then we apply these concepts to the existence problems of disjoint cyclic Steiner and Mendelsohn triple systems and the existence of disjoint 1-covering designs. © 1993 John Wiley & Sons, Inc.     

Polynomial time approximation schemes for general multiprocessor job shop scheduling

We study preemptive and non-preemptive versions of the general multiprocessor job shop scheduling problem: Given a set of n tasks each consisting of at most μ ordered operations that can be processed on different (possibly all) subsets of m machines with different processing times, compute a schedule (preemptive or non-preemptive, depending on the model) with minimum makespan where operations belonging to the same task have to be scheduled according to the specified order. We propose algorithms for both preemptive and non-preemptive variants of this problem that compute approximate solutions of any positive ε accuracy and run in O(n) time for any fixed values of m, μ, and ε. These results include (as special cases) many recent developments on polynomial time approximation schemes for scheduling jobs on unrelated machines, multiprocessor tasks, and classical open, flow and job shops.     

New steps in the amazing world of sequences and schedules

In this paper we consider classical shop problems:n jobs have to be processed onm machines. The processing timep _i,j of jobi on machinej is given for all operations (i, j). Each machine can process at most one job at a time and each job can be processed at most on one machine at a given time. The machine orders are fixed (job-shop) or arbitrary (open-shop). We have to determine a feasible combination of machine and job orders, a so-called sequence, which minimizes the makespan. We introduce a partial order on the set of sequences with the property that there exists at least one optimal sequence in the set of minimal elements of this partial order independent of the given processing times. The set of minimal elements (set of irreducible sequences) can be in detail described in the case of the two machine open-shop problem. The cardinality is calculated. We will show which sequences are generated by the well-known polynomial algorithms for the construction of optimal schedules. Furthermore, we investigate the problemO∥C _max on an operation set with spanning tree structure. Supported by Deutsche Forschungsgemeinschaft, Project ScheMA     

Preemptive scheduling with rejection

 We consider the problem of preemptively scheduling a set of n jobs on m (identical, uniformly related, or unrelated) parallel machines. The scheduler may reject a subset of the jobs and thereby incur job-dependent penalties for each rejected job, and he must construct a schedule for the remaining jobs so as to optimize the preemptive makespan on the m machines plus the sum of the penalties of the jobs rejected. We provide a complete classification of these scheduling problems with respect to complexity and approximability. Our main results are on the variant with an arbitrary number of unrelated machines. This variant is APX-hard, and we design a 1.58-approximation algorithm for it. All other considered variants are weakly -hard, and we provide fully polynomial time approximation schemes for them. Finally, we argue that our results for unrelated machines can be carried over to the corresponding preemptive open shop scheduling problem with rejection. Received: October 30, 2000 / Accepted: September 26, 2001 Published online: September 5, 2002 Key words. scheduling – preemption – approximation algorithm – worst case ratio – computational complexity – in-approximability Supported in part by the EU Thematic Network APPOL, Approximation and Online Algorithms, IST-1999-14084 Supported by the START program Y43-MAT of the Austrian Ministry of Science.     

Best Approximation with Linear Constraints: A Model Example

We consider best approximation in L_p( ), 1 ≤ p ≤ ∞, by means of entire functions y of exponential type subject to additional constraints Γ_j(y) = 0, j = 1, ..., K. Here Γ_j are (unbounded) linear functionals of the form Γ_j(y) = Dⁿy(s_j) − ∑ a_kD^ky(s_j) where s_j are fixed points.     

Preemptive scheduling of equal length jobs with release dates on two uniform parallel machines

We consider a problem of scheduling n jobs on two uniform parallel machines. For each job we are given its release date when the job becomes available for processing. All jobs have equal processing requirements. Preemptions are allowed. The objective is to find a schedule minimizing total completion time. We suggest an O(n³) algorithm to solve this problem.     

Competitive Algorithms for Relaxed List Update and Multilevel Caching

We study relaxed list update problem (RLUP), in which access requests are made to items stored in a list. The cost to access the jth item x_j is c_j, where c_i ≤ c_{i + 1} for all i. After the access, x_j can be repeatedly swapped, at no cost, with any item that precedes it in the list. This problem was introduced by Aggarwal et al. (1987, “Proc. 19th Symp. Theory of Computing,” pp. 305–313) as a model for the management of hierarchical memory that consists of a number of caches of increasing size and access time. They also proved that a version of LRU is C-competitive, for some C, for a restricted class of cost functions. We give an efficient offline algorithm that computes the optimal strategy for RLUP. We also show an elegant characterization of work functions for RLUP. We prove that move-to-front (MTF) is optimally competitive for RLUP with any cost function. An interesting feature of the proof is that it does not involve any estimates on the competitive ratio. Finally, we give a lower bound on the competitive ratio of online algorithms for RLUP.     

Efficient scheduling algorithms for a single batch processing machine

Scheduling problems of a batch processing machine are solved by efficient algorithms. On a batch processing machine, multiple jobs can be processed simultaneously in a batch form. We call the number of jobs in the batch the batch size, which can be any integer between 1 and k, a predetermined integer of the maximum batch size. The process time of a batch is constant and independent of the batch size. Preemption is not allowed. Given n jobs with release times r₁ and due dates d_i, i = 1…., n, we give efficient algorithms to find a feasible schedule, if any, which minimizes the final completion time under the assumption such that for r_i > r_j, d_i ⩾ d_j. Some industrial applications are discussed.