We consider a distributed online scheduling problem with deadlines. Assuming stationary Poisson job-arrivals, we show that Exact Scheduling minimizes the stationary variance of service capacity among distributed algorithms. Exact Scheduling works by finishing jobs exactly at their deadlines using constant speeds and is thus easy to implement in large-scale systems. When jobs have soft deadlines, we show a variation of Exact Scheduling minimizes the stationary variance. This variation works by serving each job at a constant speed which is determined by a function of its attributes. Finally, we show a performance lower bound for the optimal (centralized) algorithms and compare it with the performance of the optimal distributed algorithms.