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.
Original languageEnglish
Article number012019
Pages (from-to)012019
Number of pages8
JournalJournal of Physics: Conference Series
Volume1658
Issue number1
DOIs
StatePublished - 17 Oct 2020
EventThe II International Scientific and Practical Conference on Mathematical Modeling, Programming and Applied Mathematics - Veliky Novgorod, Russian Federation
Duration: 5 Nov 20206 Nov 2020

    Scopus subject areas

  • Mathematics(all)
  • Computer Science(all)

ID: 70945024