Near-Optimal Adaptive Policies for Serving Stochastically Departing Customers

Danny Segev ()
Additional contact information
Danny Segev: School of Mathematical Sciences and Coller School of Management, Tel Aviv University, Tel Aviv 69978, Israel

Operations Research, 2025, vol. 73, issue 5, 2744-2760

Abstract: We consider a multistage stochastic optimization problem, studying how a single server should prioritize stochastically departing customers. In this setting, our objective is to determine an adaptive service policy that maximizes the expected total reward collected along a discrete planning horizon, in the presence of customers who are independently departing between one stage and the next with known stationary probabilities. Despite its deceiving structural simplicity, we are unaware of nontrivial results regarding the rigorous design of optimal or truly near-optimal policies at present time. Our main contribution resides in proposing a quasi-polynomial-time approximation scheme for serving impatient customers. Specifically, letting n be the number of underlying customers, our algorithm identifies in O ( n O ϵ ( log 2 n ) ) time a service policy whose expected reward is within factor 1 − ϵ of the optimal adaptive reward. Our method for deriving this approximation scheme synthesizes various stochastic analyses in order to investigate how the adaptive optimum is affected by alterations to several instance parameters, including the reward values, the departure probabilities, and the collection of customers itself.

Keywords: Stochastic; Models; quasi-PTAS; probabilistic coupling; dynamic programming (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.0548 (application/pdf)

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:inm:oropre:v:73:y:2025:i:5:p:2744-2760

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().