The power of letting go: scheduling with immediate and delayed rejections in multi-server queues

Abstract Long waiting times in service systems reduce customer satisfaction, increase abandonment rates, and harm provider performance. To address these challenges, we study a multi-server, multi-class queueing system in which the operator can jointly control scheduling and implement two types of rejections: immediate rejections at arrival and delayed rejections during the waiting period. The objective is to minimize total operational costs, including waiting costs and rejection penalties. Using a fluid approximation, we characterize the structure of the optimal policy and develop an index-based control rule—the $${\mathcal {L}}\mu $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>L</mml:mi> <mml:mi>μ</mml:mi> </mml:mrow> </mml:math> rule—that jointly governs scheduling and rejection decisions. Under the $${\mathcal {L}}\mu $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>L</mml:mi> <mml:mi>μ</mml:mi> </mml:mrow> </mml:math> rule, each customer class operates in one of two distinct queueing regimes: an Erlang-B regime, where customers are rejected immediately if capacity is unavailable, or an Erlang-A regime, where customers are admitted and may be rejected after waiting. We further extend the model to incorporate class-specific service-level (SL) requirements. In this setting, we show that the index structure adjusts to ensure SL compliance, relaxing strict scheduling priorities and enabling partial capacity sharing across classes. Delayed abandonments, which play a limited role in the basic model, become effective under the adjusted policy due to the presence of SL constraints. Numerical simulation experiments illustrate the effectiveness of the proposed policies.