{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,18]],"date-time":"2025-01-18T04:40:20Z","timestamp":1737175220700,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":52,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540442523"},{"type":"electronic","value":"9783540457985"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45798-4_5","type":"book-chapter","created":{"date-parts":[[2007,7,3]],"date-time":"2007-07-03T01:42:40Z","timestamp":1183426960000},"page":"89-113","source":"Crossref","is-referenced-by-count":8,"title":["Dynamic Scheduling via Polymatroid Optimization"],"prefix":"10.1007","author":[{"given":"David D.","family":"Yao","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,9,5]]},"reference":[{"key":"5_CR1","volume-title":"Applied Probability and Queues","author":"S. Asmussen","year":"1987","unstructured":"Asmussen, S., Applied Probability and Queues. Wiley, Chichester, U.K., 1987."},{"key":"5_CR2","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/BF01149167","volume":"21","author":"D. Bertsimas","year":"1995","unstructured":"Bertsimas, D., The Achievable Region Method in the Optimal Control of Queueing Systems; Formulations, Bounds and Policies. Queueing Systems, 21 (1995), 337\u2013389.","journal-title":"Queueing Systems"},{"key":"5_CR3","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1287\/moor.21.2.257","volume":"21","author":"D. Bertsimas","year":"1996","unstructured":"Bertsimas, D. and Ni\u00f1o-Mora, J., Conservation Laws, Extended Polymatroid and Multi-Armed Bandit Problems: A Unified Approachto Indexable Systems. Mathematics of Operations Research, 21 (1996), 257\u2013306.","journal-title":"Mathematics of Operations Research"},{"key":"5_CR4","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1214\/aoap\/1177005200","volume":"4","author":"D. Bertsimas","year":"1994","unstructured":"Bertsimas, D. Paschalidis, I.C. and Tsitsiklis, J.N., Optimization of Multiclass Queueing Networks: Polyhedral and Nonlinear Characterization of Achievable Performance. Ann. Appl. Prob., 4 (1994), 43\u201375.","journal-title":"Ann. Appl. Prob."},{"key":"5_CR5","doi-asserted-by":"publisher","first-page":"186","DOI":"10.2307\/1427059","volume":"17","author":"J.S. Baras","year":"1985","unstructured":"Baras, J.S., Dorsey, A.J. and Makowski, A.M., Two Competing Queues withLinear Cost: the \u03bcc Rule Is Often Optimal. Adv. Appl. Prob., 17 (1985), 186\u2013209.","journal-title":"Adv. Appl. Prob."},{"key":"5_CR6","doi-asserted-by":"publisher","first-page":"237","DOI":"10.2307\/1427064","volume":"30","author":"C. Buyukkoc","year":"1985","unstructured":"Buyukkoc, C., Varaiya, P. and Walrand, J., The c\u03bc Rule Revisited. Adv. Appl. Prob., 30 (1985), 237\u2013238.","journal-title":"Adv. Appl. Prob."},{"key":"5_CR7","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-5301-1","volume-title":"Fundamentals of Queueing Networks: Performance, Asymptotics and Optimization","author":"H. Chen","year":"2001","unstructured":"Chen, H. and Yao, D.D., Fundamentals of Queueing Networks: Performance, Asymptotics and Optimization. Springer-Verlag, New York, 2001."},{"key":"5_CR8","volume-title":"Linear Programming","author":"V. Chv\u00e1tal","year":"1983","unstructured":"Chv\u00e1tal, V., Linear Programming. W.H. Freeman, New York, 1983."},{"key":"5_CR9","doi-asserted-by":"crossref","first-page":"810","DOI":"10.1287\/opre.28.3.810","volume":"28","author":"E. Coffman","year":"1980","unstructured":"Coffman, E. and Mitrani, I., A Characterization of Waiting Time Performance Realizable by Single Server Queues. Operations Research, 28 (1980), 810\u2013821.","journal-title":"Operations Research"},{"key":"5_CR10","volume-title":"Queues","author":"D.R. Cox","year":"1961","unstructured":"Cox, D.R. and Smith, W.L., Queues. Methunen, London, 1961."},{"key":"5_CR11","doi-asserted-by":"crossref","unstructured":"Dacre, K.D., Glazebrook, K.D., and Nin\u00f5-Mora, J., The Achievable Region Approach to the Optimal Control of Stochastic Systems. J. Royal Statist. Soc. (1999).","DOI":"10.1111\/1467-9868.00202"},{"key":"5_CR12","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1007\/BF01580137","volume":"5","author":"F.D.J. Dunstan","year":"1973","unstructured":"Dunstan, F.D.J. and Welsh, D.J.A., A Greedy Algorithm for Solving a Certain Class of Linear Programmes. Math. Programming, 5 (1973), 338\u2013353.","journal-title":"Math. Programming"},{"key":"5_CR13","unstructured":"Edmonds, J., Submodular Functions, Matroids and Certain Polyhedra. Proc. Int. Conf. on Combinatorics (Calgary), Gordon and Breach, New York, 69\u201387, 1970."},{"key":"5_CR14","doi-asserted-by":"crossref","first-page":"909","DOI":"10.1287\/opre.34.6.909","volume":"34","author":"A. Federgruen","year":"1986","unstructured":"Federgruen, A. and Groenevelt, H., The Greedy Procedure for Resource Allocation Problems: Necessary and Sufficient Conditions for Optimality. Operations Res., 34 (1986), 909\u2013918.","journal-title":"Operations Res."},{"key":"5_CR15","doi-asserted-by":"publisher","first-page":"709","DOI":"10.2307\/3214101","volume":"24","author":"A. Federgruen","year":"1987","unstructured":"Federgruen, A. and Groenevelt, H., The Impact of the Composition of the Customer Base in General Queueing Models. J. Appl. Prob., 24 (1987), 709\u2013724.","journal-title":"J. Appl. Prob."},{"key":"5_CR16","doi-asserted-by":"crossref","first-page":"1121","DOI":"10.1287\/mnsc.34.9.1121","volume":"34","author":"A. Federgruen","year":"1988","unstructured":"Federgruen, A. and Groenevelt, H., M\/G\/c Queueing Systems withMultiple Customer Classes: Characterization and Control of Achievable Performance under Non-Preemptive Priority Rules. Management Science, 34 (1988), 1121\u20131138.","journal-title":"Management Science"},{"key":"5_CR17","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1287\/opre.36.5.733","volume":"36","author":"A. Federgruen","year":"1988","unstructured":"Federgruen, A. and Groenevelt, H., Characterization and Optimization of Achievable Performance in Queueing Systems. Operations Res., 36 (1988), 733\u2013741.","journal-title":"Operations Res."},{"key":"5_CR18","series-title":"IBM Research Report","volume-title":"Time-Function Scheduling: A General Approach to Controllable Resource Management","author":"L.L. Fong","year":"1995","unstructured":"Fong, L.L. and Squillante, M.S., Time-Function Scheduling: A General Approach to Controllable Resource Management. IBM Research Report RC-20155, IBM Research Division, T.J. Watson Research Center, Yorktown Hts., New York, NY 10598, 1995."},{"key":"5_CR19","series-title":"IBM Research Report","volume-title":"Properties of Delay Cost Scheduling in Timesharing Systems","author":"P.A. Franaszek","year":"1990","unstructured":"Franaszek, P.A. and Nelson, R.D., Properties of Delay Cost Scheduling in Timesharing Systems. IBM Research Report RC-13777, IBM Research Division, T.J. Watson Research Center, Yorktown Hts., New York, NY 10598, 1990."},{"key":"5_CR20","volume-title":"Analysis and Synthesis of Computer Systems","author":"E. Gelenbe","year":"1980","unstructured":"Gelenbe, E. and Mitrani, I., Analysis and Synthesis of Computer Systems. Academic Press, London, 1980."},{"key":"5_CR21","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1111\/j.2517-6161.1979.tb01068.x","volume":"41","author":"J.C. Gittins","year":"1979","unstructured":"Gittins, J.C., Bandit Processes and Dynamic Allocation Indices (withdiscussions). J. Royal Statistical Society, Ser. B, 41 (1979), 148\u2013177.","journal-title":"J. Royal Statistical Society"},{"key":"5_CR22","volume-title":"Multiarmed Bandit Allocation Indices","author":"J.C. Gittins","year":"1989","unstructured":"Gittins, J.C., Multiarmed Bandit Allocation Indices. Wiley, Chichester, 1989."},{"key":"5_CR23","unstructured":"Gittins, J.C. and Jones, D.M., A Dynamic Allocation Index for the Sequential Design of Experiments. In: Progress in Statistics: European Meeting of Statisticians, Budapest, 1972, J. Gani, K. Sarkadi and I. Vince (eds.), North-Holland, Amsterdam, 1974, 241\u2013266."},{"key":"5_CR24","volume-title":"Monotone Structure in Discrete-Event Systems","author":"P. Glasserman","year":"1994","unstructured":"Glasserman, P. and Yao, D.D., Monotone Structure in Discrete-Event Systems. Wiley, New York, 1994."},{"key":"5_CR25","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1287\/moor.19.2.449","volume":"19","author":"P. Glasserman","year":"1994","unstructured":"Glasserman, P. and Yao, D.D., Monotone Optimal Control of Permutable GSMP\u2019s. Mathematics of Operations Research, 19 (1994), 449\u2013476.","journal-title":"Mathematics of Operations Research"},{"key":"5_CR26","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-78240-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M. Gr\u00f6tschel","year":"1993","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L and Schrijver, A., Geometric Algorithms and Combinatorial Optimization, second corrected edition. Springer-Verlag, Berlin, 1993.","edition":"second correcte"},{"key":"5_CR27","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1287\/opre.23.2.270","volume":"23","author":"J.M. Harrison","year":"1975","unstructured":"Harrison, J.M., Dynamic Scheduling of a Multiclass Queue: Discount Optimality. Operations Res., 23 (1975), 270\u2013282.","journal-title":"Operations Res."},{"key":"5_CR28","doi-asserted-by":"crossref","unstructured":"Harrison, J.M., The BIGSTEP Approach to Flow Management in Stochastic Processing Networks. In: Stochastic Networks: Theory and Applications, Kelly, Zachary, and Ziedens (eds.), Royal Statistical Society Lecture Note Series, #4, 1996, 57\u201390.","DOI":"10.1093\/oso\/9780198523994.003.0004"},{"key":"5_CR29","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01225319","volume":"5","author":"J.M. Harrison","year":"1989","unstructured":"Harrison, J.M. and Wein, L., Scheduling Networks of Queues: Heavy Traffic Analysis of a Simple Open Network. Queueing Systems, 5 (1989), 265\u2013280.","journal-title":"Queueing Systems"},{"key":"5_CR30","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1002\/nav.3800110306","volume":"11","author":"L. Kleinrock","year":"1964","unstructured":"Kleinrock, L., A Delay Dependent Queue Discipline. Naval Research Logistics Quarterly, 11 (1964), 329\u2013341.","journal-title":"Naval Research Logistics Quarterly"},{"key":"5_CR31","volume-title":"Queueing Systems","author":"L. Kleinrock","year":"1976","unstructured":"Kleinrock, L., Queueing Systems, Vol. 2. Wiley, New York, 1976."},{"key":"5_CR32","doi-asserted-by":"publisher","first-page":"532","DOI":"10.1137\/1119060","volume":"19","author":"G.P. Klimov","year":"1974","unstructured":"Klimov, G.P., Time Sharing Service Systems, Theory of Probability and Its Applications, 19 (1974), 532\u2013551 (Part I) and 23 (1978), 314-321 (Part II).","journal-title":"Theory of Probability and Its Applications"},{"key":"5_CR33","doi-asserted-by":"publisher","first-page":"447","DOI":"10.2307\/1427399","volume":"20","author":"T.L. Lai","year":"1988","unstructured":"Lai, T.L. and Ying, Z., Open Bandit Processes and Optimal Scheduling of Queueing Networks. Adv. Appl. Prob., 20 (1988), 447\u2013472.","journal-title":"Adv. Appl. Prob."},{"key":"5_CR34","unstructured":"Lu, Y., Dynamic Scheduling of Stochastic Networks with Side Constraints. Ph.D. Thesis, Columbia University, 1998."},{"key":"5_CR35","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0304-4149(77)90029-1","volume":"5","author":"I. Meilijson","year":"1977","unstructured":"Meilijson, I. and Weiss, G., Multiple Feedback at a Single-Server Station. Stochastic Proc. and Appl., 5 (1977), 195\u2013205.","journal-title":"Stochastic Proc. and Appl."},{"key":"5_CR36","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1109\/9.8648","volume":"34","author":"K.W. Ross","year":"1989","unstructured":"Ross, K.W. and Yao, D.D., Optimal Dynamic Scheduling in Jackson Networks. IEEE Transactions on Automatic Control, 34 (1989), 47\u201353.","journal-title":"IEEE Transactions on Automatic Control"},{"key":"5_CR37","doi-asserted-by":"crossref","first-page":"676","DOI":"10.1145\/116825.116847","volume":"38","author":"K.W. Ross","year":"1991","unstructured":"Ross, K.W. and Yao, D.D., Optimal Load Balancing and Scheduling in a Distributed Computer System. Journal of the Association for Computing Machinery, 38 (1991), 676\u2013690.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"5_CR38","doi-asserted-by":"publisher","first-page":"737","DOI":"10.2307\/3214103","volume":"24","author":"J.G. Shanthikumar","year":"1987","unstructured":"Shanthikumar, J.G. and Sumita, U., Convex Ordering of Sojourn Times in Single-Server Queues: Extremal Properties of FIFO and LIFO Service Disciplines. J. Appl. Prob., 24 (1987), 737\u2013748.","journal-title":"J. Appl. Prob."},{"issue":"Supplement2","key":"5_CR39","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1287\/opre.40.3.S293","volume":"40","author":"J.G. Shanthikumar","year":"1992","unstructured":"Shanthikumar J.G. and Yao D.D., Multiclass Queueing Systems: Polymatroid Structure and Optimal Scheduling Control. Operation Research, 40 (1992), Supplement 2, S293\u2013299.","journal-title":"Operation Research"},{"key":"5_CR40","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/nav.3800030106","volume":"3","author":"W.L. Smith","year":"1956","unstructured":"Smith, W.L., Various Optimizers for Single-Stage Production. Naval Research Logistics Quarterly, 3 (1956), 59\u201366.","journal-title":"Naval Research Logistics Quarterly"},{"key":"5_CR41","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1287\/opre.25.2.248","volume":"25","author":"D. Tcha","year":"1977","unstructured":"Tcha, D. and Pliska, S.R., Optimal Control of Single-Server Queueing Networks and Multiclass M\/G\/1 Queues with Feedback. Operations Research, 25 (1977), 248\u2013258.","journal-title":"Operations Research"},{"key":"5_CR42","series-title":"IBM Research Report","volume-title":"The Region of Achievable Performance in a Model of Klimov","author":"P. Tsoucas","year":"1991","unstructured":"Tsoucas, P., The Region of Achievable Performance in a Model of Klimov. IBM Research Report RC-16543, IBM Research Division, T.J. Watson Research Center, Yorktown Hts., New York, NY 10598, 1991."},{"key":"5_CR43","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1109\/TAC.1985.1103989","volume":"30","author":"P. Varaiya","year":"1985","unstructured":"Varaiya, P., Walrand, J. and Buyyokoc, C., Extensions of the Multiarmed Bandit Problem: The Discounted Case. IEEE Trans. Automatic Control, 30 (1985), 426\u2013439.","journal-title":"IEEE Trans. Automatic Control"},{"key":"5_CR44","doi-asserted-by":"crossref","unstructured":"Weber, R., On the Gittins Index for Multiarmed Bandits. Annals of Applied Probability, (1992), 1024\u20131033.","DOI":"10.1214\/aoap\/1177005588"},{"key":"5_CR45","doi-asserted-by":"publisher","first-page":"202","DOI":"10.2307\/1427380","volume":"19","author":"R. Weber","year":"1987","unstructured":"Weber, R. and Stidham, S., Jr., Optimal Control of Service Rates in Networks of Queues. Adv. Appl. Prob., 19 (1987), 202\u2013218.","journal-title":"Adv. Appl. Prob."},{"key":"5_CR46","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1017\/S0269964800000826","volume":"2","author":"G. Weiss","year":"1988","unstructured":"Weiss, G., Branching Bandit Processes. Probability in the Engineering and Informational Sciences, 2 (1988), 269\u2013278.","journal-title":"Probability in the Engineering and Informational Sciences"},{"key":"5_CR47","volume-title":"Matroid Theory","author":"D. Welsh","year":"1976","unstructured":"Welsh, D., Matroid Theory, (1976), Academic Press, London."},{"key":"5_CR48","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1111\/j.2517-6161.1980.tb01111.x","volume":"42","author":"P. Whittle","year":"1980","unstructured":"Whittle, P., Multiarmed Bandits and the Gittins Index. J. Royal Statistical Society, Ser. B, 42 (1980), 143\u2013149.","journal-title":"J. Royal Statistical Society"},{"key":"5_CR49","volume-title":"Optimization over Time: Dynamic Programming and Stochastic Control","author":"P. Whittle","year":"1982","unstructured":"Whittle, P., Optimization over Time: Dynamic Programming and Stochastic Control, vols. I, II, Wiley, Chichester, 1982."},{"key":"5_CR50","doi-asserted-by":"publisher","first-page":"706","DOI":"10.1109\/70.63256","volume":"6","author":"D.D. Yao","year":"1990","unstructured":"Yao, D.D. and Shanthikumar, J.G., Optimal Scheduling Control of a Flexible Machine. IEEE Trans. on Robotics and Automation, 6 (1990), 706\u2013712.","journal-title":"IEEE Trans. on Robotics and Automation"},{"key":"5_CR51","unstructured":"Yao, D.D. and Zhang, L., Stochastic Scheduling and Polymatroid Optimization, Lecture Notes in Applied Mathematics, 33, G. Ying and Q. Zhang (eds.), Springer-Verlag, 1997, 333\u2013364."},{"key":"5_CR52","unstructured":"Zhang, L., Reliability and Dynamic Scheduling in Stochastic Networks. Ph.D. Thesis, Columbia University, 1997."}],"container-title":["Lecture Notes in Computer Science","Performance Evaluation of Complex Systems: Techniques and Tools"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45798-4_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,18]],"date-time":"2025-01-18T03:32:18Z","timestamp":1737171138000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45798-4_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540442523","9783540457985"],"references-count":52,"URL":"https:\/\/doi.org\/10.1007\/3-540-45798-4_5","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}