Open AccessCyclic Scheduling for Parallel Processors with Precedence Constrains
Author(s) -
N. S. Grigor'eva
Publication year - 2020
Publication title -
journal of physics. conference series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 85
eISSN - 1742-6596
pISSN - 1742-6588
DOI - 10.1088/1742-6596/1658/1/012019
Subject(s) - computer science , parallel computing , scheduling (production processes) , schedule , job shop scheduling , time complexity , multiprocessor scheduling , graph , theoretical computer science , mathematical optimization , algorithm , mathematics , flow shop scheduling , operating system
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.