Ghent University Academic Bibliography

Advanced

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 (2016) 4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH. 14(3). p.281-308
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.
Please use this url to cite or link to this publication:
author
organization
year
type
journalArticle (original)
publication status
published
subject
keyword
Scheduling, Generalized processor sharing (GPS), Strict priority, Optimization, Queueing
journal title
4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH
volume
14
issue
3
pages
28 pages
publisher
SPRINGER HEIDELBERG
place of publication
HEIDELBERG
JCR category
OPERATIONS RESEARCH & MANAGEMENT SCIENCE
JCR impact factor
1.559 (2016)
JCR rank
38/83 (2016)
JCR quartile
2 (2016)
ISSN
1619-4500
DOI
10.1007/s10288-016-0312-4
language
English
UGent publication?
yes
classification
A1
copyright statement
I have transferred the copyright for this publication to the publisher
id
7189232
handle
http://hdl.handle.net/1854/LU-7189232
date created
2016-04-19 13:53:37
date last changed
2017-06-20 11:59:27
@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},
}

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.