Efficient approximation algorithms for scheduling problems with uniform p-batch machines and arbitrary processing set restrictions Full article
| Journal |
Journal of Scheduling
ISSN: 1094-6136 |
||
|---|---|---|---|
| Output data | Year: 2025, | ||
| Tags | Scheduling, uniform machines, p-batch machines, processing set restrictions, approximation algorithm, polynomial time, performance guarantee | ||
| Authors |
|
||
| Affiliations |
|
Funding (1)
| 1 | Sobolev Institute of Mathematics | 0314-2019-0014 |
Abstract:
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.
Cite:
Sevastyanov S.
Efficient approximation algorithms for scheduling problems with uniform p-batch machines and arbitrary processing set restrictions
Journal of Scheduling. 2025.
Efficient approximation algorithms for scheduling problems with uniform p-batch machines and arbitrary processing set restrictions
Journal of Scheduling. 2025.
Dates:
| Submitted: | Nov 1, 2023 |
Identifiers:
No identifiers
Citing:
Пока нет цитирований