An approach is proposed for estimating absolute errors and finding approximate solutions to classical NP-hard scheduling problems of minimizing the maximum lateness for one or many machines and makespan is minimized. The concept of a metric (distance) between instances of the problem is introduced. The idea behind the approach is, given the problem instance, to construct another instance for which an optimal or approximate solution can be found at the minimum distance from the initial instance in the metric introduced. Instead of solving the original problem (instance), a set of approximating polynomially/pseudopolynomially solvable problems (instances) are considered, an instance at the minimum distance from the given one is chosen, and the resulting schedule is then applied to the original instance.
For the quasi-gasdynamic system of equations, there holds the law of nondecreasing entropy. Difference methods based on this system have been successfully used in numerous applications and test gasdynamic computations. In theoretical terms, however, for standard spatial discretizations of this system, the nondecreasing entropy law does not hold exactly even in the onedimensional case because of the mesh imbalance terms. For the quasigasdynamic equations, a new conservative spatial discretization is proposed for which the entropy balance equation has an appropriate form and the entropy production is guaranteed to be nonnegative (which also holds in the presence of body forces and heat sources). An important element of this discretization is that it makes use of nonstandard spaceaveraging techniques, including a nonlinear “logarithmic” averaging of the density and internal energy. The results hold on arbitrary nonuniform meshes.
The classical NP-hard (in the ordinary sense) problem of scheduling jobs in order to minimize the total tardiness for a single machine 1‖ΣT j is considered. An NP-hard instance of the problem is completely analyzed. A procedure for partitioning the initial set of jobs into subsets is proposed. Algorithms are constructed for finding an optimal schedule depending on the number of subsets. The complexity of the algorithms is O(n 2Σp j ), where n is the number of jobs and p j is the processing time of the jth job (j = 1, 2, …, n).
A singular boundary value problem for a second order linear integrodifferential equation with Volterra and nonVolterra integral operators is formulated and analyzed. The problem arises in the study of the survival probability of an insurance company over infinite time (as a function of its initial surplus) in a dynamic insurance model that is a modification of the classical Cramer–Lundberg model with a stochastic process rate of premium under a certain investment strategy in the financial market.
The importance of functional differential equations of pointwise type is determined by the fact that their solutions are used to construct traveling-wave solutions for induced infinite-dimensional ordinary differential equations, and vice versa. Solutions of such equations exhibit bifurcation. A theorem on branching bifurcation is obtained for the solution to a linear homogeneous functional differential equation of pointwise type.
The inertial characteristics of celestial bodies can be calculated using their triangle partitions based on photometric observations. Such partitions can be refined along with the accumulation of necessary information. In this regard, the question arises to what extent the approximations of the inertial characteristics of celestial bodies, in particular, the approximations of the components of the Euler–Poinsot tensor of different orders, are susceptible to the choice of such partitions. Such components enter into the expansion of the gravitational potential in harmonic polynomials. In this paper, for some small celestial bodies, a comparison of such coefficients is made as coarse partitions are replaced with finer ones.