View Related Documents

Abstract

In this paper a polynomial time approximation scheme, PTAS for short, is presented for the problem of scheduling jobs in a batch processing system. Each job has a pre-defined release date, which indicates when the job is available, and a pre-defined burn-in time, which is the least time needed for processing the job. At one time, at most B jobs can be processed together, where B is a pre-given number. No preemption is permitted.

Keywords  approximation algorithm - batch processing - release date - geometric rounding - time stretching

Research supported in part by an RGC CERG grant [CityU 1081/02E] and a grant from CityU [7001347].
Supported by the fund from NSFC under grant numbers 10271065 and 60373025.

Fulltext Preview

Image of the first page of the fulltext document