Service Rate Control For Jobs with Decaying Value

Neal Master, Nicholas Bambos

Abstract

The task of completing jobs with decaying value arises in a number of application areas including healthcare operations, communications engineering, and perishable inventory control. We consider a system in which a single server completes a finite sequence of jobs in discrete time while a controller dynamically adjusts the service rate. During service, the value of the job decays so that a greater reward is received for having shorter service times. We incorporate a non-decreasing cost for holding jobs and a non-decreasing cost on the service rate. The controller aims to minimize the total cost of servicing the set of jobs. We show that the optimal policy is non-decreasing in the number of jobs remaining—when there are more jobs in the system the controller should use a higher service rate. The optimal policy does not necessarily vary monotonically with the residual job value, but we give algebraic conditions which can be used to determine when it does. These conditions are interesting because they can be verified without using algorithms like value iteration and policy iteration to explicitly compute the optimal policy.

Introduction

In many real-world systems, a "job" is not a static entity; its utility drops the longer it remains in the system. Examples include patients whose health declines while waiting for treatment, perishable food items nearing expiration, or video packets that become useless if they arrive too late for display. A system controller must decide how much effort (and cost) to expend on completing these jobs. Speeding up service reduces decay time and clears backlogs faster, but higher service rates typically incur increased operational costs. This paper seeks the optimal policy that minimizes total costs, combining holding costs, service costs, and the loss of job value.

Methodology

The system is modeled as a discrete-time Markov Decision Process (MDP), specifically a Stochastic Shortest Path (SSP) problem. The state space is defined by the backlog ($b$) and the residual value ($v$) of the current job. The controller chooses a service probability (the rate) for each time slot. To analyze the structure of the optimal policy without relying solely on brute-force computation, the authors employ submodularity and Topkis’s Theorem. These mathematical tools allow them to prove how the optimal service rate changes as the system state evolves.

Structural Properties of the Optimal Policy

Two key insights emerge regarding the structure of the optimal service rate:

  1. The Backlog Rule: The authors formally prove that the optimal policy is always non-decreasing in the number of jobs. If the queue length increases, the server should always "try harder" to clear it, regardless of the current job's value.
  2. Value Sensitivity: Unlike backlog, the relationship between service rate and job value is not always monotonic. In some scenarios, as a job's value drops, the server speeds up to "save" the remaining reward. In others, the reward becomes so small that it is no longer worth the high cost of fast service, and the server "gives up," slowing down to save on service costs.
Optimal service rate policies across different reward and cost structures, illustrating monotonic and non-monotonic behaviors relative to job value and backlog.

As visualized in Figure 3, these different regimes (monotonic vs. non-monotonic) are determined by the specific decay profiles and cost structures of the system.

Algebraic Conditions for Monotonicity

A practical contribution of this research is a set of algebraic conditions (Theorems 2 and 3). These allow researchers to determine if an optimal policy will be monotonic (increasing or decreasing) based on the system's cost and reward functions without solving complex Bellman equations via value iteration. In the common case where a job has a constant value until a deadline (a step function), the optimal policy's behavior reduces to a single, simple inequality.

Conclusion and Future Work

While the current model provides a strong theoretical foundation, it assumes a finite, static set of identical jobs. Real-world queues often involve stochastic arrivals and heterogeneous jobs with varying urgency levels. Future work could explore these complexities, as well as extending the model to continuous-time Markov chains to provide more granularity for high-speed engineering applications.

Summary updated

Abstract

The task of completing jobs with decaying value arises in a number of application areas including healthcare operations, communications engineering, and perishable inventory control. We consider a system in which a single server completes a finite sequence of jobs in discrete time while a controller dynamically adjusts the service rate. During service, the value of the job decays so that a greater reward is received for having shorter service times. We incorporate a non-decreasing cost for holding jobs and a non-decreasing cost on the service rate. The controller aims to minimize the total cost of servicing the set of jobs. We show that the optimal policy is non-decreasing in the number of jobs remaining -- when there are more jobs in the system the controller should use a higher service rate. The optimal policy does not necessarily vary monotonically with the residual job value, but we give algebraic conditions which can be used to determine when it does. These conditions are then simplified in the case that the reward for completion is constant when the job has positive value and zero otherwise. These algebraic conditions are interesting because they can be verified without using algorithms like value iteration and policy iteration to explicitly compute the optimal policy. We also discuss some future modeling extensions.
BibTeX
@inproceedings{master2015service,
  author = {Neal Master and Nicholas Bambos},
  title = {{Service Rate Control For Jobs with Decaying Value}},
  booktitle = {ACC},
  year = {2015},
  url = {https://openreview.net/forum?id=SGdTL7B_zmZ},
}
Figure