Efficient Job Scheduling Algorithms with Multi-Type Contentions

Zhenming Chen (), Vikas Singh () and Jinhui Xu ()
Additional contact information
Zhenming Chen: State University of New York at Buffalo
Vikas Singh: State University of New York at Buffalo
Jinhui Xu: State University of New York at Buffalo

Journal of Combinatorial Optimization, 2005, vol. 10, issue 2, No 5, 179-197

Abstract: Abstract In this paper, we consider an interesting generalization of the classic job scheduling problem in which each job needs to compete not only for machines but also for other types of resources. The contentions among jobs for machines and for resources could interfere with each other, which complicates the problem dramatically. We present a family of approximation algorithms for solving several variants of the problem by using a generic algorithmic framework. Our algorithms achieve a constant approximation ratio (i.e., 3) when there is only one type of resources or certain dependency relation exists among multiple types of resources. When the r resources are unrelated, the approximation ratio of our algorithm becomes k+2, where k≤ r is a constant depending on the problem instance. As an application, we also show that our techniques can be easily applied to optical burst switching (OBS) networks to design more efficient wavelength scheduling algorithms.

Keywords: job scheduling; multi-type contentions; approximation algorithm; OBS networks (search for similar items in EconPapers)
Date: 2005
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-005-2272-z 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:10:y:2005:i:2:d:10.1007_s10878-005-2272-z

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

DOI: 10.1007/s10878-005-2272-z

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 ().