NDLI: A Multiple Priority Queueing Genetic Algorithm for Task Scheduling on Heterogeneous Computing Systems

Content Provider	IEEE Xplore Digital Library
Author	Yuming Xu Kenli Li Tung Truong Khac Meikang Qiu
Copyright Year	2012
Abstract	On the distributed or parallel heterogeneous computing systems, an application is usually decomposed into several independent and/or interdependent sets of cooperating subtasks and assigned to a set of available processors for execution. Heuristic-based task scheduling algorithms consist of the two typical phases of task prioritization and processor selection. However, heuristic-based task scheduling algorithms produce a different makespan (completion time /schedule length) using the different task prioritization on a distributed or parallel heterogeneous computing systems. Therefore, the role of a good scheduling algorithm is to efficiently assign each subtask to a priority depending on the resources needed to minimize makespan. In this paper, a multiple priority queueing genetic algorithm (MPQGA) for task scheduling on heterogeneous computing systems is proposed. The basic idea of our approach is to exploit the advantages of both evolutionary and heuristic based algorithms while avoiding their drawbacks. Our algorithm incorporates a genetic algorithm (GA) approach to assign priority for each subtask while using a heuristic based heterogeneous earliest finish time (HEFT) approach to search for a solution for mapping subtasks to processors. The software simulation results, over a large set of randomly generated graphs as well as graphs for real-world problems with various characteristics, show that the makespan is increased when the number of nodes or communication to computation ratios (CCR) increased and decreased with the increasing parallelism or number of available processors. The proposed MPQGA algorithm significantly outperforms several related algorithms in terms of the schedule quality. The average makespan reduction is about 5.3 %.
Starting Page	639
Ending Page	646
File Size	328672
Page Count	8
File Format	PDF
ISBN	9781467321648
DOI	10.1109/HPCC.2012.91
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2012-06-25
Publisher Place	United Kingdom
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	makespan genetic algorithm Program processors Scheduling algorithms Heuristic algorithms Scheduling task scheduling priority queueing Biological cells Genetic algorithms
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in