Scheduling parallel jobs on heterogeneous platforms

详细信息    查看全文

• 作者：Klaus Jansen¹ ; ^{kj@informatik.uni-kiel.de" class="auth_mail" title="E-mail the corresponding author}
• 关键词：scheduling parallel tasks ; strip packing ; approximation algorithms
• 刊名：Electronic Notes in Discrete Mathematics
• 出版年：2016
• 出版时间：November 2016
• 年：2016
• 卷：55
• 期：Complete
• 页码：9-12
• 全文大小：172 K

文摘

We consider the problem of scheduling parallel jobs on heterogeneous platforms. Given a set J$\mathcal{J}$ of n jobs where each job j∈J$j\in \mathcal{J}$ is described by a pair (p_j$p_j$, 22ebc1c69df8f7059e99c83a01eb5b3" title="Click to view the MathML source">q_j$q_j$) with a processing time p_j$p_j$ and number 22ebc1c69df8f7059e99c83a01eb5b3" title="Click to view the MathML source">q_j$q_j$ of processors required and a set of N   heterogeneous platforms P_i$P_i$ with e678e" title="Click to view the MathML source">m_i$m_i$ processors, the goal is to find a schedule for all jobs on the platforms minimizing the maximum completion time. The problem is directly related to a two-dimensional multi strip packing problem. Unless P=NP$P=NP$ there is no approximation algorithm with absolute ratio better than 2 for the problem. We propose an approximation algorithm with absolute ratio 2 improving the previously best known approximation algorithms. This closes the gap between the lower bound of <2 and the best approximation ratio.