An Efficient Genetic Algorithm for Task Scheduling on Heterogeneous Computing Systems Based on TRIZ

  • سال انتشار: 1397
  • محل انتشار: مجله پیشرفت در تحقیقات کامپیوتری، دوره: 9، شماره: 3
  • کد COI اختصاصی: JR_JACR-9-3_007
  • زبان مقاله: انگلیسی
  • تعداد مشاهده: 316
دانلود فایل این مقاله

نویسندگان

Mehdi Akbari

Faculty of Computer Engineering, Najafabad Branch, Islamic Azad University, Najafabad, Iran

چکیده

An efficient assignment and scheduling of tasks is one of the key elements in effective utilization of heterogeneous multiprocessor systems. The task scheduling problem has been proven to be NP-hard is the reason why we used meta-heuristic methods for finding a suboptimal schedule. In this paper we proposed a new approach using TRIZ (specially 40 inventive principles). The basic idea of this approach is to exploit the advantages of heuristic-based algorithms to reduce space search and the time needed to find good solutions. The proposed algorithm improves the performance of genetic algorithm through significant changes in its genetic functions and introduction of new operators that guarantee sample variety and consistent coverage of the whole space. The achieved results of running this algorithm on the graphs of real-world applications and random graphs in heterogeneous computing systems with a wide range of characteristics, indicated significant improvements of efficiency of the proposed algorithm compared with other task scheduling algorithms. Although the proposed algorithm needs lower repetitions than their genetic counterparts, it needs high frequency of repetition to produce the desired answer. This is a drawback for this algorithm compared to heuristic algorithms such as CPOP and HEFT.

کلیدواژه ها

Genetic Algorithms, Task Scheduling, TRIZ, Meta Heuristic

اطلاعات بیشتر در مورد COI

COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.

کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.