Perfect periodic scheduling for three basic cycles


Kim, E. and Glass, C. 2014. Perfect periodic scheduling for three basic cycles. Journal of Scheduling. 17 (1), pp. 47-65.
TitlePerfect periodic scheduling for three basic cycles
AuthorsKim, E. and Glass, C.

Periodic scheduling has many attractions for wireless telecommunications. It offers energy saving where equipment can be turned off between transmissions, and high-quality reception through the elimination of jitter, caused by irregularity of reception. However, perfect periodic schedules, in which each (of n) client is serviced at regular, pre-specified intervals, are notoriously difficult to construct. The problem is known to be NP-hard even when service times are identical. This paper focuses on cases of up to three distinct periodicities, with unit service times. Our contribution is to derive a O(n4) test for the existence of a feasible schedule, and a method of constructing a feasible schedule if one exists, for the given combination of client periodicities. We also indicate why schedules with a higher number of periodicities are unlikely to be useful in practice. This methodology can be used to support perfect periodic scheduling in a wide range in real world settings, including machine maintenance service, wireless mesh networks and various other telecommunication networks transmitting packet size data.

JournalJournal of Scheduling
Publication dates
Online13 May 2013
Print01 Feb 2014
Publication process dates
Deposited25 Aug 2015
Accepted17 Apr 2013
Output statusPublished
Publisher's version
Copyright Statement

© Springer Science+Business Media New York 2013
Open Access This article is distributed under the terms of the Creative Commons Attribution 2.0 International License ( ), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Digital Object Identifier (DOI)
Permalink -

Download files

  • 12
    total views
  • 1
    total downloads
  • 0
    views this month
  • 0
    downloads this month

Export as