Submodular Returns and Greedy Heuristics for Queueing Scheduling Problems

References

• Aspvall B., Flam S. D., Villanger K. P. Selecting among scheduled projects. Opns. Res. Lett. (1995) 17:37–40Crossref, Google Scholar
• Bertsimas D., Niño-Mora J. Conservation laws, extended polymatroids and multi-armed bandit problems: A polyhedral approach to indexable systems. Math. Opns. Res. (1996) 21:257–306Link, Google Scholar
• De P., Ghosh J. B., Wells C. E. Job selection and sequencing on a single machine in a random environment. Eur. J. Opnl. Res. (1993) 70:425–431Crossref, Google Scholar
• Federgruen A., Groenevelt H. The impact of the composition of the customer base in general queueing models. J. Appl. Probab. (1987) 24:709–724Crossref, Google Scholar
• Federgruen A., Groenevelt H. Characterization and optimization of achievable performance in general queueing systems. Opns. Res. (1988a) 36:733–741Link, Google Scholar
• Federgruen A., Groenevelt H. M/G/c queueing systems with multiple customer classes: Characterization and control of achievable performance under nonpreemptive priority rules. Management Sci. (1988b) 34:1121–1138Link, Google Scholar
• Gelenbe E., Mitrani I.Analysis and Synthesis of Computer Systems (1980) (Academic Press, New York) Google Scholar
• Glazebrook K. D. On the evaluation of fixed permutations as strategies in stochastic scheduling. Stochastic Processes and Their Appl. (1982) 13:171–187Crossref, Google Scholar
• Nash P. Optimal allocation of resources between research projects. (1973) . Ph.D. thesis, Cambridge UniversityGoogle Scholar
• Nemhauser G. L., Wolsey L. A. Best algorithms for approximating the maximum of a submodular set function. Math. Opns. Res. (1978) 3:177–188Link, Google Scholar
• Nemhauser G. L., Wolsey L. A. Maximizing submodular set functions: Formulations and analysis of algorithms. Ann. Discrete Math. (1981) 11:279–301Google Scholar
• Ross K. W., Yao D. D. Optimal load balancing and scheduling in a distributed computer system. J. Assoc. Comput. Machinery (1991) 38:676–690Crossref, Google Scholar
• Shanthikumar J. G., Yao D. D. Multiclass queuing systems: Polymatroidal structure and optimal scheduling control. Opns. Res. (1992) 40(2):S293–299Link, Google Scholar
• Stadje W. Selecting jobs for scheduling on a machine subject to failure. Discrete Appl. Math. (1995) 63:257–265Crossref, Google Scholar
• Weber R. On the marginal benefit of adding servers to G/GI/m queues. Management Sci. (1980) 26(9):946–951Link, Google Scholar
• Weber R., Fleming W., Lions P. L. Stochastic scheduling on parallel processors and minimization of convex functions of completion times. Stochastic Differential Systems, Stochastic Control and Applications (1988) 10:601–609Crossref, Google Scholar
• Weber R. On the gittins index for multi-armed bandits. Ann. Appl. Probab. (1992) 2:1024–1033Crossref, Google Scholar
• Whittle P. Arm acquiring bandits. Ann. Probab. (1981) 9:284–292Crossref, Google Scholar