Technical Note—A Near-Optimal Algorithm for Real-Time Order Acceptance: An Application in Postacute Healthcare Services

Motivated by an application at a postacute healthcare provider, we study an infinite-horizon, stochastic optimization problem with a set of long-term capacity investment decisions and a sequence of real-time order acceptance/rejection decisions. The goal is to maximize the long-run average expected profit per period. The firm employs full-time resources of various kinds, such as nurses and therapists. For each kind of resource, multiple types are available. For example, registered nurses (RNs) are more expensive to employ than licensed practical nurses (LPNs); however, RNs can serve a greater range of patients than LPNs. Thus, the long-term capacity decision for this firm is the number of each type of resource to employ full time. A full-time resource may, at times, become unavailable (i.e., be absent); this absenteeism is stochastic. When the need for resources cannot be met from the pool of full-time employees, the firm has access to on-demand, part-time resources, who are paid a higher hourly rate than an equivalent full-time resource. On the demand side, the firm receives referrals —requests to commit service to patients over a time window (whose duration is stochastic), which is referred to as an episode —in real time. The referral arrival process is stochastic. A referral is characterized by the revenue it provides to the firm, the resources required to serve that patient, the frequency with which each of these resources is required, and the distribution of the episode duration. The decision to accept or reject a referral has to be instantaneous; if accepted, the service episode starts immediately. We develop a simple solution to the optimization problem, derive a worst-case guarantee on its optimality gap, and demonstrate that this gap vanishes in a meaningful asymptotic regime. We also illustrate the impressive performance of our solution numerically on a testbed of problem instances whose input parameters are drawn using publicly available healthcare data.