Perfect periodic scheduling for three basic cycles

Article English OPEN
Kim, Eun-Seok ; Glass, Celia (2014)
  • Publisher: Springer
  • Journal: Journal of Scheduling
  • Related identifiers: doi: 10.1007/s10951-013-0331-3
  • Subject: HD28 | Engineering(all) | Software | Management Science and Operations Research | Artificial Intelligence

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.
  • References (20)
    20 references, page 1 of 2

    Akyildiz, I. F., Wang, X., & Wang, W. (2005). Wireless mesh networks: A survey. Computer Networks, 47, 445-487.

    Allen, S. M., Cooper, I. M., Glass, C. A., Kim, E. S., & Whitaker, R. M. (2012a). Coordinating local schedules in wireless mesh networks (submitted). http://www.cs.cf.ac.uk/ISforWMN/Papers/ CoordinatingWMN.pdf.

    Allen, S. M., Cooper, I. M., & Whitaker, R. M. (2012b). Optimising multi-rate link scheduling for wireless mesh networks. Computer Communications, 35(16), 2014-2024.

    Bar-Noy, A., Bhatia, R., Naor, J., & Schieber, B. (2002a). Minimize service and operation costs of periodic scheduling. Mathematics of Operations Research, 27, 518-544.

    Bar-Noy, A., Nisgav, A., & Patt-Shamir, B. (2002b). Nearly optimal perfectly periodic schedules. Distributed Computing, 15, 207-220.

    Bar-Noy, A., Dreizin, V., & Patt-Shamir, B. (2004). Efficient algorithms for periodic scheduling. Computer Networks, 45, 155-173.

    Brakerski, Z., & Patt-Shamir, B. (2006). Jitter-approximation tradeoff for periodic scheduling. Wireless Network, 12, 723-731.

    Brakerski, Z., Dreizin, V., & Patt-Shamir, B. (2003). Dispatching in perfectly-periodic schedules. Journal of Algorithm, 49, 219-239.

    Brakerski, Z., Nisgav, A., & Patt-Shamir, B. (2006). General perfectly periodic scheduling. Algorithmica, 45, 183-208.

    Brauner, N., Crama, Y., Grigoriev, A., & van de Klundert, J. (2005). A framework for the complexity of high-multiplicity scheduling problems. Journal of Combinatorial Optimization, 9, 313-323.

  • Bioentities (1)
    3pps Protein Data Bank
  • Metrics
    No metrics available
Share - Bookmark