A polynomial time approximation scheme for general multiprocessor job scheduling

Citation
Jn. Chen et A. Miranda, A polynomial time approximation scheme for general multiprocessor job scheduling, SIAM J COMP, 31(1), 2001, pp. 1-17
Citations number
25
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Computer Science & Engineering
Journal title
SIAM JOURNAL ON COMPUTING
ISSN journal
0097-5397 → ACNP
Volume
31
Issue
1
Year of publication
2001
Pages
1 - 17
Database
ISI
SICI code
0097-5397(20010729)31:1<1:APTASF>2.0.ZU;2-W
Abstract
Recently, there hav been considerable interests in the multiprocessor job s cheduling problem, in which a job can be processed in parallel on one of se veral alternative subsets of processors. In this paper, a polynomial time a pproximation scheme is presented for the problem in which the number of pro cessors in the system is a fixed constant. This result is the best possible because of the strong NP-hardness of the problem and is a significant impr ovement over the past results: the best previous result was an approximatio n algorithm of ratio 7/6 + epsilon for 3-processor systems based on Goemans 's algorithm for a restricted version of the problem.