Worst-case absolute regret based solution algorithms for optimization problems with interval uncertainty

摘要

Uncertain versions of three classical optimization problems are examined: the resource allocation in a complex of independent operations and two task scheduling problems Q∥ΣCi, P∥Cmax. It is assumed that some parameters of the problems are uncertain and they belong to intervals of the known bounds. The complexity of the uncertain problems is determined. The worst-case absolute regret approach is used to evaluate the quality of the solutions. The exact, approximate or heuristic solution algorithms are proposed depending on the complexity and properties of the problems.