City Research Online

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-65. doi: 10.1007/s10951-013-0331-3

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.

Publication Type: Article
Publisher Keywords: Scheduling; Perfect periodicity; Feasibility testing; Wireless mesh networks
Subjects: H Social Sciences > HD Industries. Land use. Labor > HD28 Management. Industrial Management
Departments: Bayes Business School > Actuarial Science & Insurance
SWORD Depositor:
[thumbnail of perfect periodic scheduling.pdf]
Preview
Text - Published Version
Available under License Creative Commons Attribution.

Download (1MB) | Preview

Export

Add to AnyAdd to TwitterAdd to FacebookAdd to LinkedinAdd to PinterestAdd to Email

Downloads

Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login