On the optimal control of parallel processing networks with resource collaboration and multitasking. (English) Zbl 1492.90028
Summary: We study scheduling control of parallel processing networks in which some resources need to simultaneously collaborate to perform some activities and some resources multitask. Resource collaboration and multitasking give rise to synchronization constraints in resource scheduling when the resources are not divisible, that is, when the resources cannot be split. The synchronization constraints affect the system performance significantly. For example, because of those constraints, the system capacity can be strictly less than the capacity of the bottleneck resource. Furthermore, the resource scheduling decisions are not trivial under those constraints. For example, not all static prioritization policies retain the maximum system capacity, and the ones that retain the maximum system capacity do not necessarily minimize the delay (or, in general, the holding cost). We study optimal scheduling control of a class of parallel networks and propose a dynamic prioritization policy that retains the maximum system capacity and is asymptotically optimal in diffusion scale and a conventional heavy-traffic regime with respect to the expected discounted total holding cost objective.
MSC:
| 90B10 | Deterministic network models in operations research |
| 90B22 | Queues and service in operations research |
| 90B36 | Stochastic scheduling theory in operations research |
| 90C40 | Markov and semi-Markov decision processes |
| 60K30 | Applications of queueing theory (congestion, allocation, storage, traffic, etc.) |
| 91B32 | Resource and cost allocation (including fair division, apportionment, etc.) |
Keywords:
resource collaboration; multitasking; indivisible resources; scheduling control; asymptotic optimalityReferences:
| [1] | Bell SL, Williams RJ (2001) Dynamic scheduling of a system with two parallel servers in heavy traffic with resource pooling: Asymptotic optimality of a threshold policy. Ann. Appl. Probab. 11(3):608-649.Google Scholar · Zbl 1015.60080 |
| [2] | Billingsley P (1999) Convergence of Probability Measures, 2nd ed. (Wiley, New York).Google Scholar · Zbl 0944.60003 |
| [3] | Bo Y, Dawande M, Huh WT, Janakiraman G, Nagarajan M (2019) Determining process capacity: Intractability and efficient special cases. Manufacturing Service Oper. Management 21(1):139-153.Abstract, Google Scholar |
| [4] | Brucker P, Drexl A, Möhring R, Neumann K, Pesch E (1999) Resource-constrained project scheduling: Notation, classification, models, and methods. Eur. J. Oper. Res. 112(1):3-41.Google Scholar · Zbl 0937.90030 |
| [5] | Budhiraja A, Johnson D (2020) Control policies approaching hierarchical greedy ideal performance in heavy traffic for resource sharing networks. Math. Oper. Res. 45(3):797-832.Link, Google Scholar · Zbl 1451.90073 |
| [6] | Courcoubetis C, Reiman MI (1987) Optimal control of a queueing system with simultaneous service requirements. IEEE Trans. Automatic Control 32(8):717-727.Google Scholar · Zbl 0633.90020 |
| [7] | Czajkowski K, Fitzgerald S, Foster I, Kesselman C (2001) Grid information services for distributed resource sharing. Proc. 10th IEEE Internat. Sympos. High Performance Distributed Comput. (IEEE, San Francisco, CA), 181-194.Google Scholar |
| [8] | Dai JG, Lin W (2005) Maximum pressure policies in stochastic processing networks. Oper. Res. 53(2):197-218.Link, Google Scholar · Zbl 1165.90359 |
| [9] | Dobson G, Lee HH, Sainathan A, Tilson V (2012) A queueing model to evaluate the impact of patient “batching” on throughput and flow time in a medical teaching facility. Manufacturing Service Oper. Management 14(4):584-599.Link, Google Scholar |
| [10] | Glynn PW (1990) Diffusion approximations. Heyman DP, Sobel MJ, eds. Handbooks in Operations Research and Management Science, vol. 2 (North-Holland: Elsevier), 145-198.Google Scholar · Zbl 0703.60072 |
| [11] | Gurvich I, Van Mieghem JA (2015) Collaboration and multitasking in networks: Architectures, bottlenecks, and capacity. Manufacturing Service Oper. Management 17(1):16-33.Link, Google Scholar |
| [12] | Gurvich I, Van Mieghem JA (2018) Collaboration and multitasking in networks: Prioritization and achievable capacity. Management. Sci. 64(5):2390-2406.Link, Google Scholar |
| [13] | Gurvich I, O’Leary KJ, Wang L, Mieghem JAV (2020) Collaboration, interruptions and changeover times: Workflow model and empirical study of hospitalist charting. Manufacturing Service Oper. Management 22(4):754-774.Abstract, Google Scholar |
| [14] | Han L, Camlibel MK, Pang JS, Heemels WPMH (2012) A unified numerical scheme for linear-quadratic optimal control problems with joint control and state constraints. Optim. Methods Software 27(4-5):761-799.Google Scholar · Zbl 1260.49064 |
| [15] | Harrison JM (1988) Brownian models of queueing networks with heterogeneous customer populations. Fleming W, Lions PL, eds. Stochastic Differential Systems, Stochastic Control Theory and Their Applications, The IMA Volumes in Mathematics and Its Applications, vol. 10 (Springer, New York), 147-186.Google Scholar · Zbl 0658.60123 |
| [16] | Harrison JM (1998) Heavy traffic analysis of a system with parallel servers: Asymptotic optimality of discrete-review policies. Ann. Appl. Probab. 8(3):822-848.Google Scholar · Zbl 0938.60094 |
| [17] | Harrison JM (2000) Brownian models of open processing networks: Canonical representation of workload. Ann. Appl. Probab. 10(1):75-103.Google Scholar · Zbl 1131.60306 |
| [18] | Harrison JM, Mandayam C, Shah D, Yang Y (2014) Resource sharing networks: Overview and an open problem. Stochastic Systems 4(2):524-555.Link, Google Scholar · Zbl 1314.68024 |
| [19] | Hindman B, Konwinski A, Zaharia M, Ghodsi A, Joseph AD, Katz R, Shenker S, Stoica I (2011) Eighth USENIX Sympos. Networked Systems Design Implementation (NSDI 11), Mesos: A Platform for Fine-Grained Resource Sharing in the Data Center (Usenix, Boston), 1-14.Google Scholar |
| [20] | Maglaras C (2003) Continuous-review tracking policies for dynamic control of stochastic networks. Queueing Systems 43:43-80.Google Scholar · Zbl 1010.90004 |
| [21] | Meyn SP (2003) Sequencing and routing in multiclass queueing networks part II: Workload relaxations. SIAM J. Control Optim. 42(1):178-217.Google Scholar · Zbl 1061.90047 |
| [22] | Özkan E, Ward AR (2019) On the control of fork-join networks. Math. Oper. Res. 44(2):532-564.Link, Google Scholar · Zbl 1434.60265 |
| [23] | Pesic V, Williams RJ (2016) Dynamic scheduling for parallel server systems in heavy traffic: Graphical structure, decoupled workload matrix and some sufficient conditions for solvability of the Brownian control problem. Stochastic Systems 6(1):26-89.Link, Google Scholar · Zbl 1356.60156 |
| [24] | Schrijver A (1998) Theory of Linear and Integer Programming (Wiley, New York).Google Scholar · Zbl 0970.90052 |
| [25] | Shah D, Walton N, Zhong Y (2014) Optimal queue-size scaling in switched networks. Ann. Appl. Probab. 24(6):2207-2245.Google Scholar · Zbl 1307.60135 |
| [26] | Vavasis SA (2009) Complexity theory: Quadratic programming. Floudas C, Pardalos P, eds. Encyclopedia of Optimization, 2nd ed. (Springer, Boston), 451-454.Google Scholar |
| [27] | Whitt W (2002) Stochastic-Process Limits: An Introduction to Stochastic-Process Limits and Their Application to Queues (Springer, New York).Google Scholar · Zbl 0993.60001 |
| [28] | Williams RJ (1998) An invariance principle for semimartingale reflecting Brownian motions in an orthant. Queueing Systems 30:5-25.Google Scholar · Zbl 0911.90170 |
| [29] | Yu CH, Doppler K, Ribeiro CB, Tirkkonen O (2011) Resource sharing optimization for device-to-device communication underlaying cellular networks. IEEE Trans. Wireless Comm. 10(8):2752-2763.Google Scholar |
| [30] | Zychlinski N, Chan CW, Dong J (2019) Managing queues with different resource requirements. Working paper, Columbia University, New York.Google Scholar |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
