NDLI: An efficient ACO-based algorithm for scheduling tasks onto dynamically reconfigurable hardware using TSP-likened construction graph

Content Provider	Springer Nature Link
Author	Mollajafari, Morteza Shahhoseini, Hadi Shahriar
Copyright Year	2016
Abstract	Any complex application can be realized as a graph of dependent tasks, and scheduling these tasks onto a limited number of computational resources while satisfying their dependencies is a well-known NP-complete optimization problem. For microprocessor systems, several algorithms have been proposed that can efficiently find suboptimal schedules. A solution for dynamically reconfigurable hardware (DRHW), however, is more complicated, as the time and complexity of reconfiguration has to be scheduled as well. The reconfiguration overhead in these systems is significant, and quickly becomes a crucial factor in real-world applications. In this paper, a meta-heuristic method known as Feasibility Assured TSP-likened Scheduling (FATS) is proposed in which the scheduling problem is translated into a construction graph, similar to Travelling Sales Person (TSP) problem, such that it would be able to benefit from the advantages of Ant Colony Optimization (ACO) algorithm. Moreover, by exploiting such a construction graph, precedence constraints and system limitations are satisfied beforehand, the feasibility of solutions is assured, while avoiding the costly solution repair operations. To demonstrate the performance of the proposed method, it was tested on several synthetic and real-world benchmark task graphs and the results were compared with a selection of classic and state-of-the-art algorithms. A comprehensive set of experiments was performed to evaluate the method in terms of efficiency, execution time, scalability and reliability. In brief, the results of experiments on benchmarks showed that on average FATS outperforms HPSO-GA and BGA by 8.4 % and 12.2 % respectively in terms of the quality of the solutions, and its run-time is far less than the state-of-the-art algorithms. Also, on synthetic graphs the makespan improvements of the solutions generated by FATS and GA over the List scheduler are on average 11.2 % and 6.8 % better respectively; and from the execution-time point of view, our method is 27.37 % faster than GA. Moreover, the results confirm that the proposed method is scalable for large task graphs and its reliability is superior to other compared algorithms.
Starting Page	695
Ending Page	712
Page Count	18
File Format	PDF
ISSN	0924669X
Journal	Applied Intelligence
Volume Number	45
Issue Number	3
e-ISSN	15737497
Language	English
Publisher	Springer US
Publisher Date	2016-04-21
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Ant colony optimization Genetic algorithm List scheduling Reconfigurable computing Travelling sales person Artificial Intelligence (incl. Robotics) Mechanical Engineering Manufacturing, Machines, Tools
Content Type	Text
Resource Type	Article
Subject	Artificial Intelligence

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

Study on hybrid PS-ACO algorithm

Guidance-solution based ant colony optimization for satellite control resource scheduling problem

A link prediction algorithm based on ant colony optimization

Metaheuristic algorithms and probabilistic behaviour: a comprehensive analysis of Ant Colony Optimization and its variants

Dynamic Ant Colony Optimisation

Ant Colony Optimization with Global Pheromone Evaluation for Scheduling a Single Machine

Adaptive and Dynamic Ant Colony Search Algorithm for Optimal Distribution Systems Reinforcement Strategy

Escape planning in realistic fire scenarios with Ant Colony Optimisation

Ant Colony Search Algorithm for Optimal Strategical Planning of Electrical Distribution Systems Expansion

An efficient ACO-based algorithm for scheduling tasks onto dynamically reconfigurable hardware using TSP-likened construction graph

Similar Documents

Study on hybrid PS-ACO algorithm

Guidance-solution based ant colony optimization for satellite control resource scheduling problem

A link prediction algorithm based on ant colony optimization

Metaheuristic algorithms and probabilistic behaviour: a comprehensive analysis of Ant Colony Optimization and its variants

Dynamic Ant Colony Optimisation

Ant Colony Optimization with Global Pheromone Evaluation for Scheduling a Single Machine

Adaptive and Dynamic Ant Colony Search Algorithm for Optimal Distribution Systems Reinforcement Strategy

Escape planning in realistic fire scenarios with Ant Colony Optimisation

Ant Colony Search Algorithm for Optimal Strategical Planning of Electrical Distribution Systems Expansion

An efficient ACO-based algorithm for scheduling tasks onto dynamically reconfigurable hardware using TSP-likened construction graph