Abstract: An algorithm is proposed for scheduling dependent tasks in time-varying heterogeneous multiprocessor systems, in which computational power and links between processors are allowed to change over time. Link contention is considered in the multiprocessor scheduling problem. A linear switching-state space-modeling paradigm is introduced to enable theoretical analysis from a system engineering perspective. Theoretical analysis of this model shows its robustness against changes in processing power and link failure. The proposed algorithm uses a fuzzy decision-making procedure to handle changes in the multiprocessor system. The efficiency of the proposed algorithm is illustrated by several random experiments and comparison against a recent benchmark approach. The results show up to 18% average improvement in makespan, especially for larger scale systems.

Key words: Dynamic task scheduling, Fuzzy logic, Genetic algorithms, Unstructured environment, Linear switching state space

An erratum to this article can be found at doi:10.1631/jzus.C13e0204

Please provide your name, email address and a comment

Your Name: Affili: E-Mail Address:

Comment (Please comment in English):


Verification Code(click to change a pic):