Cyclic Scheduling for Parallel Processors with Precedence Constrains

Результат исследований: Научные публикации в периодических изданияхстатья в журнале по материалам конференциирецензирование


The goal of this paper is to prepare algorithms of the cyclic scheduling problem, in which some set of jobs V is to be repeated an infinite number of times. We consider the multiprocessors problem when a set of jobs is done on identical parallel processors. Cyclic scheduling problems arise (for example) in manufacturing, timesharing of processors in embedded systems. The goal is to find a periodic schedule that minimizes the cycle time under precedence constraints. Although the problem is NP-hard, we show that the special case, where the precedence graph G is a tree or there are only two processors and all jobs have a unit processing time, can be solved in polynomial time.
Язык оригиналаанглийский
Номер статьи012019
Страницы (с-по)012019
Число страниц8
ЖурналJournal of Physics: Conference Series
Номер выпуска1
СостояниеОпубликовано - 17 окт 2020
СобытиеThe II International Scientific and Practical Conference on Mathematical Modeling, Programming and Applied Mathematics - Veliky Novgorod, Российская Федерация
Продолжительность: 5 ноя 20206 ноя 2020

Предметные области Scopus

  • Математика (все)
  • Компьютерные науки (все)


Подробные сведения о темах исследования «Cyclic Scheduling for Parallel Processors with Precedence Constrains». Вместе они формируют уникальный семантический отпечаток (fingerprint).