The "additive" route problems with constraints and possible dependence of cost functions on tasks list are considered. Such settings are natural under investigation of engineering problems arising in nuclear power and mechanical engineering. In first case, decrease in dose rate for the worker of the nuclear power plant under dismantling radiation elements of equipment is discussed. In second case, procedures are connected with sheet cutting on machines with a numerical control. In article, an issue connected with employment of dynamic programming for solution of problems with constraints and above-mentioned dependence of cost functions from task list is considered. Procedures of testing and local improvements of heuristics are borne in mind. In both versions realized for sub-problems of moderate dimension apparatus of the widely understood dynamic programming is used. But, it is supposed that the above-mentioned sub-problems are complicated by the same conditions as in original “big” problem (constraints, cost functions with dependency on tasks list). For implementation of the “local” dynamic programming, the scheme with using of precedence constraints to reduce of the computational complexity is realized (precedence conditions are available practically in all variants of above-mentioned applied problems); wherein, the construction of total array of Bellman function is not required. For the accounting of emerging under performance of tasks dynamic constraints, special (threshold) cost functions with role of palpable penalties for violation of constraints are used. Results of computing experiment both for testing of above-mentioned heuristics and under solution of problems with palpable dimension are given. The article is based on a lecture one of authors in conference MKPU-10.