A simple linear time approximation algorithm for multi-processor job scheduling on four processors

Jingui Huang, Jianer Chen (), Songqiao Chen and Jianxin Wang
Additional contact information
Jingui Huang: Central South University
Jianer Chen: Central South University
Songqiao Chen: Central South University
Jianxin Wang: Central South University

Journal of Combinatorial Optimization, 2007, vol. 13, issue 1, No 3, 33-45

Abstract: Abstract Multiprocessor job scheduling problem has become increasingly interesting, for both theoretical study and practical applications. Theoretical study of the problem has made significant progress recently, which, however, seems not to imply practical algorithms for the problem, yet. Practical algorithms have been developed only for systems with three processors and the techniques seem difficult to extend to systems with more than three processors. This paper offers new observations and introduces new techniques for the multiprocessor job scheduling problem on systems with four processors. A very simple and practical linear time approximation algorithm of ratio bounded by 1.5 is developed for the multi-processor job scheduling problem P 4|fix|C max, which significantly improves previous results. Our techniques are also useful for multiprocessor job scheduling problems on systems with more than four processors.

Keywords: Multi-processor job scheduling; Approximation algorithm; NP-hard problem (search for similar items in EconPapers)
Date: 2007
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-006-9011-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:13:y:2007:i:1:d:10.1007_s10878-006-9011-y

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-006-9011-y

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().