loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
2009 International Conference on Parallel and Distributed Computing, Applications and Technologies
A Generalized Multi-Organization Scheduling on Unrelated Parallel Machines
Higashi Hiroshima, Japan
December 08-December 11
ISBN: 978-0-7695-3914-0
We consider the parallel computing environment where m organizations provide machines and several jobs to be executed. While cooperation of organizations is required to minimize the global makespan, each organization also expects the faster completion of its own jobs primarily and thus it is not necessarily cooperative. To handle the situations, we formulate the \alpha-cooperative multi-organization scheduling problem (\alpha-MOSP), where \alpha>= 1 is a parameter representing the degree of cooperativeness.\alpha-MOSP minimizes the makespan under the cooperation constraint that each organization does not allow the completion time of its own jobs to be delayed \alpha times of that in the case where those jobs are executed by itself. In this paper, we aim to reveal the relation between the makespan and the degree of cooperativeness. First, we investigate the relation between \alpha and the quality of the global makespan. For \alpha=1 (i. e., each organization never sacrifices its completion time), we show an instance where the cooperation constraint degrades the optimal makespan by $m$ times. In contrast, for \alpha>1, we can construct an algorithm transforming any unconstrained schedule to one satisfying the cooperation constraint. This algorithm bounds the degradation ratio by \alpha / (\alpha - 1), which implies that weak cooperation improves the makespan dramatically. Second, we study the complexity of \alpha-MOSP. We show its strongly NP-hardness and inapproximability for the approximation factor less than max{(\alpha + 1)/\alpha, 3/2}. We also show the hardness of transformation: Even if an optimal schedule under no cooperation constraint is given, no polynomial-time algorithm finds an optimal schedule for \alpha-MOSP. This result is a witness for inexistence of general polynomial-time transformation algorithms that preserve the approximation ratio.
Index Terms:
heterogeneous parallel computing environments, scheduling algorithm, approximation algorithm, computation complexity
Citation:
Fukuhito Ooshita, Tomoko Izumi, Taisuke Izumi, "A Generalized Multi-Organization Scheduling on Unrelated Parallel Machines," pdcat, pp.26-33, 2009 International Conference on Parallel and Distributed Computing, Applications and Technologies, 2009
Usage of this product signifies your acceptance of the Terms of Use.