POLYNOMIAL APPROXIMATION SCHEMES FOR THE MAX-MIN ALLOCATION PROBLEM UNDER A GRADE OF SERVICE PROVISION

The max-min allocation problem under a grade of service provision is defined in the following model: given a set M of m parallel machines and a set J of n jobs, where machines and jobs are all entitled to different levels of grade of service (GoS), each job J(j). J has its processing time p(j) and it can only be allocated to a machine M-i whose GoS level is no more than the GoS level the job J(j) has. The goal is to allocate all jobs to m machines to maximize the minimum machine load among these m machines, where the machine load of Mi is the sum of the processing time of jobs executed on Mi. The best known approximation algorithm [4] to solve this problem produces an allocation in which the minimum machine completion time is at least Omega (log log log m/log log m) of the optimal value. In this paper, we respectively present four approximation schemes to solve this problem and its two special versions: (1) a polynomial time approximation scheme (PTAS) with a running time O(mn (O)(1\epsilon(2))) for the general version, where epsilon > 0; (2) a PTAS and a fully polynomial time pproximation scheme (FPTAS) with the running time O(n) for the version where the number m of machines is fixed; (3) a PTAS with the running time O(n) for the version where the number of GoS levels is bounded by k.