A note on periodic schedules for linear precedence constraints

作者：Kats Vladimir; Levner Eugene^*

来源：Discrete Applied Mathematics, 2013, 161(3): 430-434.

DOI：10.1016/j.dam.2012.09.002

• Linear precedence constraints
• Periodic schedules
• Polynomial algorithm

Hanen and Munier-Kordon [C. Hanen, A. Munier Kordon, Periodic schedules for linear precedence constraints, Discrete Applied Mathematics 157 (2) (2009) 280-291] have considered a problem of scheduling periodic tasks each of which has to be repeated with its own period. They have developed a weakly polynomial algorithm for a particular class of linear precedence graphs called unitary graphs, which generalizes the usual not-earlier precedence relations between the tasks. The purpose of this note is two-fold. First, we suggest a further generalization of the unitary relations that extends the usual not-later precedence relations; as a result, the arc lengths and heights in the underlying graph may be negative. Second, we show that, as soon as the arc heights in the graph are computed, an optimum periodic schedule can be found in strongly polynomial time.

• 出版日期2013-2