Please use this identifier to cite or link to this item:
Title: A hybrid evolutionary approach for heterogeneous multiprocessor scheduling
Authors: Goh, C.K.
Teoh, E.J.
Tan, K.C. 
Keywords: Heterogeneous
Hybrid evolutionary algorithm
Local search
Multiprocessor scheduling
Issue Date: 2009
Citation: Goh, C.K., Teoh, E.J., Tan, K.C. (2009). A hybrid evolutionary approach for heterogeneous multiprocessor scheduling. Soft Computing 13 (8-9) : 833-846. ScholarBank@NUS Repository.
Abstract: This article investigates the assignment of tasks with interdependencies in a heterogeneous multiprocessor environment; specific to this problem, task execution time varies depending on the nature of the tasks as well as with the processing element assigned. The solution to this heterogeneous multiprocessor scheduling problem involves the optimization of complete task assignments and processing order between the assigned processors to arrive at a minimum makespan, subject to a precedence constraint. To solve an NP-hard combinatorial optimization problem, as is typified by this problem, this paper presents a hybrid evolutionary algorithm that incorporates two local search heuristics, which exploit the intrinsic structure of the solution, as well as through the use of specialized genetic operators to promote exploration of the search space. The effectiveness and contribution of the proposed features are subsequently validated on a set of benchmark problems characterized by different degrees of communication times, task, and processor heterogeneities. Preliminary results from simulations demonstrate the effectiveness of the proposed algorithm in finding useful schedule sets based on the set of new benchmark problems. © Springer-Verlag 2008.
Source Title: Soft Computing
ISSN: 14327643
DOI: 10.1007/s00500-008-0356-2
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.