{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T10:15:04Z","timestamp":1773656104681,"version":"3.50.1"},"reference-count":62,"publisher":"Springer Science and Business Media LLC","issue":"3-4","license":[{"start":{"date-parts":[[1995,9,1]],"date-time":"1995-09-01T00:00:00Z","timestamp":809913600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Queueing Syst"],"published-print":{"date-parts":[[1995,9]]},"DOI":"10.1007\/bf01149167","type":"journal-article","created":{"date-parts":[[2005,2,16]],"date-time":"2005-02-16T12:06:16Z","timestamp":1108555576000},"page":"337-389","source":"Crossref","is-referenced-by-count":32,"title":["The achievable region method in the optimal control of queueing systems; formulations, bounds and policies"],"prefix":"10.1007","volume":"21","author":[{"given":"Dimitris","family":"Bertsimas","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"CR1","unstructured":"E. Anderson and P. Nash,Linear Programming in Infinite-Dimensional Spaces;Theory and Applications (Wiley, 1987)."},{"key":"CR2","unstructured":"F. Avram, D. Bertsimas and M. Ricard, Optimization of multiclass fluid queueing networks: a linear control approach, to appear inStochastic Networks;Proc. IMA (1995), eds. F. Kelly and R. Williams, pp. 199?234."},{"key":"CR3","unstructured":"D. Atkins and H. Chen, Dynamic scheduling control for a network of queues, to appear."},{"key":"CR4","volume-title":"Dynamic Programming","author":"R.E. Bellman","year":"1957","unstructured":"R.E. Bellman,Dynamic Programming (Princeton University Press, Princeton, 1957)."},{"key":"CR5","unstructured":"D. Bertsimas and T. Cryssikou, Bounds and policies for loss networks, in preparation."},{"key":"CR6","unstructured":"D. Bertsimas and J. Nino-Mora, Conservation laws, extended polymatroids and multiarmed bandit problems; a unified approach to indexable systems, to appear in Math. Oper. Res."},{"key":"CR7","unstructured":"D. Bertsimas and J. Nino-Mora, Restless bandits, linear programming relaxations and a primaldual heuristic, submitted for publication."},{"key":"CR8","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1214\/aoap\/1177005200","volume":"4","author":"D. Bertsimas","year":"1994","unstructured":"D. Bertsimas, I. Paschalidis and J. Tsitsiklis, Optimization of multiclass queueing networks: polyhedral and nonlinear characterizations of achievable performance, Ann. Appl. Prob. 4 (1994) 43?75.","journal-title":"Ann. Appl. Prob."},{"key":"CR9","unstructured":"D. Bertsimas, I. Paschalidis and J. Tsitsiklis, Branching bandits and Klimov's problem: achievable region and side constraints, to appear in IEEE Trans. Autom. Contr."},{"key":"CR10","unstructured":"D. Bertsimas and H. Xu, Optimization of polling systems and dynamic vehicle routing problems on networks, submitted for publication."},{"key":"CR11","unstructured":"D. Bertsimas and R. Vohra, Linear programming relaxations, approximation algorithms and randomization: a unified approach to covering problems, submitted for publication."},{"key":"CR12","unstructured":"P.P. Bhattacharya, L. Georgiadis and P. Tsoucas, Extended polymatroids: Properties and optimization,Proc. Int. Conf. on Integer Programming and Combinatorial Optimization, Carnegie Mellon University (Mathematical Programming Society, 1991) pp 349?361."},{"key":"CR13","first-page":"349","volume-title":"Performance '90","author":"O.J. Boxma","year":"1990","unstructured":"O.J. Boxma, H. Levy and J.A. Weststrate, Optimization of polling systems, in:Performance '90, eds. P. King, I. Mitrani and R. Pooley (North-Holland, Amsterdam 1990) pp. 349?361."},{"key":"CR14","unstructured":"H. Chen and D. Yao, Optimal scheduling control of a multiclass fluid network, to appear in Oper. Res."},{"key":"CR15","doi-asserted-by":"crossref","first-page":"810","DOI":"10.1287\/opre.28.3.810","volume":"28","author":"E. Coffman","year":"1980","unstructured":"E. Coffman and I. Mitrani, A characterization of waiting time performance realizable by single server queues, Oper. Res. 28 (1980) 810?821.","journal-title":"Oper. Res."},{"key":"CR16","volume-title":"Queues","author":"D.R. Cox","year":"1961","unstructured":"D.R. Cox and W.L. Smith,Queues (Methuen, London\/Wiley, New York, 1961)."},{"key":"CR17","first-page":"69","volume-title":"Combinatorial Structures and Their Applications","author":"J. Edmonds","year":"1970","unstructured":"J. Edmonds, Submodular functions, matroids and certain polyhedra, in: Combinatorial Structures and Their Applications, eds. R. Guy et al. (Gordon and Breach, New York, 1970) pp. 69?87."},{"key":"CR18","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1287\/opre.36.5.733","volume":"36","author":"A. Federgruen","year":"1988","unstructured":"A. Federgruen and H. Groenevelt, Characterization and optimization of achievable performance in general queueing systems. Oper. Res. 36 (1988) 733?741.","journal-title":"Oper. Res."},{"key":"CR19","doi-asserted-by":"crossref","first-page":"1121","DOI":"10.1287\/mnsc.34.9.1121","volume":"34","author":"A. Federgruen","year":"1988","unstructured":"A. Federgruen and H. Groenevelt,M\/G\/c queueing systems with multiple customer classes: Characterization and control of achievable performance under nonpreemptive priority rules, Manag. Sci. 34 (1988) 1121?1138.","journal-title":"Manag. Sci."},{"key":"CR20","volume-title":"Analysis and Synthesis of Computer Systems","author":"E. Gelenbe","year":"1980","unstructured":"E. Gelenbe and I. Mitrani,Analysis and Synthesis of Computer Systems (Academic Press, New York, 1980)."},{"key":"CR21","first-page":"241","volume-title":"Progress in Statistics European Meeting of Statisticians 1972, Vol. 1","author":"J.C. Gittins","year":"1974","unstructured":"J.C. Gittins and D.M. Jones, A dynamic allocation index for the sequential design of experiments, eds. J. Gani, K. Sarkadi and I. Vince in:Progress in Statistics European Meeting of Statisticians 1972, Vol. 1 (North-Holland, Amsterdam, 1974) pp. 241?266."},{"key":"CR22","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1111\/j.2517-6161.1979.tb01068.x","volume":"B14","author":"J.C. Gittins","year":"1979","unstructured":"J.C. Gittins, Bandit processes and dynamic allocation indices, J. Roy. Stat. Soc. Series, B14 (1979) 148?177.","journal-title":"J. Roy. Stat. Soc. Series"},{"key":"CR23","unstructured":"J.C. Gittins,Bandit Processes and Dynamic Allocation Indices (Wiley, 1989)."},{"key":"CR24","doi-asserted-by":"crossref","unstructured":"K.D. Glazebrook, Stochastic scheduling with order constraints, Int. J. Syst. Sci. (1976) 657?666.","DOI":"10.1080\/00207727608941950"},{"key":"CR25","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1287\/moor.12.2.205","volume":"12","author":"K.D. Glazebrook","year":"1987","unstructured":"K.D. Glazebrook, Sensitivity analysis for stochastic scheduling problems, Math. Oper. Res. 12 (1987) 205?223.","journal-title":"Math. Oper. Res."},{"key":"CR26","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1287\/opre.23.2.260","volume":"23","author":"J.M. Harrison","year":"1975","unstructured":"J.M. Harrison, A priority queue with discounted linear costs, Oper. Res. 23 (1975) 260?269.","journal-title":"Oper. Res."},{"key":"CR27","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1287\/opre.23.2.270","volume":"23","author":"J.M. Harrison","year":"1975","unstructured":"J.M. Harrison, Dynamic scheduling of a multiclass queue: discount optimality, Oper. Res. 23 (1975) 270?282.","journal-title":"Oper. Res."},{"key":"CR28","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF01225319","volume":"5","author":"J.M. Harrison","year":"1989","unstructured":"J.M. Harrison and L.M. Wein, Scheduling network of queues: Heavy traffic analysis of a simple open network', Queueing Systems 5 (1989) 265?280.","journal-title":"Queueing Systems"},{"key":"CR29","volume-title":"Stochastic Models in Operations Research, Vol. II: Stochastic Optimization","author":"D.P. Heyman","year":"1984","unstructured":"D.P. Heyman and M.J. Sobel,Stochastic Models in Operations Research, Vol. II: Stochastic Optimization (McGraw-Hill, New York, 1984)."},{"key":"CR30","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1137\/0216029","volume":"16","author":"M. Hofri","year":"1988","unstructured":"M. Hofri and K.W. Ross, On the optimal control of two queues with server set up times and its analysis, SIAM J. Comp. 16 (1988) 399?419.","journal-title":"SIAM J. Comp."},{"key":"CR31","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1137\/0123021","volume":"23","author":"W.A. Horn","year":"1972","unstructured":"W.A. Horn, Single-machine job sequencing with treelike precedence ordering and linear delay penalties, SIAM J. Appl. Math. 23 (1972) 189?202.","journal-title":"SIAM J. Appl. Math."},{"key":"CR32","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1214\/aoap\/1177005872","volume":"1","author":"F. Kelly","year":"1991","unstructured":"F. Kelly, Loss networks, Ann. Appl. Prob. 1 (1991) 319?378.","journal-title":"Ann. Appl. Prob."},{"key":"CR33","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/moor.19.1.1","volume":"19","author":"F. Kelly","year":"1994","unstructured":"F. Kelly, Bounds on the performance of dynamic routing schemes for highly connected networks, Math. Oper. Res. 19 (1994) 1?20.","journal-title":"Math. Oper. Res."},{"key":"CR34","doi-asserted-by":"crossref","first-page":"716","DOI":"10.1287\/opre.36.5.716","volume":"36","author":"L. Kleinrock","year":"1988","unstructured":"L. Kleinrock and H. Levy, The analysis of random polling systems, Oper. Res. 36 (1988) 716?732.","journal-title":"Oper. Res."},{"key":"CR35","doi-asserted-by":"crossref","first-page":"532","DOI":"10.1137\/1119060","volume":"19","author":"G.P. Klimov","year":"1974","unstructured":"G.P. Klimov, Time sharing service systems I, Theor, Prob. Appl. 19 (1974) 532?551.","journal-title":"Theor, Prob. Appl."},{"key":"CR36","doi-asserted-by":"crossref","first-page":"1600","DOI":"10.1109\/9.310033","volume":"39","author":"S. Kumar","year":"1994","unstructured":"S. Kumar and P.R. Kumar, Performance bounds for queueing networks and scheduling policies, IEEE Trans. Autom. Contr. 39 (1994) 1600?1611.","journal-title":"IEEE Trans. Autom. Contr."},{"key":"CR37","doi-asserted-by":"crossref","first-page":"1750","DOI":"10.1109\/26.61446","volume":"38","author":"H. Levy","year":"1990","unstructured":"H. Levy and M. Sidi, Polling systems: applications, modelling and optimization, IEEE Trans. Commun. 38 (1990) 1750?1760.","journal-title":"IEEE Trans. Commun."},{"key":"CR38","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/BF02411471","volume":"6","author":"H. Levy","year":"1990","unstructured":"H. Levy, M. Sidi and O.J. Boxma, Dominance relations in polling systems, Queueing Systems 6 (1990) 155?171.","journal-title":"Queueing Systems"},{"key":"CR39","doi-asserted-by":"crossref","unstructured":"L. Lov\u00e1sz and A. Schrijver, Cones of matrices and set functions and 0?1 optimization, SIAM J. Opt. (1990) 166?190.","DOI":"10.1137\/0801013"},{"key":"CR40","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0304-4149(77)90029-1","volume":"5","author":"I. Meilijson","year":"1977","unstructured":"I. Meilijson and G. Weiss, Multiple feedback at a single-server station, Stoch. Process. Appl. 5 (1977) 195?205.","journal-title":"Stoch. Process. Appl."},{"key":"CR41","volume-title":"Linear Programming","author":"K.G. Murty","year":"1983","unstructured":"K.G. Murty,Linear Programming (Wiley, New York, 1983)."},{"key":"CR42","doi-asserted-by":"crossref","first-page":"460","DOI":"10.1214\/aoap\/1177005711","volume":"2","author":"Z. Ou","year":"1992","unstructured":"Z. Ou and L. Wein, Performance bounds for scheduling queueing networks, Ann. Appl. Prob. 2 (1992) 460?480.","journal-title":"Ann. Appl. Prob."},{"key":"CR43","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/BF01581271","volume":"58","author":"M. Queyranne","year":"1993","unstructured":"M. Queyranne, Structure of a simple scheduling polyhedron, Math. Program. 58 (1993) 263?285.","journal-title":"Math. Program."},{"key":"CR44","unstructured":"C. Papadimitriou,Computational Complexity (Addison-Wesley, 1994)."},{"key":"CR45","unstructured":"C. Papadimitriou and J. Tsitsiklis, Complexity of queueing network problems, Extended Abstract (1993)."},{"key":"CR46","unstructured":"M. Reiman and L. Wein, Dynamic scheduling of a two-class queue with setups, submitted for publication."},{"key":"CR47","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1109\/9.8648","volume":"34","author":"K.W. Ross","year":"1989","unstructured":"K.W. Ross and D.D. Yao, Optimal dynamic scheduling in Jackson Networks, IEEE Trans. Autom. Contr. 34 (1989) 47?53.","journal-title":"IEEE Trans. Autom. Contr."},{"key":"CR48","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1287\/mnsc.12.5.437","volume":"12","author":"M.H. Rothkopf","year":"1966","unstructured":"M.H. Rothkopf, Scheduling independent tasks on parallel processors, Manag. Sci. 12 (1966) 437?447.","journal-title":"Manag. Sci."},{"key":"CR49","doi-asserted-by":"crossref","first-page":"707","DOI":"10.1287\/mnsc.12.9.707","volume":"12","author":"M.H. Rothkopf","year":"1966","unstructured":"M.H. Rothkopf, Scheduling with random service times, Manag. Sci. 12 (1966) 707?713.","journal-title":"Manag. Sci."},{"issue":"Suppl. 2","key":"CR50","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1287\/opre.40.3.S293","volume":"40","author":"J.G. Shantikumar","year":"1992","unstructured":"J.G. Shantikumar and D.D. Yao, Multiclass queueing systems: Polymatroidal structure and optimal scheduling control, Oper. Res. 40, Suppl. 2 (1992) S293?299.","journal-title":"Oper. Res."},{"key":"CR51","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/nav.3800030106","volume":"3","author":"W.E. Smith","year":"1956","unstructured":"W.E. Smith, Various optimizers for single-stage production, Naval Res. Logist. Quart. 3 (1956) 59?66.","journal-title":"Naval Res. Logist. Quart."},{"key":"CR52","doi-asserted-by":"crossref","unstructured":"H. Takagi,Analysis of Polling Systems (MIT Press, 1986).","DOI":"10.1016\/0166-5316(85)90016-1"},{"key":"CR53","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1145\/62058.62059","volume":"20","author":"H. Takagi","year":"1988","unstructured":"H. Takagi, Queueing analysis of polling systems, ACM Comput. Surveys 20 (1988) 5?28.","journal-title":"ACM Comput. Surveys"},{"key":"CR54","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1287\/opre.25.2.248","volume":"25","author":"D.W. Tcha","year":"1977","unstructured":"D.W. Tcha and S.R. Pliska, Optimal control of single-server queueing networks and multi-classM\/G\/1 queues with feedback, Oper. Res. 25 (1977) 248?258.","journal-title":"Oper. Res."},{"key":"CR55","doi-asserted-by":"crossref","first-page":"576","DOI":"10.1109\/TAC.1986.1104332","volume":"31","author":"J.N. Tsitsiklis","year":"1986","unstructured":"J.N. Tsitsiklis, A lemma on the multiarmed bandit problem, IEEE Trans. Autom. Contr. 31 (1986) 576?577.","journal-title":"IEEE Trans. Autom. Contr."},{"key":"CR56","unstructured":"J.N. Tsitsiklis, A short proof of the Gittins index theorem, Ann. Appl. Prob, to appear."},{"key":"CR57","unstructured":"P. Tsoucas, The region of achievable performance in a model of Klimov, Technical Report RC16543, IBM T.J. Watson Research Center (1991)."},{"key":"CR58","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1109\/TAC.1985.1103989","volume":"30","author":"P.P. Varaiya","year":"1985","unstructured":"P.P. Varaiya, J.C. Walrand and C. Buyukkoc, Extensions of the multiarmed bandit problem: The discounted case, IEEE Trans. Autom. Contr. 30 (1985) 426?439.","journal-title":"IEEE Trans. Autom. Contr."},{"key":"CR59","doi-asserted-by":"crossref","first-page":"1024","DOI":"10.1214\/aoap\/1177005588","volume":"2","author":"R. Weber","year":"1992","unstructured":"R. Weber, On the Gittins index for multiarmed bandits, Ann. Appl. Prob. 2 (1992) 1024?1033.","journal-title":"Ann. Appl. Prob."},{"key":"CR60","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1017\/S0269964800000826","volume":"2","author":"G. Weiss","year":"1988","unstructured":"G. Weiss, Branching bandit processes, Prob. Eng. Inf. Sci. 2 (1988) 269?278.","journal-title":"Prob. Eng. Inf. Sci."},{"key":"CR61","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1111\/j.2517-6161.1980.tb01111.x","volume":"42","author":"P. Whittle","year":"1980","unstructured":"P. Whittle, Multiarmed bandits and the Gittins index, J. Roy. Stat. Soc. 42 (1980) 143?149.","journal-title":"J. Roy. Stat. Soc."},{"key":"CR62","unstructured":"P. Whittle, Restless bandits: activity allocation in changing world,Celebration of Applied Probability, ed. J. Gani, J. Appl. Prob. A25 (1988) 287?298."}],"container-title":["Queueing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01149167.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01149167\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01149167","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T10:16:27Z","timestamp":1734948987000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01149167"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,9]]},"references-count":62,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[1995,9]]}},"alternative-id":["BF01149167"],"URL":"https:\/\/doi.org\/10.1007\/bf01149167","relation":{},"ISSN":["0257-0130","1572-9443"],"issn-type":[{"value":"0257-0130","type":"print"},{"value":"1572-9443","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,9]]}}}