Online scheduling of malleable parallel jobs with setup times on two identical machines

In this paper we consider online scheduling of malleable parallel jobs on two identical machines, where jobs arrive over time. Each job Jj has an execution time tj=pj/kj+(kj-1)cj when it is processed on kj machines, where pj>0 and cj>0 are the length and setup time of job Jj. The objective is to minimize the makespan. For the problem with two machines, we present an online algorithm with competitive ratio of 1+[alpha], where . We show that 1+[alpha] is a lower bound on the competitive ratio of any online algorithm for the problem with machines. So our algorithm is optimal for the case of two machines.