A comparison of multiprocessor task scheduling algorithms with communication costs

作     者：Hwang, Reakook Gen, Mitsuo Katayama, Hiroshi 

作者机构：Waseda Univ Grad Sch Sci & Engn Dept Ind & Management Syst Engn Tokyo 1698555 Japan Waseda Univ Grad Sch Informat Prod & Syst Dept Informat Architecture Kitakyushu Fukuoka 8080135 Japan 

出 版 物：《COMPUTERS & OPERATIONS RESEARCH》 (计算机与运筹学研究)

年 卷 期：2008年第35卷第3期

页      面：976-993页

核心收录：

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

主　　题：multiprocessor task scheduling genetic algorithm priority-based multi-chromosome (PMC) 

摘      要：Both parallel and distributed network environment systems play a vital role in the improvement of high performance computing. Of primary concern when analyzing these systems is multiprocessor task scheduling. Therefore, this paper addresses the challenge of multiprocessor task scheduling parallel programs, represented as directed acyclic task graph (DAG), forexecution on multiprocessors with communication costs. Moreover, we investigate an alternative paradigm, where genetic algorithms (GAs) have recently received p much attention. which is a class of robust stochastic search algorithms for various combinatorial optimization problems. We design the new encoding mechanism with a multi-functional chromosome that uses the priority representation-the so-called priority-based multi-chromosome (PMC). PMC can efficiently represent a task schedule and assign tasks to processors. The proposed priority-based GA has show effective performance in various parallel environments for scheduling methods. (c) 2006 Elsevier Ltd. All rights reserved.