Реферат: 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.

Библиографическая ссылка: Sevastyanov S.
Efficient approximation algorithms for scheduling problems with uniform p-batch machines and arbitrary processing set restrictions
Journal of Scheduling. 2025. P.1-26. DOI: 10.1007/s10951-025-00867-8 WOS Scopus OpenAlex

Даты:

Поступила в редакцию:	1 нояб. 2023 г.
Принята к публикации:	1 нояб. 2025 г.
Опубликована в печати:	22 дек. 2025 г.
Опубликована online:	22 дек. 2025 г.

Идентификаторы БД:

Web of science:	WOS:001644256500001
Scopus:	2-s2.0-105025711331
OpenAlex:	W7116807265

Цитирование в БД: Пока нет цитирований

Альметрики: