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 JjJj has an execution time tj=pj/kj+(kj-1)cjtj=pj/kj+(kj-1)cj when it is processed on kjkj machines, where pj>0pj>0 and cj>0cj>0 are the length and setup time of job JjJj. The objective is to minimize the makespan. For the problem with two machines, we present an online algorithm with competitive ratio of 1+α1+α, where α=(5-1)/2. We show that 1+α1+α is a lower bound on the competitive ratio of any online algorithm for the problem with m(m⩾2) machines. So our algorithm is optimal for the case of two machines.