Hybrid Algorithm for Multiprocessor Scheduling with Makespan Minimization and Constraint on Interprocessor Data Exchange

In this paper we address the problem of static scheduling for multiprocessor systems, with minimization of makespan, and constraint on the number of interprocessor data transfers. Such problems arise during development of real-time data processing systems, such as telecommunication and control syste...

Full description

Saved in:
Bibliographic Details
Main Authors: Balashov, Vasily V., Kostenko, Valery A., Fedorenko, Ilya A., Savitsky, Ilya P., Sun, Chumin, Gao, Jiexing, Zhou, Li, Sun, Jie
Format: Conference Proceeding
Language:English
Subjects:
Data transfer
Heuristic algorithms
Minimization
Processor scheduling
Program processors
Schedules
Simulated annealing
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper we address the problem of static scheduling for multiprocessor systems, with minimization of makespan, and constraint on the number of interprocessor data transfers. Such problems arise during development of real-time data processing systems, such as telecommunication and control systems. A hybrid algorithm is proposed, combining greedy approach to construction of the initial solution and simulated annealing for its refinement. A specialized operation was developed, aimed at filling idle intervals in the schedule during simulated annealing phase. Experimental evaluation results are presented, demonstrating the advantage of the hybrid algorithm over both standalone greedy algorithm and simulated annealing with straightforward construction of the initial solution.
ISSN:2576-3555
DOI:10.1109/CoDIT58514.2023.10284178