Admission Control of Parallel Queues with Fork Types of Jobs

Bing Lin (), Rohit Bhatnagar and Yuchen Lin
Additional contact information
Bing Lin: Jiangsu Normal University
Rohit Bhatnagar: Nanyang Technological University
Yuchen Lin: Xi’an Jiaotong-Liverpool University

Methodology and Computing in Applied Probability, 2024, vol. 26, issue 4, 1-30

Abstract: Abstract In this paper, we consider the problem of admission control for a stream of jobs arriving at two single-server queues working in parallel, with general inter-arrival time distribution and exponential service-time distribution. The jobs are classified into three types: two of these types are dedicated to being processed completely by one of the two servers. The third job is a fork type wherein each admitted job upon arrival splits into two sub jobs and each of which enters one of the two queues. In addition, each type of jobs is further segmented into multiple classes according to the revenue earned on job acceptance. We formulate the admission control problem of the above queueing system as a finite-horizon stochastic dynamic program. Using value iteration, we characterize the structure of the optimal policy as a set of monotone switching curves. Further, we extend our analysis to the batch arrival case, the infinite-horizon case, and the case with more than two parallel queues. To address the computational issues of the multi-dimensional dynamic programming associated with the models, we develop an efficient improved control policy to solve the problem. Finally, numerical examples are used to illustrate the monotone structure of switching curves and compare the performance of the optimal and improved control policies.

Keywords: Parallel queues; Admission control; Logistics; Optimal policy; Dynamic programming (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s11009-024-10113-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:metcap:v:26:y:2024:i:4:d:10.1007_s11009-024-10113-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/11009

DOI: 10.1007/s11009-024-10113-x

Access Statistics for this article

Methodology and Computing in Applied Probability is currently edited by Joseph Glaz

More articles in Methodology and Computing in Applied Probability from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().