Title: Scheduling of variable-time jobs for distributed systems with heterogeneous processor cardinality

Authors: Jan-Jan Wu; Hung-Jui Chang; Yu-Fan Ho; Pangfeng Liu

Addresses: Institute of Information Science, Research Center for Information Technology Innovation, Academia Sinica, Taipei 115, Taiwan. ' Department of Computer Science and Information Engineering, National Taiwan University, Taipei 106, Taiwan. ' Department of Computer Science and Information Engineering, National Taiwan University, Taipei 106, Taiwan. ' Department of Computer Science and Information Engineering, National Taiwan University, Taipei 106, Taiwan

Abstract: This paper proposes scheduling algorithms for assigning jobs with different release time and execution time to machines with heterogeneous processor cardinality. We show that this scheduling problem is NP-complete, and propose dynamic programming to find the optimal schedules. Since the dynamic programming is time-consuming, we propose techniques that improve the efficiency of the dynamic programming. We also propose heuristic algorithms for this scheduling problem. Experimental results demonstrate that some of the heuristics not only compute the answer efficiently but also provide good solutions.

Keywords: job scheduling; variable-time jobs; distributed systems; dynamic programming; job assignment; release times; execution times; heterogeneous processor cardinality.

DOI: 10.1504/IJAHUC.2012.048262

International Journal of Ad Hoc and Ubiquitous Computing, 2012 Vol.10 No.2, pp.112 - 121

Published online: 30 Jul 2012 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article