Perfect periodic scheduling for three basic cycles

Kim, E-S. & Glass, C. (2014). Perfect periodic scheduling for three basic cycles. Journal of Scheduling, 17(1), pp. 47-55. doi: 10.1007/s10951-013-0331-3

[img]
Preview
Text - Published Version
Available under License Creative Commons Attribution.

Download (1MB) | Preview

Abstract

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, prespecified 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 (n 4) 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. © 2013 Springer Science+Business Media New York.

Item Type: Article
Uncontrolled Keywords: Scheduling; Perfect periodicity; Feasibility testing; Wireless mesh networks
Subjects: H Social Sciences > HD Industries. Land use. Labor > HD28 Management. Industrial Management
Divisions: Cass Business School > Faculty of Actuarial Science & Insurance
URI: http://openaccess.city.ac.uk/id/eprint/16464

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics