NP -hard scheduling problems with the criterion of minimizing the maximum penalty, e.g. maximum lateness, are considered. For such problems, a metric which delivers an upper bound on the absolute error of the objective function value is introduced. Taking the given instance of some problem and using the introduced metric, the nearest instance is deter- mined for which a polynomial or pseudo-polynomial algorithm is known. A schedule is constructed for this determined instance which is then applied to the original instance. It is shown how this approach can be applied to different scheduling problems.
Local perturbations of an infinitely long rod travel to infinity. On the contrary, in the case of a finite length of the rod, the perturbations reach its boundary and are reflected. The boundary conditions constructed here for the implicit difference scheme imitate the Cauchy problem and provide almost no reflection. These boundary conditions are non- local with respect to time, and their practical implementation requires additional calcu- lations at every time step. To minimise them, a special rational approximation, similar to the Hermite - Padé approximation is used. Numerical experiments confirm the high “transparency”of these boundary conditions and determine the conditional stability regions for finite-difference scheme.
As the practice shows, the parameters of electronic systems that determine the thermal processes are not unambiguously known and identified, but they are indeterminate and interval stochastic, which, in its turn, causes the intevally stochastic character of the thermal processes. This article develops a method that allows modelling unsteady interval stochastic thermal processes in an electronic system at the interval indeterminacy of the determinative parameters. The method is based on obtaining and further solving equations for the unsteady statistical measures (mathematical expectations, variances and covariances) of the temperature distribution in an electronic system at given change intervals and the statistical measures of the determinative parameters. Application of the elaborated method to modelling interval stochastic temperature fields by giving the example of a particular electronic system is considered.