Scholarlink

<p>In practice, the cost of delaying a job can grow as the job waits. Such behavior is modeled by the time-varying holding cost (TVHC) problem, where each job’s instantaneous holding cost increases with its current age (a job’s age is the time since it arrived). The goal of the TVHC problem is to find a scheduling policy that minimizes the time-average total holding cost across all jobs. However, no optimality results are known for the TVHC problem outside of the asymptotic regime. In this paper, we study a simple yet still challenging special case: A two-class M/M/1 queue in which class 1 jobs incur a non-decreasing, time-varying holding cost and class 2 jobs incur a constant holding cost. Our main contribution is deriving the first optimal (non-decreasing) index policy for this special case of the TVHC problem. Our optimal policy, called LookAhead, stems from the following idea: Rather than considering each job’s <i>current</i> holding cost when making scheduling decisions, we should look at their cost some <i>X</i> time into the future, where this <i>X</i> is intuitively called the “lookahead amount." This paper derives that optimal lookahead amount.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

LookAhead: the optimal non-decreasing index policy for a time-varying holding cost problem

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年1月19日

查看全文
  • Keerthana Gurushankar,
  • Zhouzi Li,
  • Mor Harchol-Balter,
  • Alan Scheller-Wolf

摘要

In practice, the cost of delaying a job can grow as the job waits. Such behavior is modeled by the time-varying holding cost (TVHC) problem, where each job’s instantaneous holding cost increases with its current age (a job’s age is the time since it arrived). The goal of the TVHC problem is to find a scheduling policy that minimizes the time-average total holding cost across all jobs. However, no optimality results are known for the TVHC problem outside of the asymptotic regime. In this paper, we study a simple yet still challenging special case: A two-class M/M/1 queue in which class 1 jobs incur a non-decreasing, time-varying holding cost and class 2 jobs incur a constant holding cost. Our main contribution is deriving the first optimal (non-decreasing) index policy for this special case of the TVHC problem. Our optimal policy, called LookAhead, stems from the following idea: Rather than considering each job’s current holding cost when making scheduling decisions, we should look at their cost some X time into the future, where this X is intuitively called the “lookahead amount." This paper derives that optimal lookahead amount.