Cyclic scheduling problems for multiprocessor system
Zapiski Nauchnykh Seminarov POMI, Investigations on applied mathematics and informatics. Part III, Tome 539 (2024), pp. 66-85
Voir la notice de l'article provenant de la source Math-Net.Ru
We consider the multiprocessors scheduling problem, when a set of jobs $V$ is done on $m$ identical parallel processors and set of jobs $V$ is to be repeated an infinitely number of times. The goal is to generate a periodic schedule, which is a schedule of one iteration that is repeated within a fixed time interval, which called the period (or cycle time). The aim of cyclic scheduling is to find a periodic schedule with the minimum period. We consider Periodic Scheduling on Identical Processors problem. Precedence constraints between jobs are represented by an uniform graph $G$. We propose algorithms for constructing cyclic schedules for four problems with parallel processors: the problem with unit processing times and three problems with arbitrary processing times. The problem with unit processing times and the problem with preemptions can be solved in polynomial time.
@article{ZNSL_2024_539_a3,
author = {N. S. Grigorieva},
title = {Cyclic scheduling problems for multiprocessor system},
journal = {Zapiski Nauchnykh Seminarov POMI},
pages = {66--85},
publisher = {mathdoc},
volume = {539},
year = {2024},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/ZNSL_2024_539_a3/}
}
N. S. Grigorieva. Cyclic scheduling problems for multiprocessor system. Zapiski Nauchnykh Seminarov POMI, Investigations on applied mathematics and informatics. Part III, Tome 539 (2024), pp. 66-85. http://geodesic.mathdoc.fr/item/ZNSL_2024_539_a3/