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.
We consider the following scheduling problem. There are m parallel machines and n independent jobs. Each job is to be assigned to one of the machines. The processing of job j on machine i requires time pij. 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 unless P = NP. We finally obtain a complexity classification for all special cases with a fixed number of processing times. The problem of scheduling a set of n jobs on m identical machines so as to minimize the makespan time is perhaps the most well-studied problem in the theory of approximation algorithms for NP-hard optimization problems. In this paper the strongest possible type of result for this problem, a polynomial approximation scheme, is presented. More precisely, for each e, an algorithm that runs in time O (( n e) 1 e 2 ) and has relative error at most e is given. In addition, more practical algorithms for e = 1 5 + 2 - k and e = 1 6 + 2 - k , which have running times O ( n ( k + log n )) and O ( n ( km 4 + log n )) are presented. The techniques of analysis used in proving these results are extremely simple, especially in comparison with the baroque weighting techniques used previously. The scheme is based on a new approach to constructing approximation algorithms, which is called dual approximation algorithms, where the aim is to find superoptimal, but infeasible, solutions, and the performance is measured by the degree of infeasibility allowed. This notion should find wide applicability in its own right and should be considered for any optimization problem where traditional approximation algorithms have been particularly elusive. 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. This paper considers the problem of nonpreemptively scheduling n independent jobs on m identical, parallel processors with the object of minimizing the “makespan”, or completion time for the entire set of jobs. Coffman, Garey, and Johnson [SIAM J. Comput., 7 (1978), pp. 1–17] described an algorithm MULTIFIT which has a considerably better worst case performance than the largest processing time first algorithm. In this paper we tighten the bounds obtained in that paper on the worst case behavior of this algorithm by giving an example showing that it may be as bad as 13 11 and proving that it can be no worse than 6 5. We consider one of the basic, well-studied problems of scheduling theory, that of nonpreemptively scheduling n independent tasks on m identical, parallel processors with the objective of minimizing the “makespan,” i.e., the total timespan required to process all the given tasks. Because this problem is @math -complete and apparently intractable in general, much effort has been directed toward devising fast algorithms which find near-optimal schedules. The well-known LPT (Largest Processing Time first) algorithm always finds a schedule having makespan within @math of the minimum possible makespan, and this is the best such bound satisfied by any previously published fast algorithm. We describe a comparably fast algorithm, based on techniques from “bin-packing,” which we prove satisfies a bound of 1.220. On the basis of exact upper bounds determined for each @math , we conjecture that the best possible general bound for our algorithm is actually @math . Consideration is given to the problem of nonpreemptively scheduling a set of N independent tasks to a system of M identical processors, with the objective to minimize the overall finish time. Since this problem is known to be NP-Hard, and hence unlikely to permit an efficient solution procedure, heuristic algorithms are studied in an effort to provide near-optimal results. Worst-case analysis is used to gauge the worth of a scheduling procedure. For a particular algorithm, an upper bound is sought for the length of its schedule expressed relative to an optimal assignment of tasks to processors. Departing from more traditional schemes of only determining an algorithm's worst-case performance bound, the work contained herein focuses on modifying a scheduling heuristic for "bad" regions of the input space, thereby improving its worst-case bound. It is shown that rather simple alterations, having little effect on the run-time of an algorithm, may guarantee a significantly better behavior. The O 1-INTERCHANGE heuristic is improved so that, while its time complexity is still O(NlogM), its worst-case performance bound is reduced from 2 to 4 3 times optimal. The familiar LPT algorithm is altered so that, while its time complexity is still O(NlogN), its worst-case bound is reduced from 4 3 to 5 4 times optimal. The major effort of this research is devoted to proving that the MULTIFIT heuristic can be modified, without increasing its time complexity from O(NlogN), so that its worst-case performance bound is reduced from some value in the range 13 11, 6 5 to 72 61 times optimal, a better bound as of this writing than that yielded by any other known polynomial-time algorithm. The following job sequencing problems are studied: (i) single processor job sequencing with deadlines, (ii) job sequencing on m -identical processors to minimize finish time and related problems, (iii) job sequencing on 2-identical processors to minimize weighted mean flow time. Dynamic programming type algorithms are presented to obtain optimal solutions to these problems, and three general techniques are presented to obtain approximate solutions for optimization problems solvable in this way. The techniques are applied to the problems above to obtain polynomial time algorithms that generate “good” approximate solutions. 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... We design a 1.75-approximation algorithm for a special case of scheduling parallel machines to minimize the makespan, namely the case where each job can be assigned to at most two machines with the same processing time on either machine. (This is a special case of so-called restricted assignment, where the set of eligible machines can be arbitrary for each job.) We also show that even for this special case it is NP-hart to compute better than 1.5 approximation. This is the first improvement of the approximation ratio 2 of Lenstra, Shmoys, and Tardos [Approximation algorithms for scheduling unrelated parallel machines, Math. Program. 46:259--271, 1990], for any special case with unbounded number of machines. Our lower bound yields the same ratio as their bound which works for restricted assignment, and which is still the state-of-the-art lower bound even for the most general case. An apparatus for generating sparks over a selected area to be used for theatrical effects. Met al wire having a diameter in the range of 0.020-0.125 inches is provided by two, independent supply sources. Each wire supply source is coupled to a wire guide which imposes synchronous, linear movement to each wire source at a selected rate. Each wire source is coupled to a tip assembly which places the terminus of each wire source adjacent one another. The positive and negative electrodes of a direct current power source are electrically connected to a respective terminus of each of the pair of wire sources, the output of the direct current power source is amplified to voltage sufficient to atomize the wire when the power source is short circuited. The atomization of the wire results in the production of heated, met allic particles simulating generated sparks. A source of compressed air is disposed adjacent the point of atomization. The atomized particles are disseminated across an area determined by the force imposed thereon by the compressed air.