کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427388 | 686499 | 2010 | 5 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Online malleable job scheduling for m⩽3m⩽3 Online malleable job scheduling for m⩽3m⩽3](/preview/png/427388.png)
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.
Journal: Information Processing Letters - Volume 111, Issue 1, 15 December 2010, Pages 31–35