Scholarlink

<p>The rapid growth of cloud computing has introduced new challenges to classical Parallel Batch Machine Scheduling (PBMS) models. This paper addresses the limitations of traditional PBMS frameworks characterized by fixed job widths and mandatory job acceptance by proposing PBMSMR (Parallel Batch Machine Scheduling with Malleable Jobs and Rejection). This extended framework incorporates two critical features for modern computing environments: malleable jobs with dynamically adjustable widths and constrained job rejection under a penalty threshold. Observing its NP-hardness, we formulate PBMSMR through a mixed-integer programming model and devise an approximation algorithm that combines greedy job reordering with iterative elimination. The algorithm minimizes the objective function while satisfying rejection constraints, achieving a time complexity of <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(O(n^2\log n)\)</EquationSource> </InlineEquation> and an approximation ratio of <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\((4-\frac{2}{Km})\)</EquationSource> </InlineEquation>, where <i>K</i> and <i>m</i> are the machine capacity and the number of machines, respectively. For jobs with identical release times, we fine-tune the algorithm to achieve an improved ratio of <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\((3 + \frac{2(K-1)}{Km})\)</EquationSource> </InlineEquation>. Lastly, we carry out experiments to demonstrate the effectiveness of our approach in balancing solution quality and runtime efficiency.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Fast approximation for scheduling malleable jobs on parallel batch machines with rejection

  • 期刊论文

  • 发表日期：

    2025年12月8日

查看全文
  • Longkun Guo,
  • Fenghe Xia,
  • Xiaoyan Zhang

摘要

The rapid growth of cloud computing has introduced new challenges to classical Parallel Batch Machine Scheduling (PBMS) models. This paper addresses the limitations of traditional PBMS frameworks characterized by fixed job widths and mandatory job acceptance by proposing PBMSMR (Parallel Batch Machine Scheduling with Malleable Jobs and Rejection). This extended framework incorporates two critical features for modern computing environments: malleable jobs with dynamically adjustable widths and constrained job rejection under a penalty threshold. Observing its NP-hardness, we formulate PBMSMR through a mixed-integer programming model and devise an approximation algorithm that combines greedy job reordering with iterative elimination. The algorithm minimizes the objective function while satisfying rejection constraints, achieving a time complexity of \(O(n^2\log n)\) and an approximation ratio of \((4-\frac{2}{Km})\) , where K and m are the machine capacity and the number of machines, respectively. For jobs with identical release times, we fine-tune the algorithm to achieve an improved ratio of \((3 + \frac{2(K-1)}{Km})\) . Lastly, we carry out experiments to demonstrate the effectiveness of our approach in balancing solution quality and runtime efficiency.