Saif Benjaafar

Problem definition: This paper studies an appointment system where a finite number of customers are scheduled to arrive in such a way that (1) the expected waiting time of each individual customer cannot exceed a given threshold; and (2) the appointment times are set as early as possible (without breaking the waiting time constraint). Methodology/results: First, we show that, under the service-level constraint, a prospective schedule can be obtained from a sequential scheduling approach. In particular, we can schedule the appointment time of the next customer based on the scheduled appointment times of the previous customers. Then, we use a transient queueing-analysis approach and apply the theory of majorization to analytically characterize the structure of the optimal appointment schedule. We prove that, to keep the expected waiting time of each customer below a certain threshold, the minimum inter-appointment time required increases with the arrival sequence. We further identify additional properties of the optimal schedule. For example, a later arrival has a higher chance of finding an empty system and is more likely to wait less than the duration of his expected service time. We show the convergence of the service-level-constrained system to the D/M/1 queueing system as the number of arrivals approaches infinity and propose a simple, yet practical, heuristic schedule that is asymptotically optimal. We also develop algorithms that can help system managers determine the number of customers that can be scheduled in a fixed time window. We compare the service-level-constrained appointment system with other widely studied systems (including the equal-space and cost-minimization systems). We show that the service-level-constrained system leads to a lower upper bound on each customer’s waiting time; ensures a fair waiting experience among customers; and performs quite well in terms of system overtime. Finally, we investigate various extended settings of our analysis, including customer no-shows; mixed Erlang service times; multiple servers; and probability-based service-level constraints. Managerial implications: Our results provide guidelines on how to design appointment schedules with individual service-level constraints. Such a design ensures fairness and incorporates the threshold-type waiting perception of customers. It is also free from cost estimation and can be easily applied in practice. In addition, under the service-level-constrained appointment system, customers with later appointment times can have better waiting experiences, in contrast to the situation under other commonly studied systems. Funding: Z. Yan was partly supported by a Nanyang Technological University startup grant; the Ministry of Education Academic Research Fund Tier 1 [Grant RG17/21] and Tier 2 [Grant MOE2019-T2-1-045]; and Neptune Orient Lines [Fellowship Grant NOL21RP04]. Supplemental Material: The online supplement is available at https://doi.org/10.1287/msom.2022.1159 .

We consider a rental service with a fixed number of rental units distributed across multiple locations. The units are accessed by customers without prior reservation and on an on-demand basis. Customers can decide on how long to keep a unit and where to return it. Because of the randomness in demand and in returns, there is a need to periodically reposition inventory away from some locations and into others. In deciding on how much inventory to reposition and where, the system manager balances potential lost sales with repositioning costs. Although the problem is increasingly common in applications involving on-demand rental services, not much is known about the nature of the optimal policy for systems with a general network structure or about effective approaches to solving the problem. In this paper, first, we show that the optimal policy in each period can be described in terms of a well-specified region over the state space. Within this region, it is optimal not to reposition any inventory, whereas, outside the region, it is optimal to reposition but only such that the system moves to a new state that is on the boundary of the no-repositioning region. We also provide a simple check for when a state is in the no-repositioning region. Second, we leverage the features of the optimal policy, along with properties of the optimal cost function, to propose a provably convergent approximate dynamic programming algorithm to tackle problems with a large number of dimensions. This paper was accepted by David Simchi-Levi, optimization. Funding: The research of S. Benjaafar is in part funded by the US National Science Foundation (NS) [Grant SCC-1831140]. The research of X. Li is in part funded by the SingaporeMinistry of Education [Grant R-266-000-128-133]. This work used the Extreme Science and Engineering Discovery Environment [NSF Grant ACI-1548562], the Bridges-2 system [NSF Grant ACI-1445606], and resources from the University of Pittsburgh Center for Research Computing. Supplemental Material: Data and the electronic companion are available at https://doi.org/10.1287/mnsc.2021.4286 .