A comparison of two metaheuristic algorithms for scheduling problem on a heterogeneous CPU/FPGA architecture with communication delays

被引：0

作者：

Abdallah, Fadel ^{[1
]}

Tanougast, Camel ^{[1
]}

Kacem, Imed ^{[1
]}

Diou, Camille ^{[1
]}

Singer, Daniel ^{[1
]}

机构：

[1] Univ Lorraine, LCOMS, EA 7306, 7 Rue Marconi, F-57070 Metz, France

来源：

2017 4TH INTERNATIONAL CONFERENCE ON CONTROL, DECISION AND INFORMATION TECHNOLOGIES (CODIT) | 2017年

关键词：

heterogeneous system; CPU/FPGA; metaheuristics; data flow graph; makespan (schedule length); genetic algorithm; simulated annealing; real time; task scheduling; optimization;

D O I：

暂无

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

This paper considers the problem of scheduling on a heterogeneous CPU/FPGA architecture with communication delays, with the aim of minimizing the makespan (or the schedule length). For this strongly NP-hard problem, we present two iterative algorithms based on simulated annealing (SA) and genetic algorithms (GAs), which are used to run in the MPSoC an application described in a data flow graph. The performance of the proposed algorithms are evaluated and compared on a set of instances with up to 50 tasks. Computational experiments indicate that the innovative proposed algorithms provide competitive results for the studied problem and that the objective function values obtained are optimal or very close to a lower bound in a reasonable computation time.

引用

页码：294 / 299

页数：6

共 50 条

[21] New MIP model for multiprocessor scheduling problem with communication delays
El Cadi, Abdessamad Ait
Ben Atitallah, Rabie
Hanafi, Said
Mladenovic, Nenad
Artiba, Abdelhakim
OPTIMIZATION LETTERS, 2017, 11 (06) : 1091 - 1107
[22] Comparison of evolutionary computation algorithms for solving bi-objective task scheduling problem on heterogeneous distributed computing systems
Chitra, P.
Venkatesh, P.
Rajaram, R.
SADHANA-ACADEMY PROCEEDINGS IN ENGINEERING SCIENCES, 2011, 36 (02): : 167 - 180
[23] Simulated Annealing Algorithms for the Heterogeneous Robots Task Scheduling Problem in Heterogeneous Robotic Order Fulfillment Systems
Wang, Hanfu
Chen, Weidong
INTELLIGENT AUTONOMOUS SYSTEMS 16, IAS-16, 2022, 412 : 276 - 287
[24] Solving a Production Scheduling Problem by Means of Two Biobjective Metaheuristic Procedures
Toncovich, Adrian
Oliveros Colay, Maria Jose
Maria Moreno, Jose
Rafael Corral, Jimenez
THIRD MANUFACTURING ENGINEERING SOCIETY INTERNATIONAL CONFERENCE: MESIC-09, 2009, 1181 : 539 - +
[25] Conventional and Metaheuristic Optimization Algorithms for Solving Short Term Hydrothermal Scheduling Problem: A Review
Fakhar, Muhammad Salman
Liaquat, Sheroze
Kashif, Syed Abdul Rahman
Rasool, Akhtar
Khizer, Muhammad
Iqbal, Muhammad Ahmad
Baig, Muhammad Anas
Padmanaban, Sanjeevikumar
IEEE ACCESS, 2021, 9 : 25993 - 26025
[26] Optimization of economic lot scheduling problem with backordering and shelf-life considerations using calibrated metaheuristic algorithms
Mohammadi, Maryam
Musa, Siti Nurmaya
Bahreininejad, Ardeshir
APPLIED MATHEMATICS AND COMPUTATION, 2015, 251 : 404 - 422
[27] A comparison of multiprocessor task scheduling algorithms with communication costs
Hwang, Reakook
Gen, Mitsuo
Katayama, Hiroshi
COMPUTERS & OPERATIONS RESEARCH, 2008, 35 (03) : 976 - 993
[28] Application and comparison of hybrid evolutionary multiobjective optimization algorithms for solving task scheduling problem on heterogeneous systems
Chitra, P.
Rajaram, R.
Venkatesh, P.
APPLIED SOFT COMPUTING, 2011, 11 (02) : 2725 - 2734
[29] A Two-Level Metaheuristic Algorithm for the Job-Shop Scheduling Problem
Pongchairerks, Pisut
COMPLEXITY, 2019, 2019
[30] Optimization of mixed integer nonlinear economic lot scheduling problem with multiple setups and shelf life using metaheuristic algorithms
Mohammadi, Maryam
Musa, S. Nurmaya
Bahreininejad, Ardeshir
ADVANCES IN ENGINEERING SOFTWARE, 2014, 78 : 41 - 51

← 1 2 3 4 5 →