The discretization problem: analysis of computational complexity, and polynomially solvable subclasses

We consider the problem to draw up the optimal schedule for a single server fed by a finite deterministic flow of claims, minimizing the sum of linear functions of individual penalties of claims. For the introduced hierarchies of subclasses of the mass problem under consideration we give the bounds where NP-complexity takes place. We demonstrate that if we pose some natural, from the practical viewpoint, constraints on the class of schedules or models, then we are able to construct polynomial algorithms to draw up optimal schedules, which are based on recursive dynamic programming relations.
This work was supported by the Russian Foundation for Basic Research, grant 93–013–16253.