We study resource constrained scheduling problems where the objective is to compute feasible preemptive schedules minimizing the makespan and using no more resources than what are available. We present approximation schemes along with some inapproximability results showing how the approximability of the problem changes in terms of the number of resources. The results are based on linear programming formulations (though with exponentially many variables) and some interesting connections between resource constrained scheduling and (multidimensional, multiple-choice, and cardinality constrained) variants of the classical knapsack problem. In order to prove the results we generalize a method by Grigoriadis et al. for the max-min resource sharing problem to the case with weak approximate block solvers (i.e., with only constant, logarithmic, or even worse approximation ratios). Finally, we present applications of the above results in fractional graph coloring and multiprocessor task scheduling.

We study the problem of scheduling n independent tasks on a set of m parallel processors, where the execution time of a task is a function of the subset of processors assigned to the task. For any fixed m, we propose a fully polynomial approximation scheme that for any fixed $\epsilon > 0$ finds a preemptive schedule of length at most $(1+\epsilon)$ times the optimum in $O(n)$ time. We also discuss the nonpreemptive variant of the problem, and present for any fixed m a polynomial approximation scheme that computes an approximate solution of any fixed accuracy in linear time. In terms of the running time, this linear complexity bound gives a substantial improvement of the best previously known polynomial bound [J. Chen and A. Miranda, SIAM J. Comput., 31 (2001), pp. 1--17].

We consider the problem of scheduling n independent jobs on m unrelated parallel machines.Each job has to be processed by exactly one machine, processing job j on machine i requires p;j time units, and the objective is to minimize the makespan, i.e. the maximum job completion time.We focus on the caSe when n is fixed and develop a fully polynomial approximation scheme whose running time depends only linearly on n.In the second half of the paper we extend this result to a variant of the problem, where processing job j on machine i also incurs a cost of cij, and thus there are two optimization criteria: makespan and cost.We show that for any fixed m, there is a fully polynomial approximation scheme that, given values T and C, computes for any fixed E > 0 a schedule in O(n) time with makespan at most (1 + e)T and cost at most (1 + e)C, if there exists a schedule of makespan T and cost C.

Let Y be a convex set in R/sup k/ defined by polynomial inequalities and equations of degree at most d/spl ges/2 with integer coefficients of binary length l. We show that if Y/spl cap/Z/sup k//spl ne//spl theta/, then Y contains an integral point of binary length ld/sup O/((k/sup 4/)). For fixed k, our bound implies a polynomial-time algorithm for computing an integral point y/spl isin/Y. In particular, we extend Lenstra's theorem on the polynomial-time solvability of linear integer programming in fixed dimension to semidefinite integer programming.