Scholarlink

<p>We consider scheduling problems of processing a given set of independent jobs on parallel p-batch machines subject to arbitrary processing set restrictions (PSR). Two types of p-batch machines are considered: equal-speed and uniform. For the corresponding <i>P</i>- and <i>Q</i>-problems, efficient (strongly polynomial) approximation algorithms with a priori and a posteriori absolute and relative accuracy bounds have been designed. The presented results are the first attempt of an approximate solution of a that general problem (with arbitrary PSR and individual batch capacities of machines) in a strongly polynomial time and with performance ratios strictly less than two. As an auxiliary result, we have developed a new (linear-time) rounding algorithm for a given fractional distribution of jobs by machines in a tree-like graph.</p>

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

Efficient approximation algorithms for scheduling problems with uniform p-batch machines and arbitrary processing set restrictions

  • 期刊论文

  • 发表日期：

    2025年12月22日

查看全文
  • Sergey Sevastyanov

摘要

We consider scheduling problems of processing a given set of independent jobs on parallel p-batch machines subject to arbitrary processing set restrictions (PSR). Two types of p-batch machines are considered: equal-speed and uniform. For the corresponding P- and Q-problems, efficient (strongly polynomial) approximation algorithms with a priori and a posteriori absolute and relative accuracy bounds have been designed. The presented results are the first attempt of an approximate solution of a that general problem (with arbitrary PSR and individual batch capacities of machines) in a strongly polynomial time and with performance ratios strictly less than two. As an auxiliary result, we have developed a new (linear-time) rounding algorithm for a given fractional distribution of jobs by machines in a tree-like graph.