A new method for reconstructing medium inhomogeneities using Rayleigh waves: Case studies

The problem of reconstructing local low-contrast inhomogeneities in the Earth’s surface layers by means of coherent Rayleigh surface waves is considered. It is shown that analysis of the frequency characteristics of shear projections in this wave on the surface allows construction of the function of inhomogeneity distribution in a specified depth range. The results from seismoacoustic reconstruction of inhomogeneities correlate with data obtained using standard geophysical methods and are confirmed by direct observations.     

Computing and minimizing the relative regret in combinatorial optimization with interval data

We consider combinatorial optimization problems with uncertain parameters of the objective function, where for each uncertain parameter an interval estimate is known. It is required to find a solution that minimizes the worst-case relative regret. For minmax relative regret versions of some subset-type problems, where feasible solutions are subsets of a finite ground set and the objective function represents the total weight of elements of a feasible solution, and for the minmax relative regret version of the problem of scheduling n jobs on a single machine to minimize the total completion time, we present a number of structural, algorithmic, and complexity results. Many of the results are based on generalizing and extending ideas and approaches from absolute regret minimization to the relative regret case.     

Robust univariate spline models for interpolating interval data

We consider spline interpolation problems where information about the approximated function is given by means of interval estimates for the function values over ranges of x-values instead of specific knots. We propose two robust univariate spline models formulated as convex semi-infinite optimization problems. We present simplified equivalent formulations of both models as finite explicit convex optimization problems for splines of degrees up to 3. This makes it possible to use existing convex optimization algorithms and software.     

Seismoacoustic survey of artificial inhomogeneities in the ground

The results of processing the field test data obtained for the seismoacoustic system designed at the Institute of Applied Physics of the Russian Academy of Sciences for the visualization of underground engineering structures are presented. The described experiment is the first demonstration of the use of a high-power, high-stability transmitting-receiving system for producing a coherent insonification with a frequency of 195 Hz. The receiving element of the system is a synthetic aperture array. With the use of focusing as a method of the final signal processing, an image of a tunnel lying at a depth of 30 m is obtained in three spatial cross-sections, which demonstrates the possibility of a three-dimensional, coherent, high-frequency seismic survey of engineering structures.     

Emergency path restoration problems

We consider the problem of optimally scheduling the restoration of edges of a transportation network destroyed/damaged by a disaster. The restoration is performed by service units (servers) which have fixed restoration speeds. If several servers work simultaneously at the same point of the network, their collective restoration speed is the sum of their individual restoration speeds. The servers are initially located at some nodes. Each server can travel within the already restored part of the network with infinite speed, that is, at any time can immediately relocate to another point of the same connected component of the already restored part of the network. It is required to minimize a scheduling objective that can be expressed as the maximum or the sum of nondecreasing functions of the recovery times of the nodes, where the recovery time of a node is the time when the node is reached for the first time by a server. We present polynomial-time algorithms on path networks for problems with fixed initial locations of the servers. For problems with flexible locations that should also be optimized, we present polynomial-time algorithms for the case of equal restoration speeds of the servers, and prove that the problems are strongly NP-hard if the restoration speeds of the servers can be different.     

On-line supply chain scheduling problems with preemption

We consider supply chain scheduling problems where customers release jobs to a manufacturer that has to process the jobs and deliver them to the customers. The jobs are released on-line, that is, at any time there is no information on the number, release and processing times of future jobs; the processing time of a job becomes known when the job is released. Preemption is allowed. To reduce the total costs, processed jobs are grouped into batches, which are delivered to customers as single shipments; we assume that the cost of delivering a batch does not depend on the number of jobs in the batch. The objective is to minimize the total cost, which is the sum of the total flow time and the total delivery cost. For the single-customer problem, we present an on-line two-competitive algorithm, and show that no other on-line algorithm can have a better competitive ratio. We also consider an extension of the algorithm for the case of m customers, and show that its competitive ratio is not greater than 2m if the delivery costs to different customers are equal.     

On-line integrated production–distribution scheduling problems with capacitated deliveries

In on-line integrated production–distribution problems, customers release jobs to a manufacturer that has to process the jobs and deliver them to the customers. The jobs are released on-line, that is, at any time there is no information about future jobs. Processed jobs are grouped into batches, which are delivered to the customers as single shipments. The total cost (to be minimized) is the sum of the total weighted flow time and the total delivery cost. Such on-line integrated production–distribution problems have been studied for the case of uncapacitated batches. We consider the capacitated case with an upper bound on the size of a batch. For several versions of the problem, we present efficient on-line algorithms, and use competitive analysis to study their worst-case performance.