【正文】 ount of resourcesallocated to job j. As a special case, our approach prises linear timeresource tradeofffunctions, where pj(x) = 175。pj ? ajx, aj being the slope of the linear timeresource tradeofffunction, and 175。pj being the default processing time. Notice that our result generalizes the3previous (3 + )approximation of [7] in several directions: They consider the special casek = 1, which can be interpreted as linear timeresource tradeoff functions, and they considera constant number of machines m. Although we obtain the same performance bound, westress that our result relies on a pletely different approach. Also notice that we derivethe first polynomial time approximation algorithms for problems with succinctly encodabletimeresource tradeoff functions, as previous approaches such as [8] generally do not yieldpolynomial time algorithms.Apart from improving previous results in the scheduling context, we would like to stressthat the main contribution of the paper is rather on the methodology side. In fact, we obtainour result by using a mathematical programming formulation that constitutes a relaxationof the problem. This mathematical program is allowed to contain, both in the objectiveand in the constraints, arbitrary polynomial time putable functions. When restricted tolinear timeresource tradeoff functions, for example, this mathematical program is a concaveminimization problem with linear constraints. We show that the solution of the mathematicalprogram is NPhard even for the special case of linear timeresource tradeoff functions.Nevertheless, in general we show that it can be solved with arbitrary precision in polynomialtime。 a result of interest in its own.Moreover, we provide a parametric example to show that our analysis cannot be improvedfurther than a factor of even for linear timeresource tradeoff functions, by showing thatthe allocation of resources that is puted with the mathematical program can indeedprovide the ‘wrong’ answer. The same example shows that it may happen that the schedulingalgorithm we use, based on the resource allocation as suggested by the mathematicalprogram, is a factor 2 away from the optimum.2. Problem definitionLet V = {1, . . . , n} be a set of jobs. Jobs must be processed nonpreemptively on a set of mparallel machines, and the objective is to find a schedule that minimizes the makespan Cmax,that is, the time of the last job pletion. Each job j is assigned to exactly one of themachines, and Vi denotes the set of jobs assigned to machine i, such that V =Si Vi formsa partition of the jobs. During its processing, a job j may be assigned an amount x 2{0, 1, . . . , k} of a discrete resource, for instance personnel, that may speed up its processing.The amount of resources assigned to a job must be constant throughout its processing, and4is restricted to be at most k. If x resources are allocated to a job j, the processing time ofthat job is pjx, x = 0, . . . , k. The global resource constraint now consists of the fact that ina feasible solution, at any time no more than k units of the resource may be consumed bythe schedule. Clearly, we may assume k _ 1 since the problem is trivial otherwise.The actual processing time pjx of a job is puted via time resource tradeoff functionspj( ) : {0, 1, . . . , k} ! Z+. We assume (without loss of generality) that all timeresourcetradeoff functions pj( ) are nonincreasing on their domains, meaning that the more resourcesare allocated to a job, the shorter the processing time, and 175。pj := pj(0) is the defaultprocessing time, j 2 V . We moreover assume that these functions are putable in polynomialtime, that is, there is an algorithm that, for any given value x 2 {0, 1, . . . , k}, returnsthe value pj(x) in time polynomial in the encoding length of the function pj( ) and log k.By definition, we have pjx = pj(x) for all j 2 V and x 2 {0, 1, . . . , k}. We make the seeminglyartificial distinction between pjx and pj(x) only to highlight the possible difference inthe encoding length: All possible processing times of all jobs are given by the values pjx,j 2 V , x = 0, . . . , k. The encoding length of these values is clearly (nk). But all timeresource tradeoff functions pj( ), j 2 V , may in general be encoded more succinctly. Lettingp = maxj2V 175。pj and A be the maximal encoding length of any timeresource tradeofffunction, the encoding length of the problem is O( n log p + nA + log k ). For example, if weassume linear timeresource tradeoff functions where pj(x) = 175。pj ? ajx, the encoding lengthis O( n(log p + log a) + log k ), with a = maxj2V aj .3. Computational ComplexityAs a generalization of the dedicated machine scheduling problem as considered by Kellererand Strusevich [14], it follows that the problem at hand is strongly NPhard. We next derivea stronger result, namely an inapproximability result.Theorem 1 Unless P = NP, there is no approximation algorithm with a performance guaranteesmaller than for scheduling parallel jobs with timeresource tradeoff.Proof. Adapting a proof idea from [8], we use a reduction from the NPplete problemPartition: We are given k integers a1, . . . , ak, withPkj=1 aj = 2B, and we are asked todecide if there exists a subset S _ {1, . . . , k} withPj2S aj = B. We define for each item aj5one job j, to be processed on its individual machine (so m = n), with timeresource tradeofffunction as followspj(x) =(2aj + 1 ? 2x x _ aj ,1 x aj .Moreover, let the availability of the resource be k = B. Obviously, the encoding length ofany timeresource function is in O( log aj ), hence this transformation is polynomial. Now itis easy to see that there exists a partition if and only if the optimal solution for the schedulingproblem has a makespan of 2: Each job j gets assigned exactly aj units of the resource,thus