Online MapReduce scheduling problem of minimizing the makespan |
| |
Authors: | Cong Chen Yinfeng Xu Yuqing Zhu Chengyu Sun |
| |
Institution: | 1.School of Management,Xi’an Jiaotong University,Xi’an,China;2.The State Key Lab for Manufacturing Systems Engineering,Xi’an,China;3.Department of Computer Science,California State University,Los Angeles,USA |
| |
Abstract: | MapReduce system is a popular big data processing framework, and the performance of it is closely related to the efficiency of the centralized scheduler. In practice, the centralized scheduler often has little information in advance, which means each job may be known only after being released. In this paper, hence, we consider the online MapReduce scheduling problem of minimizing the makespan, where jobs are released over time. Both preemptive and non-preemptive version of the problem are considered. In addition, we assume that reduce tasks cannot be parallelized because they are often complex and hard to be decomposed. For the non-preemptive version, we prove the lower bound is \(\frac{m+m(\Psi (m)-\Psi (k))}{k+m(\Psi (m)-\Psi (k))}\), higher than the basic online machine scheduling problem, where k is the root of the equation \(k=\big \lfloor {\frac{m-k}{1+\Psi (m)-\Psi (k)}+1 }\big \rfloor \) and m is the quantity of machines. Then we devise an \((2-\frac{1}{m})\)-competitive online algorithm called MF-LPT (Map First-Longest Processing Time) based on the LPT. For the preemptive version, we present a 1-competitive algorithm for two machines. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|