Hostname: page-component-586b7cd67f-l7hp2 Total loading time: 0 Render date: 2024-11-28T03:29:38.623Z Has data issue: false hasContentIssue false
  • English
  • Français

Optimal control of a flexible server

Part of: Operations research and management science Computer system organization Stochastic systems and control

Published online by Cambridge University Press:  01 July 2016

Hyun-Soo Ahn ,
Izak Duenyas  and
Rachel Q. Zhang
Hyun-Soo Ahn*
Affiliation:
University of California, Berkeley
Izak Duenyas*
Affiliation:
University of Michigan
Rachel Q. Zhang*
Affiliation:
Cornell University
*
∗ Postal address: Department of Industrial Engineering and Operations Research, University of California, Berkeley, CA 94720-1777, USA.
∗∗ Postal address: University of Michigan Business School, Ann Arbor, MI 48109, USA. Email address: [email protected]
∗∗∗ Johnson Graduate School of Management, Cornell University, Ithaca, NY 14853, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider the dynamic scheduling of a multiclass queueing system with two servers, one dedicated (server 1) and one flexible (server 2), with no arrivals. Server 1 is dedicated to processing type-1 jobs while server 2 is primarily responsible for processing type-2 jobs but can also aid server 1 with its work. We address when it is optimal for server 2 to aid server 1 with type-1 jobs rather than process type-2 jobs. The objective is to minimize the total holding costs incurred until all jobs in the system are processed and leave the system. We show that the optimal policy can exhibit one of three possible structures: (i) an exhaustive policy for type-2 jobs, (ii) a nonincreasing switching curve in the number of type-1 jobs and (iii) a nondecreasing switching curve in the number of type-1 jobs. We characterize the necessary and sufficient conditions under which each policy will be optimal. We also explore the use of the optimal policy for the problem with no arrivals as a heuristic for the problem with dynamic arrivals.

Keywords

Stochastic schedulingmultiserver queueflexible serverclearing system

MSC classification

Primary: 93E20: Optimal stochastic control
Secondary: 90B22: Queues and service 68M20: Performance evaluation; queueing; scheduling
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 36 , Issue 1 , March 2004 , pp. 139 - 170
Copyright
Copyright © Applied Probability Trust 2004 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Ahn, H.-S., Duenyas, I. and Zhang, R. Q. (1999). Optimal stochastic scheduling of a two-stage tandem queue with parallel servers. Adv. Appl. Prob. 31, 1095–1117.Google Scholar
Andradottir, S., Ayhan, H. and Down, D. G. (2001). Server assignment policies for maximizing the steady-state throughput of finite queueing systems. Manag. Sci. 47, 1421–1439.CrossRefGoogle Scholar
Bell, S. and Williams, R. (2001). Dynamic scheduling of a system with two parallel servers in heavy traffic with complete resource pooling: asymptotic optimality of a continuous review threshold policy. Ann. Appl. Prob. 11, 608–649.Google Scholar
Buyukkoc, C., Varaiya, P. and Walrand, J. (1985). The cμ rule revisited. Adv. Appl. Prob. 17, 237–238.Google Scholar
Chen, M., Pandit, C. and Meyn, S. P. (2003). In search of sensitivity in network optimization. Queueing Systems 44, 313–363.Google Scholar
Duenyas, I., Gupta, D. and Olsen, T. (1998). Control of a single-server tandem queueing system with setups. Operat. Res. 46, 218–230.Google Scholar
Farrar, T. (1993). Optimal use of an extra server in a two station tandem queueing network. IEEE Trans. Automatic Control 38, 1296–1299.Google Scholar
Harrison, J. M. (1998). Heavy traffic analysis of a system with parallel servers: asymptotic analysis of discrete-review policies. Ann. Appl. Prob. 8, 822–848.CrossRefGoogle Scholar
Harrison, J. M. and Lopez, M. J. (1999). Heavy traffic resource pooling in parallel-server systems. Queueing Systems 33, 339–368.CrossRefGoogle Scholar
Iravani, S. M. R., Posner, M. J. M. and Buzacott, J. A. (1996). An N-stage tandem queueing system attended by a moving server with holding and switching costs. Tech. Rep. 96-09, Department of Industrial Engineering, University of Toronto.Google Scholar
Iravani, S. M. R., Posner, M. J. M. and Buzacott, J. A. (1997). A two-stage tandem queue attended by a moving server with holding and switching costs. Queueing Systems 26, 203–228.Google Scholar
Kim, E. and Van Oyen, M. P. (1998). Beyond the cμ rule: dynamic scheduling of a two-class loss queue. Math. Meth. Operat. Res. 48, 17–36.Google Scholar
Kumar, S. and Muthuraman, M. (2002). A numerical method for solving singular stochastic control problems. Preprint, Stanford University.Google Scholar
Meyn, S. (2001). Sequencing and routing in multiclass queueing networks. I. Feedback regulation. 40, 741–776.Google Scholar
Meyn, S. (2003). Sequencing and routing in multiclass queueing networks. II. Workload relaxations. SIAM J. Control Optimization 42, 178–217.Google Scholar
Pandelis, D. G. and Teneketzis, D. (1994). Optimal multiserver stochastic scheduling of two interconnected priority queues. Adv. Appl. Prob. 26, 258–279.CrossRefGoogle Scholar
Van Oyen, M. P., Gel, E. S. and Hopp, W. J. (2001). Performance opportunity for workforce agility in collaborative and noncollaborative work systems. IIE Trans. 33, 761–777.CrossRefGoogle Scholar
Walrand, J. (1988). An Introduction to Queueing Networks. Prentice-Hall, New York.Google Scholar