带强制测试的调度中索引规则的精确竞争比
Exact Competitive Ratios of Index Rules for Scheduling with Obligatory Testing
Felix Buld
AI 速览：作者提出一种保持竞争比的实例归约方法，精确计算了1-SORT等索引规则在带强制测试调度中的竞争比，证明1-SORT的竞争比恰为黄金比例φ≈1.618。
We revisit scheduling with obligatory testing, where each job consists of two operations: a test with an initially known time and an operation whose processing time is revealed upon completion of the job's test. We develop an iterative competitive-ratio-preserving instance-reduction method that enables us to compute exact competitive ratios directly on highly structured instances for various index rules. Our main result is a clean analysis showing that the competitive ratio of the algorithm $1$-SORT is exactly the Golden Ratio $\varphi\approx 1.618$, improving the recent best-known upper bound of $1.861$ for arbitrary testing times. We further leverage this method to obtain near-tight bounds for a simple randomized algorithm on instances with uniform testing times.