Index rules achieve exact ratios for scheduling tasks with testing
Exact Competitive Ratios of Index Rules for Scheduling with Obligatory Testing
Data Structures and Algorithms
Summary
Scheduling tasks that need a test before the main job is tricky because the time needed after the test is unknown beforehand. The authors found a new way to simplify these scheduling problems so they can calculate precise performance numbers for certain scheduling methods, called index rules. They proved that one simple scheduling method called 1-SORT performs exactly as well as the Golden Ratio, improving on previous estimates. They also studied a random scheduling approach and found close-to-best performance bounds when all tests take the same amount of time.
What this means in practice
- •For manufacturing schedulers: Schedule manufacturing jobs requiring upfront testing to minimize overall completion time using precisely analyzed index rules.
- •For cloud resource managers: Improve task scheduling in cloud systems where job runtimes are uncertain until initial test phases complete.
Authors
Felix Buld
Abstract
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.