On-line scheduling of parallel jobs on two machines

We study the problem of on-line scheduling of parallel jobs on two machines. The jobs are parallel in the sense that each of them specifies the number of processors, in this case 1 or 2, required for simultaneous processing. The jobs are presented one by one. Upon receiving a job, we must assign the job to a time slot in the schedule before the next job is presented. No re-assignment is allowed. The goal is to minimize the makespan of the final schedule. There is a straightforward algorithm which achieves a competitive ratio of 2. In this paper we show that no on-line algorithm can have a competitive ratio less than 1+2/3(≈1.816)(≈1.816). We also study two special cases of the problem: (i) Jobs arrive in a non-decreasing order of processing times where we give an optimal algorithm with competitive ratio 3/2; (ii) Jobs arrive in a non-increasing order of processing times where we show that no on-line algorithm has a competitive ratio less than 9/7 and give a greedy algorithm with a competitive ratio 4/3.