DOI

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
Том1658
Номер выпуска1
DOI
СостояниеОпубликовано - 17 окт 2020
СобытиеThe II International Scientific and Practical Conference on Mathematical Modeling, Programming and Applied Mathematics - Veliky Novgorod, Российская Федерация
Продолжительность: 5 ноя 20206 ноя 2020

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

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

ID: 70945024