POLYNOMIAL APPROXIMATION SCHEMES FORTHE MAX-MIN ALLOCATION PROBLEM UNDERA GRADE OF SERVICE PROVISION

摘要

The max-min allocation problem under a grade of service provision is defined in the fol-lowing model: given a set .A.4 of m parallel machines and a set J of n jobs, where machinesand jobs are all entitled to different levels of grade of service (GoS), each job J3 E J hasits processing time pj and it can only be allocated to a machine Mi whose GoS level is nomore than the GoS level the job Jj has. The goal is to allocate all jobs to m machines tomaximize the minimum machine load among these m machines, where the machine loadof Mi is the sum of the processing time of jobs executed on Mi. The best known approxi-mation algorithm [4] to solve this problem produces an allocation in which the minimummachine completion time is at least 1 (log log log m/ log log m) of the optimal value. In this paper, we respectively present four approximation schemes to solve this prob-lem and its two special versions: (1) a polynomial time approximation scheme (PTAS) with a running time 0(mn°(;12-)) for the general version, where E > 0; (2) a PTAS anda fully polynomial time approximation scheme (FPTAS) with the running time 0(n) forthe version where the number m of machines is fixed; (3) a PTAS with the running time0(n) for the version where the number of GoS levels is bounded by k.