Benjamin Legros
email: benjamin.legros@centraliens.net

Oualid Jouini
email: oualid.jouini@centralesupelec.fr

• O Zeynep Akşin

Ger Koole
email: ger.koole@vu.nl

Front-office multitasking between service encounters and back-office tasks

Keywords: Multitasking, front-office service work, case-manager system, queueing system control

We model the work of a front-line service worker as a queueing system. The server interacts with customers in a multi-stage process with random durations. Some stages require an interaction between server and customer, while other stages are performed by the customer as a self-service task or with the help of another resource.

Random arrivals by customers at the beginning and during an encounter create random lengths of idle time in the work of the server (breaks and interludes respectively). The server considers treatment of an infinite amount of back-office tasks, or tasks that do not require interaction with the customer, during these idle times. We consider an optimal control problem for the server's work. The main question we explore is whether to use the interludes in service encounters for treating back-office, when the latter incur switching times. Under certain operating environments, working on back-office during interludes is shown to be valuable. Switching times play a critical role in the optimal control of the server's work, at times leading the server to prefer remaining idle during breaks and interludes, instead of working on back-office, and at others to continue back-office in the presence of waiting customers. The optimal policy for use of the interludes is one with multiple thresholds depending on both the customers queueing for service, and the ones who are in-service. We illustrate that in settings with multiple interludes in an encounter, if at all, the back-office work should be concentrated on fewer, longer and later interludes.

Introduction

In front-office service processes the customer is present during production and delivery and may take an active role as a co-producer. Such services require multiple phases of service employee-customer interactions and are labeled as service encounters. The focus of this paper is the work of the front-office service employee (the focal service worker) in such a service encounter. In some settings, these service encounters are called cases, and the front-office service employee is known as a case manager. Phases of the service encounter that are not performed by the focal worker are not explicitly modeled and are characterized as a delay with random duration in the focal employee's work. These delays, that occur during an ongoing service encounter while the customer is away for an offline task, are labelled as interludes for the front-office server. Each new customer arrival generates a new service encounter. The random duration during which there are no customers present in the system is labelled as a break in the focal employee's work. During times when the focal worker is not interacting with customers, i.e. during interludes and breaks, the worker can choose to remain idle or work on other tasks that can be performed without the presence of a customer.

The latter tasks are known as back-office tasks and are expected to have lower urgency compared to the front-office.

Alternating between front-office and back-office tasks requires a switching time for the focal server. In such a setting, the goal of this paper is to formulate and analyze the optimal control problem for the focal server' work, exploring the use of interludes and breaks to perform back-office tasks when these incur switching times. The simplest such system is one where the front-office service worker is an investigator. In an after-sales technical service center, a customer with a repair need may report a problem to an investigator, perform several tests on the item as suggested by this server in self-service mode, report back on the results of these to the investigator to obtain a suggestion regarding next steps. At an insurance firm or bank branch, the customer who wants to buy a product makes a request with the focal server, then completes requested documentation, subsequently coming back to the investigator to conclude the application process. Both of these examples can be characterized by a three-stage process where the first and last stages are with the focal server, and the second stage consists of an external delay (an interlude) that involves either a self-service step, or another task performed by other resources. [START_REF] Dobson | Optimal workflow decisions for investigators in systems with interruptions[END_REF] provide an example from an emergency department (ED) for such a three-stage process. An investigator who is an ED physician examines the patient, then tests necessary for diagnosis are performed by a back-office, and the patient returns to the physician in stage three to conclude the investigation. In other settings, processes may be more complex involving more than three stages. For example, an audit process consists of several interactions between a client and the focal server, while other servers will provide required validations between steps. Similarly, a general practitioner (the focal server) may have several interactions with a patient, interrupted by tests or imaging performed between visits. In all of these examples, the focal server has a choice between remaining idle, starting a new service encounter, or performing some back-office tasks during interludes and breaks between customers. For instance, in the after-sales service center the server may perform some routine paper work while the customer is away, and in the insurance firm the server may work on investigations during such interludes. The general practitioner may be writing reports concerning other patients.

The existence of switching times when multitasking between two types of distinct tasks is well documented in the behavioral literature. First, multitasking or working on several tasks at a time actually means working on different tasks by alternation instead of working on them strictly at the same time. Simultaneity is not efficient for humans, as it can create interferences between jobs [START_REF] Gladstones | Division of attention: The single-channel hypothesis revisited[END_REF], and can lead to mistakes [START_REF] Rosen | The myth of multitasking[END_REF][START_REF] Lohr | Slow down, brave multitasker, and don't read this in traffic[END_REF]. Yet alternation induces inefficiency and time loss related to switching between tasks [START_REF] Rosen | The myth of multitasking[END_REF]. Minimizing such losses requires the limitation to alternation between at most two distinct tasks [START_REF] Charron | Divided representation of concurrent goals in the huma frontal lobes[END_REF][START_REF] Dux | Training improves multitasking performance by increasing the speed of information precessing in human prefontal cortex[END_REF]. In this paper, our main motivation is to study the role of switching times when alternating between front-office and back-office tasks in the work of a front-office service worker. Front-office tasks are considered to be of higher urgency relative to back-office tasks due to the presence of the customer. The server's multitasking control problem can be formulated as one that tries to maximize the proportion of time spent on back-office tasks while respecting some service level on the waiting times of front-office tasks. More precisely, the question we wish to analyze is how to use the interludes and breaks in service: by remaining idle and thus ready for the customer, by initiating the service of new customers, or by making use of these times to work on back-office tasks at the expense of incurring switching times to start and then to return to the customer task? One way of avoiding switching times, while keeping the server busy, is to have the server start on a new task of similar nature. In the service front-office context, this corresponds to starting the service of a new customer during an interlude. As the front-office server initiates new service encounters during interlude times, several customers will be in the system at different stages of their service encounter. The number of customers in the system may be unrestricted in settings where the customer performs self-service tasks during interlude times. In other systems, managers may impose a limit on the number of customers that are allowed to be simultaneously in service to avoid in-service waits or other disruptions. This limit is called a caseload. Examples of such systems can be a contact center where servers manage multiple online chats [START_REF] Legros | On the scheduling of operations in a chat contact center[END_REF], or an emergency department where physicians treat multiple patients simultaneously [START_REF] Campello | Queueing models of case managers[END_REF]. While our main research question is how to make use of interludes in the presence of switching times between front and back-office tasks, we also explore the effect of an exogenously determined caseload on this main problem.

More generally, white-collar service work consists of multi-stage customer-server interactions, where back-office tasks can be combined with customer service. Workflow systems enable the management of such multitasking and render automated control of such work viable. While the idea of optimally controlling the way such a server blends back-office tasks between customer encounters has been studied in the context of call center blending problems, the combined problem of blending back-office work between as well as within service encounters has not been analyzed before. The latter feature requires not just considering pre-process waiting times but also in-process waiting times for customers as the server chooses between staying idle or working on back-office tasks. Switching times have not been considered in any front office-back office blending models before.

Our analysis shows that using the interludes may make sense in some operating environments, and further explores how this choice interacts with features such as the workload, task durations, switching time durations, and caseload of the server. For three-stage systems, we characterize the optimal policy via a Markov decision process approach. Switching times play a critical role in the optimal control of the server's work, at times leading the server to prefer remaining idle during breaks and interludes, instead of working on back-office tasks, and at others to continue back-office tasks in the presence of waiting customers. For more general service encounters, we focus on a simpler non-optimal policy where the performance measures can be computed explicitly. Sensitivity analyses in the simpler policy demonstrate that blending should first be undertaken during breaks and only then attempted during interludes. Our analysis also reveals that the interlude duration should not be artificially extended by continuing the work on back-office tasks while a customer wants to finish a last stage of service. In addition, the direction of the swicthes from front-office to back-office or back-office to front-office task has an influence. In the presence of multiple interludes in an encounter, if at all, the back-office tasks should be concentrated on fewer, longer and later interludes.

Literature review

Models of multitasking in queueing systems can be classified into three categories based on the way the server treats the tasks: simultaneous treatment, blending treatment (treat one task at a time), and imbricated treatment (treat one task within the treatment of another one). Simultaneous treatment is related to computer multitasking in switching networks or processor sharing queues [START_REF] Stolyar | Maxweight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic[END_REF][START_REF] Gromoll | Fluid limits for processor-sharing queues with impatience[END_REF]. Human simultaneous multitasking is rare and is typically done in the form of alternating between tasks.

The main idea in queue blending models is to determine efficient scheduling policies for the treatment of urgent and non-urgent jobs. As in this paper, the optimization problem in these studies consists of maximizing the time spent on non-urgent jobs while achieving a service level constraint on urgent ones. One important difference in all of the queue blending models as compared to our model assumptions is that the urgent tasks consist of single stages and switching times between tasks are not considered. Blending models have been widely studied in the context of call centers with urgent inbound and non-urgent outbound calls. Models by [START_REF] Brandt | On a two-queue priority system with impatience and its application to a call center[END_REF], [START_REF] Deslauriers | Markov chain models of a telephone call center with call blending[END_REF] evaluate performance in such systems. [START_REF] Bhulai | A queueing model for call blending in call centers[END_REF]; [START_REF] Gans | A call-routing problem with service-level constraints[END_REF]; [START_REF] Legros | Adaptive threshold policies for multi-channel call centers[END_REF] consider queue blending models where the inbound jobs have a non-preemptive priority over the outbound ones. They show that the optimal policy is a reservation threshold policy on the number of busy servers. Further references on queue blending operations include [START_REF] Keblis | Improving customer service operations at amazon.com[END_REF]; [START_REF] Pichitlamken | Modeling and simulation of a telephone call center[END_REF]; [START_REF] Pang | A logarithmic safety staffing rule for contact centers with call blending[END_REF]. Server's reservation is also shown to be effective in our article when switching times between tasks are considered. [START_REF] Armony | Contact centers with a call-back option and real-time delay information[END_REF]; [START_REF] Legros | Optimal scheduling in call centers with a callback option[END_REF] analyze optimal server scheduling policies in models with a call-back option, which allows to transform an inbound call into an outbound one. As in this paper, they show that optimal policies are a function of the number of waiting inbound calls and have a threshold form.

Polling systems consider servers that alternate between stations. The objective in these studies is to determine the optimal priority rules between stations to minimize the expected time spent in the system or a more complex holding cost function. These queueing models are also called reentrant lines and are very complex to analyze [START_REF] Hasenbein | Necessary conditions for global stability of multiclass queueing networks[END_REF][START_REF] Koole | Optimal control of tandem reentrant queues[END_REF][START_REF] Dai | Stability and instability of a two-station queueing network[END_REF][START_REF] Yom-Tov | Erlang-R: A time-varying queue with reentrant customers, in support of healthcare staffing[END_REF]. None of these studies investigate the possibility to initiate non-urgent tasks and most of them do not consider switches when moving from one station to another. In [START_REF] Srinivasan | When should a roving server be patient?[END_REF], a system where different customer classes are served at different parallel stations, with a roving server who incurs a switching time to switch from one station to another is considered. Their analysis shows that it may be better from a work in-process minimization perspective for the server to wait at a station even when there are no waiting jobs at this station, rather than roving. In our setting, the server moves between tandem service stations and a parallel back-office station, and customers may be waiting both to get into service or to continue service at an in-process station, while back-office tasks are infinite and always available. We show that the server may choose to continue treating back-office tasks during interludes when customers are waiting, or to remain idle during these times despite the desire to treat back-office tasks.

Without switches, in a multi-phase service process, [START_REF] Johri | Scheduling service in tandem queues attended by a single server[END_REF] show that it is optimal to keep on serving a customer until service completion instead of initiating the service of new customers, when the objective is to minimize the expected time spent in the system. Our optimization problem differs from theirs as we do not have the objective to minimize the time spent in the system by high priority jobs. Our conclusion is therefore also different; a strict priority for the oldest customer in the system may not be optimal. [START_REF] Iravani | A two-stage tandem queue attended by a moving server with holding and switching costs[END_REF] consider a model with two phases of service, two queues, and no switch. Using a Markov decision process approach, they derive the optimal policy and show that it can be approximated by a triple-threshold policy. The thresholds determine the states at which, it is preferred to switch from the first to the second queue, it is preferred to wait in the first queue, or it is preferred to switch back from the second to the first queue. In a similar setting, with switches, we also show that the optimal policy has a threshold nature and that the switches from urgent to non-urgent jobs are done in different states than the switches back from non-urgent to urgent jobs. In the multi-server case, [START_REF] Andradóttir | Server assignment policies for maximizing the steady-state throughput of finite queueing systems[END_REF] determine the contexts where it is optimal to spread the severs among the different stations. With switches, [START_REF] Duenyas | Control of a single-server tandem queueing system with setups[END_REF] provide a partial characterization of the optimal policy. In particular, as in our article, they show that the server should stay at a given station until the number of customers at another station exceeds a given threshold.

Case-manager systems are an example of imbricated service. [START_REF] Campello | Queueing models of case managers[END_REF] study such systems where a case-manager deals with the case of a customer that consists of a random number of tasks, interspersed with so called external delays (similar to interludes herein) during which the customer is away completing tasks elsewhere. The maximum number of customers that a case-manager takes on at a time is called the caseload. The paper investigates the tradeoff between the wait by customers upon arrival which is reduced with an increase in the caseload, and the in-process wait of customers who come back from external delay and find their case-manager working on other customers' cases which is increasing in the caseload. In [START_REF] Kc | Does multitasking improve performance? Evidence from the emergency department[END_REF], multitasking in an emergency department is measured by the number of patients simultaneously under care, thus resembling the caseload in [START_REF] Campello | Queueing models of case managers[END_REF]. Increased caseload has a negative effect on quality in KC (2013), while in [START_REF] Campello | Queueing models of case managers[END_REF] increasing the caseload has an effect on wait times. [START_REF] Dobson | Optimal workflow decisions for investigators in systems with interruptions[END_REF] consider a model for an investigator, where again the investigator can take on new customers while an existing one is away. There is no switching time for the investigator between customers, however customers who remain in the system generate so called interruptions, which affect the efficiency of the investigator. Chat service systems in contact centers are also a form of multitasking with imbricated service, where it is assumed that a server can simultaneously treat different chats [START_REF] Shae | Efficient internet chat services for help desk agents[END_REF][START_REF] Cui | Approximations for chat service systems using many-server diffusion limits[END_REF][START_REF] Tezcan | Routing and staffing in customer service chat systems with impatient customers[END_REF], alternating between chats whenever the focal one enters into an interlude. None of these papers consider the possibility of a different type of task, like the back-office tasks we consider.

Another instance of multitasking with imbricated service is found in [START_REF] Gurvich | Collaboration and multitasking in networks: Prioritization and achievable capacity[END_REF] between collaborative and individual work for professional service workers. Workers' individual work is interrupted by collaborative work, which requires the simultaneous presence of multiple workers. The individual tasks of [START_REF] Gurvich | Collaboration and multitasking in networks: Prioritization and achievable capacity[END_REF] are like the back-office tasks in our setting. Collaborative tasks resemble the front-office tasks.

While those that are labeled as cases of reaching out by the server are different from front-office tasks in that their demand is driven by the server, those that are labeled as responding to collaborative requests are similar to front-office tasks where the server needs to respond to customer requests arriving randomly. For this latter type, their arrivals are exogenous and require the presence of more than one party to be present. In our model the two parties are the server and the customer, while in theirs it is two servers. Similar to our paper, [START_REF] Gurvich | Collaboration and multitasking in networks: Prioritization and achievable capacity[END_REF] emphasize the importance of efficiency losses created by switching times between different types of tasks. Collaboration is also modeled in [START_REF] Gurvich | Collaboration and multitasking in networks: Architectures, bottlenecks, and capacity[END_REF], who study networks where some activities require the simultaneous processing by multiple types of multitasking human resources. [START_REF] Dobson | A queueing model to evaluate the impact of patient batching on throughput and flow time in a medical teaching facility[END_REF] consider a system with three tandem stations and two servers. Each server serves at one station, however a third station in the middle represents a collaborative task where both servers have to be simultaneously present. This model combines the tandem nature of our service encounter, with a collaborative task between servers. While we assume back-office tasks are infinite, here patient requests are infinite so that arrivals are not random. There is no switching time between tasks for the servers, however the need to have both servers simultaneously present combined with random service times, induces the optimality of batching for the collaborative station. This resembles the queue state-dependent policies we find.

In our setting, random customer returns from interludes and the need for simultaneous presence of the customer and the server, combined with switching times creates a similar effect.

Problem description and modeling

We consider a single-server multitasking problem with high urgency (HP) and low urgency (LP) jobs. HPs require the presence of the customer (front-office), arrive over time and should be treated quickly, whereas LPs do not require the presence of a waiting customer (back-office) and hence do not necessitate immediate treatment. The HP treatment consists of a succession of working phases interrupted by interlude phases for the server. During interlude phases, the server is not needed and can possibly work on another task. During working phases there is a direct interaction between the HP in service and the server. No other task can be assigned to the server at these moments.

Model assumptions. We model the server multitasking problem as a single-server queueing system. The server we consider is referred to as the focal server, and any other server is referred to as a non-focal server. The arrival process of HP is Poisson with arrival rate λ. If the server cannot serve an arriving HP, then the HP waits (pre-process) in a first-come-first-served (FCFS) infinite capacity queue called Queue 1. In its full generality, we model the service time of an HP by a succession of N ≥ 1 independent working and interlude phases, where working phases are generally distributed and interlude phases are exponentially distributed. The first and the last phases are working phases (thus N is an odd number). With N = 1, the service is in one single phase without interlude. The investigator system, with a single interlude, corresponds to the case N = 3. After its last phase of service, the HP leaves the system. All HPs are assumed to require the same number of service phases. This restricts the model to settings where the service encounters can be considered as relatively standardized in terms of service phases needed per customer. Processes with standard operating procedures would fall in this group. While going through an interlude phase, the HP is routed to a non-focal resource which is modeled as a random length of the interlude duration. Thus, our model does not explicitly characterize the non-focal resource. The latter is modeled as though there is an infinite capacity with no waiting or blocking due to the unavailability of this resource. After a random interlude time spent with this non-focal resource, the HP directly continues its service if the focal server is available. Otherwise, the HP waits (in-process) in another FCFS queue, called Queue 2, until the server becomes available. We consider a dynamic state-dependent priority between Queue 1 and Queue 2 which is optimized within the optimization Problem (1) defined below.

In addition, we assume to have an infinite number of LPs that are waiting to be treated. These tasks are independent from the HPs and their service time distribution does not need to be specified. At any point in time, if the server is working on LP, she can decide to interrupt her work in order to serve an HP waiting in Queue 1 or in Queue 2. Since HP and LP represent different types of tasks, the server incurs a switching time in switching from LP to HP. The switching time can be considered as a mental adjustment time for the server, the time for the server to switch systems, or the time it takes to wrap-up the ongoing LP work. The switching time duration is random and assumed to be exponentially distributed with rate µ S1 .

When the server is working on HP during a working phase of the service, the service cannot be preempted by any other jobs. At the end of a working phase, the server can decide either to remain idle, to serve another HP if there is one either in Queue 1 or in Queue 2, or to serve an LP. If the server decides to work on LP, then there also exists a switching time from HP to LP. The switching time duration is random and assumed to be exponentially distributed with rate µ S2 . For simplicity, we use the notation µ S when µ S1 = µ S2 = µ S . Note that during a switching time from HP to LP, an HP may arrive at Queue 1 or at Queue 2. In this case, we assume that the HP is directly served by the server without waiting for the end of the switch. This is a simplifying assumption made for tractability, and may not hold in some applications.

For the focal server, we distinguish the periods of time where the system is empty of HP; the server's break, and the ones where the server is not working on HP but at least one HP is with the non-focal server; the interlude. In addition, some systems limit the number of HPs which have initiated their service. The maximal number of HPs either in service with the focal server, with the non-focal server, or in Queue 2 is called the caseload. For instance, with caseload= 1, the server is not allowed to initiate the service of any HP until the HP currently in service has completely finished its service. In other words, with caseload= 1, a strict reservation-priority is given to Queue 2. We assume that the system parameters are such that the system is stable. The stability condition can be obtained when the focal server does not initiate LPs. For caseload= 1, the stability condition corresponds to the one of an M/G/1 queue, where the expected service time includes the working phases and the interludes (see [START_REF] Dai | Stability and instability of fluid models for reentrant lines[END_REF]. Other references for the stability of reentrant lines include [START_REF] Hasenbein | Necessary conditions for global stability of multiclass queueing networks[END_REF]; [START_REF] Koole | Optimal control of tandem reentrant queues[END_REF]; [START_REF] Dai | Stability and instability of a two-station queueing network[END_REF]; [START_REF] Yom-Tov | Erlang-R: A time-varying queue with reentrant customers, in support of healthcare staffing[END_REF]. For finite caseload, the stability condition is complex to determine as the system is not work-conserving. To the best of our knowledge, the literature on reentrant lines does not provide stability conditions for this case. With exponential working phases, we can determine the stability condition by the matrix geometric technique developed in [START_REF] Neuts | Matrix-Geometric Solutions in Stochastic Models: an Algorithmic Approach[END_REF]. The idea is to compute the traffic coefficient for the associated Quasi-birth-and-death process, and, to determine the condition under which the infinitesimal generator matrix is positive recurrent. This condition will ensure the existence of the stationary regime. This method is however only limited to small caseload values. For larger values of the caseload, the system dimensionality may be too high to implement this approach. The model is depicted in Figure 1.

λ µ1 + λ µ2 + • • • + λ µn < 1 (
The optimization problem. To evaluate the performance measures related to LPs and HPs, we consider the random variables T and W which represent the proportion of time spent by the server on LP and the total waiting time in the two queues by an HP customer, respectively. We are interested in the long-run expected values of these random variables; E(T ) and E(W ). More specifically, consider an interval of time [0, t] and denote by L(t) the total time spent on LP by the server excluding the switching times. We define E(T ) as

E(T ) = lim t-→∞ L(t)
t . Let us denote by A(t) the number of arrivals during [0, t] and by W k the total waiting time of the k th customer in the system (i.e., the wait in Queue 1 and in Queue 2). We then define E(W ) as

E(W ) = lim t-→∞ A(t) k=1 W k A(t) .
The quantity E(W ) can be decomposed into the expected wait in Queue 1 (denoted by E(W 1 )) plus the expected wait in Queue 2 (denoted by

E(W 2 )), E(W ) = E(W 1 ) + E(W 2 ).
At any point in time, the server has to decide whether to remain idle, to serve an HP, or to serve an LP in order to have an efficient allocation of the time to front and back-office tasks. As customers are actively waiting to be served, a waiting time constraint has to be met for HPs. LPs are non-urgent but are nevertheless valuable for the system, so the time spent to treat these tasks should be maximized. Having a service level constraint on urgent tasks and maximizing the proportion of time spent on non-urgent ones is consistent with the optimization problems encountered in the queue blending literature [START_REF] Bhulai | A queueing model for call blending in call centers[END_REF][START_REF] Gans | A call-routing problem with service-level constraints[END_REF][START_REF] Legros | Adaptive threshold policies for multi-channel call centers[END_REF].

We thus formulate the optimization problem as:

Maximize E(T ) subject to E(W ) ≤ w, (1)
where the expected waiting time service level threshold is w. A solution to Problem (1) exists if we have E(W ) ≤ w when no LPs are treated. For simplicity, we will refer to the expected proportion of time spent on LP as the expected time spent on LP instead. We choose to restrict the class of admissible policies to the class of stationary policies which are non-idling in HPs, i.e. the server is not allowed to idle if an HP is available for service. This assumption is in line with typical service management practice.

Because of the exponential assumptions for inter-arrival times at Queue 1 and for interlude times with the nonfocal server (which corresponds to arrivals at Queue 2), if a decision is optimal upon a service phase completion or an arrival instant, then the same decision is also optimal later on and as long as the system state does not change.

This result is due to the memoryless property of the exponential distribution. Although the server working phases can be generally distributed, job preemption is not allowed when the server is working on HP. Therefore, the decision instants for the server are only upon the service phase completion times and the arrival instants of HPs at Queue 1 or at Queue 2.

Consider a decision instant where the server has just completed the service phase of an HP and at least one HP is waiting in Queue 1 or in Queue 2. The focal server has to choose between scheduling an HP or an LP (or idling, but this is evidently suboptimal). Giving priority to LPs and delaying HPs obviously leads to higher waiting times.

Delaying the processing of an LP job does not change the performance for this class, as we are interested in the long-term time spent by the server on these jobs. This intuitive argument implies that, when a server becomes idle and an HP is waiting, it is optimal to serve this HP. Based on this intuitive argument, we assume that the server gives priority to HPs after a service phase completion of an HP and another HP is waiting. This priority rule is consistent with similar optimization problems encountered in the queue blending literature [START_REF] Bhulai | A queueing model for call blending in call centers[END_REF][START_REF] Legros | Adaptive threshold policies for multi-channel call centers[END_REF]. Moreover, during a switch from HP to LP if an HP arrives at Queue 1 or at Queue 2, then this HP is directly served.

Hence, after the service phase completion of an HP, the decision to treat LP can only be taken if there is no HP waiting in the system or if Queue 2 is empty and the caseload is such that the server is not allowed to start the service of an HP from Queue 1. In such cases, the server can decide either to remain idle or to treat LP. The value of remaining idle is to avoid any waste of time due to switching times when an HP should be served. The value of serving LPs is to increase the time spent on these jobs. This decision is complex and depends on the system state;

the number of HPs in Queue 1, the number of HPs with the non-focal server, and the service progress of each HP while going through the interlude.

Consider now a situation where the server is working on LP. The next possible decision instants are those of HP arrivals at Queue 1 or at Queue 2. Due to the switching time from LP to HP, the server may not automatically interrupt the service of LP upon an HP arrival at one of the queues. It may instead be beneficial to wait until the congestion in one of the queues is sufficiently important to consider the switch. Finally, if the server is in switch from LP to HP, an arrival at Queue 1 or at Queue 2 will not modify the initial decision to treat an HP.

In Figure 2, we summarize the decision actions discussed above. The server's optimal actions are state-dependent when working on LP at an arrival instant, or when an HP working phase has finished and no HP is waiting for service. The optimal policy is a function of the number of HPs in Queue 1, in Queue 2, with the non-focal server, and the remaining service time distribution of each HP. This makes it difficult to obtain. We therefore propose the following analyses to solve the optimization problem.

1. Optimal Policy (Section 4). We first focus on investigator systems with N = 1 and N = 3, assuming process (MDP) approach, we compute the optimal policy and evaluate the impact of the caseload.

2. Policy P (Section 5). We then address the problem for service encounters with multi-interludes (N ≥ 3) and generally distributed working phases. We propose and analyze a heuristic policy, labeled as Policy P, that is not state-dependent for the use of the interludes. Such a policy also provides managerial simplicity. Under

Policy P, we derive performance measures in closed-form, allowing us to further characterize the preference for when to use the interludes for LP work.

We end this section by a summary of the Notations used throughout the paper in Table 1.

4 Analysis of the optimal policy for investigator systems

In this section, we focus on solving Problem (1). To this end, we develop a Markov decision process approach in Section 4.1 to determine the optimal policy. Next, in Section 4.2, we consider special cases for the system parameters where structural properties of the optimal policy can be proven. Finally, in Section 4.3, we conduct a numerical study to understand the impact of the system parameters on the optimal policy. In order to define a Markov decision process for this system and to avoid dimensionality explosion, we assume here that working phases are exponentially distributed, and that the number of interludes is at most one (i.e., N = 1 or N = 3).

Markov decision process approach

We consider the case N = 3 and formulate the problem via the definition of states, the transition structure and the possible actions. The simpler case N = 1, can be easily deduced from the case N = 3. We denote by µ 1 , µ 2 , and µ I , the exponential rates of the first working phase, the last one, and the interlude duration, respectively and by c the caseload. Recall that µ S1 and µ S2 are defined as the exponential rates for the switch from LP to HP and for the switch from HP to LP, respectively. We define a state of the system by (Ω, v), where Ω is the state of the server; and v = (x, y, z), for x, y, z ≥ 0, where x, y, and z are the number of HPs in Queue 1 and in the first service phase, in Threshold on the number of customers in Queue 1 above which the server chooses to switch from LP to HP in order to serve high priority jobs (n * ≥ 0) p * Probability to start working on LP during the interlude (with probability 1 -p * the server remains available for directly serving HP) q * Probability to start working on LP after a switch when the system is empty of HP (with probability 1 -q * the server remains available for directly serving HP) t *

Extra time spent on LP before a switch during the interlude when the customer is ready for service completion Random Variables X Time actively spent by the server on serving the customer (it excludes the interlude times) I Time during which the customer is busy without needing the server. I is exponentially distributed with parameter µ I X S1 , X S2

Switching times respectively from HP to LP and from LP to HP, respectively T Proportion of time spent on LP W Overall waiting time for a given customer S Overall time during which the server is without the customer (either waiting for the customer, in switch or busy with LP) Probabilities for the performance evaluation under Policy P p t (n, r)

Probability-density of having n customers in the system, n ≥ 1 and a remaining service time of r, r ≥ 0, at time t (given some arbitrary initial distribution) p(n, r) p(n, r) = lim t→∞ p t (n, r), for n ≥ 1

P (n, s) P (n, s) =
∞ r=0 e -sr p(n, r) dr is the LST associated with p(n, r) π n

Stationary probability to have n customers in the system when the server is busy with high priority tasks, for n ≥ 1 (π n = ∞ r=0 p(n, r) dr) π 0,s Stationary probability to be in a system with no high priority tasks and a server in switch from HP to LP π 0,0 Stationary probability to be in a system with no high priority tasks and a server reserved for LP (not working on LP) π 0 π 0 = π 0,s + π 0,0 φ n Stationary probability to have n customers in the system when the server is busy with low priority tasks, for 0 ≤ n ≤ n * or in switch from LP to HP for n > n *

Queue 2 and in the second service phase, and with the non-focal server, respectively. The server can be working on HP, idle and waiting for an HP, or be in switch from HP to LP. In these cases, the state of the server is denoted by H and the server treats HP as long as an available HP is present in Queue 1 or in Queue 2. Otherwise, the server can be dedicated to LP or in switch from LP to HP. In these cases, the state of the server is denoted by L and the server is not allowed to treat HP even if there are HPs in Queue 1 or in Queue 2.

We next describe the possible transitions and actions from a given state (Ω, v), for Ω ∈ {H, L} and v ∈ N 3 . We denote by e i the vector (δ i,1 , δ i,2 , δ i,3 ) for i = 1, 2, 3, where δ i,j is the Kronecker delta; δ i,j = 1 if i = j, and δ i,j = 0 otherwise.

1. An arrival at Queue 1 with rate λ. The number of HPs in Queue 1 and in the first service phase is increased by 1, which changes the state to (Ω, v + e 1 ).

2. An arrival at Queue 2 with rate zµ I . The number of HPs with the non-focal server is reduced by 1 and the number of HPs in Queue 2 or in the second phase of service is increased by 1. This changes the state to

(Ω, v -e 3 + e 2 ).

3. A service phase completion can be decided either from Queue 1 or from Queue 2 with rate µ 1 or µ 2 , respectively.

If Ω = H, x > 0, y = 0, and z < c, then the server serves an HP from Queue 1. If y > 0 and either x = 0 or y + z = c, then the server serves an HP from Queue 2. Finally, if x > 0, y > 0, and y + z < c, then the server chooses the minimizing action between serving an HP from Queue 1 or from Queue 2. When a service phase completion from Queue 1 occurs, the number of HPs with the non-focal server is increased by 1 and the number of HPs in Queue 1 or in the first phase of service is reduced by 1. This changes the state to (H, v -e 1 + e 3 ).

When a service phase completion from Queue 2 occurs, the number of HPs in Queue 2 or in the second phase of service is reduced by 1. This changes the state to (H, v -e 2 ).

4. A switch from HP to LP can be decided if Ω = H, x = y = 0 (i.e., the two queues are empty) or if y = 0 and z = c (i.e., Queue 2 is empty and the number of HPs with the non-focal server attains the caseload). If this choice is made, the state changes to (L, v) upon the switch completion with rate µ S2 .

5.

A switch completion from LP to HP can be decided if Ω = L. If this choice is made, the state changes to (H, v)

upon the switch completion with rate µ S1 .

With finite caseload, the maximal event rate, λ

+ cµ I + µ S1 + µ S2 + µ 1 + µ 2 , is bounded. This continuous-time
model is therefore uniformizable. We then choose to discretize it (Section 11.5.2. in [START_REF] Puterman | Markov Decision Processes[END_REF]). We assume

that λ + cµ I + µ S1 + µ S2 + µ 1 + µ 2 = 1
, such that the rate out of each state is equal to 1 by adding fictitious transitions from a state to itself; then we can consider the rates to be transition probabilities. Note that the system with infinite caseload can only be approximated with a sufficiently high finite caseload. We define the dynamic programming value functions V k (Ω, v) over k ≥ 0 steps, depending on the state of the system (Ω, v), for Ω ∈ {L, H}

and v ∈ N 3 . We choose V 0 (Ω, v) = 0, for Ω ∈ {L, H} and v ∈ N 3 . Next, we express V k+1 (Ω, v) in terms of V k (Ω, v)
in the following way. The objective to maximize the time spent on LP and the constraint for HP are merged into a single cost function using a Lagrange parameter γ which accounts for the time spent by an HP in Queue 1 or in Queue 2 and with the focal server. The value of γ is chosen such that for the optimal policy E(W ) = w [START_REF] Altman | Constrained Markov decision processes[END_REF]. The procedure to set the value of γ is presented in Section 1 of the Online Appendix. Moreover, we count a reward of one when the server is treating some LPs in order to obtain the proportion of time spent on LPs. The objective for the server is to determine when to initiate the switches from HP to LP and those from LP to HP. The optimal decisions are captured by the minimization operator, V * k (Ω, v), in the value function formulation.

We write for k ≥ 0, Ω ∈ {L, H} and v ∈ N 3 :

V k+1 (H, v) = γ(x + y) λ + λV k (H, v + e 1 ) + zµ I V k (H, v -e 3 + e 2 ) (2) + 1 x>0,y=0,z<c µ 1 V k (H, v -e 1 + e 3 ) + 1 y>0,(x=0∪y+z=c) µ 2 V k (H, v -e 2 ) + 1 y=0,(x=0∪z=c) µ S2 V * k (H, v) + 1 x>0,y>0,y+z<c min (µ 1 (V k (H, v -e 1 + e 3 ) -V k (H, v)), µ 2 (V k (H, v -e 2 ) -V k (H, v))) + (1 -λ -zµ I -µ 1 1 x>0,y=0,z<c -µ 2 1 y>0,(x=0∪y+z=c) -µ S2 1 y=0,(x=0∪z=c) )V k (H, v)
, and,

V k+1 (L, v) = γ(x + y) λ -1 + λV k (L, v + e 1 ) + zµ I V k (L, v -e 3 + e 2 ) + µ S1 V * k (L, v) + (1 -λ -zµ I -µ S1 )V k (L, v),
where 1 x∈A is the indicator function of a given subset A, and

V * k (L, v) = min(V k (H, v) + 1, V k (L, v)) (i.e.
, switching decision from LP to HP), and

V * k (H, v) = min(V k (H, v), V k (L, v)) (i.e., switching decision from HP to LP), if v = z e 3 for z ≥ 0 or v = x e 1 + c e 3 , for x ≥ 0 and, V * k (H, v) = V k (H, v), otherwise.
In Equation ( 2), the terms γ(x+y) λ measure the expected wait in the system. The terms proportional with λ represent a customer's arrival in Queue 1. The terms proportional with zµ I correspond to an arrival in Queue 2 from a customer who completes a service with the non-focal server. The terms proportional with µ i corresponds to the end of working phase i for i = 1, 2. The terms proportional with µ S1 and µ S2 capture the possibility to start an HP or an LP after a switch time. The minimizing operator in the first part of the equation optimizes the decision for serving a customer from Queue 1 or from Queue 2.

The last term gives the fictitious transition from a state to itself. Note that a cost of one is counted if a switch from LP to HP is executed in order not to count the switching time into the time spent on LP.

To obtain the infinite horizon average optimal actions we rely on the value iteration technique by recursively evaluating V k using Equation ( 2), for k ≥ 0. As k tends to infinity, the optimal policy converges to the unique average optimal policy. This convergence result is ensured by Theorem 8.10.1 in Puterman (1994) (a countable state set, finite set of actions and a uniformizable system). As k tends to infinity, the difference V k+1 -V k converges to γE(W ) -E(T ) [START_REF] Puterman | Markov Decision Processes[END_REF]. Since E(W ) = w for the optimal policy, one can then easily compute the value of E(T ). Note that by redefining the cost associated with the number of HPs in Queue 1 or in Queue 2, one can also obtain E(W 1 ) and E(W 2 ) using value iteration.

The numerical investigations show that the optimal policy for the switches from LP to HP or from HP to LP either during the interlude or during the break is a state-dependent threshold policy. This policy is characterized by the following properties:

• If it is optimal to switch from LP to HP in state (L, x, y, z), then it is also optimal to operate this switch in states (L, x + 1, y, z), (L, x, y + 1, z), and (L, x, y, z + 1), for x ≥ 0 and 0 ≤ y + z < c.

• If it is optimal to switch from HP to LP in state (H, 0, 0, z + 1) (respectively, in state (H, x + 1, 0, c)), then it is also optimal to operate this switch in state (H, 0, 0, z) (respectively, in state (H, x, 0, c)), for 0 ≤ z < c and

x ≥ 0.
Even though, we can compute the optimal policy numerically, it is not possible to prove its properties using an induction step for the general case. In the following section, considering some special cases of the system parameters, we prove some of the structural properties of the optimal policy. These properties will be used in Section 5 to propose a simpler policy to solve Problem (1).

Structural properties of the optimal policy in special cases

First, we consider the case N = 1, where the service of an HP is executed in one single stage without interlude. The analysis of this case enables us to better characterize the optimal decisions that the server should make during the break. Next, we investigate the case N = 3 with a caseload= 1, where the optimal decisions during the interlude can be proven. Finally, we investigate the case N = 3 with infinite caseload and a strict priority for Queue 1 in order to prove how the state variables x, y, and z impact the optimal decisions.

Analysis of the case N = 1

Without interludes, the value function can be reformulated in a simpler form as the system becomes one-dimensional.

Equation ( 2) is then reformulated as

V k+1 (H, x) = γx λ + λV k (H, x + 1) + 1 x>0 µ 1 V k (H, x -1) + µ S2 1 x=0 V * k (H, 0) (3) + (1 -λ -µ 1 1 x>0 -µ S2 1 x=0 )V k (H, x)
, and,

V k+1 (L, x) = γx λ -1 + λV k (L, x + 1) + µ S1 V * k (L, x) + (1 -λ -µ S1 )V k (L, x),
where x is the number of customers in the system, with

V * k (L, x) = min(V k (H, x) + 1, V k (L, x)) (i.e.
, switching decision from LP to HP), and

V * k (H, x) = min(V k (H, x), V k (L, x)).
In Proposition 1, we prove, under some conditions reflecting a high care for customer's wait and a sufficiently long switching time, that the optimal policy for the use of the break is a threshold policy. This result extends those for the queue blending literature without switches, and will be used in Section 5 to construct Policy P.

Proposition 1 With µ S2 ≤ µ 1 ≤ 2µ S2 and γ ≥ λ, the optimal policy for the use of the break is defined by the parameters n * and q * , such that a switch from LP to HP is initiated whenever the number of HPs in Queue 1 is strictly above n * and the switch from HP to LP is initiated with probability q * when the system becomes empty.

The proof of Proposition 1 is given in Section 2 of the Online Appendix. The parameter n * is a threshold which defines a deterministic state-dependent priority for HP. The parameter q * allows the system to provide something stronger than a simple priority. In the case n * = 0 and q * = 1, a strict priority is given to HP in a work-conserving situation. If q * = 0, no LPs are treated in between HP in order to reserve the server for HP.

Analysis of the case N = 3 with caseload= 1

For such a setting, the optimal policy for the switch from LP to HP is simpler due to the constraint 0 ≤ y + z ≤ 1.

Moreover, with caseload= 1, Queue 2 has a strict priority over Queue 1. Therefore, Equation (2) can be rewritten as follows:

V k+1 (H, v) = γ(x + y) λ + λV k (H, v + e 1 ) + zµ I V k (H, v -e 3 + e 2 ) (4) + 1 x>0,y=0,z=0 µ 1 V k (H, v -e 1 + e 3 ) + 1 y>0 µ 2 V k (H, v -e 2 ) + 1 y=0,(x=0∪z=1) µ S2 V * k (H, v) + (1 -λ -zµ I -µ 1 1 x>0,y=0,z=0 -µ 2 1 y>0 -µ S2 1 y=0,(x=0∪z=1) )V k (H, v), and, V k+1 (L, v) = γ(x + y) λ -1 + λV k (L, v + e 1 ) + zµ I V k (L, v -e 3 + e 2 ) + µ S1 V * k (L, v) + (1 -λ -zµ I -µ S1 )V k (L, v).
For the switch from LP to HP, we observe numerically that there exist three thresholds on the number of HPs in Queue 1 denoted by u I1 , u I2 , and u B , depending on whether the server is in an interlude and an HP is with the non-focal server (y = 0, z = 1), the server is in an interlude and an HP is in Queue 2 (y = 1, z = 0), or no HP is with the non-focal server nor in Queue 2 (i.e., a server's break: y = z = 0), such that the decision to switch from LP to HP is taken if and only if the number of HPs in Queue 1 is above these thresholds. A switch from HP to LP, may occur either if x = y = z = 0 (switch during the break) or if y = 0, z = 1 and x < ũI (switch during the interlude).

In Proposition 2, we show the threshold structure of the optimal policy during the interlude for the switch from LP to HP and from HP to LP. Moreover, we show that u I1 ≥ u I2 . The proof of Proposition 2 is given in Section 3 of the Online Appendix. Note that the threshold structure of the optimal policy for the switch from LP to HP during the break cannot be proven with this technique due to the caseload limitation which breaks the monotonicity properties of the value function.

Proposition 2 For caseload= 1, the optimal policy during the interlude is of threshold type. There exists thresholds u I1 , u I2 and ũI such that:

• The switch from LP to HP is initiated if and only if x ≥ u I1 with y = 0 and z = 1, or x ≥ u I2 with y = 1 and

z = 0. Moreover, u I1 ≥ u I2 .
• The switch from HP to LP during an interlude is initiated if and only if x < ũI .

Analysis of the case N = 3 with infinite caseload and priority for Queue 1

With infinite (or unrestricted) caseload, some properties of the optimal policy can be proven. However, we need to simplify the model assumptions by giving strict priority to Queue 1 instead of optimizing the queue priority and by assuming µ 1 = µ 2 = µ S2 . Moreover, as the system is non-uniformizable with infinite caseload, the MDP approach can be implemented only if the real system is approximated by a sufficiently high finite caseload such that uniformization is possible and the effect of the caseload restriction can be neglected.

Even though the problem becomes three-dimensional with infinite caseload, as the switch from HP to LP can only be operated if x = y = 0, the decision to switch from HP to LP only depends on the state variable z. This simplifies the analysis as compared to a case with a finite caseload.

Under the aforementioned assumptions, in Proposition 3, we prove the threshold structure of the optimal policy in the variables y and z. Yet, we are not able to show the same result in the variable x as some of the monotonicity properties do not propagate via an induction step. However, by further replacing the expected wait E(W ) in Problem

(1) by the expected wait in Queue 1, E(W 1 ), the optimal policy can be fully proven. This objective is compatible with a priority to Queue 1. The proof of Proposition 3 is given in Section 4 of the Online Appendix. As reflected in this proposition, the optimal policy may be impracticable due to its complexity. Therefore, in Section 5, we simplify the analysis by considering non-state-dependent decisions during the interlude.

Proposition 3 In the case µ 1 = µ 2 = µ S2 , without caseload restriction, with priority for Queue 1, the optimal policy is a threshold type policy with the following properties:

• Switch from HP to LP. There exists a threshold on the number of customers with the non-focal server, ũ, such that the server initiates a switch from HP to LP if and only if both queues are empty and the number of HPs with the non-focal server is strictly below this threshold; z < ũ.

• Switch from LP to HP. For each x ≥ 0, there exists a threshold function z = u x (y), decreasing in y, such that if the server is working on LP in state (x, y, z) then it is optimal to switch from LP to HP if and only if

z ≥ u x (y).
Under the same conditions, while considering E(W 1 ) instead of E(W ) in the objective, the optimal policy is also of threshold type but the switch from LP to HP can be further characterized as follows:

Numerical analysis

We end this section with a numerical analysis to better understand how the optimal policy is influenced by the environmental conditions. First, in Section 4.3.1, we investigate the effect of the system parameters on the optimal policy in the case N = 3 and caseload= 1. Next, in Section 4.3.2, we evaluate the role of the caseload.

Effect of the system parameters

Table 2 tabulates the thresholds for the policy computed with Equation (4) (see Section 4.2.2) for different values of the system parameters under the stability condition λ < µ -1

1 + µ -1 I + µ -1 2 -1
. Note that the service rates are chosen such that the expected service time of an HP is constant (i.e., µ -1 1 + µ -1 I + µ -1 2 is constant). Consistent with Proposition 2, we observe that u I1 ≥ u I2 . We also observe that u I1 ≥ ũI . This means that if a switch from HP to LP is decided in a given state, then in the same state the server should not initiate a switch back from LP to HP. In most cases, we also observe that u B ≥ u I1 : For a given number of HPs in Queue 1, one more HP is present in the system during an interlude (either with the non-focal server or in Queue 2) than during a break.

Hence, it is more urgent to switch from LP to HP during an interlude than during a break which is represented by u B ≥ u I1 . Surprisingly, counterexamples can be found for low values of µ S (see lines 8 and 9). The explanation comes from the long switching times. If a decision to treat LP during the interlude is taken (i.e., at state (x, 0, 1)), then the HPs already waiting in Queue 1 suffer from a first switch from HP to LP and from an additional one from LP to HP. The decision to treat LP during the break can only be taken in an empty system due to the priority for HP, so no HP is impacted by the switch from HP to LP. (Recall that an HP who arrives during a switch from HP to LP is directly served.) During the break, arriving HPs are only impacted by the switch from LP to HP. To reduce the negative effect of a double switch during the interlude compared to a single one during the break, the server should continue working on LP for a larger number of waiting HPs during the interlude than during the break. This behavior of the optimal policy explains why it is not possible to show the monotone behavior of the optimal policy as a function of the congestion in Queue 1 during the break. The preference for using the break or the interlude will be further investigated via a sensitivity analysis under policy P in Section 5.

Table 2 is organized in order to explore the impact of various system parameters.

• Comparison of lines 4-6 with lines 10-12 shows the role played by the service level objective, ω. We observe that the thresholds increase when the desired service level on HP is less strict, i.e., when these requests become less urgent, and consequently more time is dedicated to LP work as seen in the increased values of E(T ) in the last column.

• Comparison of lines 1-3 with lines 4-6 or with lines 7-9 shows the important role played by the switching times when switches from HP to LP and from LP to HP have the same expected duration. With long switching times, the server should postpone the switch from LP to HP. This is reflected by high thresholds for the switch from LP to HP (u I1 , u I2 , and u B ). The last column shows the high negative impact that switching times may have on the expected time spent on LP. In order to avoid making too frequent switches, we also could expect to have ũI decreasing with the length of the switching time. However, since ũI has reached its minimal value already with µ S1 = µ S2 = 10, no further reduction can be observed while increasing the switching rate.

• The examples in lines 13-14 highlight the impact of the interlude duration. A long interlude duration is an incentive to use this interlude to treat LP. This can be observed with u B increasing from 1 to 3 when µ I changes from 5 to 0.5, making the interlude duration ten times longer.

• Lines 15-16 provide examples where the two working phases have different duration. The observations here can only be made in cases where the rates µ 1 and µ 2 are significantly different. If µ 2 >> µ 1 , then an HP does not represent a significant amount of remaining work for the server after the completion of the first working phase.

Therefore, the decisions of the server during the interlude are close to those during the break as observed at line 15 (u B = u I1 ). If µ 2 << µ 1 , the important amount of remaining work after the completion of the first working phase tends to reduce the value of using the interlude and is reflected by smaller thresholds (u I1 and ũI ).

• Lines 11, 17 and 18 illustrate the impact of having different switching duration from LP to HP and from HP to LP. We choose 1

µ S 1 + 1 µ S 2
= 2 such that the sum of the expected duration of the switches is kept constant.

We observe that a long switch from HP to LP is less problematic than a long switch from LP to HP. This observation is due to the beneficial possibility of preemption by an HP when the server is in switch from HP to LP while this preemption is not possible for the switch back from LP to HP. We observe in particular that the thresholds are higher at line 17 than at line 18 which reflects longer periods of time spent on LPs.

• The impact of the arrival rate is less straightforward. In some examples we observe that the thresholds increase with the arrival rate (see lines 1 to 3 or lines 4 to 6), while in others the threshold decrease (see lines 7 to 9). This may be the result of the competition between two phenomena. With high arrival rates, the proportion of time spent on HP should be important in order to attain the service level constraint for HP. This would imply decreasing thresholds as the arrival rate increases, as observed in lines 7-9. However, lines 1-3 and 4-6 contradict this conclusion. It is in fact not good to have high thresholds with low arrival rates (see lines 1 and 4). Consider a situation where the server is treating LP and one HP is at the head of Queue 1. The switch from LP to HP will be executed when the number of HPs in Queue 1 attains the threshold. With a low arrival rate, the time between two arrivals is long. Hence, high thresholds would lead to an excessive wait for the HP at the head of the queue. This explains why with a low arrival rate, it makes sense to also have low thresholds.

Impact of the caseload

A caseload restriction may be imposed either for managerial reasons (a quality concern in a healthcare setting) or to limit the overall service time of an HP. Clearly, the caseload creates an additional constraint for the optimization problem, which can only deteriorate the solution. We investigate the impact of the caseload on E(W 1 ), E(W 2 ) and E(T ). Using the computed policy with Equation (2), we determine the performance measures by adjusting the cost parameters in the value function.

In Figure 3, we present the performance measures as a function of the arrival rate λ for three values of the caseload (1, 2 and 3). We first observe that as the caseload increases, the interval for λ which allows the system to achieve E(W ) = ω increases. This observation can be related to the stability of the system which increases with the caseload. The second observation is that the proportion of time spent on LP is higher with a higher caseload. The

= µ 2 = 2, µ I = 1, µ S1 = µ S2 = 4, ω = 1)
difference can be significant for high arrival rates (see Figure 3(a)). So, clearly, an unrestricted caseload is the best choice for Problem (1).

Another observation is that although

E(W ) = E(W 1 ) + E(W 2 ) is maintained constant, E(W 1 ) (respectively, E(W 2
)) increases (respectively, decreases) with the arrival rate and decreases (respectively, increases) with the caseload. Since the caseload limits the number of HPs in Queue 2, increasing the caseload allows more HPs to wait in Queue 2 and clearly leads to higher values for E(W 2 ). The caseload limits the congestion in Queue 2. Hence, the congestion increases more in Queue 1 than in Queue 2, when the arrival rate increases. This explains why E(W 1 ) is increasing in λ. The caseload restriction gives a state-dependent server reservation for Queue 2 (i.e., if too many HPs are either in Queue 2 or with the non-focal server, then the server is not allowed to initiate an HP from Queue 1).

This explains why for a low caseload and a high arrival rate we have E(W 2 ) < E(W 1 ). Having a small in-service wait, E(W 2 ), can be important in some contexts. For example, in the after-sales technical service setting, it may be desirable to complete the repair of a critical item urgently, or the general practitioner may wish to complete the initial treatment of a serious patient in order to direct them to a specialist without delay. In a chat service context, customers may be more annoyed by an in-chat wait than a pre-chat wait. Despite the increase in performance for Problem (1) as the caseload is increased, we note that the improvement is decreasing in caseload, suggesting an eventual saturation. Taken together with the fact that the in-service waiting time increases, one is left with the recommendation that the caseload should not be increased beyond several customers.

5 Analysis for general multi-stage encounters under a restricted policy

In this section, we consider multi-stage service encounters like the earlier mentioned audit process or general practitioner examples, possibly having more than one interlude. Given the fixed number of stages assumption made, as stated in the modeling section, we are considering mostly processes with standard operating procedures or protocols.

This in turn suggests that an exponential working phase may be too restrictive as an assumption. Therefore, we wish to consider general service times for the working phases. The analysis of Section 4 shows us that even in the presence of a single interlude, optimal policies during interludes are state-dependent, with state-dependent thresholds. This creates a very complex policy to implement. It is clear that for a setting with multiple interludes, policies will be even more complex. The desire to have general service times will further complicate the analysis, with policies that need to depend on the remaining service time distribution of HP. In addition to being analytically intractable, state-dependent policies for use of the interludes may also not be practical. Having a single policy for all interludes may be preferred. Thus, motivated by both tractability and managerial simplicity concerns, we limit the analysis of Problem (1) for general multi-stage encounters to a restricted class of policies called Policy P. The idea is to keep the policy for use of the break state-dependent as shown to be optimal in Section 4.2.1, while making that for the interludes a static policy. Keeping the control during the breaks state-dependent is relatively easier, as this decision only depends on the number of customers in Queue 1. The benefit of using this simpler (non-optimal) policy is that we can characterize performance measures and some policy parameters analytically when caseload= 1. This in turn allows us to explore the general question of when one would be interested in using the interludes for back-office work in such general multi-stage service encounters.

This section is organized as follows. Section 5.1 defines Policy P. Section 5.2 gives the explicit performance measures and partially characterizes the optimal control parameters in the case caseload= 1. Section 5.3 provides the results of the numerical investigation showing the main drivers for the use of the interlude or the break. Section 5.4 extends the analysis of Section 5.3 in order to answer managerial questions.

Definition of Policy P

For Policy P, we give a strict priority for Queue 2. The policy for the use of the break and the interlude is defined as follows:

The server's policy during a break. We propose a queue length dependent threshold priority for HP. We define a threshold n * on the number of HPs in Queue 1 and a parameter q * such that

• At a service completion of an HP, if the system is empty of HP (i.e., a break), then with probability q * the server switches from HP to LP and with probability 1 -q * , she chooses to remain idle and thus available for directly serving HP (reservation). Recall that if an HP arrives before the end of the switching time, this HP is directly served.

• If the server is working on LP, the server initiates a switch from LP to HP if and only if the number of HPs in Queue 1 is strictly above n * .

Note that this policy is identical to the one found in Proposition 1.

The server's policy during an interlude. During an interlude, we choose a non-state dependent policy. At the beginning of an interlude, the server automatically switches from HP to LP with probability p * and works until an HP comes back. When the customer comes back,

• if the server is still in switch from HP to LP then the customer is directly served,

• if the server is working on LP then the server continues working on LP during t * time units then switches from LP to HP before continuing the service of the HP customer.

The possibility to continue working on LP for a duration t * allows the server to reduce the negative impact of the switching times by working longer on LP. Note that in the case p * = t * = 0, the server is reserved for HP, in the case p * = 1 and t * = 0, then a strict priority is given to HP but the server adopts a work-conserving strategy. The definition of this policy can be extended to a case with multiple interludes by setting a parameter p * and t * for each interlude.

The randomizing parameters q * and p * are useful by allowing exact attainment of the service level constraint for HP. The parameters p * and q * control the decision to switch from HP to LP whereas the parameters n * and t * control the decision to switch back from LP to HP. From a simulation study, we compare the performance of Policy P to the optimal policy for investigator systems (N = 3) in Section 5 of the Online Appendix. We observe that it performs well, and its performance may even coincide with the optimal one in some cases (for high and low arrival rates). However, in cases with long interlude durations, short switching times and a high workload its performance begins to deviate from the optimal one.

Analysis of Policy P with caseload= 1

Theorem 1 gives closed-form expressions for the performance measures of interest for Policy P with caseload= 1. In order to simplify the notation, we assume that the service encounter includes only one interlude with an exponential rate µ I . We denote by R, the random service time of an HP. It is defined as the interval of time from the initiation of the first phase of service of an HP to the last service phase completion. It includes the working phases, the time spent with the non-focal server and the wait in Queue 2. Hence, the service time can be decomposed as the sum of two random variables, X and S, where X is the time actively spent with the server (the working phases) and S is the time spent without the server (the time spent with the non-focal server plus the time spent in Queue 2), R = X + S. The system performance measures are functions of E(R) and cv R defined as the expected service time and the coefficient of variation of the service time R, respectively. The random variable X is given by the distributions of the working phases. What remains to be characterized is the random variable S. Hence, for the performance evaluation, we determine the first and the second moments of S; denoted by E(S) and E(S 2 ), respectively. Finally, we denote by a Si the ratio λ/µ Si , for i = 1, 2. The stability condition in this model is identical to the one of an M/G/1 queue since HPs are served one by one (caseload= 1), i.e., λE(R) < 1. Note that the performance measures can easily be extended to the case of more than one interlude; while the parts of the expressions of E(T ) and E(W ) depending on the break would remain identical, other parts corresponding to additional interludes should be added. These additional terms would be obtained in a similar way as the parts related to single interlude.

The approach to compute the performance measures first consists of providing a recursive formula for the computation of the stationary probabilities, using a state definition based on the residual service time for a given customer.

From the recursive relations for the stationary probabilities, we derive the probability of an empty system, the expected waiting time and the expected time spent on LP as a function of the system parameters, the first and the second moments of the time spent in service (which includes the time spent with the server plus the time spent with the non-focal server plus the time spent in Queue 2), and the expected time spent on LP during the interlude. The complete detailed proof is given in Section 6 of the Online Appendix.

Theorem 1 The expected proportion of time spent on LP, E(T ), is

E(T ) = p * λ µ S1 µ I + µ S1 t * + 1 µ I - 1 µ S1 + µ I e -µ S 1 t * µ S1 (µ S1 + µ I ) + (1 -λE(R))(n * + 1) n * + 1 q * + 1 q * (a S1 + q * a S2 )
.

(5)

The expected waiting time, E(W ), is

E(W ) = p * µ S1 µ S1 + µ I 1 µ S2 + t * + λE(R) 2 (1 + cv 2 R ) 2(1 -λE(R)) + n * (n * + 1 + 2a S2 ) 2λ n * + 1 q * + 1 q * (a S1 + q * a S2 ) (6) + 1 µ S2 • 1 + a S2 n * + 1 q * + 1 q * (a S1 + q * a S2 )
.

The first and second moments of S are

E(S) = 1 µ I + p * µ S1 µ S1 + µ I 1 µ S2 + t * , (7)
E(S 2 ) = 2 µ 2 I + p * µ S1 µ S1 + µ I t * + 1 µ S2 2 + 1 µ 2 S2 + 2 µ I t * + 1 µ S2 . ( 8
)
The expected time spent on LP, as given in Equation ( 5), is the sum of the expected time spent on LP during the interlude, E(T

I ) = p * λ µ S 1 µ I +µ S 1 t * + 1 µ I -1 µ S 1 + µ I e -µ S 1 t * µ S 1 (µ S 1 +µ I )
, and the expected time spent on LP during the break,

E(T B ) = (1-λE(R))(n * +1) n * + 1 q * + 1 q * (aS 1 +q * a S 2 )
. The expected waiting time, as given in Equation ( 6), is the sum of four terms.

The first one is the in-service wait in Queue 2,

E(W 2 ) = p * µ S 1 µ S 1 +µ I 1 µ S 2
+ t * , and the second one is similar to the expected waiting time in an M/G/1 queue. This second term shows that the variability of the working phases negatively affects the solution of Problem (1). The last two terms may be more complicated to interpret. Note that in the case of q * = 1 and µ S1 = µ S2 , the third term is exactly equal to n * 2λ which corresponds to the effect of n * on the waiting time (n * /2 is the average queue size when the server is on LP).

Computation of the optimal threshold parameters under Policy P. We proceed by first assuming that the policy for the use of the interlude is fixed (i.e., the parameters p * and t * are fixed) in order to derive closed-form expressions for the optimal values of n * and q * . Next, the values of p * and t * will be computed numerically. Since the use of the interlude is fixed, the difference

K = w -E(W 2 ) - λE(R) 2 (1+cv 2 R ) 2(1-λE(R))
is also fixed. We assume that K ≥ 0, otherwise the waiting time constraint in Problem (1) cannot be satisfied. In Proposition 4, we state the optimal expressions of n * and q * in K and the system parameters. The proof is given in Section 7 of the Online Appendix.

Proposition 4 The following holds.

1. If a S2 ≥ 1 √ 2 and λK ≤ √ 2a S 2 (( √ 2+1)a S 2 -1 2 ) 1+a S 1 2 +( √ 2+1)a S 2 -1 , then the optimal couple (n * , q * ) is n * = √ 2a S2 -1 and q * = λK 2 (1+a S 1 ) √ 2a S 2 (a S 2 ( √ 2+1)-1/2)-λK(a S 2 ( √ 2+1)-1) . 2. If a S2 < 1 √ 2 and λK ≤ a S 2 (1+a S 2 ) 1+a S 1 +a S 2
, then the optimal couple (n * , q * ) is n * = 0 and q * = (a S 1 +1)λK a S 2 (1+a S 2 -λK) .

3. In the remaining cases, the optimal couple (n * , q * ) is

n * = λK -a S2 -1 2 + 1 2 2 + (2λK + 2a S1 + 1) 2 -(1 + 2a S1 ) 2 -(1 + 2a S2 ) 2 and q * = 1.
It is not possible to obtain the parameters p * and t * in closed-form. To solve Problem (1), we first fix a policy for the interlude and determine q * and n * according to Proposition 4. Next, by an exhaustive search, we obtain the best combination of parameters which solve Problem (1).

Main drivers for the decisions to use the interlude and the break

From numerical investigations, we observe that the switching times have a major impact on the optimal policy. For caseload= 1, from the expression of E(T I ), the difference between 1/µ S1 and 1/µ I implies that if the expected time of the interlude is shorter than the expected switching time, then E(T I ) decreases in p * . So, in this case the interlude should not be used and p * = t * = 0. Second, the switching times also have a strong impact on the choice of n * as shown in Proposition 4. In case of long switching times (first and last statement of the proposition), a high value for n * may reduce the switches from HP to LP during the break. Finally in most cases, t * = 0. It is almost never optimal to extend the interlude duration.

In Figure 4, we depict the possible cases generally observed in the case where µ S1 = µ S2 (i.e., no distinction between the switches from HP to LP and from LP to HP). The characterization (long or short) of the switching time is relative to the service time, the characterization (high or low) of the workload is relative to the difficulty of satisfying the service level constraint and the characterization (long or short) of the interlude time is relative to the switching time. Considering an insurance or audit setting, one can envision a long switch if the server needs to change the software or system which they are using for HP and LP tasks, while a short switch may be seen in settings where the two tasks are not dramatically different and require a short mental adjustment. It is interesting to observe that in many cases very simple solutions should be implemented. For instance, with short switching times and high workload the combination n * = 0 and q * = 1 indicates that a strict priority should be given to HP. With even higher workload and short switching times, p * = 0 means that it is a good strategy to reserve the server for HP during the interlude. On the contrary, in low workload situations, p * = 1, suggesting to systematically treat LP during the interlude. More generally, we observe that many parameter combinations lead to a postponed switch policy, indicating that the server will continue working on LP despite some waiting HP tasks. Similarly, whenever p or q are equal to zero, the server is preferring to remain idle during the interlude or break, despite an infinite amount of LP work available.

Illustration. An illustrating instance is provided in Figures 5 and6 for caseload= 1 and infinite caseload, respectively. For the comparison, the results for caseload= 1 are included in Figure 6 with the dotted curve. The results of Figure 5 are derived from the explicit expressions of the performance measures in Section 5.2 while those of Figure 6 are obtained from simulations. We propose here a simple procedure based on intuitive assumptions regarding the monotonicity properties of the performance measures. From simulations, we observe that increasing one of the parameters p * , q * , or n * increases E(W ) and E(T ). This observation is intuitive as spending more time on LPs reduces the server's availability which in turn increases the wait. Based on this assumption, in what follows, we explain how we can restrict the number of simulations to a finite set of possible values for the control parameters.

As p * and q * may take an infinite set of values, we discretize their values. We introduce the parameter M ∈ N + , such that the values of p * and q * are restricted to 0

, 1 M , 2 M , • • • , M -1 M , 1.
Therefore, the couple (p * , q * ) can take (M + 1) 2 values. The parameter n * can also take an infinite number of positive integer values. In the simulations, for each set of parameters p * and q * , we increase n * by one until we reach E(W ) > w. For a given couple (p * , q * ), the optimal value for n * is the highest integer such that E(W ) ≤ w. As E(W ) is unbounded in n * , the optimal value for n * can be determined after a finite number of simulation experiments. It may happen that for a given couple (p * , q * ), we have E(W ) > w for n * = 0. In this case, the couple (p * , q * ) should be excluded from the set of possible solutions as well as any couple with a higher value for p * or q * . This allows us to reduce the number of simulation experiments. Note also that with p * = q * = 0%, n * does not need to be specified. we observe that E(T ) decreases with the variability of the service time. Moreover, the impact of the variability of the working phases is stronger when the interlude is not used (Figure 5 . Two phenomena concur in this effect. First, if the interlude is long, then the working phases have a relatively small impact on the overall service length. Hence, the variability of these working phases has a small effect on the performance as shown in Figures 5(a), 5(c), 6(a) and 6(c). Second, if the interlude is long then it is also used for treating LP. This creates in-service switches which further reduce the relative importance of the working phases in the service process of an HP. Although the optimal policy derived in Section 4 differs from the one studied here for the use of the interlude, we observe the same drivers as in Section 4 for the switch from LP to HP (high congestion in Queue 1 or in Queue 2, short interludes, and short switching times).

Ύ с Ϭ й Ϭ ф Ƌ Ύ ф ϭ Ϭ Ϭ й ͕ Ŷ Ύ с Ϭ (c) µ I = 0.02, µ S 1 = µ S 2 = 0.1, E(X) = 1, E(X 2 ) = 1, ω = 100
(d) µ I = 10, µ S 1 = µ S 2 = 0.05, E(X) = 1, E(X 2 ) = 1, ω = 25
Ύ с Ϭ й Ϭ ф Ƌ Ύ ф ϭ Ϭ Ϭ й ͕ Ŷ Ύ с Ϭ (a) µ I = 0.02, µ S 1 = µ S 2 = 0.1, E(X) = 1, E(X 2 ) = 100, ω = 100
Ύ с Ϭ й Ϭ ф Ƌ Ύ ф ϭ Ϭ Ϭ й ͕ Ŷ Ύ с Ϭ (c) µ I = 0.02, µ S 1 = µ S 2 = 0.1, E(X) = 1, E(X 2 ) = 1, ω = 100
ƉΎсϬй͕ ƋΎсϭϬϬй͕ ŶΎхϬ Ɖ Ύ с Ϭ й ͕ Ϭ ф Ƌ Ύ ф ϭ Ϭ Ϭ й ͕ Ŷ Ύ х Ϭ (d) µ I = 10, µ S 1 = µ S 2 = 0.05, E(X) = 1, E(X 2 ) = 1, ω = 25

Managerial questions

We end this section by focusing on specific questions related to our optimization problem. The analysis in the section is made with the performance measures obtained for caseload= 1 but are checked to be valid with higher caseload.

We first explore the question of when to use the interlude and when to prefer the break for LP work. To this end, we compare p * and q * . We observe in Figure 5(a) that as the workload increases, we should first decrease p * and then q * . This is consistent with the results of Section 4 (see Table 2) where in most cases u B ≥ u I1 . The second observation is t * = 0. Apparently, extending the interlude duration is not a good strategy. The last observation is that the switch from HP to LP has a worse impact than the switch from LP to HP. Finally, when more than one interlude is involved should we either spread the work on LPs over different interludes or should we instead concentrate this work on fewer ones? Are these observations generalizable? Theorem 1 allows us to explore these questions analytically and to understand the intuition behind preferences for use of the interlude compared to the break.

Which duration to use more frequently for back-office work: interlude or break?

We consider a situation where t * = 0 (i.e., no possibility of increasing the interlude duration) and explore whether the interlude should be used for LP work (i.e., switch from HP to LP). We first consider Problem (1) without the waiting time constraint. We compare an increase in p * with an increase in q * in order to get an insight on the eventual preference for a more frequent use of the interlude or the break for LP work. After some algebra, we obtain

∂E(T ) ∂p * - ∂E(T ) ∂q * = -(a S1 + 1)(n * + 1)(1 -λE(R)) (1 + n * q * + a S1 + q * a S2 ) 2 + a I n * q * (a 2 I -a I a S2 -a S1 a S2 ) + q * a S2 (a 2 I -a I -a S1 ) + a 2 I (1 + a S1 ) (a I + a S1 ) 2 (1 + n * q * + a S1 + q * a S2 )
.

If this difference is positive then increasing the use of the interlude is preferred and vice-versa. To make this difference positive, one should either increase a I , E(R) or decrease a S1 or a S2 . In other words, for treating LP, the interlude is preferred to the break when the service duration is long, the interlude time is long, or the switch times are short.

The service level constraint is imposed next. Figure 7, depicts a case with a high workload in (Figure 7 understood through the following rewriting of the optimization problem at saturation of the service level constraint (i.e., E(W ) = w):

   Maximize E(T ) = E(T I ) + (1 -λE(R)) w -E(W 2 ) - λE(R) 2 (1+cv 2 R ) 2(1-λE(R)) + 1 µ S 2 1+n * +a S 2 n * + 1 q * + 1 q * (aS 1 +q * a S 2 ) subject to E(W ) = w. (9)
In the expression of E(T ), the parameter p * appears in E(T I ) with a positive effect, and in the terms E(W 2 ) and

λE(R) 2 (1+cv 2 R ) 2(1-λE(R))
with a negative one. As the workload increases, the impact of the terms related to the wait increase in the expression of E(T ). So the negative effect of an increase in p * can overcome its positive effect on E(T I ). Thus, in low workload situations, the interlude is a real opportunity to increase the time spent on LP, but under high workload situations it might not be preferred in comparison with spending more time on LP during breaks.

Which duration to extend for more back-office work: interlude or break?

We compare two strategies: increase the service time (more time for LP during the interlude) or increase the busy period (more time for LP during the break) in order to treat more LP? Consider a situation where it is optimal to choose p * = q * = 1. Such a situation may occur with a low arrival rate or a non-restrictive service level constraint.

What is more effective: increasing the LP working time of the server during the break with parameter n * or during the interlude with parameter t * ? Since the nature of n * and t * is different, we consider the variable λt * instead of t * , enabling a comparison with n * . First, observe that

∂E(T ) ∂n * = (a S1 + a S2 )(1 -λE(R)) (n * + 1 + a S1 + a S2 ) 2 , and, ∂E(T ) ∂λt * = a I (a S1 + a S2 ) (a S1 + a I )(n * + 1 + a S1 + a S2 ) - a S1 a I (a S1 + a I ) 2 e -λt * /a S 1 .
Clearly ∂E(T ) ∂n * > 0. When one disregards the waiting time constraint, increasing the time spent on LP between HP therefore cannot be counterproductive. The same cannot be said for the time spent on LP during the interlude;

∂E(T ) ∂λt * < 0 is equivalent to (a I + a S1 )(a S1 + a S2 ) < a S1 (n * + 1 + a S1 + a S2 )e -λt * /a S . ( 10
)
Starting from a situation where t * = 0, Inequality (10) becomes

a I (a S 1 +a S 2 ) a S 1
< n * + 1. Since a I < 1 due to stability reasons then Inequality ( 10) is often met and extending the duration of the service time would not make sense in most cases (except if the workload is very low, the interlude duration is very short or the threshold on the queue length is very low). The manager is then in general more tempted to increase n * rather than t * . This explains why t * = 0 is optimal in most cases. Yet, counterexamples can be found (see Section 8 of the Online Appendix).

Which is the worst switch?

We question here the impact of the switching times by differentiating the switch from HP to LP to the switch from LP to HP. In Table 3, using the results of Theorem 1 and Proposition 4, we give the optimal control parameters and the optimal value for E(T ) for different values of the system parameters. We choose λ = 0.2, 0.35, and, 0.37 in order to reflect low, moderate, and, high workload situations. We also assume that 1

µ S 1 + 1 µ S 2
= 1, such that, the cumulative expected duration of the two switches is kept constant.

In all cases, we observe that the duration of the switch from LP to HP (i.e. decrease of µ S2 ) has a worst effect than the switch from HP to LP (i.e. decrease of µ S1 ). This confirms the observation of Table 2. When the server is in switch from HP to LP, an arriving HP in Queue 1 or in Queue 2 can directly start service. Therefore, HP jobs seems to only be delayed by the switch from LP to HP. This explains why, when µ S2 = ∞, the server should never Table 3: Performance evaluation (µ idle (i.e., p * = q * = 100%). We also observe that the sensitivity to the switching rates increases with the workload.

I = 1, E(X) = 1, E(X 2 ) = 10, 1 µ S 1 + 1 µ S 2 = 1, w = 10) µ S1 µ S2 n * p * q * E(T ) 1 ∞ 3.
In high workload situations, more HPs are present in the system. Therefore, the server can more frequently switch from HP to LP during the interlude or the break. Hence, this increases the sensitivity to the switch parameters.

In fact, the switch from HP to LP even has a beneficial effect on the wait of HPs. The reason is that with a long switch from HP to LP, the server has less chance to start serving LPs before an HP arrives in Queue 1 or in Queue 2. Since HPs can preempt a switch from HP to LP, having a long switch means having a long period of time during which an arriving HP can be served without being delayed. This can be proven using the results of Theorem 1. Consider the expression of the expected wait in Equation ( 6) with t * = 0. The first part, which represents E(W 2 ), can be rewritten as

E(W 2 ) = p * λ a I a S 2 a I +a S 1
. Since a S1 is only in the denominator of this expression, E(W 2 ) is decreasing in a S1 which means that the wait in Queue 2 decreases with the length of the switch from HP to LP. For the same reason, the third and the fourth parts of the expression of E(W ) are also decreasing in a S1 . The second part of

E(W ), λE(R) 2 (1+cv 2 R )
2(1-λE(R)) , can be rewritten as . This leads to

1 λ λ 2 E(X 2 )
∂ λE(R) 2 (1+cv 2 R ) 2(1-λE(R)) ∂a S1 = - 1 λ p * a S2 a I λ 2 E(X 2 ) 2 + (1 -a I -λE(X))(λE(X) + a S2 ) + a I ((a I + a S1 )(1 -λE(X) -a I ) -p * a I a S2 ) 2 .
This expression is negative as 1 -λE(X) -a I > 0 for stability reasons. Therefore, we have proven that E(W )

decreases with the length of the switch from HP to LP. The expected time spent on LPs during the interlude,

E(T I ) = a 3 I (aI+aS 1 )
2 , is clearly decreasing in a S1 . The expected time spent on LPs during the break, E(T B ) =

(n * +1) 1-λE(X)-a I -p * a I a S 2 a I +a S 1 n * + 1 q * + 1 q * (aS 1 +q * a S 2 )
is not always decreasing in a S1 . After deriving the derivative of E(T B ) we show that

E(T B ) is increasing in a S1 if and only if p * a S2 a I (1 + n * q * + 2a S1 + a I + q * a S2 ) > (a I + a S1 ) 2 (1 -λE(X) -a I ).
This condition is complex to analyze but it qualitatively means that the length of the switch from HP to LP can be beneficial for the time spent on LPs during the break when the interlude and the break are highly used for LPs (i.e.

high value of p * , q * and n * ), and when the switch from LP to HP is long. In such cases, having a long switch from HP to LP allows to have shorter interlude duration by not having enough time to initiate LPs during the interlude.

This reduces the expected service time of HPs, E(R), and allows the server to have less HPs present in the system.

Consequently, the breaks can be longer and the time spent on LPs during the breaks can also be longer.

5.4.4 How to deal with more than one interlude?

An important question is how the server should organize her work when multiple interludes are present in the service encounter? Each time LP work is attempted during an interlude, the server will incur the switching time twice.

As shown earlier, this affects system performance both in terms of expected duration and variability of the service process. Intuitively, this would point to a policy of concentrating LP work on fewer interludes. Yet a more myopic policy that considers each interlude independently from another and attempts LP work whenever an interlude is long enough relative to the switching time might also be efficient and may lead to a choice of using more of the interludes for LP work. We explore the performance implications of these two options. A policy of concentration further requires a choice of which interludes to use for LP work. In an environment with a constraint on the expected waiting time of HP, it makes sense intuitively to delay the LP work to later interludes, at which point there are a small number of remaining working phases for HP. To provide rules of thumb for managers addressing these questions, we consider a situation with only two interludes with interlude rates, µ I1 and µ I2 . We optimize the use of the interludes under Policy P. Under this policy, the position of an interlude during service does not influence the optimal decision since the use of the interlude is non state-dependent. In Section 9 of the Online Appendix, to further explore the role of the position of an interlude, using an MDP approach similar to the one developed in Section 4, we characterize more complex properties that the optimal policy for the use of the interludes may have. We show that the optimal policies provide similar insights to those derived under Policy P in this subsection.

Without loss of generality for Policy P, we assume here that µ I2 > µ I1 . So, the second interlude is shorter than the first one. Clearly, there is a preference for using the first interlude. We assume that it is not optimal to extend the interlude duration (t * = 0). The server has the choice between two policies. Either using only the first interlude with control parameter p * a (concentration on one interlude) or a bit of both interludes with control parameters p * b and p * c (spreading of the work between the two interludes). If the two policies achieve the same expected time on LP during service, using the expression of E(T I ), we may write

p * a = p * b + p * c µ I1 (µ S + µ I1 ) µ I2 (µ S + µ I2 ) .
We now compare the expected waiting time in Queue 2 under the two policies by computing the difference

E(W 2,A ) -E(W 2,B
) where E(W 2,A ) is the expected supplementary waiting time when the work is concentrated on one interlude and E(W 2,B ) is the expected supplementary waiting time when the work is spread on the two interludes.

We have

E(W 2,A )-E(W 2,B ) = p * c µ S +µ I 2 µ I 1 µ I 2
-1 < 0. Thus the supplementary waiting time is higher when the work is spread on two interludes. Similarly, we show that the expected service time is also longer when the work is spread on two interludes. We now consider the difference E(S 2 A ) -E(S 2 B ) which represents the difference between the second order moments of the interlude times in the two situations. We have

E(S 2 A ) -E(S 2 B ) = 2p * c µ S (µ S +µ I 2 ) µ I 1 µ I 2 -1 < 0.
Again concentrating the work on one interlude has a better effect in terms of reducing variability, than spreading it over more than one interlude.

The intuitive conclusion here is that if a given quantity of time can be dedicated to LP during the interludes then it is better to concentrate the work on a limited number of interludes without extending any of these. The chosen interludes should be the longest. This avoids having too many switching times.

Concluding remarks

A lot of service front-office work has intervals of random length during and between the treatment of different customers, when the server is not needed. In this paper, we have explored the use of these interludes and breaks to treat back-office tasks. The latter tasks are different in nature from the front-office tasks, and imply switching times as the server alternates between these in their work. Our analysis shows that these switching times are important to model and have a significant effect on the structure of optimal choices regarding when to treat back-office tasks.

The server may prefer to make customers wait while continuing to work on back-office due to long switching times.

Alternatively, the server may prefer to remain idle despite an infinite amount of back-office tasks to process, due to the long switching times otherwise incurred. Optimal policies for use of the interludes and breaks are state-dependent and are controlled by several thresholds. Due to its dependence on random arrivals by customers both pre-process and in-process, the control of the interlude blending decision is more difficult relative to the one during the break.

Furthermore the two interact. In the absence of automation, the optimal policies may be hard to implement by a server. For such cases, simpler non state-dependent policies are proposed. Both type of policies lead to similar insights regarding the drivers to use the interlude times for back-office blending: a low or moderate workload, long interlude times, low sensitivity of customers to waiting (as captured by the waiting service level constraint). These findings suggest that managers need to understand specific process features well, before determining ideal blending approaches. It is shown that blending of front-back office work is not just meaningful during breaks between customers but also in interludes within service, despite the switching times that need to be incurred in doing so. In the presence of multiple interludes, the rule of thumb developed is to make use of the longer and later interludes in a service

encounter.

An alternative to the front-back office work blending to make use of server idle times, is working on several customers (front-office tasks) simultaneously as in case-manager systems. Studied in different contexts, earlier work has shown that limiting the caseload in such systems may be preferred due to quality or efficiency related reasons.

The analysis herein shows the effect of an increasing caseload on in-process waits. When coupled with the observation of diminishing benefits to increasing the caseload, this suggests to limit caseloads in front-back office work blending settings to low numbers.

In future research, it would be interesting but challenging to extend the analysis to cases with more than two tasks done by alternation. Different assumptions regarding switching times may be needed to analyze settings where the multitasking is done between different types of customer tasks that are all front-office (requiring customer interaction) instead of a front-office versus back-office task. Another challenging extension is to investigate other objectives for front-office tasks like wait percentiles or the average excess wait. Choosing other objectives would lead one to reconsider fundamental assumptions like the priority for front-office tasks at their service completion. New technologies allow service systems to keep track of past performance. So, we could also envision to rethink the priority rules from the second queue based on the past performance in the first queue. Going one step beyond the current framework where the length of the interlude is modeled as an exogenous parameter (exponential with given rate), one can consider this parameter to be the outcome of a coproductive service design [START_REF] Roels | Optimal design of coproductive services: Interaction and work allocation[END_REF]. This is relevant for settings where the interlude is a self-service task. Endogenous choice of the interlude duration would correspond to the determination of the extent of self-service in a service encounter. This would enable creating settings where the interlude length is controlled via service design.

Online Appendix to "Front-office multitasking between service encounters and back-office tasks" This is an online appendix to the main paper, with the same title.

1 Procedure to set the appropriate value for γ in Section 4

We further explain the procedure to obtain the value of γ in order to achieve E(W ) = w. From the numerical study, the computed policy from Equation (2) in the main paper can be formalized as follows:

• Switch from LP to HP. There exists a threshold function z = u(x, y), such that if the server is working on LP in state (x, y, z) then it is optimal to switch from LP to HP if and only if z ≥ u(x, y).

• Switch from HP to LP. There exists a threshold function z = ũ(x), such that the server initiates a switch from HP to LP if and only if either both queues are empty and the number of HPs with the non-focal server is strictly below this threshold; z < ũ(0) or if the number of HPs with the non-focal server is equal to c and c < ũ(x).

Here, we show a case where the priority is given to Queue 2. The same approach can be adjusted to any other priority rule.

The algorithm for the computation of the Lagrange multiplier is as follows:

Initialization. Set γ 0 = 0, γ 1 = γ > 0 and > 0. For γ 0 = 0, the thresholds are infinite and E(W ) = ∞ (i.e., the server only treats LP). Next, go to Step 1 with m = 1.

Step 1. At iteration m, determine the threshold functions of the optimal policy, u γm (x, y) and ũγm (x, y), using Equation (2) of the main paper with the value γ m . Next, go to Step 2.

Step 2. Using the obtained threshold function, u γm (x, y) and ũγm (x, y), recalculate the value function by removing the sign -1 which counts for the time spent on LP, count a cost of 1 per customer and per waiting time unit and replace the minimizing operators in Equation (2) as follows:

V k+1 (H, v) = x + y λ + λV k (H, v + e 1 ) + zµ I V k (H, v -e 3 + e 2 ) (1) + 1 x>0,y=0,z<c µ 1 V k (H, v -e 1 + e 3 ) + 1 y>0 µ 2 V k (H, v -e 2 ) + 1 y=0,(x=0∪z=c) µ S 2 (1 z<ũγ m (x,0) V k (L, v) + 1 z≥ũγ m (x,0) V k (H, v)) + (1 -λ -zµ I -µ 1 1 x>0,y=0,z<c -µ 2 1 y>0 -µ S 2 1 y=0,(x=0∪z=c) )V k (H, v), V k+1 (L, v) = x + y λ + λV k (L, v + e 1 ) + zµ I V k (L, v -e 3 + e 2 ) + µ S 1 (1 z<uγ m (x,y) V k (L, v) + 1 z≥uγ m (x,y) V k (H, v)) + (1 -λ -zµ I -µ S 1 )V k (L, v).
As k tends to infinity, one can compute E(W ). If ũγm (0) = 0, then the server never treats LP. In this case, E(W ) is equal to the limit as k tends to infinity of λ(V k (H, e 1 ) -V k (H, 0)). Note that if this limit is strictly above ω, then the optimization problem cannot be solved. If ũγm (0) > 0, then E(W ) is equal to the limit as k tends to infinity of λ(V k (L, e 1 ) -V k (L, 0)).

• Case 1. If E(W ) > ω for γ m . -Case 1.1. If γ m-1 < γ m , then choose γ m+1 = γ m + γm-γ m-1
2 and go to Step 1.

-Case 1.2. If γ m-1 > γ m and γ m-1 -γ m > , then choose γ m+1 = γm+γ m-1
2 and go to Step 1.

-Case 1.3. If γ m-1 > γ m and γ m-1 -γ m ≤ , then go to Step 3. • Case 2. If E(W ) < ω for γ m .
-Case 2.1. If γ m-1 < γ m and γ m -γ m-1 > , then choose γ m+1 = γm+γ m-1 2 and go to Step 1.

-Case 2.2. If γ m-1 < γ m and γ m -γ m-1 ≤ , then go to Step 3.

-Case 2.3. If γ m-1 > γ m , then choose γ m+1 = γ m -γ m-1 -γm 2
and go to Step 1.

Step 3. For a given value of , we have found two different threshold policies for γ m and γ m-1 such that E(W ) > ω for one policy and E(W ) < ω for the other one. In order to achieve E(W ) = w, we choose to randomize between these two policies. For instance, if it is optimal to switch from LP to HP in state (x, y, z) with γ m and if it is not optimal to initiate this switch with γ m-1 , then we apply a policy such that with probability p x,y,z a switch is initiated from LP to HP and with probability 1 -p x,y,z no switch is made.

Proof of Proposition 1

The switch from HP to LP may occur only when the system is without HPs, just after the service completion of an HP. The only possible policy when only one state is involved is a policy that randomizes between the actions of initiating and not initiating a switch (i.e., it corresponds to a Bernoulli policy with parameter q * ).

expression to the one proportional with µ 1 1 x=0 at the first line, we get (µ

1 -µ S 2 )(V k (H, 1) -V k (H, 0)) + µ S 2 (V k (L, 1) -V k (H, 0). Since V k satisfies Relation (2)
, the latter expression is positive. Otherwise if

V * k (H, 0) = V k (H, 0
), then Relation (5) proves that the last line is positive. Therefore, V k+1 satisfies Relation (5) which finishes the proof of the proposition. 2

3 Proof of Proposition 2

Proof of the first part:

We want to show the threshold structure of the optimal policy for the switch from LP to HP during the interlude (first part of Proposition 2). First, let us recall the state definition. A state of the system is defined by (Ω, v), where Ω is the state of the server; and v = (x, y, z), for x, y, z ≥ 0, where x, y, and z are the number of HPs in Queue 1 and in the first service phase, in Queue 2 and in the second service phase, and with the non-focal server, respectively. In Proposition 2, we assume that caseload= 1, this means that we either have y = 0 and z = 0, y = 1 and z = 0, or y = 0 and z = 1. The server can be working on HP, idle and waiting for an HP, or be in switch from HP to LP. In these cases, the state of the server is denoted by H and the server treats HP as long as an available HP is present in Queue 1 or in Queue 2. Otherwise, the server can be dedicated to LP or in switch from LP to HP. In these cases, the state of the server is denoted by L and the server is not allowed to treat HP even if there are HPs in Queue 1 or in Queue 2.

Consider a state where the server is treating LPs and an HP is either with the non-focal server (z = 1) or in Queue 2 (y = 1) and x HPs are in the queue (x ≥ 0). This situation corresponds to an interlude where the server is working on LPs. The system state is then (L, v), where v = x e 1 + e 3 or v = x e 1 + e 2 , for x ≥ 0. Under a threshold policy based on the number of HPs in Queue 1, if it is optimal not to operate a switch in state v then it is also not optimal to operate a switch in state v + e 1 . The opposite is also true (i.e., if it is optimal to operate a switch in state v + e 1 , then it is also optimal to operate a switch in state v). Therefore for every k ≥ 0, if V k (H, v + e 1 ) + 1 -V k (L, v + e 1 ) ≥ 0 (i.e., it is optimal to switch in state v + e 1 ), then we should have

V k (H, v) + 1 -V k (L, v) ≥ 0 (i.e., it is optimal to switch in state v), and if V k (H, v) + 1 -V k (L, v) ≤ 0 (i.e.
, it is optimal not to switch in state v), then we should have

V k (H, v + e 1 ) + 1 -V k (L, v + e 1 )
≤ 0, (i.e., it is optimal not to switch in state v + e 1 ). A sufficient condition for this is

V k (L, v + e 1 ) + V k (H, v) -V k (H, v + e 1 ) -V k (L, v) ≥ 0, (6)
for k ≥ 0, v = x e 1 + e 3 or v = x e 1 + e 2 , and x ≥ 0.

We want to show that Relation (6) holds for every k ≥ 0 using an induction step. Clearly, since 6) holds for k = 0. Assume now that Relation (6) holds for a given k ≥ 0. We want to show that the same property holds for V k+1 .

V 0 (L, v) = V 0 (H, v) = 0 for v ∈ N 3 , Relation (
We consider the case v = x e 1 + e 3 , for x ≥ 0 (the case v = x e 1 + e 2 can be shown similarly). By substituting Equation (2) (Bellman equation) of the main paper into Relation (6), one may write

V k+1 (L, v + e 1 ) + V k+1 (H, v) -V k+1 (H, v + e 1 ) -V k+1 (L, v) (7) = λ(V k (L, v + 2 e 1 ) + V k (H, v + e 1 ) -V k (H, v + 2 e 1 ) -V k (L, v + e 1 )) (7a) + µ I (V k (L, v + e 1 -e 3 + e 2 ) + V k (H, v -e 3 + e 2 ) -V k (H, v + e 1 -e 3 + e 2 ) -V k (L, v -e 3 + e 2 )) (7b) + µ S 1 (V * k (L, v + e 1 ) + V k (H, v) -V k (H, v + e 1 ) -V * k (L, v)) (7c) + µ S 2 (V k (L, v + e 1 ) + V * k (H, v) -V * k (H, v + e 1 ) -V k (L, v)) (7d) + (1 -λ -µ I -µ S 1 -µ S 2 )(V k (L, v + e 1 ) + V k (H, v) -V k (H, v + e 1 ) -V k (L, v)). (7e)
In the right hand side of Equation ( 7), each line is positive. Lines (7a), ( 7b) and (7e) are positive since V k satisfies Relation (6). Let us now prove that Lines (7c) and ( 7d) are also positive. The approach is identical for both lines. Consider Line (7c). Since

V * k (L, v) = min(V k (L, v), V k (H, v) + 1) ≤ V k (L, v) and V * k (L, v) = min(V k (L, v), V k (H, v) + 1) ≤ V k (H, v) + 1, we have V k (H, v + e 1 ) + V * k (L, v) ≤ V k (H, v + e 1 ) + V k (L, v) (8) V k (H, v + e 1 ) + V * k (L, v) ≤ V k (H, v + e 1 ) + V k (H, v) + 1. (9) If V * k (L, v + e 1 ) = V k (L, v + e 1 )
, then Inequality (8) combined with the induction hypothesis for

V k proves Relation (6) for V k+1 . If V * k (L, v + e 1 ) = V k (H, v + e 1
) + 1, then Inequality (9) directly proves Relation (6) for V k+1 . Using the same inequalities, we show that Line (7d) is also positive. This proves the threshold structure of the optimal policy during the interlude. This first step of the proof shows the existence of two thresholds; u I 1 and u I 2 which define the policy for the switch from LP to HP during the interlude.

We now prove that u I 1 ≥ u I 2 . This inequality means that if it is optimal to operate a switch from LP to HP in state v + e 3 , then it is also optimal to operate the same switch in state v + e 2 , for v = x e 1 , with x ≥ 0. Again, we use an induction step to prove this result. The idea is to show that for every k ≥ 0, if

V k (L, v + e 3 ) -V k (H, v + e 3 ) -1 ≥ 0, then V k (L, v + e 2 ) -V k (H, v + e 2 ) -1 ≥ 0. A sufficient condition for this is V k (L, v + e 2 ) + V k (H, v + e 3 ) -V k (H, v + e 2 ) -V k (L, v + e 3 ) ≥ 0. ( 10
)
Since V 0 ( v) = 0 for v ∈ N 3 , Relation (10) holds for k = 0. Assume that Relation (10) holds for a given k ≥ 0. For v = x e 1 , by substituting Equation (2) (Bellman equation) of the main paper into Relation (10), one may write

V k+1 (L, v + e 2 ) + V k+1 (H, v + e 3 ) -V k+1 (H, v + e 2 ) -V k+1 (L, v + e 3 ) (11) = λ(V k (L, v + e 2 + e 1 ) + V k (H, v + e 3 + e 1 ) -V k (H, v + e 2 + e 1 ) -V k (L, v + e 3 + e 1 )) (11a) + µ I (V k (L, v + e 2 ) + V k (H, v + e 2 ) -V k (H, v + e 2 ) -V k (L, v + e 2 )) (11b) + µ S 1 (V * k (L, v + e 2 ) + V k (H, v + e 3 ) -V k (H, v + e 2 ) -V * k (L, v + e 3 )) (11c) + µ S 2 (V k (L, v + e 2 ) + V * k (H, v + e 3 ) -V * k (H, v + e 2 ) -V k (L, v + e 3 )) (11d) + (1 -λ -µ I -µ S 1 -µ S 2 )(V k (L, v + e 2 ) + V k (H, v + e 3 ) -V k (H, v + e 2 ) -V k (L, v + e 3 )). (11e)
In the right hand side of Equation ( 11) each line is positive. Lines (11a) and (11e) are positive since V k satisfies Relation (10). Line (11b) is equal to zero. Let us now prove that Line (11c) is positive. Since

V * k (L, v + e 3 ) ≤ V k (L, v + e 3 ) and V * k (L, v + e 3 ) ≤ V k (H, v + e 3 ) + 1, we have V k (H, v + e 2 ) + V * k (L, v + e 3 ) ≤ V k (H, v + e 2 ) + V k (L, v + e 3 ) (12) V k (H, v + e 2 ) + V * k (L, v + e 3 ) ≤ V k (H, v + e 2 ) + V k (H, v + e 3 ) + 1. ( 13
) If V * k (L, v + e 2 ) = V k (L, v + e 2 ), then Inequality (12) proves the result. If V * k (L, v + e 2 ) = V k (H, v + e 2 )
+ 1, then Inequality (13) proves the result. With the same approach, one can show that Line (11d) is also positive. This proves that u I 1 ≥ u I 2 .

Proof of the second part:

Consider a situation where the server has just completed the first working phase of an HP (z = 1) and x HPs are in Queue 1 (x ≥ 0). The system state is then (H, v), where v = x e 1 + e 3 , for x ≥ 0. We want to prove that the optimal policy to initiate LPs is of threshold type and depends on the number of HPs in the queue. In other words, we want to show that if it is optimal to initiate LPs when x+1 HPs are in the queue then it is also optimal to initiate LPs when x HPs are in the queue, x ≥ 0. Therefore, we want to show that for every k ≥ 0, if

V k (H, v + e 1 ) -V k (L, v + e 1 ) ≥ 0 then V k (H, v) -V k (L, v) ≥ 0, where v = x e 1 + e 3 and x ≥ 0. A sufficient condition for this is V k (L, v + e 1 ) + V k (H, v) -V k (H, v + e 1 ) -V k (L, v) ≥ 0, which
corresponds to Relation (6), already proven above. This last step of the proof shows the existence of a threshold; ũI which defines the policy for the switch from HP to LP during the interlude. The proof of the proposition is completed.

2

4 Proof of Proposition 3

Proof. With a priority for Queue 1, the value function of Section 4 can be rewritten as follows: v), and,

V k+1 (H, v) = γ(x + y) λ + λV k (H, v + e 1 ) + zµ I V k (H, v -e 3 + e 2 ) (14) + 1 x>0,y+z<c µ 1 V k (H, v -e 1 + e 3 ) + 1 y>0,(x=0∪z+y=c) µ 2 V k (H, v -e 2 ) + 1 y=0,(x=0∪z=c) µ S 2 V * k (H, v) + (1 -λ -zµ I -µ 1 1 x>0,y+z<c -µ 2 1 y>0,(x=0∪z+y=c) -µ S 2 1 y=0,(x=0∪z=c) )V k (H,
V k+1 (L, v) = γ(x + y) λ -1 + λV k (L, v + e 1 ) + zµ I V k (L, v -e 3 + e 2 ) + µ S 1 V * k (L, v) + (1 -λ -zµ I -µ S 1 )V k (L, v),
where 1 x∈A is the indicator function of a given subset A, and

V * k (L, v) = min(V k (H, v) + 1, V k (L, v)) (i.
e., switching decision from LP to HP), and

V * k (H, v) = min(V k (H, v), V k (L, v)) (i.e.
, switching decision from HP to LP), if v = z e 3 for z ≥ 0 or v = x e 1 + c e 3 , for x ≥ 0 and, V * k (H, v) = V k (H, v), otherwise. Let us first consider the first part of the proposition where we want to find the optimal policy which minimizes γE(W ) -E(T ). As mentioned in Section 3, the service discipline for HPs is irrelevant since we consider the expected time spent by these customers in the system. However, to show the propagation of the wanted monotonicity properties which describe the the optimal policy, the priority for Queue 1 is required. Using µ = µ 1 = µ 2 = µ S 2 , we can reformulate the value function as follows:

V k+1 (H, v) = γ(x + y) λ + λV k (H, v + e 1 ) + zµ I V k (H, v -e 3 + e 2 ) ( 15
) + µ[1 x>0 V k (H, v -e 1 + e 3 ) + 1 x=0,y>0 V k (H, v -e 2 ) + 1 x=y=0 V * k (H, v)] + (1 -λ -zµ I -µ)V k (H, v), V k+1 (L, v) = γ(x + y) λ -1 + λV k (L, v + e 1 ) + zµ I V k (L, v -e 3 + e 2 ) + µ S 1 V * k (L, v) + (1 -λ -zµ I -µ S 1 )V k (L, v), where V * k (L, v) = min(V k (H, v), V k (L, v)) (i.e.
, switching decision from LP to HP), and

V * k (H, v) = min(V k (H, v), V k (L, v)) (i.e., switching decision from HP to LP), if v = z e 3 for z ≥ 0 and V * k (H, v) = V k (H, v), otherwise.
For the proof simplicity, the time in switch from LP to HP is rewarded as if it was a time spent on LPs. This change does not modify the form of the optimal policy and the required monotonicity properties that have to be shown.

Different operators are involved for the transition from V k to V k+1 . We consider the cost operator,

C(f (Ω, v)) = γ(x + y) λ -1 Ω=L ,
the arrival operator in Queue 1,

A(f (Ω, v)) = f (Ω, v + e 1 ),
the arrival operator in Queue 2,

B(f (Ω, v)) = zf (Ω, v + e 2 -e 3 ) + (c -z)f (Ω, v),
for Ω = L, H, and z ≤ c and the departure operator defined by

D(f (H, v)) = µ[1 x>0 f (H, v -e 1 + e 3 ) + 1 x=0,y>0 f (H, v -e 2 ) + 1 x=y=0 f * (H, v)] + (1 -λ -µ -cµ I )f (H, v), and
D(f (L, v)) = µ S 1 f * (L, v) + (1 -λ -µ S 1 -cµ I )f (L, v).
We hence may write

V k+1 (Ω, v) = C(V k (Ω, v)) + λA(V k (Ω, v)) + µ I B(V k (Ω, v)) + D(V k (Ω, v)),
for k ≥ 0. It then suffices to show that the specified relations propagate via the operators A, B, C, and D to show the propagation of these relations from V k to V k+1 .

We define the class of functions F from {H, L} × N 3 to R as follows: f ∈ F if we have for v = (x, y, z) ∈ N 3 : Fondamental Relations:

f (L, v + e 3 ) + f (H, v) ≥ f (H, v + e 3 ) + f (L, v)
, (Switch from HP to LP and from LP to HP), ( 16)

f (L, v + e 2 ) + f (H, v) ≥ f (H, v + e 2 ) + f (L, v), (Switch from LP to HP). ( 17
)
First order Relations (Ω = L, H) :

f (Ω, v + e i ) ≥ f (Ω, v), for i ∈ {2, 3} (18)
Second order Relations:

f (H, v + e 1 + e 2 ) + f (H, v + e 3 ) ≥ f (H, v + e 1 ) + f (H, v + e 2 + e 3 ), (19)
f (H, v + e 1 + e 2 ) + f (H, v + e 2 ) ≥ f (H, v + e 1 ) + f (H, v + 2 e 2 ), (20)
f (H, v + 2 e 2 ) + f (H, v) ≥ 2f (H, v + e 2 ), (21)
f (H, v + e 1 + e 3 ) + f (H, v + e 3 ) ≥ f (H, v + e 1 ) + f (H, v + 2 e 3 ), (22)
f (H, v + e 1 + e 3 ) + f (H, v + e 2 ) ≥ f (H, v + e 1 ) + f (H, v + e 2 + e 3 ), (23)
f (H, v + e 2 + e 3 ) + f (H, v) ≥ f (H, v + e 2 ) + f (H, v + e 3 ), (24)
f (H, v + 2 e 3 ) + f (H, v) ≥ 2f (H, v + e 3 ). (25)
Relations ( 16) and ( 17) define the threshold structure of the optimal policy. Relation (19) states that the function f is increasing in the variables y and z.

The other relations ( 19)-( 25) are second order relations which ensure the propagation of Relations ( 16) and ( 17) via the operators A, B, C, and D. Note that for the second order Relations, the letter H can be parlty replaced by L for some terms. For instance, by summing up Relation (17) where v is replaced by v + e 1 and Relation ( 19), we get

f (L, v + e 1 + e 2 ) + f (H, v + e 3 ) ≥ f (L, v + e 1 ) + f (H, v + e 2 + e 3 ).
In what follows, we show the stability of F via the operators A, B, C, and D. These relations are obviously stable via the operators A and C.

Let us first consider the operator B. When e 3 is not involved in a relation, then the transition rate which corresponds to an arrival in Queue 2 is zµ I for all terms in the relation. Since this rate is constant, these relations automatically propagate via B. It is the case for Relations ( 17), ( 20) and ( 21). For the other relations, each term e 3 is changed into e 2 via the operator B. As an illustration, consider Relation (16).

We have

B(f (L, v + e 3 )) + B(f (H, v)) -B(f (H, v + e 3 )) -B(f (L, v)) = z(f (L, v + e 2 ) + f (H, v + e 2 -e 3 ) -f (H, v + e 2 ) -f (L, v + e 2 -e 3 )) + f (L, v + e 2 ) -f (H, v + e 2 ) + (c -(z + 1))(f (L, v + e 3 ) + f (H, v) -f (H, v + e 3 ) -f (L, v)) + f (H, v) -f (L, v) ≥ f (L, v + e 2 ) + f (H, v) -f (H, v + e 2 ) -f (L, v).
Hence Relation (17) for f proves Relation ( 16) for B(f ).

When the term 2 e 3 is involved, this one is changed into e 2 + e 3 and sometimes two relations should be involved to prove the propagation. As a second illustration, consider Relation (22). We have

B(f (H, v + e 1 + e 3 )) + B(f (H, v + e 3 )) -B(f (H, v + e 1 )) -B(f (H, v + 2 e 3 )) = z(f (H, v + e 1 + e 2 ) + f (H, v + e 2 ) -f (H, v + e 1 + e 2 -e 3 ) -f (H, v + e 2 + e 3 )) + f (H, v + e 1 + e 2 ) + f (H, v + e 2 ) -2f (H, v + e 2 + e 3 ) + (c -(z + 2))(f (H, v + e 1 + e 3 ) + f (H, v + e 3 ) -f (H, v + e 1 ) -f (H, v + 2 e 3 )) + f (H, v + e 1 + e 3 ) + f (H, v + e 3 ) -2f (H, v + e 1 ) ≥ f (H, v + e 1 + e 3 ) + f (H, v + e 2 ) -f (H, v + e 2 + e 3 ) -f (H, v + e 1 ) f (H, v + e 3 ) + f (H, v + e 1 + e 2 ) -f (H, v + e 2 + e 3 ) -f (H, v + e 1 ).
Hence, Relations ( 19) and ( 23) for f prove Relation (22) for B(f ). Exactly the same approach holds the other relations which involve 2 e 3 .

Consider now the departure operator D. Let us start with Relation ( 16). One may write

D(f (L, v + e 3 )) + D(f (H, v)) -D(f (H, v + e 3 )) -D(f (L, v)) = µ S 1 (f * (L, v + e 3 ) -f * (L, v)) + µ[1 x>0 (f (H, v -e 1 + e 3 ) -f (H, v -e 1 + 2 e 3 )) + 1 x=0,y>0 (f (H, v -e 2 ) -f (H, v + e 3 -e 2 )) + 1 x=y=0 (f * (H, v) -f * (H, v + e 3 ))] + (1 -λ -cµ I -µ S 1 -µ)(f (L, v + e 3 ) + f (H, v) -f (H, v + e 3 ) -f (L, v)) + µ(f (L, v + e 3 ) -f (L, v)) -µ S (f (H, v + e 3 ) -f (H, v)) ≥ µ S 1 (f * (L, v + e 3 ) + f (H, v) -f (H, v + e 3 ) -f * (L, v)) + µ[1 x>0 (f (L, v + e 3 ) + f (H, v -e 1 + e 3 ) -f (H, v -e 1 + 2 e 3 ) -f (L, v)) + 1 x=0,y>0 (f (L, v + e 3 ) + f (H, v -e 2 ) -f (H, v + e 3 -e 2 ) -f (L, v)) + 1 x=y=0 (f (L, v + e 3 ) + f * (H, v) -f * (H, v + e 3 ) -f (L, v))].
In what follows, we prove that each line after the second inequality sign is positive. Consider the term proportional with µ S 1 after the inequality sign. We have Consider now the last line. We have

f (H, v + e 3 ) + f * (L, v) ≤ f (H, v + e 3 ) + f (H, v), and, (26)
f (H, v + e 3 ) + f * (L, v) ≤ f (H, v + e 3 ) + f (L, v). (27)
f * (H, v + e 3 ) + f (L, v) ≤ f (L, v + e 3 ) + f (L, v), and, (28)
f * (H, v + e 3 ) + f (L, v) ≤ f (H, v + e 3 ) + f (L, v). ( 29
) If f * (H, v) = f (L, v) then Inequality (28) proves the result. Otherwise, if f * (H, v) = f (H, v) then Relation
(16) combined with Inequality (29) proves the result. With the same approach, we show that Relations (18), ( 19) and ( 21) for f prove Relation (17) for D(f ).

Let us now consider the first order Relation (19). We have for Ω = L, H, and i ∈ {2, 3}

D(f (Ω, v + e i )) -D(f (Ω, v)) = 1 Ω=H µ[1 x>0 (f (H, v -e 1 + e 3 + e i ) -f (H, v -e 1 + e 3 )) + 1 x=0,y>0 (f (H, v -e 2 + e i ) -f (H, v -e 2 )) + 1 x=y=0,i=2 (f (H, v) -f * (H, v)) + 1 x=y=0,i=3 (f * (H, v + e 3 ) -f * (H, v)) + 1 Ω=L µ S (f * (L, v + e i ) -f * (L, v))] + (1 -λ -cµ I -1 Ω=H µ -1 Ω=L µ S )(f (Ω, v + e i ) -f (Ω, v)).
The first two lines after the equality sign are clearly positive due to Relation (19). The third line is clearly , v). For the fourth line, if f * (H, v+ e 3 ) = f (H, v+ e 3 ) then using f * (H, v) ≤ f (H, v), we show that this line is positive. If f * (H, v + e 3 ) = f (L, v + e 3 ) then using

positive since f * (H, v) = min(f (H, v), f (L, v)) ≤ f (H
f * (H, v) ≤ f (L, v)
, we also show that this line is positive. With the same approach, we show that the firth line is positive and clearly the last one is also positive.

Consider now the second order Relation (20). We have

D(f (H, v + e 1 + e 2 )) + D(f (H, v + e 3 )) -D(f (H, v + e 1 )) -D(f (H, v + e 2 + e 3 )) = µ[f (H, v + e 3 + e 2 ) + 1 x>0 f (H, v -e 1 + 2 e 3 ) + 1 x=0,y>0 f (H, v -e 2 + e 3 ) + 1 x=y=0 f * (H, v + e 3 ) -f (H, v + e 3 ) -1 x>0 f (H, v + e 2 + 2 e 3 -e 1 ) -1 x=0,y>0 f (H, v + e 3 ) -1 x=y=0 f * (H, v + e 3 )] + (1 -λ -cµ I -µ)(f (H, v + e 1 + e 2 ) + f (H, v + e 3 ) -f (H, v + e 1 ) -f (H, v + e 2 + e 3 ).
For the case x > 0, Relation (20) for f proves Relation (20) for D(f ). If x = 0 and y > 0, then Relation (25) for f proves Relation (20) for D(f ). Finally, if x = y = 0, Relation (18) for i = 2 proves Relation (22)

for D(f ).

All the other relations can be shown in a similar fashion. In Figure 1 under the dashed line, we explain the connections between the necessary relations for the induction from f to B(f ) and from f to D(f ). We

write R i B -→ R j or R i D -→ R j to state that Relation R j for f is required to show Relation R i for B(f )
or D(f ), respectively. We simplify the notations by writing (0

) instead of f (H, v), (0) L instead of f (L, v), (e i ) instead of f (H, v + e i ), (e i ) L instead of f (L, v + e i )
and (e i + e j ) instead of f (H, v + e i + e j ), for i, j ∈ {1, 2, 3}. Above the dashed line, we include the relations which prove the threshold structure of the optimal policy when the expected waiting time in Queue 1 is included instead of the overall waiting time in the system. The proof is finished. Policy P is not optimal due to the non-state dependent decisions taken during the interlude. In Figure 2, we illustrate the difference in performance that can be observed between Policy P and the optimal policy computed using the MDP approach developed in Section 4 in a context with one interlude, caseload= 1, and exponential working phases. We illustrate different cases of long/short switching/interlude times.

2 ሺ݁ ଷ ሻ ሺ0ሻ ሺ݁ ଷ ሻ ሺ0ሻ ሺ݁ ଶ ሻ ሺ0ሻ ሺ݁ ଶ ሻ ሺ0ሻ ሺ݁ ଵ ݁ ଷ ሻ ሺ݁ ଷ ሻ ሺ݁ ଵ ሻ ሺ2݁ ଷ ሻ ሺ݁ ଶ ݁ ଷ ሻ ሺ0ሻ ሺ݁ ଶ ሻ ሺ݁ ଷ ሻ ሺ2݁ ଶ ሻ ሺ0ሻ 2ሺ݁ ଶ ሻ ሺ݁ ଶ ሻ ሺ0ሻ ሺ݁ ଵ ݁ ଷ ሻ ሺ݁ ଶ ሻ ሺ݁ ଵ ሻ ሺ݁ ଶ ݁ ଷ ሻ ሺ݁ ଵ ݁ ଶ ሻ ሺ݁ ଷ ሻ ሺ݁ ଵ ሻ ሺ݁ ଶ ݁ ଷ ሻ ሺ2݁ ଷ ሻ ሺ0ሻ 2ሺ݁ ଷ ሻ ሺ݁ ଵ ݁ ଶ ሻ ሺ݁ ଶ ሻ ሺ݁ ଵ ሻ ሺ2݁ ଶ ሻ ሺ݁ ଵ ሻ ሺ0ሻ ሺ݁ ଵ ሻ ሺ0ሻ ሺ2݁ ଵ ሻ ሺ݁ ଷ ሻ ሺ݁ ଵ ሻ ሺ݁ ଵ ݁ ଷ ሻ ሺ݁ ଵ ݁ ଶ ሻ ሺ0ሻ ሺ݁ ଶ ሻ ሺ݁ ଶ ݁ ଷ ሻ ሺ݁ ଵ ሻ ሺ݁ ଷ ሻ ሺ݁ ଶ ሻ ሺ2݁ ଵ ሻ ሺ݁ ଶ ሻ ሺ݁ ଵ ሻ ሺ݁ ଵ ݁ ଶ ሻ ሺ݁ ଵ ݁ ଷ ሻ ሺ0ሻ ሺ݁ ଷ ሻ ሺ݁ ଶ ݁ ଷ ሻ ሺ݁ ଶ 2݁ ଷ ሻ ሺ0ሻ ሺ݁ ଷ ሻ ሺ݁ ଶ ݁ ଷ ሻ ሺ݁ ଷ 2݁ ଶ ሻ ሺ0ሻ ሺ݁ ଶ ሻ ሺ݁ ଶ ݁ ଷ ሻ ሺ3݁ ଶ ሻ ሺ0ሻ ሺ݁ ଶ ሻ ሺ2݁ ଶ ሻ ሺ݁ ଷ 2݁ ଶ ሻ ሺ0ሻ ሺ݁ ଷ ሻ ሺ2݁ ଶ ሻ
These illustrations together with an extensive numerical study, reveal that Policy P performs well for very high or low arrival rates, a short interlude and long switching times. These observations can be explained from the analysis of Section 5. With a short interlude the optimal decision is not to use the interlude in most cases. Hence, the difference between the optimal policy and Policy P in Figures 2(c We want to derive the performance measures (E(T ) and E(W )) of the system under Policy P. Different methodologies corresponding to different states of the system need to be employed to derive the performance measures. The different parts of the analysis are described as follows:

1. Part 1: Markov chain analysis.

State of the

The server is working on LP, is in switch during a break or is idle.

In this case, the number of HPs in the system can be used as a state definition. Therefore, a standard Markov chain approach can be employed to determine the queue length distribution.

2. Part 2: Analysis based on the remaining service time of the HP in service.

State of the system:

The service of an HP has been initiated but hasn't reached completion.

With generally distributed working phases and an interlude duration which may be used to treat LPs, a standard Markov chain analysis does not allow us to determine the performance measures. In particular, the remaining service time duration is required to define the system state. Under Policy P the service of LPs during the interlude is not state-dependent. Therefore, we can consider the overall duration of the service time (including the interlude) starting from the initiation of the first working phase and ending at the completion of the last working phase. For simplicity, we call this duration the "service time". The random variable defining the service time is generally distributed and is independent of the system state. Hence, when the server is working on HPs, we can study a

^Ğƌ|Ğƌ ǁŽƌŬŝŶŐ ŽŶ >W ߣ ߣ ߣ ߣ ߣ ߣ ߣ ߣ ߣ ߣ ߣ ߣ ሺ1 െ ݍ * ሻµ µ µ µ µ µ ݍ * µ ߣ ߣ µ ߣ µ ௌ మ µ ௌ మ µ ௌ భ 0 0, ݏ 0,0 1 2 ݊ * ݊ * ݊ * 1 ݊ * 1 ݊ * 2 ݊ * 2 1 2 ^Ğƌ|Ğƌ ǁŽƌŬŝŶŐ ŽŶ ,W ^ǁŝƚĐŚ

State of the system:

The server is in an interlude.

In the last part of the analysis, we study the use of the interlude under Policy P in order to evaluate the in-service wait and the time spent on LPs during the interlude. For this purpose, we analyze the random variables defining the switching times, the interlude duration and the wait in Queue 2. Note that the analysis for Part 3 is independent from the analysis for Parts 1 and 2.

In order to visualize the system dynamic, we give in Figure 3 the Markov chain of the system for the case where the service of an HP follows an exponential service time distribution with parameter µ.

Analysis for Part 1

We denote by φ n the stationary probability of having n customers in the system when the server is busy with LP, for 0 ≤ n ≤ n * or in switch from LP to HP for n > n * . One may write λφ n = (λ + µ S 2 )φ n+1 for n ≥ n * . This leads to

φ n = φ n * λ λ + µ S 2 n-n * , for n ≥ n * . Moreover, since φ n = φ n+1 for 0 ≤ n ≤ n * , we have φ n = φ 0 λ λ + µ S 2 n-n * ,
for n ≥ n * . Therefore, for Part 1, the probabilities φ n for n ≥ 0 can all be expressed as a function of φ 0 .

The probability φ 0 will be used to derive the stationary probabilities in Part 2.

Analysis of Part 2

As mentioned above, we consider here a generally distributed service time distribution for the overall service of an HP (time between service initiation and service completion). We assume that the overall time spent for the service of an HP follows a general distribution with probability density g(.) and we denote by G(.) the Laplace-Stieltjes Transform (LST) of the service time; G(s) = ∞ x=0 g(x)e -sx dx. At a given instant t, when the server is busy with an HP, a state of the system is defined by the vector (n(t), r(t)), where n(t) is the number of HPs in the system (n(t) ∈ N) and r(t) is the remaining service time for the HP in service (r(t) ∈ R + ). At an arbitrary instant, a single arrival occurs within δt time units with probability λδt + o(δt), two or more arrivals occur with probability o(δt) and the probability of no arrivals is 1 -λδt + o(δt). The vector (n(t), r(t)) is therefore a Markov process since it completely summarizes all past history relevant to the future system development.

We propose to study the stationary distribution of this Markovian process. We proceed as follows:

a We start by determining the flow equations of the system.

b Next, we establish the relations governing the queue length distribution.

c Subsequently, we determine recursive relations which allow us to compute the stationary probabilities when the server is working on an HP. d Finally, the obtained relations are employed to derive the performance measures.

Part 2-a: Flow equations

We denote by p t (n, r) the probability-density of having n customers in the system, n ≥ 1 and a remaining service time of r, r ≥ 0, at time t (given some arbitrary initial distribution), and p(n, r) the limit of p t (n, r) as t tends to infinity; p(n, r) = lim t→∞ p t (n, r), for n ≥ 1. In Lemma 1, we give the differential equations defining the evolution of the system state when the stationary regime is reached.

Lemma 1 For all r ≥ 0, p(n, r) obeys the following differential equations

p (1, r) = λp(1, r) -λπ 0 g(r) -p(2, 0)g(r), ( 30
) p (n, r) = λp(n, r) -λp(n -1, r) -p(n + 1, 0)g(r), for 2 ≤ n ≤ n * , (31)
p (n, r) = λp(n, r) -λp(n -1, r) -p(n + 1, 0)g(r) -µ S 2 g(r)φ 0 λ λ + µ S 2 n-n * , for n > n * , (32)
where p (n, r) = dp(n,r) dr .

Proof. We will start with the case where n = 1 (Equation ( 30)). Using the transition rates in the Markov chain during a duration dt, we obtain

p t+dt (1, r) = (1 -λdt)p t (1, r + dt) + λπ 0 g(r)dt + p(2, 0)g(r)dt.
Taking t → ∞ and dividing by dt leads to

p(1, r + dt) -p(1, r) dt = λp(1, r + dt) -λπ 0 g(r) -p(2, 0)g(r).
Next, taking dt → 0, we obtain Equation (30). For 2 ≤ n ≤ n * , we have

p t+dt (n, r) = (1 -λdt) • p t (n, r + dt) + λdt • p t (n -1, r + dt) + g(r)dt • p(n + 1, 0).
Taking t → ∞ and dividing by dt leads to

p(n, r + dt) -p(n, r) dt = λp(n, r + dt) -λp(n -1, r + dt) -p(n + 1, 0)g(r).
Next, taking dt → 0, we obtain Equation (31). For 2 ≤ n ≤ n * , we have

p t+dt (n, r) = (1-λdt)•p t (n, r+dt)+λdt•p t (n-1, r+dt)+g(r)dt•p(n+1, 0)+µ S 2 g(r)dt•φ 0 λ λ + µ S 2 n-n * .
Taking t → ∞ and dividing by dt leads to

p(n, r + dt) -p(n, r) dt = λp(n, r + dt) -λp(n -1, r + dt) -p(n + 1, 0)g(r) -µ S 2 g(r) • φ 0 λ λ + µ S 2 n-n *
Next, taking dt → 0, we obtain Equation (32). This finishes the proof of the lemma. . For the right hand side of the equations, we denote by π n the stationary probability to have n customers in the system when the server is serving an HP, π n = ∞ r=0 p(n, r) dr for n ≥ 1, by π 0,s the stationary probability to be in a system with no HP and a server in switch from HP to LP, and by π 0,0 the stationary probability to be in a system with no HP and a server reserved for HP (not working on LP), and we define π 0 as π 0 = π 0,s + π 0,0 . Using ∞ r=0 g(r) dr = 1, we have

-p(1, 0) = λπ 1 -λπ 0 -p(2, 0), ( 33
) -p(n, 0) = λπ n -λπ n-1 -p(n + 1, 0), for 2 ≤ n ≤ n * , ( 34
) -p(n, 0) = λπ n -λπ n-1 -p(n + 1, 0) -µ S 2 φ 0 λ λ + µ S 2 n-n * , for n > n * . ( 35
)
Observe from Equations ( 33) and (34) that the difference p(n + 1, 0) -λπ n is a constant function of n, for 0 ≤ n ≤ n * . Therefore, we have

p(n + 1, 0) -λπ n = p(1, 0) -λπ 0 , (36)
for 0 ≤ n ≤ n * . One can show by induction using Equation ( 35) and Equation (36) that

p(n + 1, 0) -λπ n = p(1, 0) -λπ 0 -λφ 0 1 - λ λ + µ S 2 n-n * , (37)
for n ≥ n * . For stability reasons, both p(n + 1, 0) and π n tend to zero as n tends to infinity. Therefore, by letting n tend to infinity in Equation (37), we obtain p(1, 0) = λ(π 0 + φ 0 ). Therefore, Equations ( 36) and

(37) can be rewritten as

p(n + 1, 0) = λπ n + λφ 0 , for 0 ≤ n ≤ n * , (38) p
(n + 1, 0) = λπ n + λφ 0 λ λ + µ S 2 n-n * , for n ≥ n * . (39)
Equations ( 38) and ( 39) relate the queue length distribution at arbitrary instants (given by π n , for n ≥ 0)

and the queue length distribution at service completion times (given by p(n, 0), for n ≥ 1).

Part 2-c: Recursive formula for the stationary probabilities

We give a recursive formula for the π's. In Lemma 2, we compute the LST of Equations ( 30)-( 32). For this purpose, we introduce the notation P (n, s) = ∞ r=0 e -sr p(n, r) dr (LST associated with p(n, r)).

Proof. We start with the case where n = 1. First, Equation (30) can be written as e -λu (p (1, u) -λp(1, u)) = -e -λu (λπ 0 + p(2, 0))g(u). ( 46)

Observe that the left hand side of Equation ( 46) is (e -λu p(1, u)) . Therefore, ∞ u=r e -λu (p (1, u)-λp(1, u)) = -e -λr p(1, r). Integrating Equation (46) for u from r to ∞ yields Equation (40). Inserting r = 0 in (40) leads to Equation (41). Equation (31) can be rewritten as e -λu (p (n, u) -λp(n, u)) = -e -λu (λp(n -1, r) + p(n + 1, 0)g(u)), (47) for 2 ≤ n ≤ n * . The left hand side of Equation ( 47) is (e -λu p(n, u)) . Thus, integrating Equation (47) for u from r to ∞ yields Equation ( 42). Inserting r = 0 in (42) leads to Equation (43). Equation ( 32) can be rewritten as e -λu (p (n, u) -λp(n, u)) = -e -λu λp(n -1, u) + p(n + 1, 0)g(u) + µ S 2 g(u)φ 0 λ λ + µ S 2 n-n * , (48) for n > n * . Again, the left hand side of Equation ( 48) is (e -λu p(n, u)) . Thus, integrating Equation ( 48) for u from r to ∞ yields Equation (44). Inserting r = 0 in (44) leads to Equation (45). This finishes the proof of the lemma.

2

Lemma 2 allows us to express the probabilities p(n, 0) as functions of P (n, λ), for n ≥ 0. Therefore, using Equations ( 38) and ( 39) one can also express the probabilities π n as functions of P (n, λ), for n ≥ 0.

At this step of the proof, there remains to determine P (n, λ), for n ≥ 0. We first derive P (1, s). From Equation (30), we have and π 0 and φ 0 are related via Equations ( 52) and ( 53). Therefore, we can compute φ 0 using f (0) = -1-G(λ)+λ G (0)

λ 2 G(λ)

, P 1 (0) = φ 0 +π 0 G(λ)

(1 -G(λ)), P 1 (0) = φ 0 +π 0 λ G(λ) ). There still remains to express p(2, 0). Equation (41) leads to p(2, 0) = p(1,0) G(λ) -λπ 0 and Equation (38) allows us to deduce that p(2, 0) = λ 1

G(λ) -1 π 0 + 1 G(λ) φ 0 .
After simplifications, we obtain

φ 0 = 1 -λE(R) n * + 1 q * + 1 q * (a S 1 + q * a S 2 )
.

The expected time spent on LP during the break is the sum φ 0 + φ 1 + • • • + φ n * . Since φ n is constant for 0 ≤ n ≤ n * as proven in Part 1 above, we can deduce the expression of the expected time spent on LP during the break;

(1 -λE(R))(n * + 1) n * + 1 q * + 1 q * (a S 1 + q * a S 2 )

.

Let us now focus on the expected waiting time in the queue. From Little's law, one can equivalently focus on the expected number of HPs in the queue. The approach to obtain this performance is to relate

(λ) + ∞ n=1 n 2 n-2 k=0 (-λ) k k! f (k) (λ)u n-1-k . ( 71
)
Since n 2 = (n -1)(n -2) + 3(n -1) + 1, ∞ n=1 n 2 (-λ) n-1 (n -1)! P

(n-1) 1

(λ) = λ 2 P

(2) 1 (0) -3λP 1 (0) + P 1 (0).

Next,

∞ n=1 n 2 n-2 k=0 (-λ) k k! f (k) (λ)u n-1-k = ∞ k=0 (-λ) k k! f (k) (λ) ∞ n=1
(n + k + 1) 2 u n .

Since (n + k + 1) 2 = n 2 + n(2 + 2k) + k(k -1) + 3k + 1, we get Combining f (s) = -1 λ(φ 0 +π 0 ) P 1 (s) and P

(2)

1 (0) = π 0 +φ 0 λ 2 G(λ)
λ G (2) (0) + 2λ G (0) + 2(1 -G(λ)) with Equation ( 72) leads after some algebra to the expression of the expected number of customers in the system. By dividing the expected number of customers in the system by λ (Little's law), we deduce the expected time spent in the system by an HP. Finally, by subtracting the expected service time duration from the expected time spent in the system by an HP we deduce the expected waiting time in Queue 1;

λE(R) 2 (1 + cv 2 R ) 2(1 -λE(R))
+ n * (n * + 1 + 2a S 2 ) 2λ n * + 1 q * + 1 q * (a S 1 + q * a S 2 ) + 1 µ S 2 • 1 + a S 2 n * + 1 q * + 1 q * (a S 1 + q * a S 2 ) .

Analysis of Part 3

We now consider the analysis of the interlude. We are interested in the expected time spent by the server on LPs, in the expected in-service wait of an HP and in the first and second moments of the overall interlude time. To obtain these performance measures, we consider the random time S spent by the server during the interlude under Policy P. Under Policy P, the server decides to initiate the service of some LPs based on a Bernoulli distribution with parameter p * . We denote by U this Bernoulli random variable with parameter p * . If the server remains idle, then she/he has to wait until the HP finishes the service with the non-focal server. We denote by I the time during which the HP is with the non-focal server. The random variable I is exponentially distributed with parameter µ I . If the server decides to serve LPs, then she/he has to switch from HP to LP. Next, the server treats LPs until the HP finishes its service with the non-focal server and extends the time spent on LPs of a deterministic duration t * . Once the server decides to serve the HP waiting in Queue 2, she/he has to switch from LP to HP.We denote by X s 1 and X s 2 the E(T ) is strictly increasing in q * . Moreover, ∂E(W ) ∂n * = 1 λ q * [1 + a S 1 + a S 2 (2 -q * + 2a S 1 ) + n * (2 + n * q * + 2a S 1 + 2q * a S 2 )] 2(1 + n * q * + a S 1 + q * a S 2 ) 2 > 0.

Therefore, E(W ) is strictly increasing in n * . Also, from ∂E(W ) ∂q * = 1 λ (a S 1 + 1) n * 2 + 2a S 2 n * + n * + 2a S 2 2 + 2a S 2 2(1 + n * q * + a S 1 + q * a S 2 ) 2 > 0, we deduce that E(W ) is strictly increasing in q * . Consequently, for a given n * , there exists a unique threshold q * , that answers Problem (1) as defined in the main paper. It is a solution of E(W ) = w. This threshold is given by q * = 2λ(a S 1 + 1)K n * 2 + 2a S 2 n * + n * + 2a Yet, the support of n * is R + and that of q * is [0, 1]. It remains to check if the solution n * = √ 2a S 2 -1 respects the supports of n * and q * . After some algebra, we obtain the conditions under which either n * = √ 2a S 2 -1 is the solution (first statement), n * = 0 (second statement), or q * = 1 (third statement).

When one parameter has an extreme value (second and third statement), the remaining control parameter can be obtained by solving E(W ) = w. This completes the proof of the proposition. 2

8 Counterexamples where t * > 0 is optimal Since the function in a S ; a S n * +2a S is increasing in a S , the last inequality indicates that if the interlude time is short or if the switching times are long then it may be preferred to increase the time in between HP instead of the interlude time. In Figure 4, we give an illustration where t * = 0 is not optimal. In Figure 4(a), we draw the curve of E(T ) on the interval [0, 7.8]. On this interval, we observe that E(T ) is first increasing then decreasing. It is first increasing because increasing t * allows not to respect Relation ( 7).

Yet, increasing t * above a threshold leads to lower performance due to the increasing of the workload. In Figure 4(b), we focus on a shorter interval to confirm what has been mentioned above; for small values of t * , E(T ) is more likely to be decreasing in t * . The presented situation is however an exception. In most cases, increasing n * is better than increasing t * . The constraint of having very low workload situations to prefer t * instead of n * also leads to a very limited improvement. In Figure 4, the improvement from t * = 0 to t * = 7 is only 0.00075%. 9 Delay back-office work to later interludes under a state-dependent policy We investigate the state-dependent policy using an MDP approach for a service encounter with two interludes and three exponential working phases with rates µ 1 , µ 2 , and µ 3 . For this purpose, we adjust the value function defined in Equation (3) of the article to the new situation and derive the optimal policy. A state of the system here is defined by (Ω, x, y) where Ω ∈ {L, H} (server dedicated to HP or to LP), x is the number of HPs in Queue 1 and y is the progress of service of the oldest HP in the system (y = 1: HP in Queue 1 or in the first service phase, y = 2: HP with the non-focal server for the first time, y = 3: HP in the second phase of service, y = 4: HP with the non-focal server for the second time, y = 5: HP in the last phase of service, x = 0 and y = 1 means that there is no HP in the system).

We observe that the threshold structure of the optimal policy is maintained with more than one interlude. More precisely, for the switch from LP to HP, there exists 5 thresholds, u B , u I 1,1 , u I 1,2 , u I 2,1 , and u I 2,2 , which correspond to the cases y = 1, 2, 3, 4, 5, respectively such that the switch from LP to HP is initiated if and only if the number of HPs in Queue 1 is above the corresponding threshold. For the switch from LP to HP, there exists 2 thresholds, ũI 1 and ũI 2 , which correspond to the cases y = 2, and y = 4, Table 1: Optimal thresholds (ω = 20, µ S 1 = µ S 2 = µ S , µ 1 = µ 2 = µ 3 = 1)

Exogenous parameters

Thresholds for the Thresholds for the switch from LP to HP switch from HP to LP λ µI 1 µI 2 µS uI 1,1 uI 1,2 uI 2,1 uI 2,2 uB ũI 1 ũI 2 E(T ) 1 0.05

Figure 2 :

 2 Figure 2: Decision actions

Figure 3 :

 3 Figure 3: Impact of the caseload (µ 1 = µ 2 = 2, µ I = 1, µ S1 = µ S2 = 4, ω = 1)

Figures 5

 5 Figures 5(a), 5(c), 6(a), 6(c) depict a case with a short switching time and Figures 5(b), 5(d), 6(b) and 6(d) a case with a long one, showing how switching times influence the blending decisions. Further, by comparing Figure 5(a) with Figure 5(c), Figure 6(a) with Figure 6(c), Figure 5(b) with Figure 5(d), or Figure 6(b) with Figure 6(d),

  (b) or 6(b) compared with Figure 5(d) or 6(d))

Figure 4 :

 4 Figure 4: Summary of numerical study

Figure 5 :

 5 Figure 5: E(T ) as a function of λ for short (a),(c) and long (b),(d) switching times for caseload= 1

  µ I = 10, µ S 1 = µ S 2 = 0.05, E(X) = 1, E(X 2

Figure 6 :

 6 Figure 6: E(T ) as a function of λ for short (a),(c) and long (b),(d) switching times with M = 10 for infinite caseload

  (a)) and a case with a low workload in (Figure7(b)). It illustrates that, as the workload increases, the impact of p * on E(T ) varies from a positive effect to a negative one. The negative effect of p * under a high workload situation can be Case 1 (λ = 0.43,µ I = 1, µ S 1 = µ S 2 = 0.1, E(X) = 1, E(X 2 ) = 2, w = 50) µ I = 1, µ S 1 = µ S 2 = 10, E(X) = 1, E(X 2 ) = 100, w = 100)

Figure 7 :

 7 Figure 7: E(T ) as a function of p * and q *

2

  +λE(X) a I +p * a I a S 2 a I +a S 1 +a I a I +p * a S 2 (a S 2 +a I ) a I +a S 1 1-λE(X)-a I -p * a I a S 2 a I +a S 1

  If f * (L, v + e 3 ) + f (H, v) = f (H, v + e 3 ) + f (H, v), so, Inequality (26) proves the result. Otherwise, iff * (L, v + e 3 ) + f (H, v) = f (L, v + e 3 ) + f (H, v),then Inequality (27) combined with Relation (16) proves the result. Consider now the terms proportional with µ. The first and second ones are clearly positive due to Relations (22) and (24) combined with Relation (16).

Figure 1 :

 1 Figure 1: Description of the proof

  ) and 2(d) is small. With long switching times, extreme choices are most of the time taken for the use of the interlude as explained in Figure4of the main paper. This is the reason why the difference between the performance of the two policies is also not significant in Figure2(b). With short switching times and a high workload as in Figure2(a), the difference can be significant because most of the time spent on LP is spent during the interlude. µI = 3, µS 1 = µS 2 = 4

Figure 2 :

 2 Figure 2: E(T ) as a function of λ (µ 1 = µ 2 = 2, ω = 1)

Figure 3 :

 3 Figure 3: Markov chain with exponential service

  2-b: Queue length distributionWe now integrate both sides of Equations (30), (31) and (32) for r from 0 to ∞. For the left hand side of the equations, we have ∞ r=0 p (n, r) dr = lim r-→∞ p(n, r) -p(n, 0). Since lim r-→∞ p(n, r) = 0 for stability reason, we have ∞ r=0 p (n, r) dr = -p(n, 0)

  (λp(n -1, u) + p(n + 1, 0)g(u)) du, for 2 ≤ n ≤ n * , (42)p(n, 0) = λ P (n -1, λ) + p(n + 1, 0) G(λ), for 2 ≤ n ≤ n * , (43) p(n, r) = e λr ∞ u=r e -λu (λp(n -1, u) + p(n + 1, 0)g(u) + µ S 2 φ 0 λ λ + µ S 2 n-n * g(u)) du, for n > n * , (44) p(n, 0) = λ P (n -1, λ) + p(n + 1, 0) G(λ) + µ S 2 φ 0 λ λ + µ S 2 n-n * G(λ), for n > n * ,

e∞

  -sr p (1, r) dr = ∞ r=0 e -sr (λp(1, r) -(p(2, 0) + λπ 0 )g(r)) dr.This equation is equivalent tos P (1, s) -p(1, 0) = λ P (1, s) -(p(2, 0) + λπ 0 ) G(s).Therefore,P (1, s) = p(1, 0) -(p(2, 0) + λπ 0 ) G(s) s -λ .Combining this equation with Equation (41) leads toP (1, s) = -λ(π 0 + φ 0 ) G(λ) G(s) -G(λ) s -λ .Letting s tend to λ in the last expression leads toP (1, λ) = -λ(π 0 +φ 0 ) G(λ)G (λ). We now compute P (n, s) for 2 ≤ n ≤ n * . From Equation (31), we have∞ r=0 e -sr p (n, r) dr = ∞ r=0 e -sr (λp(n -1, r) -p(n + 1, 0)g(r)) dr.This equation is equivalent tos P (n, s) -p(n, 0) = λ P (n, s) -λ P (n -1, s) -p(n + 1, 0) G(s).Therefore,P (n, s) = p(n, 0) -λ P (n -1, s) -p(n + 1, 0) G(s) s -λ . 0) -λ(-λP 1 (0) + P 1 (0)) -µ S 2 φ 0 f (0) -λf (0)) .Moreover, the definition of u n leads to ∞ n=1 u n = λ(π 0 + φ 0 -G(λ)),

( 1 -∞=

 1 G(λ) + λ G (0)), G (0) = -E(R)where R is the time elapsed between the initiation of the first working phase and the completion of the last one (i.e., it is the service time), and µ S 2 φ 0 λφ 0 (n * + 1 + λ µ S 2

  n and deduce the expected number of HPs in the queue. One may write

  2 f (2) (0) -3λf (0) + f (0)) ∞ n=1 u n .

Figure 4 :

 4 Figure 4: E(T ) as a function of t * (λ = 0.05, ω = 200, µ S = 100, µ I = 0.1, E(X) = cv(X) = 1)

Table 1

 1

	: Notations
	Exogenous parameters

Table 2 :

 2 Computed thresholds with N = 3 and caseload= 1

				Exogenous parameters			Thresholds for the	Threshold for the
									switch from LP to HP	switch from HP to LP
		ω	λ	µ 1	µ 2	µ I	µ S 1	µ S 2	u I 1	u I 2	u B	ũI	E(T )
	1	5	0.05	1	1	1	10	10	1	1	1	1	88.98%
	2	5	0.1	1	1	1	10	10	1	1	1	1	78.89%
	3	5	0.2	1	1	1	10	10	2	1	1	2	55.94%
	4	5	0.05 68.96%
	6	5	0.2	1	1	1	1	1	2	1	2	1	34.97%
	7	5	0.05	1	1	1	0.05 0.05	11	10	13	1	11.17%
	8	5	0.1	1	1	1	0.05 0.05	5	2	3	1	6.48%
	9	5	0.2	1	1	1	0.05 0.05	4	2	2	1	1.03%
	10	10 0.05	1	1	1	1	1	2	1	2	1	88.86%
	11	10	0.1	1	1	1	1	1	4	2	2	4	71.79%
	12	10	0.2	1	1	1	1	1	6	4	6	5	39.20%
	13	5	0.2	2	2	0.5	1	1	2	2	3	2	33.52%
	14	5	0.2	0.71 0.71	5	1	1	2	1	1	1	32.29%
	15	5	0.2	1	10	0.53	1	1	3	1	3	3	32.04%
	16	5	0.2	10	1	0.53	1	1	2	1	3	2	31.81%
	17	10	0.1	1	1	1	0.67	2	5	2	3	6	73.35%
	18	10	0.1	1	1	1	2	0.67	3	2	2	3	67.31%

Switch from LP to HP. There exists a threshold function z = u 1 (x, y), decreasing in the variables x and y, such that if the server is working on LP in state (x, y, z) then it is optimal to switch from LP to HP if and only if z ≥ u 1 (x, y).

  Benjamin Legros 1 • Oualid Jouini 2 • O. Zeynep Akşin 3 • Ger Koole 4 1 EM Normandie, Laboratoire Métis, 64 Rue du Ranelagh, 75016 Paris, France 2 Laboratoire Genie Industriel, CentraleSupélec, Université Paris-Saclay, Grande Voie des Vignes, 92290 Chatenay-Malabry, France 3 College of Administrative Sciences and Economics, Koç University, Rumeli Feneri Yolu, 34450 Sariyer-Istanbul, Turkey 4 VU University Amsterdam, Department of Mathematics, De Boelelaan 1081a, 1081 HV Amsterdam, The Netherlands benjamin.legros@centraliens.net • oualid.jouini@centralesupelec.fr • zaksin@ku.edu.tr • ger.koole@vu.nl Accepted in European Journal of Operational Research, 2020.

  2 S 2 + 2a S 2 -2λK(a S 2 + n -λE(R)). This leads to an expression of E(T ) that is only a function of n * ;E(T ) = E(T I ) + 2(1 -λE(R))(n * + 1)λK n * 2 + 2a S 2 n * + n * + 2a 2 S 2 + 2a S 2 . 2 + 2a S 2 n * + n * + 2a 2 S 2 + 2a S 2

	λE(R) 2 (1+cv 2 R )
	2(1One may write
	∂E(T )
	∂n

* )

,

where K = w -E(W 2 ) -* = 2(1 -λE(R))(2a 2 S 2 -(1 + n * ) 2 )λK n * 2 .

The function in n * , 2a 2 S 2 -(1 + n * ) 2 , is positive if and only if n * ≤ √ 2a S 2 -1. Thus, E(T ) is maximized for n * = √ 2a S 2 -1.

  In Section 5.4.2 in the main paper, we state that t * = 0 is almost always optimal. However, counterexamples may exist. In what follows, we illustrate such a counterexample in a case where µ S 1 = µ S 2 = µ S . Observe that for high values of t * , e -λt * /a S tends to zero as t * tends to infinity. Therefore, Inequality (7) may not be met for high values of t * . So, this keeps open the possibility to increase the interlude time. Consider now the difference∂E(T ) ∂n

* -∂E(T ) ∂λt * . It is positive for all t * ≥ 0 if and only if a I < a S n * + 2a S .

The switch from LP to HP may occur in any state with x ≥ 0. We want to show the threshold structure of the optimal policy for this switch. A sufficient condition for this is

for k, x ≥ 0. This property of the value function has to be proven together with a set of other properties called Class C. We define Class C as follows. A function f (., x) is said to be in Class C if for x ≥ 0 we have f (H, x + 1) ≥ f (H, x), f (L, x + 1) ≥ f (L, x), and f (L, x + 1) ≥ f (H, x)

(2)

f (L, x + 1) + f (H, x) ≥ f (H, x + 1) + f (L, x).

(5)

Relation (2) expresses the increasing property of f , while Relation (3) defines its convexity property when the server is in state H. Relation ( 5) is the relation proving the threshold nature of the optimal policy.

We now prove by induction on k that V k belongs to Class C. Since V 0 (H, x) = V 0 (L, x) = 0, for x ≥ 0, V 0 satisfies Relations (2)-( 5). We now assume that V k belongs to Class C and we want to show that V k+1 also belongs to Class C.

Relation (2): For x, k ≥ 0, we have

Therefore, V k+1 (H, x) is increasing in x. We also have

We have , x). This proves that V k+1 (L, x) is increasing in x. Next, we may write

Let us consider the last two lines. The term proportional with µ S 1 is positive due to Relation (2) whether

The term proportional with µ 1 1 x>0 is also positive due to Relation (2). Finally, since V * k (H, 0) ≤ V k (H, 0), the term proportional with µ S 2 is also positive. This proves that V k+1 (., x) satisfies Relation (2).

Relation (3): For x, k ≥ 0, we have

satisfies Relation (4). Therefore, using µ 1 ≥ µ S 2 , this proves that V k+1 satisfies Relation (3).

Relation (4): For x, k ≥ 0, we have

Consider the last three lines. The term proportional with 1 x>0 µ 1 is positive since V k satisfies Relations

(2) and ( 3). The term proportional with µ S 1 is also positive. Either

and Relation (4) shows the result. For the last line either

) and (i) the term proportional with µ 1 is positive, and (ii) the term proportional with 2µ S 2 is zero, or

). In the latter case, the last line can be rewritten as (2µ

). This expression is positive as we assumed that 2µ S 2 ≥ µ 1 .

Relation (5): For x, k ≥ 0, we have

Consider the last three lines. In the first line, the term proportional with

For the second line, if

)). Adding this

Using Equation ( 43), we get

for 2 ≤ n ≤ n * . By letting s tend to λ, we deduce that

for 2 ≤ n ≤ n * . With the same approach using Equation (45), we also obtain

for n > n * . Observe that Equation ( 49) for 2 ≤ n ≤ n * and Equation ( 51) are identical for n > n * .

Therefore, Equation ( 49) and the expression of P (n, λ) in Equation ( 50) are valid for n ≥ 2.

The above analysis allows us to give the set of equations which governs the dynamic of the queueing system.

P (1, s) = -λφ 0 (a S 1 + 1)

Next, for n ≥ 1,

Part 2-d: Performance measures

We now use Equations ( 52)-( 60) to derive the performance measures. We define (u n ) n≥1 by

for n ≥ 1 and

. We also simplify the notations by defining P n (s) = P (n, s). Therefore, Equation ( 60) can be rewritten as

for n ≥ 1. In Lemma 3, we provide a relation to compute P n (s) as a function of P 1 (s), for n ≥ 1.

Lemma 3 For n ≥ 1, we have

where

Proof. From the definition of Taylor expansions, Equation (64) directly follows from Equation (63) by letting s → λ. We now prove Equation ( 63) by induction on n. For n = 1, this equation is obviously true (i.e., for n = 1, Equation ( 63) is P 1 (s) = P 1 (s)). Assume now that Equation ( 63) is true for a given n (n ≥ 1). By replacing the expression of P n (s) of Equation ( 63) into Equation ( 62), we obtain

This proves that Equation ( 63) is true for n ≥ 1. The proof of the lemma is completed. 2

We are now interested in the expected time spent on LP during the break. The approach to obtain the performance measure is to determine a set of equations relating

u n , and

where u n is defined in Equation ( 61) and P n (λ) is defined in Equation ( 64). After simplification, this set of equations lead to the expected time spent on LP during the break. Let us start with

nP n (λ) using the expression of P n (λ) in Lemma 3. We may write

Moreover,

At this step, 43) and ( 45). We obtain a recursive definition of u n ;

Summing up the product of Equations ( 67) and ( 68) with n for n from 2 to infinity yields

By replacing the expression of

nP n (λ) from Equation (66) into Equation (69), we obtain

-λf (0) = 0. Therefore, the left hand side of the Equation ( 70) is zero. It switching times respectively from HP to LP and from LP to HP. We therefore may write

Since the variable X s 2 + t * and 1 I≥Xs 1 are independent, we have

Again, using the independence of I, X s 1 and X s 2 , one may write

The waiting time in Queue 2, W 2 , is U • (X s 2 + t * ) • 1 I≥Xs 1 . The expected value of this random variable is

The time spent on LP during a service is 1 I≥Xs 1 • max(U (t * + I -X s 1 ), 0). The probability density function of t * +I is µ I e -µ I (t-t * ) 1 t≥t * and the one of -X s 1 is µ S e µ S t 1 t≤0 . The probability density function of I +t * -X s 1 is given by the convolution of these two functions. After some algebra we obtain f I+t * -Xs 1 (t) = µ S 1 µ I µ S 1 +µ I e µ S 1 t+µ I t * -(µ S 1 +µ I ) max(t,t * ) , for t ≥ 0. The case t < 0 does not need to be computed since we are only interested in the positive realizations of I + t * -X s 1 . By integration t • f I+t * -Xs 1 (t) from 0 to ∞, we obtain

This completes the proof of the theorem. 2

7 Proof of Proposition 4

We will start with the first order monotonicity properties of the performance measures. We have

Thus, E(T ) is strictly increasing in n * . Since such that the switch from HP to LP is initiated if and only if the number of HPs in Queue 1 is below the corresponding threshold.

In Table 1, we evaluate the thresholds for different combinations of the system parameters. Similar observations to those of Section 4 in the article can be made. For instance, by comparing lines 3 and 4

with lines 5 and 6, we observe that with short switching times the thresholds increase with the arrival rate whereas the opposite effect can be observed with long switching times. This observation can only be made if the switching times are sufficiently long. For instance, in lines 1 and 2 with shorter switching times, it is not possible to differentiate the use of each interlude. In addition, from lines 1-6, we observe that if the two interludes have the same expected duration, then the server will use the second interlude more for treating LP than the first one (higher thresholds on the second interlude). Lines 7 and 8 confirm the idea of Section 5.3 in the article; the longest interlude is used the most. In line 7, when the longest interlude is at the end of the service process, we even observe that the first interlude is not used. Hence, the optimal policy follows a simple principle: preference for the longest and latest interludes for treating LP. By comparing E(T ) of lines 5-6 with line 2, we note that the system has better performance when the interludes have different durations.