Fixed-parameter tractability analysis and scheduling are two core domains of combinatorial optimization which led to deep understanding of many important algorithmic questions. However, even though fixed-parameter algorithms are appealing for many reasons, no such algorithms are known for many fundamental scheduling problems. In this paper we present the first fixed-parameter algorithms for classical scheduling problems such as makespan minimization, scheduling with job-dependent cost functions-one important example being weighted flow time-and scheduling with rejection. To this end, we identify crucial parameters that determine the problems' complexity. In particular, we manage to cope with the problem complexity stemming from numeric input values, such as job processing times, which is usually a core bottleneck in the design of fixed-parameter algorithms. We complement our algorithms with W[1]-hardness results showing that for smaller sets of parameters the respective problems do not allow FPT-algorithms. In particular, our positive and negative results for scheduling with rejection explore a research direction proposed by D 'aniel Marx. We hope that our contribution yields a new and fresh perspective on scheduling and fixed-parameter algorithms and will lead to further fruitful interdisciplinary research connecting these two areas.
One very classical scheduling problem studied in this paper is to schedule a set of jobs non-preemptively on a set of @math identical machines, i.e., @math . Research for it dates back to the 1960s when Graham showed that the greedy list scheduling algorithm yields a @math -approximation and a @math -approximation when the jobs are ordered non-decreasingly by length @cite_12 . After a series of improvements @cite_19 @cite_24 @cite_0 @cite_2 , Hochbaum and Shmoys present a polynomial time approximation scheme (PTAS), even if the number of machines is part of the input @cite_21 . On unrelated machines, the problem is @math -hard to approximate with a better factor than @math @cite_13 @cite_22 and there is a 2-approximation algorithm @cite_22 that extends to the generalized assignment problem @cite_32 . For the restricted assignment case, i.e., each job has a fixed processing time and a set of machines where one can assign it to, Svensson @cite_16 gives a polynomial time algorithm that estimates the optimal makespan up to a factor of @math .
@cite_22 @cite_21 @cite_32 @cite_24 @cite_19 @cite_0 @cite_2 @cite_16 @cite_13 @cite_12
1995073517 1923579438 2963782499 2135932424
In 1966, Graham showed that a simple procedure called list scheduling yields a 2-approximation algorithm for the central problem of scheduling precedence constrained jobs on identical machines to minimize makespan. To date this has remained the best algorithm, and whether it can or cannot be improved has become a major open problem in scheduling theory. We address this problem by establishing a quite surprising relation between the approximability of the considered problem and that of scheduling precedence constrained jobs on a single machine to minimize weighted completion time. More specifically, we prove that if the single machine problem is hard to approximate within a factor of @math , then the considered parallel machine problem, even in the case of unit processing times, is hard to approximate within a factor of @math , where @math tends to 0 as @math tends to 0. Combining this with Bansal and Khot's recent hardness result for the single machine problem gives that it is NP-hard to improve upon the approximation ratio obtained by Graham, assuming a new variant of the unique games conjecture. The main aim of this note is to show that a polynomial-time algorithm for the scheduling problem 1|r j ; p j = p| ∑ Uj given by Carlier in (1981) is incorrect. In this problem we are given n jobs with release times and deadlines. All jobs have the same processing time p. The objective is to find a non-preemptive schedule that maximizes the number of jobs completed by their deadlines. The feasibility version of this problem, where we ask whether all jobs can meet their deadlines, has been studied thoroughly. Polynomial-time algorithms for this version were first found, independently, by Simons (1978) and Carlier (1981). A faster algorithm, with running time O(n log n), was subsequently given by (1981). The elegant feasibility algorithm of Carlier (1981) is based on dynamic programming and it processes jobs from left to right on the time-axis. For each time t, it constructs a partial schedule with jobs that complete at or before time t. Carlier also attempted to apply the same technique to design a polynomial-time algorithm for the maximization version, 1|r j ; p j = p| ∑ Uj , and claimed an O(n3 log n)-time algorithm. His result is now widely cited in the literature. We show, however, that this algorithm is not correct, by giving an instance on which it produces a sub-optimal schedule. Our counter-example can be, in fact, extended to support a broader claim, namely that even the general approach from Carlier (1981) cannot yield a polynomial-time algorithm. By this general approach we mean a class of algorithms that processes the input from left to right and make decisions based on the deadline ordering, and not their exact values. The question remains as to how efficiently can we solve the scheduling problem 1|r j ; p j = p| ∑ Uj . Baptiste (1999) gave an O(n7)-time algorithm for the more general version of this problem where jobs have weights. We show how to modify his algorithm to obtain a faster, O(n5)-time algorithm for the non-weighted case. These last two results are discussed only briefly in this note. The complete proofs can be found in the full version of this paper, see (2004). We consider the classical scheduling problem on parallel identical machines to minimize the makespan. There is a long history of studies on this problem, focusing on exact and approximation algorithms, and it is thus natural to consider whether these algorithms are best possible in terms of the running time. Under the Exponential Time Hypothesis (ETH), we achieve the following results in this paper: • The scheduling problem on a constant number m of identical machines, which is denoted as Pm||Cmax, is known to admit a fully polynomial time approximation scheme (FPTAS) of running time O(n) + (1 e)O(m) (indeed, the algorithm works for an even more general problem where machines are unrelated). We prove this algorithm is essentially the best possible in the sense that a (1 e)O(m1-δ) + nO(1) time FPTAS for any δ > 0 implies that ETH fails. • The scheduling problem on an arbitrary number of identical machines, which is denoted as P||Cmax, is known to admit a polynomial time approximation scheme (PTAS) of running time 2O(1 e2 log3(1 e))+nO(1). We prove this algorithm is nearly optimal in the sense that a 2O((1 e)1-δ+nO(1) time PTAS for any δ > 0 implies that ETH fails, leaving a small room for improvement. In addition, we also consider exact algorithms for the scheduling problem and prove the following result: • The traditional dynamic programming algorithm for P||Cmax is known to run in 2O(n) time. We prove this is essentially the best possible in the sense that even if we restrict that there are n jobs and the processing time of each job is bounded by O(n), an exact algorithm of running time 22O(n1-δ) for any δ > 0 implies that ETH fails. To obtain these results we will provide two new reductions from 3SAT, one for Pm||Cmax and another for P||Cmax. Indeed, the new reductions explore the structure of scheduling problems and can also lead to other interesting results. For example, using the framework of our reduction for P||Cmax, [5] are able to prove the APX-hardness of the scheduling problem in which the matrix of job processing times P = (pij)mxn is of rank 3, solving the open problem mentioned in [2]. One of the classic results in scheduling theory is the @math -approximation algorithm by Lenstra, Shmoys, and Tardos for the problem of scheduling jobs to minimize makespan on unrelated machines; i.e., job @math requires time @math if processed on machine @math . More than two decades after its introduction it is still the algorithm of choice even in the restricted model where processing times are of the form @math . This problem, also known as the restricted assignment problem, is NP-hard to approximate within a factor less than @math , which is also the best known lower bound for the general version. Our main result is a polynomial time algorithm that estimates the optimal makespan of the restricted assignment problem within a factor @math , where @math is an arbitrarily small constant. The result is obtained by upper bounding the integrality gap of a certain strong linear program, known as the configuration LP, that was previously successfu...