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 条

[31] Solving a stochastic hierarchical scheduling problem by VNS-based metaheuristic with locally assisted algorithms ?
Lu, Shaojun
Ma, Chongyao
Kong, Min
Zhou, Zhiping
Liu, Xinbao
APPLIED SOFT COMPUTING, 2022, 130
[32] Mathematical programming and three metaheuristic algorithms for a bi-objective supply chain scheduling problem
Zarei, Hamid
Rasti-Barzoki, Morteza
NEURAL COMPUTING & APPLICATIONS, 2019, 31 (12) : 9073 - 9093
[33] Parallel machine earliness-tardiness scheduling - Comparison of two metaheuristic approaches
Bazyluk, Marcin
Koszalka, Leszek
Burnham, Keith J.
ICINCO 2008: PROCEEDINGS OF THE FIFTH INTERNATIONAL CONFERENCE ON INFORMATICS IN CONTROL, AUTOMATION AND ROBOTICS, VOL ICSO: INTELLIGENT CONTROL SYSTEMS AND OPTIMIZATION, 2008, : 80 - 85
[34] Multi-objective metaheuristic algorithms for the resource-constrained project scheduling problem with precedence relations
Gomes, Helton Cristiano
das Neves, Francisco de Assis
Freitas Souza, Marcone Jamilson
COMPUTERS & OPERATIONS RESEARCH, 2014, 44 : 92 - 104
[35] Integrated production scheduling and vehicle routing problem with energy efficient strategies: Mathematical formulation and metaheuristic algorithms
Yagmur, Ece
Kesen, Saadettin Erhan
EXPERT SYSTEMS WITH APPLICATIONS, 2024, 237
[36] Comparison of evolutionary computation algorithms for solving bi-objective task scheduling problem on heterogeneous distributed computing systems
P CHITRA
P VENKATESH
R RAJARAM
Sadhana, 2011, 36 : 167 - 180
[37] Multiobjective evolutionary computation algorithms for solving task scheduling problem on heterogeneous systems
Chitra, P.
Venkatesh, P.
INTERNATIONAL JOURNAL OF KNOWLEDGE-BASED AND INTELLIGENT ENGINEERING SYSTEMS, 2010, 14 (01) : 21 - 30
[38] Simulated annealing and genetic algorithms for the two-machine scheduling problem with a single server
Hasani, Keramat
Kravchenko, Svetlana A.
Werner, Frank
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2014, 52 (13) : 3778 - 3792
[39] An Enhanced Two-Level Metaheuristic Algorithm with Adaptive Hybrid Neighborhood Structures for the Job-Shop Scheduling Problem
Pongchairerks, Pisut
COMPLEXITY, 2020, 2020
[40] Accelerating floating-point fitness functions in evolutionary algorithms: a FPGA-CPU-GPU performance comparison
Gomez-Pulido, Juan A.
Vega-Rodriguez, Miguel A.
Sanchez-Perez, Juan M.
Priem-Mendes, Silvio
Carreira, Vitor
GENETIC PROGRAMMING AND EVOLVABLE MACHINES, 2011, 12 (04) : 403 - 427

← 1 2 3 4 5 →