A PTAS for Semiconductor Burn-in Scheduling |
| |
| Authors: | Xiaotie?Deng Haodi?Feng Email author" target="_blank">Guojun?LiEmail author Benyun?Shi |
| |
| Institution: | (1) Department of Computer Science, City University of Hong Kong, Hong Kong, China;(2) School of Computer Science and Technology, Shandong University, Jinan, 250100, China;(3) School of Mathematics and System Science, Shandong University, Jinan, 250100, China;(4) Institute of Software, Chinese Academy of Sciences, Beijing, 100080, China |
| |
| 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.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. |
| |
| Keywords: | approximation algorithm batch processing release date geometric rounding time stretching |
| 本文献已被 SpringerLink 等数据库收录！ |
|
