caa a22 4500 445838418 CHVBK 20180317145336.0 cr unu---uuuuu 170323e20110201xx s 000 0 eng 10.1007/s10951-009-0159-z doi (NATIONALLICENCE)springer-10.1007/s10951-009-0159-z MunierKordon Alix Laboratoire LIP6 4 place Jussieu, 75 252, Paris cedex 05, France aut A graph-based analysis of the cyclic scheduling problem with time constraints: schedulability and periodicity of the earliest schedule [Elektronische Daten] [Alix MunierKordon] We consider in this paper a set of generic tasks constrained by a set of uniform precedence constraints corresponding to a natural generalization of the basic cyclic scheduling problem. The two parameters of any uniform constraint (namely the value and the height) between two tasks may be negative, which allows one to tackle a larger class of practical applications. We firstly study the structure and the existence of a periodic schedule. A necessary and sufficient condition for the existence of a schedule is then deduced. As there are no resource constraints, tasks following the earliest schedule have minimum average cycle times. The permanent state of the earliest schedule is characterized and we point out that the minimum average cycle times of tasks are equal for the earliest schedule and an optimal periodic schedule. An algorithm to check the existence of a schedule and to compute these minimum average cycle times using linear programming is lastly presented. Springer Science+Business Media, LLC, 2010 Cyclic schedules nationallicence Earliest schedules nationallicence Periodic schedules nationallicence Journal of Scheduling Springer US; http://www.springer-ny.com 14/1(2011-02-01), 103-117 1094-6136 14:1<103 2011 14 10951 https://doi.org/10.1007/s10951-009-0159-z text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10951-009-0159-z text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- MunierKordon Alix Laboratoire LIP6 4 place Jussieu, 75 252, Paris cedex 05, France aut NATIONALLICENCE 773 0- Journal of Scheduling Springer US; http://www.springer-ny.com 14/1(2011-02-01), 103-117 1094-6136 14:1<103 2011 14 10951 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer