PaperlayerView exact revision on arXiv

Source-linked AI summary

Review-Period Sensitivity in Multiclass Queue Scheduling

Mir Mikdad Talpur, Vahid Sarhangian

arXiv:2608.29398v1eess.SY

TL;DR

The paper asks how multiclass queue-scheduling performance changes when server assignments can be revised only at discrete review epochs. It analyzes review-period-parameterized fluid control problems and their value-function sensitivities, finding nonmonotonic behavior at short periods and structured monotone curvature at sufficiently large periods. The analysis also examines limitations from nondifferentiable costs, transitions, and policy changes at active-constraint boundaries.

  • Problem

    Queueing control is often studied continuously, but practical managers may intervene only at discrete, potentially far-apart epochs, leaving the value of review frequency to be understood.

  • Method

    The paper studies a family of discrete-time finite-horizon fluid dynamic programs parameterized by review-period length and differentiates their Bellman equations at regular points.

  • Results

    The value function need not be monotone for short review periods; for sufficiently large periods it becomes monotone increasing and may transition from convex or linear behavior to concavity.

  • Takeaways & Limitations

    Review timing, not only review frequency, affects control value, while the stochastic problem largely smooths short-scale nonmonotonicity but retains the fluid model's qualitative structure.

  • Takeaways & Limitations

    Sensitivity analysis faces nondifferentiable cost and transition functions and possible policy nondifferentiability when active constraints change.

Abstract

from arXiv · show

Optimal control of stochastic 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. 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.

1. Introduction

The paper studies multiclass queue scheduling when server assignments can change only at discrete review epochs, treating review-period length as an operational constraint. It develops fluid sensitivity results and shows that the value function's response can be nonmonotone at short periods but follows structured curvature patterns at larger periods.

  • Motivation: Discrete review epochs can fundamentally change optimal queueing policies and raise whether control remains effective when continuous intervention is infeasible.The paper focuses on multiclass scheduling with shared servers and discrete reassignment opportunities.
  • Problem and approach: The study varies review periods from zero, representing continuous-time control, toward infinity, representing static allocation, to assess the value of control frequency.The analysis treats the review period as a given operational constraint rather than merely an implementation device for continuous-time policies.
  • Method: A family of finite-horizon fluid control problems is parameterized by review-period length, and first- and second-order value-function sensitivities are derived through a dynamic-programming formulation.The approach applies nonlinear-program sensitivity results to sequential decisions and differentiates the Bellman equation at regular points.
  • Optimal policy: The optimal fluid policy prioritizes higher-index classes unless doing so would empty the higher-priority class before the current period ends.This characterizes how capacity is allocated across classes within a discrete review period.
  • Sensitivity results: For two classes, the value function need not be monotone in review-period length because the timing of review epochs matters in addition to their frequency.For sufficiently large periods, it becomes monotone increasing and may be convex or linear before eventually becoming concave.
  • Numerical study: In the stochastic problem, nonmonotonicity is largely smoothed out, while the fluid value-function structure remains similar.The qualitative sensitivity patterns become more pronounced as the system scale increases.

2. Problem Description

The paper formulates a multiclass multiserver queue in which integer server assignments are changed only at discrete decision epochs, then studies a continuous-allocation fluid relaxation. Its dynamic program defines period-dependent costs and transitions, whose value functions have convexity and monotonicity properties in the state and lose smoothness at queue-clearing boundaries.

  • Queueing model: The system has K classes with Poisson arrivals, exponential service rates, and linear holding costs, ordered by decreasing h_kμ_k indices.The ordering avoids ties in the fluid analysis and supports the structural policy characterization.
  • Queueing model: At each decision epoch, a manager assigns servers to customer classes, with assignments fixed for a period of length δ over a finite horizon T.There are n(δ) = ⌈T/δ⌉ decision epochs, and service within each class follows a non-idling FCFS policy.
  • Fluid approximation: The fluid approximation permits arbitrary fractions of aggregate capacity across classes, making it a continuous-allocation relaxation of integer server assignments.The approximation is considered under the conventional heavy-traffic framework and is used because the stochastic value function is not tractable.
  • Fluid control formulation: The period-dependent transition function maps the current state, action, and review-period length δ to the next-period state, while the single-period cost maps state and action to cost.The finite-horizon dynamic program uses these functions to define optimal cost-to-go values and Bellman recursions.
  • Regularity boundaries: Smoothness can fail when a queue clears exactly at a period endpoint or starts empty and receives insufficient capacity.The single-period cost remains continuously differentiable at endpoint clearing, but twice continuous differentiability fails there.
  • Value-function properties: For fixed δ, the dynamic-program objective is convex in state and action, and the value function is convex and componentwise nondecreasing in the state.These properties follow from convexity of the period cost and transition structure.

3. Structure of the Optimal Fluid Policy

The optimal fluid policy prioritizes classes by descending cμ index while satisfying lower bounds needed to prevent avoidable idleness. Discrete review periods can alter the trajectory substantially relative to continuous-time control, especially when concentrating capacity would create idleness.

  • Optimal allocation structure: Theorem 1 establishes lower bounds on allocations to the first K−1 classes when h₁μ₁ > h₂μ₂ > ··· > h_Kμ_K.Each lower bound is the capacity needed to empty a class during the period after accounting for higher-priority allocations.
  • Optimal allocation structure: The lower-bound result generalizes an earlier two-class result to multiple classes under a conventional heavy-traffic regime, using a different proof approach.The paper uses an induction argument and exchange improvements rather than implicit differentiation of optimality equations.
  • Optimal allocation structure: Whenever extra allocation to a class does not create idleness, optimal policies allocate it before capacity goes to classes with lower cμ indexes.Once idleness occurs, additional allocation requires trading off diminishing holding-cost reductions against benefits for lower-priority classes.
  • Numerical illustration: For the illustrated system, continuous-time control empties class 1 at t=9.4, whereas discrete control with δ=25 empties it at t=16.2 and serves class 2 during the first period.Under continuous-time control, all capacity initially serves class 1; under discrete control, doing so would create suboptimal idleness.
  • Proof strategy: The proof combines a single-period lower bound with an exchange argument that preserves future-state feasibility across periods.Induction extends the bound from the continuation problem to the first period.

4. First- and Second-Order Sensitivity Analysis

The sensitivity analysis treats review-period length as a parameter in a sequence of local nonlinear programs and characterizes value-function derivatives under regularity conditions. These smoothness results fail at queue-clearing boundaries and other points where constraint regularity can break down.

  • Local sensitivity setup: The analysis fixes a reference review length δ₀ and studies a selected optimal trajectory as δ varies locally around δ₀.Active and inactive nonnegativity constraints are tracked along the base optimizer.
  • Optimality conditions: The dynamic program represents each period as a nonlinear optimization problem with state, allocation, feasibility, and continuation-value terms.The first-period Lagrangian and KKT conditions provide the local optimality framework.
  • Regularity conditions: Under LICQ, strict complementary slackness, and SOSC, the primal-dual optimizer is locally unique and C1, while the local value function is C2.The active inequality set remains fixed locally under these assumptions.
  • Regularity conditions: The required C2 smoothness fails when a class empties exactly at the end of a period or starts empty and receives capacity to remain empty.Other failures can arise from strict-complementary-slackness and second-order sufficient-condition violations.
  • Reduced problems: Maintained-empty classes are fixed at zero in reduced period problems, leaving the remaining state and allocation coordinates as optimization variables.This reduction reflects the active structure of the base optimal trajectory.

Appendix EC.2 we demonstrate this for the single-stage cost.

At regular review lengths, the reduced Bellman problems have stable smooth optimal solutions, enabling first- and second-order derivatives of the value function. The sensitivity formulas rely on envelope and differentiated KKT arguments.

  • A regular point keeps the period count, smooth pieces, active sets, and cutoff choices locally unchanged.These conditions exclude period-count, endpoint-clearing, and cutoff-tie boundaries.
  • Proposition 4 gives a unique locally stable optimizer with C1 dependence, locally constant active constraints, and a C2 value function.
  • The first derivative of the value function exists at regular points and does not require differentiating the optimal policy.
  • The second derivative follows by differentiating the first-order envelope expression along the differentiable optimal trajectory.
  • KKT cancellation and differentiated stationarity identities provide the optimizer-sensitivity terms used in the two-class formulas.
  • The sensitivity results do not apply when a positive queue clears exactly at a period endpoint, although those cases are treated directly later.

5. The Two-Class Case

The two-class analysis partitions review lengths into regions determined by when class 1 clears and how the optimal allocation changes. Value sensitivity is nonmonotone for short periods but becomes increasing for sufficiently larger periods, with region-dependent curvature.

  • Definitions and Overview of the Results: Three regions arise from thresholds ˜δ and ˆδ: before class-1 clearing, during the transition, and after the optimal first-period allocation changes.Region 1 is (0,˜δ], Region 2 is (˜δ,ˆδ], and Region 3 is (ˆδ,T].
  • Region 1: In Region 1, the value function can be non-monotone because discrete review epochs may miss the timing needed to reproduce continuous-time trajectories.When δ divides the relevant clearing time, the continuous-time trajectories can be attained and produce low-cost valleys.
  • Region 1: At review lengths δ∈{4,8,16}, continuous-time trajectories are attainable, whereas δ∈{6,14} produces different optimal trajectories.
  • Regions 2 and 3: For δ∈(˜δ,T), the value function is increasing wherever its derivative exists.
  • Regions 2 and 3: Endpoint-clearing intervals can make the value function locally linear, while the Region 2–Region 3 cutoff may create a first-order kink.
  • Regions 2 and 3: In Region 2, the value function is strictly convex when class 2 clears before T and strictly concave when it does not.

1. Clearing class 1 right at the end of the first period,

When class 1 is optimally cleared exactly at the end of the first period, the value function has a distinctive local structure. This regime can produce linearity, while larger review lengths eventually yield concavity.

  • Endpoint-clearing analysis depends on whether class 2 remains positive or clears by the terminal time.
  • Endpoint clearing can remain optimal over an open interval of review lengths, not merely at a single threshold.
  • If endpoint clearing is optimal for some δ>˜δ, the first derivative is constant and the value function is locally linear.
  • The value function may be convex or linear over some review lengths, but it is eventually concave for sufficiently large δ.

6. More than Two Classes

The multi-class fluid problem retains key two-class sensitivity patterns but adds richer trajectory-matching constraints. Review-length oscillations can remain nonmonotone, while smooth regimes recover increasing and convex–concave behavior.

  • For more than two classes, the value function can also be non-monotone in the review length.
  • In a three-class example, oscillation valleys are unequal and peaks do not increase successively.
  • At plotted nondifferentiable review lengths, the value function fails to be differentiable when review epochs can coincide with class-clearing times.
  • Continuous-time trajectories may be impossible to match exactly because no single positive review length divides all class-clearing times.Different review lengths can nevertheless produce closer approximations, generating value-function oscillations.
  • On smooth intervals where classes 1 through K−1 clear before the first period ends and class K remains positive, the value function is increasing.
  • Within that regime, curvature is concave if class K does not clear by T; if it does, curvature depends on whether class K receives first-period capacity.

7. Numerical Study

The numerical study examines how review-period length affects fluid and stochastic scheduling value functions across parameter regimes. It finds systematic curvature patterns in the fluid model and qualitatively similar, smoother behavior in stochastic systems.

  • Study design: The experiments vary review-period length, utilization, load ratio, and cμ-index ratio to study value-function structure and stochastic generalization.The stochastic problem is formulated as a finite-horizon discrete-time MDP, with simulation used because transient transition probabilities cannot be obtained explicitly.
  • Fluid-model sensitivity: Higher ν does not always imply a larger relative cost increase: at sufficiently high utilization and load ratio, ν=20 can fall below ν=5 and ν=2.For (ρ,r)=(0.9,2), the ν=20 system has a lower relative cost increase than the ν=5 system, and for r=2 it can fall below ν=2.
  • Stochastic robustness: Stochasticity smooths small-scale non-monotonicity, while larger scaling recovers the fluid model’s curvature regions and brings values closer to continuous-allocation fluid values.At η=1 the stochastic value function appears monotone and concave, whereas non-monotonicity and initial convexity appear for η∈{5,10}.

8. Conclusions

The paper studies sensitivity of multiclass scheduling value to the review period through associated fluid control problems and derivative analysis. It shows that short-period value need not be monotone, while larger periods produce structured monotonicity and curvature, with stochastic effects smoothing the smallest-scale behavior.

  • Contributions: The paper analyzes review-period sensitivity by characterizing first- and second-order derivatives of the associated fluid value function.The derivatives are used to identify monotonicity and curvature regimes.
  • Main findings: For small review periods, the value function need not be monotone because review-epoch timing matters beyond control frequency alone.This behavior reflects the interaction between review timing and system clearing dynamics.
  • Main findings: Once the review period is large enough for class 1 to clear in the first period, the two-class value function increases with the review period.Its curvature can be linear, strictly convex, or strictly concave before becoming concave near the no-control regime.
  • Interpretation: When the high-priority class clears quickly, within-period class-1 idleness and lower-priority buildup reduce flexibility and increase the value of more frequent control.This mechanism links priority asymmetry to review-period sensitivity.
  • Stochastic extension: Stochastic experiments retain the fluid model’s broad structure but smooth its initial non-monotonicity because random clearing times weaken exact epoch alignment.The stochastic and fluid results therefore agree qualitatively while differing at smaller scales.
  • Scope and future work: The study identifies sensitivity questions for other queueing controls, including service rates, staffing, routing, and pricing.It also notes that finite-horizon stochastic dynamic programming remains challenging because transition probabilities depend on the review period.

Proofs

The proofs establish regularity and structural properties of the fluid value function through convexity, monotonicity, differentiability, and backward induction. These properties support the sensitivity analysis and curvature results.

  • Regularity: The one-period cost function is jointly convex and continuously differentiable in state, allocation, and review-period length.The proof uses positive-part representations and integration over the review period.
  • Regularity: Away from nondifferentiability boundaries, the one-period cost is twice continuously differentiable in the relevant variables.Locally, positive-part terms are either active affine functions or identically zero.
  • Value-function structure: Backward induction preserves convexity and componentwise monotonicity of the value function across periods.Partial minimization over the convex feasible allocation set preserves both structural properties.
  • Value-function structure: The resulting value function is componentwise nondecreasing in the initial queue state.This conclusion follows by comparing every feasible allocation at ordered initial states.
  • Value-function structure: The induction step combines convex stage costs, monotone convex state transitions, and a convex monotone continuation value.Taking the pointwise minimum over feasible allocations then yields a componentwise nondecreasing value function.

EC.1.1. Proofs for Theorem 1

The appendix proofs establish structural properties of optimal allocations by constructing local policy improvements and analyzing smooth optimization regimes. The arguments use capacity shifts, monotonicity of continuation values, and second-order conditions.

  • Policy perturbations: The proof compares a candidate policy with a perturbed policy that shifts capacity between two classes while preserving feasibility.The comparison treats separately whether the affected class clears during the next period.
  • Case analysis: If the affected class clears in period 2, the perturbed policy clears it at the same time while assigning freed capacity to the other class.The resulting state is weakly smaller after period 2, so monotonicity bounds the continuation cost.
  • Optimality contradiction: Under the strict priority condition h_jμ_j>h_mμ_m, the perturbed policy achieves strictly lower cost, contradicting optimality of the original policy.This conclusion closes both clearing and non-clearing cases.
  • Case analysis: If the affected class does not clear in period 2, a period-2 repair offsets the period-1 perturbation and weakly reduces the later state.The proof compares period-1 and period-2 costs and invokes continuation-value monotonicity.
  • Smooth sensitivity regime: The smooth-regime proof uses affine reduced constraints, LICQ, strict complementarity, and second-order sufficiency to obtain a locally unique C^1 optimizer and C^2 value.Convexity then supports the local value-function characterization.

EC.1.2. Proofs for Theorem 8

The paper derives first- and second-derivative formulas for multiclass fluid scheduling across clearing regimes, then examines their implications numerically. The results show regime-dependent curvature, eventual monotonicity for sufficiently large review periods, and similar qualitative patterns in stochastic systems.

  • Derivative formulas: The multiclass analysis extends the two-class case by deriving first- and second-derivative formulas when the first K−1 classes clear during the initial review period.The K=2 condition reduces to class 1 clearing during the first period.
  • Fluid-model implications: For a four-class fluid system, the value function is nondifferentiable at divisors of the clearing thresholds and becomes monotone once three classes optimally clear during the first period.The nondifferentiability occurs at countably many threshold-related review lengths.
  • Additional fluid experiments: Across fluid experiments, systems with lower cost ratios generally have smaller relative cost increases as review intervals lengthen, but high-cost-ratio systems can fall below them at sufficiently small intervals.This reversal is associated with a convex region in the high-cost-ratio systems.
  • Additional fluid experiments: Curvature varies by cost ratio: ν=2 systems are initially linear before becoming concave, ν=5 systems are generally concave, and ν=20 systems can contain a convex region when class 2 clears within the horizon.These patterns persist across systems with unequal service rates.
  • Stochastic robustness: Stochastic-system sensitivity curves remain almost identical under increased sample counts or system-size caps, with minimal changes in scaled value functions as review length varies.The experiments suggest the selected caps are large enough that almost no arrivals are rejected.
Loading 2608.29398v1…