Exact Certificate-Aware Nonpreemptive Scheduling with General Availability Calendars and Additive-Frequency Bounds

Abstract

Nonpreemptive scheduling under fragmented availability is governed by contiguous feasible intervals rather than total available time. We study rational single-machine calendars with arbitrary downtime and the arithmetic subclass defined by the three coupled frequencies a, b, a + b. An exact subset dynamic program maximizes the total weight of heterogeneous jobs with individual release times, deadlines, and processing durations; a proof establishes that retaining only the earliest completion time for each selected subset preserves optimality. An independent checker validates rational schedules, while exact recomputation provides a finite, although exponential, optimality check. For the additive subclass, we establish the sharp availability inequality μ(S(a, b)) ≥ 13/20 by combining a torus integral, an explicit grid-discrepancy bound, and exhaustive integer-arithmetic verification of all 11,698 primitive pairs below the analytic cutoff; equality occurs at (1, 14). This yields a certified uninterrupted interval of length at least 13/[40(a + b)], while distinguishing individual job feasibility from simultaneous schedulability. The implementation integrates exact calendar normalization, constructive admission, a restricted packing formula, certificate verification, and bounded timing-translation analysis. Exhaustive small-instance comparisons validate the generalized optimizer’s results, providing computational support for the exact scheduling framework.