A PTAS for Semiconductor Burn-in Scheduling

Author: Deng Xiaotie   Feng Haodi   Li Guojun   Shi Benyun  

Publisher: Springer Publishing Company

ISSN: 1382-6905

Source: Journal of Combinatorial Optimization, Vol.9, Iss.1, 2005-02, pp. : 5-17

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

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.