Efficient Job Scheduling Algorithms with Multi-type Contentions

摘要

In this paper, we consider an interesting generalization of the classic job scheduling problem in which each job needs to compete for not only machines but also other types of resources. The contentions among jobs for machines and 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) if there is only one type of resources or certain dependency relation exists among multiple types of resources. For the case that r unrelated resources are given, 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 for deriving more efficient wavelength scheduling algorithms.