Abstract.  We consider the problem of scheduling jobs with deadlines in an on-line single-processor system. It is known for long that unless the system is underloaded, any on-line algorithm is not optimal in the sense that it may fail to match the optimal offline algorithm on the total work of jobs meeting their deadlines. In this paper, we extend this fact with two new lower bound results. First, we show that even if the on-line scheduler can use a processor s times faster than the offline scheduler, where s ≥ 1 is any real number less than the golden ratio (i.e. (1+√5)/2 ≈ 1.618), no on-line algorithm can be optimal. Furthermore, if we restrict our attention to on-line algorithms that decide at the release time of a job whether the job will be processed to meet its deadline, then the speed requirement for optimal on-line algorithms is at least 2. These lower bound results should be contrasted with the recent upper bound result that with a two times faster processor, a simple extension of the earliest deadline first strategy (EDF) is optimal.