Online malleable job scheduling for m⩽3m⩽3

A malleable parallel job is one that may be assigned to any number of processors in a parallel computing environment. In our particular problem, we assume that the execution time of a job j   with processing requirement pjpj is pj/kj+(kj−1)cpj/kj+(kj−1)c if the job is assigned to kj∈{1,2,…,m}kj∈{1,2,…,m} processors, where c is a constant representing overhead and m   is the number of processors. Given a sequence of jobs, an online algorithm must assign to each job, as it arrives, both a number of processors and a start time to minimize the makespan of the schedule. We provide online algorithms for m=2m=2 and m=3m=3 with asymptotically optimal competitive ratios of 3/2 and 5/3, respectively. We also provide a similar online algorithm for the more general problem with job dependent overhead term cjcj that has optimal competitive ratio ϕ=(1+5)/2 when m=2m=2.

Research highlights
► A job with length p   has execution time p/k+(k−1)cp/k+(k−1)c if assigned to k   processors.
► Asymptotically optimal online algorithms are presented for m⩽3m⩽3 machines.
► An optimal online algorithm for variable cjcj is also presented for m=2m=2.