Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Kim, Eun-Seok; Glass, Celia (2014)
Publisher: Springer
Journal: Journal of Scheduling
Languages: English
Types: Article
Subjects: 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.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • 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.
    • Chen, W. M., & Huang, M. K. (2008). Adaptive general perfectly periodic scheduling. In 2008 International Symposium on Ubiquitous Multimedia, Computing (pp. 29-34).
    • Corominas, A., Kubiak, W., & Palli, N. M. (2007). Response time variability. Journal of Scheduling, 10, 97-110.
    • Glass, C. A. (1992). Feasibility of scheduling lot sizes of three products on one machine. Management Science, 38, 1482-1494.
    • Glass, C. A. (1994). Feasibility of scheduling lot sizes of two frequencies on one machine. European Journal of Operational Research, 75, 354-364.
    • Glass, C. A., Gupta, J. N. D., & Potts, C. N. (1994). Lot streaming in three stage production processes. European Journal of Operational Research, 75, 378-394.
    • Jones, G. A., & Jones, J. M. (1998). Elementrary number theory. Berlin: Springer.
    • Kim, E. S., & Glass, C. A. (2012). Perfect periodic scheduling for binary trees (submitted). http://www.cs.cf.ac.uk/ISforWMN/ Papers/PPSBinaryTrees.pdf.
    • Patil, S., & Garg, V. K. (2006). Adaptive general perfectly periodic scheduling. Information Processing Letters, 98, 107-114.
    • Quintas, D., & Friderikos, V. (2012). Energy efficient spatial TDMA scheduling in wireless networks. Computers & Operations Research, 39(9), 2091-2099.
    • Steiner, G., & Yeomans, S. (1993). Level schedules for mixed-model, just-in-time processes. Management Science, 39, 728-735.
  • No related research data.
  • No similar publications.
  • BioEntity Site Name
    3ppsProtein Data Bank

Share - Bookmark

Cite this article