"If the Total Workload Is 5/6 or Less, Deadlines Can Always Be Met": A 1993 Conjecture Proven After 30 Years (Kyoto University)

Explanation

Associate Professor Akitoshi Kawamura and Associate Professor Yusuke Kobayashi of the Research Institute for Mathematical Sciences, Kyoto University, announced on August 17, 2026, that they had used mathematics and computers to prove a conjecture that had remained unsolved for over 30 years regarding the "pinwheel scheduling" problem, in which multiple periodic tasks are performed in sequence using a single resource. Part of the results was published online in the Proceedings of the National Academy of Sciences (PNAS) on August 7, 2026.

Pinwheel scheduling asks whether, under the condition that "each of multiple periodic tasks must be executed at least once every XX days (or XX milliseconds)," all tasks can be executed sequentially using a single resource. For the "packing" type, in which tasks are packed without gaps, the "5/6 conjecture" — which states that scheduling is always possible if the total workload (density) is 5/6 (approximately 83.3%) or less — had been a theoretical challenge since it was proposed in 1993, but this conjecture has now been proven correct.

For the "covering" type, the opposite of the packing type, which sets an upper limit on frequency, the team also identified and proved that the best density bound is approximately 1.264. The research team says it carried out the proof by combining mathematical analysis with computer-assisted exhaustive search, and that the results provide theoretical guarantees for the allocation of time-constrained tasks such as embedded control, communication processing, and robot patrol scheduling.