A hybrid evolutionary approach for heterogeneous multiprocessor scheduling

作     者：Goh, C. K. Teoh, E. J. Tan, K. C. 

作者机构：Data Storage Inst Spintron Media & Interface Div Singapore 117608 Singapore Natl Univ Singapore Dept Elect & Comp Engn Singapore 117576 Singapore 

出 版 物：《SOFT COMPUTING》 (Soft Comput.)

年 卷 期：2009年第13卷第8-9期

页      面：833-846页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Multiprocessor scheduling Heterogeneous Hybrid evolutionary algorithm Local search Precedence 

摘      要：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.