CS Paper Radar

Whittle index approach to multi-server scheduling with convex delay costs and impatient customers

Samuli Aalto

cs.PF math.PR ·submitted 2026-09-17 06:58 UTC · v1

Abstract

We consider the dynamic scheduling problem in a multi-class M/G/N + M queue with convex delay costs and impatient customers that have exponential abandonment times. We apply the Whittle index approach to find a reasonable heuristic solution for this tricky problem. By assuming exponential abandonment times, we are able to make a very straightforward use of the results of the corresponding problem with patient customers presented in Queueing Systems, Vol. 110, Article no. 2, 2026. Our main theoretical achievements are proving that the closed version of the corresponding discrete-time problem is indexable and deriving an explicit expression for the Whittle index. The discrete-time results are utilized to develop the Whittle index policy for the original continuous-time scheduling problem.

Closest papers

Nearest neighbours by meaning across the whole index.

New Complexity Results for Fair Repetitive Scheduling

cs.DS ·2026-08-20 ·Moran Koren, Michael L. Pinedo, Dvir Shabtay
similarity 0.61
Abstract · 12 pages

We revisit the problem of finding fair solutions to repetitive scheduling problems with a single machine. In this problem, we are given a set of $n$ clients and a planning horizon consisting of $q$ periods (days). Each day, every client submits a single job that must be processed by the machine. The objective is to construct a set of $q$ schedules, one for each day, such that the quality of service (QoS) received by each client meets a predefined threshold. The QoS measure may be any standard scheduling criterion, such as the total waiting time or total completion time of a client's jobs over the entire planning horizon. This problem has been studied in the literature, with previous works providing complexity classifications and approximation algorithms for various QoS measures. Nevertheless, several important questions remain open. In this paper, we resolve three of these questions and identify several additional directions for future research.

0.23

Joint Service Depth and Priority Design in Queueing Systems

cs.GT econ.THmath.OC ·2026-10-23 ·Adam N. Elmachtoub, Yash Kanoria, Jonathan Y. Tan
similarity 0.58
Abstract

In AI-assisted service systems, the server can choose how much processing effort to spend on each job, which we call the service depth. Deeper reasoning improves output quality but occupies the server longer and increases congestion, and the realized processing time remains random because AI models are probabilistic and tasks vary in complexity. We study the joint design of service depth and priority in a single-server queue whose customers differ in delay sensitivity, with the goal of maximizing social welfare. For each customer type, the decision maker chooses a priority level and a service depth, and service times are exponential with mean equal to the chosen depth. With two customer types and linear service values, we characterize the centralized optimum. Counterintuitively, it prioritizes the patient type and gives it a smaller service depth when patient customers are sufficiently prevalent. When delay sensitivity is private, however, incentive compatibility requires the impatient type to receive a weakly shorter sojourn time, so the optimal price menu never prioritizes the patient type. Consequently, there can be a welfare gap between the centralized decision maker's optimal control policy and the optimal decentralized pricing mechanism. With a continuum of types, the centralized optimum is monotone: more delay-sensitive customers receive weakly smaller depth and higher priority, so the optimum can be implemented by a price menu with no welfare loss. Allowing randomized depths similarly closes the gap in the two-type model. Finally, we calibrate an agentic AI service system using published coding-agent trials from DeepSWE and numerically examine priority inversion, the value of joint design, and the welfare gain from personalization.

0.26

Stochastic Aggregation with Prescribed Resources and Additive Delay

cs.DS ·2026-11-10 ·Tianhang Lu, Runtian Ren, Shengcai Liu
similarity 0.57
Abstract

We study online aggregation with prescribed resources and additive delay. In this problem, we are given a finite set of resources with purchase costs and a collection of request types, each specifying the resources it requires. Requests arrive over time, and each request can be served immediately or postponed to a later time. A service may serve several pending requests together by purchasing every resource required by at least one of them, paying for each purchased resource only once. These purchases serve only the current batch; resources needed in a later service must be purchased again. A request served $t$ units of time after its arrival incurs delay cost $t$. The objective is to serve all requests while minimizing the sum of resource purchase costs and individual delay costs. We consider a stochastic version of this problem in which requests of each type follow an independent Poisson process of known rate. An online algorithm knows these rates but observes requests only upon arrival. We compare its expected cost with that of an offline optimum that knows the entire realized input and may choose every batch freely. A resource--scale linear program supplies both an offline lower certificate and synchronized service periods. This yields a deterministic online algorithm with polynomial-time preprocessing on rational input and a long-run ratio of expectations below $2.113$. The guarantee applies in particular to rooted multi-level aggregation and prescribed-pair aggregation on trees. Besides, for Poisson TCP acknowledgment, we further characterize the optimal long-run ratio of expectations at every load, showing that its worst-case value is approximately 1.409 and is attained by a deterministic online policy.

0.18

Load Balancing with Partial Queue Information - Threshold Optimality and Indexability

cs.NI ·2026-09-23 ·Sathwik Chadaga, Eytan Modiano
theory similarity 0.56
Abstract

We consider the problem of load balancing in a system with one dispatcher and $N$ parallel servers. The dispatcher must select one server to dispatch new jobs at every time-step and each server buffers incoming jobs in a queue. However, the dispatcher does not know the servers' backlogs and must make dispatching decisions based on previous observations. The dispatcher's objective is to dispatch jobs to the shortest queue. This problem can be formulated as a restless multi-arm bandit (RMAB) problem where each arm's state is its corresponding belief vector. Our goal is to verify Whittle indexability for this problem and derive a low complexity Whittle index policy. Previous Whittle indexability results cannot be directly applied due to the multi-dimensional nature of the belief vector. To overcome this issue, we define the RMAB state as the tuple of the most recent backlog observation and the time since this observation. We consider two model variations, a standard finite queue model and a blocking queue model. We show that the single-arm decoupled problems of both these models have threshold optimal solutions under some assumptions. For the standard finite queue model, we prove indexability and derive the Whittle index policy in closed form. For the blocking queue model, we derive a sufficient condition for indexability under threshold optimality and use it to show indexability for some special cases.

0.14

Online Service with Per-Batch Maximum Delays

cs.DS ·2026-08-19 ·Tianhang Lu, Runtian Ren, Shengcai Liu, Ke Tang
similarity 0.56
Abstract

We study online service with per-batch maximum delays on a finite metric space. Requests arrive over time, and a server serves each batch by following a walk visiting its requests' locations. Movement is instantaneous. The objective is to minimize the total distance traveled by the server plus the sum, over all batches, of the maximum waiting time in each batch. We give deterministic polynomial-time algorithms with competitive ratios $10$ on finite lines, $12$ on weighted trees, and $20$ on arbitrary finite metrics. Unlike additive delay, maximum delay allows younger requests to join a batch without increasing its delay charge. Our algorithms coordinate service using a common waiting clock and a threshold determined by the metric. The analysis uses certificates for groups of requests to compare this policy with any offline schedule, even one that serves different batches and follows different walks. This comparison shows that coordinating service in this way loses only a constant factor. The bounds hold whether the server must serve requests it visits or may leave them unserved; the two rules also have equal offline optimal costs. Offline optimization is polynomial on lines and explicitly represented weighted trees, and NP hard on general metrics. When arrivals are announced but locations are hidden until visited, we give an $84$-competitive algorithm on a known finite line under either rule.

0.13

Optimal Scheduling in Generalized Switch in Heavy Traffic

cs.PF ·2026-09-15 ·Runhan Xie, Ziv Scully, Rhonda Righter, Izzy Grosof
theory similarity 0.56
Abstract

The generalized switch is a highly flexible queueing model, covering multiclass, multiserver, and multiresource queueing systems as well as a wide variety of stochastic networks. Although many scheduling policies have been developed for this model, they almost entirely address unknown job duration settings. How to optimally use known job durations in the generalized switch has remained open. Moreover, optimizing mean response time remains open in both settings. We introduce the first policy to guarantee heavy-traffic optimal mean response time in the generalized switch, our Smallest Equalizing Bucket (SEB) policy. The key challenge in designing an optimal scheduling policy is that we must simultaneously prioritize small jobs and also minimize resource waste, all while fitting within the generalized switch's service options. SEB overcomes this challenge by grouping jobs into duration-based buckets and enforcing an "equalizing" service structure that keeps each bucket balanced while still prioritizing the smallest jobs. We prove SEB's heavy-traffic optimality. Simulations further confirm the effectiveness of SEB-inspired heuristics.

0.28

Review-Period Sensitivity in Multiclass Queue Scheduling

eess.SY ·2026-08-29 ·Mir Mikdad Talpur, Vahid Sarhangian
similarity 0.55
Abstract

Optimal control of queueing networks is typically studied under continuous-time control. In many service settings, however, managers can adjust decisions only at discrete and potentially infrequent review epochs. We study a multiclass queue scheduling problem in which server assignments can be changed only at the beginning of discrete review periods, and examine how performance depends on the review-period length. We analyze a family of associated fluid control problems parameterized by the review-period length and characterize the first- and second-order sensitivity of the value function. For the two-class case, we derive explicit expressions for these derivatives and characterize their signs. We find that for short review periods, the value function need not be monotone. Once the review period is sufficiently large, the value function becomes monotone nondecreasing and may exhibit a convex or linear region before eventually becoming concave. These results provide insights on when the value of more frequent control, or \emph{flexibility} with respect to server assignments, is higher. We further numerically examine the robustness of these observations for the original stochastic scheduling problem and show that stochasticity smooths the nonmonotonicity at smaller scales, while the qualitative sensitivity patterns remain visible and become more pronounced as the scale of the system increases.

0.25

Scheduling to Maximize Weighted Throughput with an Active-Time Budget

cs.DS ·2026-08-29 ·Susanne Albers, G. Wessel van der Heijden
publishedtheory similarity 0.55
Abstract · 16 pages, 5 figures, To appear at WAOA 2026

We study the active-time scheduling problem with weighted throughput maximization. In this setting, a set of $n$ jobs $J$ arrive at integer release times, each with an integer processing time and integer deadline. Jobs may be preempted at integer time slot boundaries. A schedule assigns jobs to time slots, with at most $m$ jobs assigned to the same time slot. A slot is called \emph{active} if at least one job is scheduled in it. Instead of scheduling all jobs to minimize the number of active time slots, we consider the more general variant of \emph{weighted throughput} with an active-time budget $K$, where each job $j\in J$ has a weight $w_j$. The objective is to maximize the total weight of \emph{completed} jobs using at most $K$ active time slots. This means that partially scheduled jobs do not count towards the objective. The classical active-time minimization problem is recovered by asking whether all jobs can be completed within a given active-time budget. We give hardness, approximation, and exact algorithmic results. For general intervals with unbounded parallelism, we prove NP-hardness, rule out an FPTAS unless $\mathrm{P}=\mathrm{NP}$, and give a pseudo-polynomial time $Ω(1/\log K)$-approximation. For proper intervals, we prove a canonical structural lemma and obtain an exact $(nK)^{O(m)}$-time algorithm. For laminar intervals, we give an exact $f(K,m)\cdot n^{O(1)}$-time algorithm.

0.25