|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ПсковГУ |
||
On the approximate tradeoff for bicriteria batching and parallel machine scheduling problemsстатья
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 8 октября 2025 г.
- Авторы: Angel E., Bampis E., Kononov A.
- Журнал: Theoretical Computer Science
- Том: 306
- Год издания: 2003
- Издательство: Elsevier BV
- Местоположение издательства: Netherlands
- Первая страница: 319
- Последняя страница: 338
- DOI: 10.1016/S0304-3975(03)00288-3
- Аннотация: We consider multiobjective scheduling problems, i.e. scheduling problems that are evaluated with respect to many cost criteria, and we are interested in determining a trade-off (Pareto curve) among these criteria. We study two types of bicriteria scheduling problems: single-machine batching problems and parallel machine scheduling problems. Instead of proceeding in a problem-by-problem basis, we identify a class of multiobjective optimization problems possessing a fullypolynomial time approximation scheme (FPTAS) for computing an -approximate Pareto curve.This class contains a set of problems whose Pareto curve can be computed via a simplepseudo-polynomial dynamic program for which the objective and transition functions satisfysome, easy to verify, arithmetical conditions. Our study is based on a recent work of Woeginger (Electronic Colloquium on Computational Complexity, Report 84 (short version appeared in SODA’99, pp. 820 –829)) for the single criteria optimization ex-benevolent problems. We show how our general result can be applied to the considered scheduling problems.
- Добавил в систему: Кононов Александр Вениаминович