A comparison of multiprocessor task scheduling algorithms with communication costs

Reakook Hwang, Mitsuo Gen*, Hiroshi Katayama

*Corresponding author for this work

    Research output: Contribution to journalArticlepeer-review

    87 Citations (Scopus)


    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), for execution on multiprocessors with communication costs. Moreover, we investigate an alternative paradigm, where genetic algorithms (GAs) have recently received 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.

    Original languageEnglish
    Pages (from-to)976-993
    Number of pages18
    JournalComputers and Operations Research
    Issue number3
    Publication statusPublished - 2008 Mar


    • Genetic algorithm
    • Multiprocessor task scheduling
    • Priority-based multi-chromosome (PMC)

    ASJC Scopus subject areas

    • Information Systems and Management
    • Management Science and Operations Research
    • Applied Mathematics
    • Modelling and Simulation
    • Transportation


    Dive into the research topics of 'A comparison of multiprocessor task scheduling algorithms with communication costs'. Together they form a unique fingerprint.

    Cite this