Proof of the density threshold conjecture for pinwheel scheduling

Area of Science:

• Computer Science
• Operations Research
• Real-Time Systems

Background:

• The pinwheel scheduling problem requires tasks with periods to be scheduled daily, ensuring each task meets its deadline.
• A necessary condition for schedulability is that the sum of task execution rates (density) must not exceed 1.

Purpose of the Study:

• To prove that all instances of the pinwheel scheduling problem with a density not exceeding 5/6 are schedulable.
• To address the conjecture proposed by Chan and Chin in 1993.

Main Methods:

• The proof involves a computer search for schedules across a large, finite set of instances.
• Generalization of the pinwheel problem to fractional periods was a key step in reducing the problem to finite cases.

Main Results:

• All instances of the pinwheel scheduling problem with density up to 5/6 are proven to be schedulable.
• A simple proof for the schedulability of instances with two distinct periods and density at most 1 was developed.
• A fast algorithm for the bamboo garden trimming problem with a 4/3 approximation ratio was obtained.

Conclusions:

• The 5/6 density bound for the pinwheel scheduling problem is established, confirming the Chan and Chin conjecture.
• The methods developed offer new insights into scheduling theory and related problems.
• The study provides practical algorithms with proven performance guarantees.