The subject disclosure is directed towards scheduling jobs with a speed for running a processor(s) having variable speeds to save energy yet complete in time, in which the volume of the job is not known in advance, that is, in a non-clairvoyant setting. A non-clairvoyant algorithm uses an existing clairvoyant algorithm to determine the speed based upon information known from running one or more jobs, in full or in part. Also described is rounding jobs based upon their densities into rounding queues so that a hybrid of highest density first rules and FIFO rules may be used to obtain information used by the clairvoyant algorithm.