Managing Queues with Reentrant Customers in Support of Hybrid Healthcare

1. Introduction

The COVID-19 pandemic has dramatically affected healthcare worldwide, accelerating broad acceptance of telemedicine and transforming the provision of medical care (Bokolo 2020, Kadir 2020). Telemedicine refers to technologies that enable the provision of remote clinical services via real-time communication between patients and healthcare providers, using video conferencing and patient monitoring (Monaghesh and Hajizadeh 2020). Telemedicine and virtual care can be integrated into the healthcare system to maximize the efficiency of healthcare delivery (Hur and Chang 2020, Kadir 2020). Indeed, telehealth adoption has significantly increased across the 50 countries most affected by COVID-19 (Wong et al. 2021).

Telemedicine advantages include the reduction of contagion risk and emergency room/clinic visits (Chauhan et al. 2020, Doshi et al. 2020). Virtual visits promote social distancing and help circumvent prolonged waiting times. Moreover, by minimizing in-person visits, telehealth can help reduce spread of today’s virus and future ones and protect medical practitioners from infection (Hollander and Carr 2020). Clearly, healthcare provision through telehealth will have a permanent role in traditional healthcare delivery long after COVID-19 becomes endemic (Ahmed et al. 2020).

Despite the obvious advantages of virtual visits, when operating and designing such systems, one must be aware of their potential for providing low-value instead of quality care (O’Reilly-Jacob et al. 2021). In this paper, we focus on one important aspect of ensuring that patients receive quality care, which has significant operational implications: the requirement for a supplementary face-to-face visit. Specifically, there is evidence that virtual visits are likely to lead to a follow-up, in-person visit (Ashwood et al. 2017, Shi et al. 2018). This usually has to do with the fact that some medical examinations/procedures cannot be executed remotely (McConnochie et al. 2015, Uscher-Pines et al. 2016). Indeed, an empirical study from a large healthcare system in the United States revealed that e-visits remove the gatekeepers between patients and specialist physicians and trigger a 6% increase in in-person visits (Bavafa et al. 2018).

To ground our model, we consider the real-world case of an urgent care center or a community clinic that patients visit only when they feel sick. An example of such a center, mentioned in Çakıcı and Mills (2021), is Northwell Health (https://www.gohealthuc.com/northwell), the largest healthcare provider in New York state. When patients seek urgent care, they are offered the opportunity to book a telehealth visit instead of heading to the clinic for an in-person visit. Then, they can meet with any available physician on call. If they choose a telehealth visit and require a supplementary in-person visit, they arrive at the clinic and see one of the available physicians there.

To better understand the effect of these supplementary visits on system performance and decision making, we study a hybrid healthcare system, which provides virtual and in-person visits. The first visit to the system can be either in person or virtual. In a face-to-face visit, patients wait in a waiting room and are, thus, exposed to other illnesses. In a virtual visit, patients wait in the comfort of their home; nevertheless, they might require a supplementary in-person visit. We model the patients requiring a supplementary visit as a different class of patients (i.e., the patient’s class switches when physically entering the clinic). This is because the supplementary visit might have different characteristics in terms of service times, holding costs and abandonment rates than the first (face-to-face or virtual) visit. In particular, because some information has already been collected, the service time of the supplementary visit might be shorter than a full in-person visit. The holding cost and abandonment rate might be different as well because the patient is now required to wait a second time and, therefore, may be more agitated and less patient.

There are two basic questions that come to mind when considering such a hybrid setting. First, there is a design question: how do we allocate capacity among the three types of services? The second question is an operative one: how do we schedule/prioritize the three classes or decide whom to admit when a physician becomes available? This paper attempts to address these two questions by studying a multiserver queueing model with three customer classes: face-to-face, virtual, and supplementary. (We use the terms “patients” and “customers” interchangeably.) In Section 5, we discuss two model extensions for more classes and different supplementary classes for teletriage systems.

The optimal scheduling of multiclass queues is studied extensively in the literature (see Section 1.1). The main takeaway from these studies is the need to carefully balance the holding cost and service and abandonment rates. Our work captures an additional feature in multiclass queueing systems: customer return and class transition when returning. The analysis suggests that, in addition to the holding cost and the service and abandonment rates, we also have to take into account the return probability and associated penalty. How to balance these factors can be highly nontrivial. The optimality of the $c\mu /\theta$ rule, for example, is only achieved asymptotically (Atar et al. 2010). Moreover, solving the Markov decision process (MDP) exactly often leads to limited structural insights and suffers from the curse of dimensionality especially in large systems (Papadimitriou and Tsitsiklis 1999).

Using a fluid framework, we study the optimal scheduling and capacity allocation policies. Specifically, the strong dependency between virtual and supplementary visits requires an integrative approach. To this end, we develop an effective index-based policy, the $\mathcal{R}-c\mu /\theta$ rule (or the $\mathcal{R}$ rule in short), which captures this dependency. We demonstrate how important it is to consider the return probability and penalty when scheduling and capacity allocating service systems with returns. In particular, using policies that neglect the dependency between first and second time visitors can lead to unsatisfactory performances.

Our main contributions can be summarized as follows:

• Modeling. We study a multiserver queuing model with reentrant customers that have different characteristics than first time visitors to the system. The main motivation for the model is facilitating a hybrid healthcare setting that provides face-to-face, virtual, and supplementary in-person services. Nevertheless, the model is relevant to other service systems, such as technical support centers, in which some repairs must be handled through an in-person service center. We provide two model extensions: the first includes multiple classes for each channel, and the second refers to the virtual channel as a teletriage system that classifies patients according to the supplementary service they require. We use a deterministic fluid model to approximate the system dynamics and derive scheduling and capacity allocation policies that shed light on the convenience versus low-value trade-off of virtual healthcare services.

• The $\mathcal{R}$ rule. For maximizing the fluid, long-run profit of a hybrid healthcare setting, we introduce an index-based policy that incorporates the return probability and associated penalty along with the holding cost, service time, abandonment rate, and service completion reward from each service channel. The $\mathcal{R}$ rule, which performs well in different parameter regimes, utilizes the $\mathcal{R}$ index of each class together with an integrated index for virtual and returning patients. We demonstrate that the $\mathcal{R}$ rule, which is optimal for the fluid problem, performs well—very close to optimal—in the corresponding stochastic system. Moreover, we show that our policy performs much better than other known policies that neglect the dependency between classes even under nonstationary arrival rates. The simplicity of the policy, together with its strong performance and the lack of other good policies for this setting, make the policy appealing and implementable.

• Service capacity coordination. Our work underscores the need for an integrated view of patients’ first and following (if any) visits. In terms of system design, we show the importance of joint capacity allocation, in particular, for virtual and returning patients. This is done by carefully balancing the service allocation for these two classes and incorporating the return probability and associated penalty. We identify the cases in which this coordination has the largest impact. In these cases, the superiority of the $\mathcal{R}$ rule is most significant when compared with other benchmark policies.

The rest of the paper is organized as follows. This section is concluded with a brief relevant literature review. In Section 2, we introduce our model and assumptions. In Section 3, we develop the $\mathcal{R}$ index rule and discuss its properties, optimality, and implications in terms of system design and scheduling. In Section 4, we provide numerical experiments for the $\mathcal{R}$ index rule, including a comparison with the optimal solution from the MDP solution, the $c\mu /\theta$ rule, and the max-weight policies. This section also considers the transient profit-maximization problem under nonstationary arrivals. In Section 5, we discuss two model extensions: multiple supplementary services that consider the virtual channel as a teletriage system and a multiple class model. Section 6 offers concluding remarks and future research directions.

1.1. Literature Review

This paper is related to two main bodies of literature. The first is the operations research (OR)/operations management (OM) literature on virtual/e-visits in healthcare systems. The second includes scheduling and capacity planning of queues with different customer classes.

Because the accommodation of virtual/e-visits in healthcare systems is a relatively new practice, there are only a few OR/OM papers in this area. Rajan et al. (2019) study the impact of telehealth on the quality–speed trade-off for chronic patients. By considering an M/M/1 queue with strategic behavior, the authors show that telemedicine can contribute to the specialists’ productivity and overall social welfare. Nevertheless, some patients who continue to use in-person visits may be worse off. In a recent study, Bavafa et al. (2021) focus on the physician compensation scheme (pricing) of e-visits in a primary care setting. The authors demonstrate that patients requiring intermediate healthcare may improve or worsen when e-visits are introduced and identify settings in which system outcomes worsen under e-visits. Çakıcı and Mills (2021) recently studied the use of teletriage, a telemedicine service that allows patients to consult about their health condition. By analyzing an MDP to model patients’ choices under triage errors, the authors find that, for patients with high uncertainty regarding their health condition, teletriage can be beneficial in terms of cost outcomes. Nevertheless, because of the general overtriage rate, adding teletriage may increase the emergency department (ED) arrival rate and produce a negative cost outcome.

In our paper, we focus on a different aspect of telemedicine, which is the supplementary in-person visit and its effect on scheduling and capacity allocation decisions.

The scheduling of multiple customer classes in stochastic processing networks is a broad literature area. Cox and Smith (1961) prove the optimality of a simple index-based policy, known as the $c\mu$ rule for a single-server queue with linear holding costs. Many generalizations have been offered for the rule; their optimality, however, is mostly obtained asymptotically (e.g., Van Mieghem 1995, Mandelbaum and Stolyar 2004, Huang et al. 2015).

In a multiserver system, Harrison and Zeevi (2004) and Atar et al. (2004) study the scheduling of multiple classes with customer abandonment under the critically loaded regime. Atar et al. (2010) derive the asymptotic optimality of the $c\mu /\theta$ rule for many-server queues with abandonment under the many-server heavy traffic regime. More recently, Long et al. (2020) suggest an extension of the rule to general queue length cost functions and customer patience time distributions. Puha and Ward (2019) provide a tutorial on scheduling policies of many-server queues with impatient customers under the overloaded regime. Other recent extensions include scheduling of customers with different resource requirements (Zychlinski et al. 2020, 2023) and scheduling of proactive services (Hu et al. 2021). The latter, as is our current paper, is studied under the conventional heavy-traffic regime.

In this work, we complement this literature body by studying the scheduling of new and reentrant customers. This feature is relevant for hybrid healthcare settings as well as other services that may require a supplementary in-person visit. We allow returning patients to have different characteristics than the first time visitor and address the questions of how to schedule and allocate capacity among the different service channels.

2. The Hybrid Queuing Model

We consider a Markovian N-server queuing model and three classes of visits: face-to-face (f), virtual (v), and supplementary (s), as illustrated in Figure 1. The in-person and virtual classes arrive to the system according to a time-homogeneous Poisson process with rate λ_f and λ_v, respectively. Upon completion of a virtual visit, with probability p_s, the patient requires a follow-up in-person visit. To allow returning patients to have different characterizations than the face-to-face or virtual patients and support the decision of how to schedule/prioritize the different classes, we consider returning patients to be a separate class of patients. Service and patience times of each class are exponential with rates μ_i and θ_i, $i=f,v,s$, respectively.

We assume that patients may return for an additional service at most once. If their service requirements have not been filled after that, they permanently leave the system. In the context of a hybrid emergency clinic, patients are usually referred to an ED if their health requirements have not been met during the in-person visit. Moreover, patients arriving for their virtual visit whose health condition is critical are referred to the ED. On the other hand, patients arriving for their virtual visit who are mildly ill do not require a supplementary in-person visit. Consequently, we assume that there is no significant difference in terms of health criticality between first and second time (following a virtual visit) in-person patients. This allows us to focus on a profit/cost-effective metric.

Note that we refer to face-to-face patients as ones who do not reenter the system immediately upon service completion. After a while, if such patients require service, we consider them to be new arrivals.

Let $X_i(t)$ and $Q_i(t),\hspace{0.17em}i=f,v,s,$ denote the number of class i customers in the system and in the queue, respectively, at time t, $t\ge 0$. Moreover, we use the notation $X(t)=(X_i(t),i=f,v,s)$ and $Q(t)=(Q_i(t),i=f,v,s)$. Let $Z_i(t)$ denote the number of servers assigned to class i at time t; $Z(t)=(Z_i(t),i=f,v,s)$ are the decision variables. A scheduling policy π determines the allocation of servers to customers. We consider Markovian nonanticipating policies; that is, server allocations are made based on the current state $(X;Q)$ only. Under these scheduling policies, $\{(X(t);Q(t)):t\ge 0\}$ is a Markov process. Finally, we also denote by ${\mathrm{\Gamma }}_i(t),\hspace{0.17em}i=f,v,s$, the cumulative number of class i patients who abandoned the queue by time t.

Each completed service is associated with a profit of r_i, $i=f,v,s$. To capture a variety of reimbursement/pricing schemes, we do not impose any restrictions on these profits or their relationship. Each class incurs a holding cost of h_i, $i=f,v,s,$ per patient per unit of time. It makes sense to assume that the holding cost of a face-to-face visit is higher than that of a virtual visit because of the inconvenience and higher exposure to other illnesses prevalent in clinics and waiting rooms. Nevertheless, to keep the analysis as general as possible, we do not impose such a restriction.

Finally, we incur an abandonment cost α_i, $i=f,v,s$ for each class i patient who abandons the queue while waiting and a return cost $\gamma \ge 0$ for each virtual patient who requires a supplementary in-person service. The aggregated profit up to time T is, therefore,

where, under the Markovian modeling assumption,

Equation (1) can then be rewritten as follows:

For simplicity of notation and similar to Hu et al. (2021), we introduce the “generalized” holding costs $c_i=h_i+{\alpha }_i{\theta }_i,\hspace{0.17em}i=f,v,s$.

Our goal is, therefore, to find a scheduling policy π that maximizes the total expected long-run average profit, specifically,

where Ω denotes the set of admissible controls. Note that the superscript π in $X^{\pi }(t)$ and $Q^{\pi }(t)$ emphasizes the dependency of the processes on policy π.

The objective function includes an aggregation of the long-run profit from the three classes. In particular, it includes the profit from each completed service minus the holding cost of the waiting patients minus the return penalty γ for each returning patient.

The first constraint states that the total allocated number of servers cannot exceed the total service capacity N. The second constraint implies that the number of servers allocated to class i cannot exceed the number of class i customers.

This profit-maximization problem is an MDP. The curse of dimensionality (Papadimitriou and Tsitsiklis 1999)—a large (infinite) state and policy space—makes it prohibitively hard to solve and characterize the optimal scheduling policy. To gain structural insights into the optimal scheduling policy and capacity allocation, we take a deterministic fluid approach. Fluid models are known to provide good approximation of the first order mean dynamics of stochastic systems and are, thus, useful for a variety of applications related to service operations management (Zychlinski 2022). Such models are usually derived as limits through the functional law of large numbers. In this paper, we apply the conventional heavy traffic regime (Whitt 2002). In this regime, the arrival and service rates are scaled up (this is equivalent to scaling up time), whereas the number of servers is held fixed.

2.1. The Fluid Model

In the fluid model, deterministic continuous rates replace the stochastic processes. We use lowercase x_i, q_i, and z_i, $i=f,v,s$, to denote the fluid content in the system, the queue length, and the service capacity assigned to class i, respectively. The decision variable z_i’s can be thought of as the level of service capacity that is allocated to class i. For a given capacity allocation, z_i, $i=f,v,s$ such that $z_f+z_v+z_s\le N$, and $0\le z_i\le x_i$, the system dynamics under the fluid model are characterized by the following set of differential equations:

The first equation for the first face-to-face or virtual visit describes the rate of change in the corresponding queue length, which includes the arrival rate minus the departure rate. The latter includes the service completion rate and the abandonment rate from the queue. The second equation is for the supplementary in-person visit that may be needed after the virtual visit. Here, the arrival rate is the departure rate from the virtual service, ${\mu }_v{z}_v(t)$, multiplied by the return probability. Note that the virtual service is the feeding source of the supplementary visit. That is, if no capacity is allocated to the virtual service, no patients require a supplementary visit.

The fluid analog for the long-run profit-maximization problem is, therefore, the following infinite dimensional linear program:

where the system dynamics constraints are as in (3). In addition to reaching scheduling decisions for the three classes, we also wish to derive the optimal capacity allocation for the three service channels. We are, therefore, interested in finding the equilibrium point to which the fluid approximation converges. Theorems 1 and 2 allow us to rewrite the problem as a finite dimensional linear program. Specifically, if the fluid approximation converges to an equilibrium point $\left(\overline{q},\overline{z}\right)$ as $t\to \infty$, then maximizing the long-run average profit can be achieved by finding the optimal equilibrium point

The first two constraints are derived by imposing ${\dot{q}}_i(t)=0,\hspace{0.17em}i=f,v,s$, in the first two fluid dynamic constraints in (4) and replacing the functions $q_i(t)$ and $z_i(t)$ by their equilibrium ${\overline{q}}_i$ and ${\overline{z}}_i$, respectively. Note that according to the first two constraints, the rate of visit loss is ${\lambda }_i-{\mu }_i{\overline{z}}_i={\theta }_i{\overline{q}}_i$ for classes $i=f,v$, and $p_s{\mu }_v{\overline{z}}_v-{\mu }_s{\overline{z}}_s={\theta }_s{\overline{q}}_s$ for class s.

Rearranging (5), by substituting

in the objective function and omitting the constants that do not affect the optimal solution yields the following equivalent problem:where the $\mathcal{R}$ indexes are

The first constraint in (6) states that at most ${\lambda }_i/{\mu }_i,\hspace{0.17em}i=f,v$ service capacity is needed to handle the face-to-face and virtual customers. The second constraint states that at most $p_s{\mu }_v{\overline{z}}_v/{\mu }_s$ service capacity is needed to handle the returning patients.

Note that, when r_i = 0, $i=f,v,s$, and p_s = 0, we retrieve the $c\mu /\theta$ indexes according to which the $c\mu /\theta$ rule prioritizes the classes (Atar et al. 2010). Note also that return probability p_s and return penalty γ reduce the virtual customers’ index. That is, as the virtual service becomes less effective (i.e., associated with a higher return probability), the optimal policy tends to utilize the virtual services less. This result is intuitive in the sense that prioritizing virtual patients leads to excessive costs when some of them are returning for supplementary service. In the extreme case in which the return probability and penalty are very high, the optimal decision might be to cancel virtual services at that particular clinic entirely.

In addition to (7), we also introduce the index ${\mathcal{R}}_{v,s}$, which is a weighted average of the ${\mathcal{R}}_v$ and ${\mathcal{R}}_s$ indexes, namely,

Note that, when p_s = 0, we have ${\mathcal{R}}_{v,s}={\mathcal{R}}_v$. In Section 3, we see that, in some cases, the scheduling and capacity allocation decisions rely on this integrated index. A further intuition on the integrated ${\mathcal{R}}_{v,s}$ index is provided in Remark 1.

Throughout the paper, we make the technical assumption that the $\mathcal{R}$ indexes are all distinct. That is, ${\mathcal{R}}_i\ne {\mathcal{R}}_j$ for $i\ne j$. Nonunique indexes could complicate our analysis in Sections 3 and 5 by adding many more cases to consider.

Finally, we consider an autonomous differential equation:

Suppose there exists an equilibrium point $\overline{q}$ so that $f(\overline{q})=0$. Then, $\overline{q}$ is globally asymptotically stable if, for any initial condition q₀, ${\lim }_{t\to \infty }\Vert q(t)-\overline{q}\Vert =0$, where $\Vert ·\Vert$ is the Euclidean norm.

3. The $\mathcal{R}$-Index Policy

Because of the dependency between virtual and returning patients, the optimal solution to (6) is not necessarily to straightforwardly assign larger values of $\overline{z}$ to the ones with the larger $\mathcal{R}$ index. Before we characterize the optimal solution to (6), we introduce two index-based policies as well as the $\mathcal{R}$ rule, which combines the two.

Definition 1

(The Naive $\mathcal{R}$ Rule). Assign priority to class i, $i=f,v,s$, having the higher ${\mathcal{R}}_i$ index.

For the following definition, we combine the virtual and supplementary classes together to form a joint (artificial) class {v, s}, which is associated with the ${\mathcal{R}}_{v,s}$ index. In the first step, we set the priority between class f and the joint class {v, s}. Then, in the second step, we set the priority within the joint class (for classes v and s).

Definition 2

(The Two-Step $\mathcal{R}$ Rule). Assign priority to class i, $i=f,\{v,s\}$, with the higher ${\mathcal{R}}_i$ index. Then, within the joint class, assign priority to class i, $i=v,s$, with the higher ${\mathcal{R}}_i$ index.

Note that, when p_s = 0, both the naive and two-step $\mathcal{R}$ rules retrieve the $c\mu /\theta$ rule (Atar et al. 2010).

Definition 3

(The $\mathcal{R}$ Rule). Case 1: When ${\mathcal{R}}_s<{\mathcal{R}}_v$, prioritize the classes according to the naive $\mathcal{R}$ rule. Case 2: When ${\mathcal{R}}_s>{\mathcal{R}}_v$, prioritize the classes according to the two-step $\mathcal{R}$ rule.

Next, we prove that the optimal solution to the fluid optimization problems (6) and (7) is a globally asymptotically stable equilibrium under the $\mathcal{R}$ index rule. Moreover, we characterize the capacity allocation in equilibrium for each service channel and for different parameter regimes. Theorem 1, which we prove in Appendix A, formalizes this result.

Theorem 1

(Globally Asymptotically Stable Equilibria). When following the $\mathcal{R}$ rule for the system dynamics described in (4) from any initial condition and for ${\theta }_i>0,\hspace{0.17em}i=f,v,s$, the globally asymptotically stable equilibria, $\overline{z}=({\overline{z}}_f,{\overline{z}}_v,{\overline{z}}_s)$ and $\overline{q}=({\overline{q}}_f,{\overline{q}}_v,{\overline{q}}_s)$, are as shown in Table 1.

The equilibrium queue lengths are then given by

Note that, under case 2, ${\overline{z}}_s=p_s{\mu }_v{\overline{z}}_v/{\mu }_s$ so that ${\overline{q}}_s=0$. This makes sense because, in this case, class s is prioritized over class v. If ${\overline{q}}_s>0$, we could get an improvement by shifting some capacity from class v to class s. Therefore, in equilibrium, we need to make sure that just enough capacity is allocated to class v to ensure that ${\overline{q}}_s=0$.

The $\overline{z}$’s in Theorem 1 can be interpreted as the long-run capacity allocated to each service channel. Specifically, when ${\mathcal{R}}_s<{\mathcal{R}}_v$, capacity is allocated to each service channel separately according to its $\mathcal{R}$ index. In this case, returning patients are treated as any other class (except for the fact that the class demand is determined by the capacity allocation to the virtual channel).

When ${\mathcal{R}}_s>{\mathcal{R}}_v$, however, capacity allocation of virtual and returning patients must be coordinated to ensure that enough capacity is allocated to the virtual channel that feeds the supplementary channel. In this case, classes v and s are treated jointly, and the relevant relation then becomes the face-to-face channel versus the joint channel of virtual and supplementary visits.

We are now ready for Theorem 2, which establishes the optimality of the $\mathcal{R}$ rule for the long-run profit-maximization problem (6). The proof of the theorem, which is provided in Appendix B, is based on Theorem 1 in which we guarantee that the fluid system converges to the equilibrium point under the $\mathcal{R}$ rule.

Theorem 2

(Optimality of the $\mathcal{R}$ Rule). For the long-run profit maximization problem (6) with ${\theta }_i>0,\hspace{0.17em}i=f,v,s$, and any initial condition, the $\mathcal{R}$ rule is optimal.

The suggested $\mathcal{R}$ rule is an index-based policy; such policies often exhibit many desirable properties, such as being simple to implement and achieving good (if not optimal) performance. Because of the dependency between virtual and returning patients, there is a need to combine the naive and two-step $\mathcal{R}$ rules. In Section 4, we demonstrate, through extensive numerical experiments, the effectiveness and robustness of the $\mathcal{R}$ rule. Specifically, we show that the policy performs very close to optimal and much better than other known policies in various settings and under different system loads.

Note that ${\mathcal{R}}_v={\mu }_v(r_v+c_v/{\theta }_v-p_s(\gamma +c_s/{\theta }_s))$ is decreasing in p_s, so the switching point between cases 1 and 2 is

Specifically, if $p_s<\widetilde{p_s}$, the naive $\mathcal{R}$ rule is optimal, and if $p_s>\widetilde{p_s}$, the two-step $\mathcal{R}$ rule is optimal. In particular,

• When ${\mathcal{R}}_v{|}_{p_s=0}<{\mathcal{R}}_s$, the two-step $\mathcal{R}$ rule is optimal for every $p_s\in [0,1]$.

• When ${\mathcal{R}}_s<{\mathcal{R}}_v{|}_{p_s=1}={\mu }_v\left(r_v+c_v/{\theta }_v-\left(\gamma +\frac{c_s}{{\theta }_s}\right)\right)$, the naive $\mathcal{R}$ rule is optimal for every $p_s\in [0,1]$.

Remark 1.

What is the motivation for the joint index ${\mathcal{R}}_{vs}$?

Intuitively, when ${\mathcal{R}}_s>{\mathcal{R}}_v$, we tend to prioritize returning patients over virtual ones. Because the latter are the feeding source of the former, enough capacity needs to be allocated to virtual patients to ensure that ${\overline{z}}_s=p_s{\mu }_v{\overline{z}}_v/{\mu }_s$.

By substituting ${\overline{z}}_s$ in the objection function in (6), we get

$$\underset{{\overline{z}}_f,{\overline{z}}_v}{\max } {\mathcal{R}}_f{\overline{z}}_f+\left({\mathcal{R}}_v+\frac{p_s{\mu }_v}{{\mu }_s}{\mathcal{R}}_s\right){\overline{z}}_v.$$(10)

When the capacity constraint is active (i.e., ${\overline{z}}_f+{\overline{z}}_v+{\overline{z}}_s=N$), we have

$${\overline{z}}_v=\frac{{\mu }_s}{{\mu }_s+p_s{\mu }_v}(N-{\overline{z}}_f),$$

which, in turn, is plugged in back into (10) and gives the following objective function:

$$\underset{{\overline{z}}_f}{\max }{\mathcal{R}}_f{\overline{z}}_f+{\mathcal{R}}_{v,s}(N-{\overline{z}}_f).$$

Now, it is clear that capacity needs to be allocated to class f when ${\mathcal{R}}_f>{\mathcal{R}}_{v,s}$ and jointly to classes v and s, otherwise.

Remark 2.

In urgent care centers, which constitute our main motivating application, the queue regime is often not first come, first served (e.g., Hu et al. 2021, Zychlinski et al. 2023) but some other merit that takes into account the severity of patients’ conditions and service time. For example, the supplementary channel might be prioritized over the first time in-person channel if the former has much shorter service times because the patient has already been diagnosed/treated remotely or if the patient’s condition has deteriorated (in our model, this translates into a higher holding cost). Waiting patients might perceive this as being unfair when patients arriving after them start their service before them. To overcome this, when arriving at such centers, patients must usually sign in at a (self-service) registration stand and receive a number. Announcements and display screens in the waiting room show which number should enter each physician office. In this way, the prioritization can be done through the system without being too obvious.

3.1. Optimal System Design

The $\mathcal{R}$ rule addresses the operational question of how to schedule/prioritize the three classes or whom to admit when a physician becomes available. Additionally, the $\mathcal{R}$ rule addresses an even more basic question that comes to mind when considering such a hybrid setting; specifically, it focuses on the design question of how to allocate capacity among the three services channels. We find that, in some extreme cases, it is better to utilize only one or two service channels.

Another way of looking at the optimal system design according to the $\mathcal{R}$ rule is that it chooses which channel(s) to utilize, which channel(s) not to utilize, and at most one channel to partially utilize. Under the naive $\mathcal{R}$ rule, this intuition is straightforward. Under the two-step $\mathcal{R}$ rule, this observation is true because of the careful balancing of capacity allocated to the virtual and supplementary channels.

Table 1 describes the optimal long-run capacity allocation to the three service channels. As the need for supplementary service increases (i.e., the return probability increases), the virtual service becomes less effective. This is because many patients’ issues cannot be resolved through the virtual channel. Consequently, more capacity is allocated to the in-person service. Figure 2 illustrates different structures of the optimal capacity allocation as a function of return probability p_s. For example, in the left plot, the policy switches from the naive $\mathcal{R}$ rule (case 1a) to the two-step $\mathcal{R}$ rule (case 2a) when $p_s=0.24$. Then, at $p_s=0.62$, the policy switches within the two-step $\mathcal{R}$ index to case 2b, in which the entire service capacity is allocated to the face-to-face channel. Indeed, when the virtual service is less effective, it is better to focus mainly on the face-to-face channel. Note that it is possible to have the same capacity allocation for different cases (see the right plot when switching from case 1b to 1c). Moreover, there could be extreme cases under heavy load when the optimal solution would tend not to utilize one or two service channels. For example, when the virtual service is associated with a very high return rate, it might be best to focus only on the face-to-face channel. Under such heavy loads when not all channels are utilized, it might also be beneficial to optimize staffing levels by considering the trade-off between service completion reward (including abandonment penalty) and staffing costs.

Table 1. Globally Asymptotically Stable Equilibria

3.1.1. Translation of the Optimal Solution Back to the Stochastic System.

In terms of scheduling, the translation relies on the priorities determined by the $\mathcal{R}$ rule when a service provider becomes available. In Section 4, we provide numerical examples demonstrating that the policy is effective when implemented in the stochastic system. The translation of the long-term capacity allocation is in terms of system design. That is, we determine how much capacity needs to be allocated on average to each service channel. If, for example, the healthcare facility follows a nonsharing policy of physicians to different service channels (e.g., in a certain shift, physicians cannot switch between service channels), then the capacity allocation is the average amount of physicians’ time that needs to be assigned to each service channel.

4. Numerical Experiments

In this section, we examine the performance of the $\mathcal{R}$ rule in the original stochastic system using simulation. When the number of servers is very small, we can solve the MDP numerically and then compare it to the performance of the $\mathcal{R}$ rule. We also compare two other well-known policies: the $c\mu /\theta$ rule (Atar et al. 2010) and the max-weight policy (Stolyar 2004, Dai and Lin 2005). We modify the $c\mu /\theta$ rule to include the reward from each service completion; specifically, the index of class i is now $(r_i+c_i/{\theta }_i){\mu }_i$. We also modify the max-weight policy to include the reward from each service completion and the abandonment rate as follows: at each time t, given X(t) = x and Q(t) = q, the server allocation, $z=(z_f,z_v,z_s)$, under the max-weight policy is the solution to the following integer programming problem:

We note that the numerical experiments for the stochastic system assume preemption. The fluid analysis, however, applies for both preemptive and nonpreemptive regimes.

Figure 3 presents the ratio between each policy’s long-run average profit and the optimal profit achieved by explicitly solving the MDP. We present the ratios for different values of the return probability p_s in four scenarios. We observe that the $\mathcal{R}$ rule performs very well in all scenarios and for all values of p_s. The $c\mu /\theta$ and the max-weight policy perform reasonably well under small return probability. Their respective performance, however, deteriorates in comparison with the optimal policy as the return probability increases. This deterioration prevails even when there is no penalty associated with patient return (i.e., γ = 0).

Recall that the $\mathcal{R}$ rule is derived from a fluid approximation model that can arise as a limit through the functional law of large numbers under the conventional heavy traffic regime. We, therefore, wish to examine the policies’ performances under different system loads. To this end, we define the traffic intensity as follows:

Table 2 compares the long-run average profit of the three policies to the optimal profit achieved by solving the MDP. We vary ρ by proportionally scaling up the arrival rates. For each case and policy, we present (in parentheses) the ratio between the policy’s profit and the optimal profit. We observe that the $\mathcal{R}$ rule performs very well in all cases. The performance under moderate and high traffic intensities, when effective scheduling policies are most needed, is very close to optimal. This is because the $\mathcal{R}$ rule was derived under conventional heavy traffic, which tends to be more accurate as traffic intensity increases. Moreover, we see that the $c\mu /\theta$ and max-weight policies perform slightly better than the $\mathcal{R}$ rule under very low traffic intensity. Under high traffic intensity, however, their performance deteriorates; this deterioration does not happen under the $\mathcal{R}$ rule, which keeps performing very close to optimal.

Table 2. Comparison Between the Long-Run Average Profit Under Different Policies and Traffic Intensities

Next, we examine the performance of the $\mathcal{R}$ rule for different system sizes. Figure 4 compares the suggested $\mathcal{R}$ rule to the $c\mu /\theta$ rule. Using simulation, we calculate the average capacity allocated to each channel (i.e., the average number of patients in service) and the average profit for each policy. The circles present the optimal allocation and long-run profit according to the fluid solution. The results are presented for different system sizes. As N increases, we scale up the arrival rates proportionally using an appropriate Poisson process. In Example 1, the $\mathcal{R}$ rule allocation (which coincides with the fluid solution) suggests allocating a similar amount of capacity to each service channel (the capacity ratio is $(0.375,0.34,0.285)$ for the face-to-face, virtual, and supplementary channels, respectively). The $c\mu /m$ rule, however, assigns most of the capacity to the supplementary and virtual channels and relatively little capacity to the face-to-face channel (the capacity ratio is $(0.115,0.425,0.46)$). The $\mathcal{R}$ rule in this example achieves a 78% higher long-run average profit than the $c\mu /\theta$ rule. In Example 2, the $\mathcal{R}$ rule allocation (which, again, coincides with the fluid solution) suggests allocating most of the capacity to the face-to-face channel and the remainder to the virtual and supplementary channels. The $c\mu /m$ rule, however, assigns most of the capacity to the virtual channel and then to the supplementary one. It allocates almost no capacity to the face-to-face channel. In terms of system design, following the $c\mu /\theta$ rule leads to utilizing only the virtual and supplementary channels and eliminating the face-to-face channel. The $\mathcal{R}$ rule achieves a 21% higher long-run average profit than the $c\mu /\theta$ rule. Note that, to facilitate a relatively fair comparison, we do not consider the return penalty in these experiments (i.e., γ = 0).

To demonstrate why the naive $\mathcal{R}$ rule is insufficient, especially in heavily loaded systems, we focus on a setting in which the scheduling according to the $\mathcal{R}$ rule and the naive $\mathcal{R}$ rule are different. Specifically, let n = 15, $p_s=0.8$, γ = 0, ${\lambda }_f=45,\hspace{0.17em}{\lambda }_v=90$; for classes $[f,v,s]$, $r=[12,12,8],\hspace{0.17em}c=[2.5,0.2,1.5],\hspace{0.17em}\mu =[4,6,6],\hspace{0.17em}\theta =[0.8,0.1,0.3]$. In this example, the $\mathcal{R}$ rule allocates most of the capacity to the supplementary and virtual channels, allocating very little capacity to the face-to-face channel. The naive $\mathcal{R}$ rule, however, allocates most of the capacity to the face-to-face channel. These two policies lead to a completely different system design. In this case, the long-run average profit under the $\mathcal{R}$ rule is 700, which is 15.7% higher than the 590 achieved by the naive $\mathcal{R}$ rule.

We can summarize these examples by first stating that the fluid approximation accurately describes the stochastic system. Second, we see that each policy can lead to a different prioritization and different system design. Third, we observe that the $\mathcal{R}$ rule achieves higher average profit compared with the other two policies for different system sizes.

4.1. Performance of the $\mathcal{R}$ Rule Under Transient Profit Maximization

In some settings, there can be random shocks that move the system far from its usual mode of operation. In these cases, improving the transient performance of the system becomes the main goal. That is, we want to find an effective scheduling policy to support demand surges. The COVID-19 pandemic, for example, caused sudden surges in demand on healthcare systems around the world. We consider the objective of maximizing the cumulative expected profit over a finite time horizon T. The fluid equivalent is, therefore,

We observe through numerical experiments that, even when the arrival rate is highly nonstationary, the $\mathcal{R}$ rule still performs very well in maximizing the transient profit compared with the $c\mu /\theta$ rule. Figure 5 presents a scenario in which, at time t = 600, both classes experience a quadratic surge in demand that lasts 800 time units. The left plot presents the instantaneous profit as a function of time over the time horizon $[0,2,000]$. The right plot presents the average number of patients in service for each class over the time horizon. During the surge in demand, both the $\mathcal{R}$ rule and the $c\mu /\theta$ rule become more extreme in their prioritization: the $\mathcal{R}$ rule allocates the entire capacity to the face-to-face channel, whereas the $c\mu /\theta$ allocates the entire capacity to the virtual channel, leaving almost no capacity for returning patients. In terms of the objective function, the $\mathcal{R}$ rule achieves twice the cumulative profit than the $c\mu /\theta$ rule. This result demonstrates the robustness of the $\mathcal{R}$ rule, even in maximizing the transient performance.

5. Model Extensions

We now discuss two model extensions. The first considers multiple face-to-face, virtual, and supplementary classes. The second extension refers to the virtual channel as a teletriage system that classifies patients according to the supplementary service they require (as opposed to a binary decision that we have considered thus far).

5.1. Multiple Classes in Each Service Channel

In this section, we consider a more general setting with k_f face-to-face classes of patients and k_v (=k_s) virtual and supplementary classes as illustrated in Figure 6. The different classes within each channel may represent different severity levels. Specifically, each face-to-face, virtual, and supplementary class is characterized by $({\lambda }_f^i,{\mu }_f^i,{\theta }_f^i,c_f^i,r_f^i),\hspace{0.17em}i=1,\dots ,k_f,\hspace{0.17em}\left({\lambda }_v^i,{\mu }_v^i,{\theta }_v^i,c_v^i,r_v^i,p_s^i,{\gamma }^i\right),\hspace{0.17em}i=1,\dots ,k_v$, and $\left({\mu }_s^i,{\theta }_s^i,c_s^i,r_s^i\right),\hspace{0.17em}i=1,\dots ,k_v$, respectively. In total, the scheduling problem in this case needs to consider $k_f+2k_v$ classes.

The equivalent problem to (5), for which the optimal equilibrium point would maximize the long-run average profit, is

Rearranging (12) and omitting the constants yields the following:

where the $\mathcal{R}$ indexes are

We also have the equivalent ${\mathcal{R}}_{v,s}$ for each virtual/supplementary class:

Proving the optimality of a generalized form of the $\mathcal{R}$ rule in this setting requires us to follow the line of analysis conducted in Section 3. That is, we must first prove that, under the generalized $\mathcal{R}$ rule, the fluid approximation converges to an equilibrium point that is a globally asymptotically stable one (a generalization of Theorem 1). Then, we must prove that the optimal solution to (13) and (14) is the globally asymptotically stable equilibrium (a generalization of Theorem 2). Utilizing this approach quickly becomes prohibitively tedious with too many scenarios to consider. We, therefore, provide an algorithm that extends the essence of the $\mathcal{R}$ rule for setting the prioritization among classes. Note that, for a given set of parameters, this algorithm needs to be run once.

The following algorithm utilizes the sorted set $\mathcal{S}$, including the classes’ $\mathcal{R}$ indexes according to which the priority among classes is set.

Algorithm 1

(Generalized $\mathcal{R}$ Rule for Multiple Classes)

1. Set $\mathcal{S}\leftarrow \{{\mathcal{R}}_f^i,i=1,\dots k_f\}$

2. For each class i, $i=1,\dots ,k_v$

   1. If ${\mathcal{R}}_s^i<{\mathcal{R}}_v^i$, then $\mathcal{S}\leftarrow \mathcal{S}\cup \{{\mathcal{R}}_v^i,{\mathcal{R}}_s^i\}$

   2. Otherwise, $\mathcal{S}\leftarrow \mathcal{S}\cup \{{\mathcal{R}}_{v,s}^i\}$

3. Sort the set $\mathcal{S}$ in a decreasing order

4. Replace the ${\mathcal{R}}_{v,s}^i$'s in $\mathcal{S}$ with $\{{\mathcal{R}}_s^i,{\mathcal{R}}_v^i\}$

5. Return $\mathcal{S}$.

The prioritization of classes is done according to their order in the sorted set $\mathcal{S}$. The algorithm shares the same principles as the $\mathcal{R}$ rule presented in Section 3: if the index of the virtual class is higher than the index of the supplementary class, then the prioritization is set according to the $\mathcal{R}$ indexes. If, however, the index of the supplementary class is higher than the index of the virtual class, we jointly prioritize the virtual and supplementary classes according to their integrated ${\mathcal{R}}_{v,s}$ index.

5.2. A Teletriage System with Multiple Supplementary Services

Thus far, we assume that each virtual service leads to one type of supplementary service. Nevertheless, one common strategy for controlling healthcare needs, called “forward triage,” refers to the online channel as a sorting stage offered to patients. It allows them to be efficiently screened before being referred to a medical center. Respiratory symptoms, which may be early signs of COVID-19, for example, can commonly be evaluated using this approach (Hollander and Carr 2020).

Motivated by such a teletriage setting, we study a model extension in which, based on an initial virtual assessment, patients are classified according to the supplementary service they require. The supplementary services vary in their urgency, length, and/or cost. To this end, we consider k_s optional supplementary services for each virtual service. Each supplementary service i occurs with probability $p_s^i,\hspace{0.17em}i=1,\dots ,k_s$, and is associated with a supplementary class that is characterized by $\left(p_s^i,{\mu }_s^i,{\theta }_s^i,c_s^i,r_s^i,{\gamma }_i\right)$ as illustrated in Figure 7. The equivalent problem to (5), for which the optimal equilibrium point maximizes the long-run average profit, is

Rearranging (15) yields the following:

where the $\mathcal{R}$ indexes are

We denote the joint virtual/supplementary index for a set of supplementary classes, $\mathcal{B}$:

The ${\mathcal{R}}_{v,s}^{\mathcal{B}}$ index is an extension of the ${\mathcal{R}}_{v,s}$ index that was used when each virtual service could lead to a single type of supplementary service. The interpretation of the index remains the same: it is the weighted average of the virtual and supplementary $\mathcal{R}$ indexes. When $\mathcal{B}$ includes one supplementary service, we retrieve the original ${\mathcal{R}}_{v,s}$.

As stated in Section 5.1, proving the optimality of a generalized form of the $\mathcal{R}$ rule in this setting requires us to follow the line of analysis conducted in Section 3. Utilizing this approach quickly becomes prohibitively tedious. Therefore, we provide a heuristic algorithm in the spirit of the $\mathcal{R}$ rule for setting the prioritization among classes. Note that, for a given set of parameters, this algorithm needs to be run once.

The following algorithm uses two sorted sets: $\mathcal{S}$ and $\mathcal{B}$. Set $\mathcal{S}$ includes the classes’ $\mathcal{R}$ indexes according to which the priority among classes is set. Set $\mathcal{B}$ includes the classes for which their ${\mathcal{R}}_s^i$ index is larger than ${\mathcal{R}}_v$.

Algorithm 2

(The Generalized $\mathcal{R}$ Rule for Multiple Supplementary Services)

1. Set $\mathcal{S}\leftarrow \{{\mathcal{R}}_f\}$ and $\mathcal{B}=\{v\}$

2. For each class i, $i=1,\dots ,k_s$

   1. If ${\mathcal{R}}_s^i<{\mathcal{R}}_v$, then $\mathcal{S}\leftarrow \mathcal{S}\hspace{0.17em}\cup \hspace{0.17em}\left\{{\mathcal{R}}_s^i\right\}$

   2. Otherwise, $\mathcal{B}\leftarrow \mathcal{B}\hspace{0.17em}\cup \hspace{0.17em}\{i\}$

3. Calculate ${\mathcal{R}}_{v,s}^{\mathcal{B}}$ according to (18)

4. Sort in a decreasing order the set $\mathcal{S}\hspace{0.17em}\cup \hspace{0.17em}{\mathcal{R}}_{v,s}^{\mathcal{B}}$ and the set $\mathcal{B}$ according to the $\mathcal{R}$ indexes

5. Replace the index ${\mathcal{R}}_{v,s}^{\mathcal{B}}$ in $\mathcal{S}$ with the $\mathcal{R}$ indexes of the classes in $\mathcal{B}$

6. Return $\mathcal{S}$.

The prioritization of classes is done according to their order in the sorted set $\mathcal{S}$. The ideas behind the algorithm are the same as for the $\mathcal{R}$ rule presented in Section 3: the supplementary classes whose $\mathcal{R}$ index is smaller than ${\mathcal{R}}_v$ can be prioritized as any other class. The supplementary classes whose $\mathcal{R}$ index is larger than ${\mathcal{R}}_v$ need to be considered jointly with the virtual class and the other supplementary classes by using the joint ${\mathcal{R}}_{v,s}^{\mathcal{B}}$ index.

6. Concluding Remarks and Future Directions

Motivated by healthcare provision trends, in this paper, we study the optimal scheduling and capacity allocation for multiserver queues in which patients may return for supplementary service. The main motivating example for this work is a hybrid healthcare setting that provides three service channels: face-to-face, virtual, and in-person supplementary services that some patients require following virtual service. The strong dependency between the virtual and returning patients (i.e., the former constitute the feeding source for the latter) imposes additional constraints when scheduling and allocating capacity. Using a fluid relaxation approach, we derive and prove the optimality of the $\mathcal{R}$ index rule for maximizing the long-run average profit. From an operational point of view, the $\mathcal{R}$ rule helps prioritize classes (i.e., which class to admit when a service provider becomes available). From a design perspective, the $\mathcal{R}$ rule allocates capacity for each service channel. We show that the $\mathcal{R}$ rule performs very close to optimal and significantly better than other known policies in various settings and under different system loads. Finally, we show that, even though the $\mathcal{R}$ rule is designed to maximize long-run average profit, it also performs well in a transient time-horizon and nonstationary arrival scenario.

We identify a few interesting future research directions. The first is to consider nonstationary systems with time-varying arrival rates. Indeed, urgent care centers often experience such arrival patterns and peak hours at which the demand is much higher than at other times of the day (Armony et al. 2015). Deriving an effective robust scheduling policy under arbitrary time-varying arrival rates is challenging because the optimal policy may depend on these time-varying arrival rates as well as on the system’s state. Moreover, it is plausible that the arrival rates to the virtual and in-person channels are not synchronized: at some hour during the day, patients may prefer the virtual channel, whereas at other hours, patients may prefer the in-person channel. These patterns, in turn, also affect the supplementary channel.

The second direction is related to improved continuity of care, that is, allowing patients to see the same physician in their virtual visit and supplementary in-person visit when needed. Specifically, there are two types of queues to consider: The first is a joint queue for all physicians and first time visitors. The second type of queue, for second time visitors, is separate for each physician. The queue management and scheduling policy would have to take into account both queue types.

Another interesting direction is to incorporate strategic behavior. On the one hand, the patient chooses which service channel to use: face-to-face or virtual, according to the expected waiting cost and return probability. On the other hand, by considering patients’ behavior, the healthcare provider chooses how to allocate capacity among the three services in order to maximize its profits. Another interesting direction is to focus on reimbursement policies (e.g., fee for service versus bundled payment) for the different service channels. Through these reimbursement policies, virtual services can be encouraged or discouraged in order to optimize system performance and healthcare provision.