Before revision: In this paper we study a single machine scheduling problem on a set of independent jobs whose execution time is not known, but guaranteed to be either short or long , for two given processing times. At every time step, the scheduler has the possibility either to test a job, by querying a processing time oracle , which reveals its processing time , and occupies one time unit on the schedule .
After revision: In this paper we study a single machine scheduling problem on a set of independent jobs whose execution time is not known, but guaranteed to be either short or long . This information is necessary to produce the optimal schedule. However it is initially hidden to the algorithm, only the execution of a processing time oracle , which reveals its processing time , and occupies one time unit on the schedule .