| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427388 | Information Processing Letters | 2010 | 5 Pages |
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.
