TY - GEN
T1 - Dynamic scheduling via polymatroid optimization
AU - Yao, David D.
PY - 2002
Y1 - 2002
N2 - Dynamic scheduling of multi-class jobs in queueing systems has wide ranging applications, but in general is a very difficult control problem. Here we focus on a class of systems for which conservation laws hold. Consequently, the performance space becomes a polymatroid — a polytope witha matroid-like structure, withall the vertices corresponding to the performance under priority rules, and all the vertices are easily identified. This structure translates the optimal control problem to an optimization problem, which, under a linear objective, becomes a special linear program; and the optimal schedule is a priority rule. In a more general setting, conservation laws extend to so-called generalized conservation laws, under which the performance space becomes more involved; however, the basic structure that ensures the optimality of priority rules remains intact. This tutorial provides an overview to the subject, focusing on the main ideas, basic mathematical facts, and computational implications.
AB - Dynamic scheduling of multi-class jobs in queueing systems has wide ranging applications, but in general is a very difficult control problem. Here we focus on a class of systems for which conservation laws hold. Consequently, the performance space becomes a polymatroid — a polytope witha matroid-like structure, withall the vertices corresponding to the performance under priority rules, and all the vertices are easily identified. This structure translates the optimal control problem to an optimization problem, which, under a linear objective, becomes a special linear program; and the optimal schedule is a priority rule. In a more general setting, conservation laws extend to so-called generalized conservation laws, under which the performance space becomes more involved; however, the basic structure that ensures the optimality of priority rules remains intact. This tutorial provides an overview to the subject, focusing on the main ideas, basic mathematical facts, and computational implications.
UR - http://www.scopus.com/inward/record.url?scp=84957106307&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84957106307&origin=recordpage
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 9783540442523
VL - 2459
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 89
EP - 113
BT - Performance Evaluation of Complex Systems: Techniques and Tools
A2 - Tucci, Salvatore
A2 - Calzarossa, Maria Carla
PB - Springer Verlag
T2 - IFIP WG 7.3 International Symposium on Computer Modeling, Measurement, and Evaluation, Performance 2002
Y2 - 23 September 2002 through 27 September 2002
ER -