On the approximate tradeoff for bicriteria batching and parallel machine scheduling problemsстатья
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 8 октября 2025 г.
Аннотация: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.