Scheduling of variable–time jobs for distributed systems with heterogeneous processor cardinality. (31st July 2012)

• Record Type: Journal Article
• Authors: Wu, Jan–Jan; Chang, Hung–Jui; Ho, Yu–Fan; Liu, Pangfeng
• Is Part Of: International journal of ad hoc and ubiquitous computing. Volume 10:Number 2(2012)
• Page Start: 112
• Page End: 121
• Publication Date: 2012-07-31
• Subjects: job scheduling -- variable–time jobs -- distributed systems -- dynamic programming -- job assignment -- release times -- execution times -- heterogeneous processor cardinality; Ubiquitous computing -- Periodicals; Embedded computer systems -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; Wireless communication systems -- Periodicals; Computer architecture -- Periodicals; 004.2
• Languages: English
• ISSNs: 1743-8225

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.