On-line multi-threaded scheduling

This paper presents results on on-line scheduling problems with multiple threads. The jobs are organized in a number of sequences called threads. Each job becomes available (is presented) only at the moment a scheduling decision is made on all the preceding jobs in the same thread. Thus, apart from decisions on scheduling of jobs also decisions are required on the order of exploring the threads. We consider two different on-line paradigms. The first paradigm can be regarded as constructing, in an on-line way, a schedule of the jobs which is to be executed later, a sort of batch process. The other paradigm models a real-time planning situation, in which the jobs are immediately executed at the moment they are assigned to a machine. We study two classical objective functions: the makespan defined as the maximum completion time of the jobs, and the average completion time of the jobs, also called the latency of the jobs. We establish a fairly complete set of results for these on-line multithreaded scheduling problems. One of the highlights of our results is that List Scheduling is an optimal algorithm for the makespan problem under the real-time on-line model if the number of machines does not exceed the number of threads. Another one is that for the latency problem on a single machine under both on-line paradigms there exists a non-trivial algorithm that is best possible and has competitive ratio equal to the number of threads