Advanced search
1 file | 1.24 MB

On the optimization of two-class work-conserving parameterized scheduling policies

Jasper Vanlerberghe (UGent) , Tom Maertens (UGent) , Joris Walraevens (UGent) , Stijn De Vuyst (UGent) and Herwig Bruneel (UGent)
Author
Organization
Abstract
Numerous scheduling policies are designed to differentiate quality of service for different applications. Service differentiation can in fact be formulated as a generalized resource allocation optimization towards the minimization of some important system characteristics. For complex scheduling policies, however, optimization can be a demanding task, due to the difficult analytical analysis of the system at hand. In this paper, we study the optimization problem in a queueing system with two traffic classes, a work-conserving parameterized scheduling policy, and an objective function that is a convex combination of either linear, convex or concave increasing functions of given performance measures of both classes. In case of linear and concave functions, we show that the optimum is always in an extreme value of the parameter. Furthermore, we prove that this is not necessarily the case for convex functions; in this case, a unique local minimum exists. This information greatly simplifies the optimization problem. We apply the framework to some interesting scheduling policies, such as Generalized Processor Sharing and semi-preemptive priority scheduling. We also show that the well-documented -rule is a special case of our framework.
Keywords
Scheduling, Generalized processor sharing (GPS), Strict priority, Optimization, Queueing

Downloads

  • (...).pdf
    • full text
    • |
    • UGent only
    • |
    • PDF
    • |
    • 1.24 MB

Citation

Please use this url to cite or link to this publication:

Chicago
Vanlerberghe, Jasper, Tom Maertens, Joris Walraevens, Stijn De Vuyst, and Herwig Bruneel. 2016. “On the Optimization of Two-class Work-conserving Parameterized Scheduling Policies.” 4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH 14 (3): 281–308.
APA
Vanlerberghe, J., Maertens, T., Walraevens, J., De Vuyst, S., & Bruneel, H. (2016). On the optimization of two-class work-conserving parameterized scheduling policies. 4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 14(3), 281–308.
Vancouver
1.
Vanlerberghe J, Maertens T, Walraevens J, De Vuyst S, Bruneel H. On the optimization of two-class work-conserving parameterized scheduling policies. 4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH. HEIDELBERG: SPRINGER HEIDELBERG; 2016;14(3):281–308.
MLA
Vanlerberghe, Jasper, Tom Maertens, Joris Walraevens, et al. “On the Optimization of Two-class Work-conserving Parameterized Scheduling Policies.” 4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH 14.3 (2016): 281–308. Print.
@article{7189232,
  abstract     = {Numerous scheduling policies are designed to differentiate quality of service for different applications. Service differentiation can in fact be formulated as a generalized resource allocation optimization towards the minimization of some important system characteristics. For complex scheduling policies, however, optimization can be a demanding task, due to the difficult analytical analysis of the system at hand. In this paper, we study the optimization problem in a queueing system with two traffic classes, a work-conserving parameterized scheduling policy, and an objective function that is a convex combination of either linear, convex or concave increasing functions of given performance measures of both classes. In case of linear and concave functions, we show that the optimum is always in an extreme value of the parameter. Furthermore, we prove that this is not necessarily the case for convex functions; in this case, a unique local minimum exists. This information greatly simplifies the optimization problem. We apply the framework to some interesting scheduling policies, such as Generalized Processor Sharing and semi-preemptive priority scheduling. We also show that the well-documented -rule is a special case of our framework.},
  author       = {Vanlerberghe, Jasper and Maertens, Tom and Walraevens, Joris and De Vuyst, Stijn and Bruneel, Herwig},
  issn         = {1619-4500},
  journal      = {4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH},
  keyword      = {Scheduling,Generalized processor sharing (GPS),Strict priority,Optimization,Queueing},
  language     = {eng},
  number       = {3},
  pages        = {281--308},
  publisher    = {SPRINGER HEIDELBERG},
  title        = {On the optimization of two-class work-conserving parameterized scheduling policies},
  url          = {http://dx.doi.org/10.1007/s10288-016-0312-4},
  volume       = {14},
  year         = {2016},
}

Altmetric
View in Altmetric
Web of Science
Times cited: