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.     

Approximation algorithm for the on-line multi-customer two-level supply chain scheduling problem

A manufacturer has to process jobs released on-line and deliver them to customers. Preemption is allowed. Jobs are grouped into batches for delivery. The sum of the total flow time and the total delivery cost is minimized. Deliveries to different customers cannot be combined. We present an on-line algorithm with the competitive ratio bounded by 3+α$3+\alpha$, where α$\alpha$ is the ratio of the largest processing time to the smallest processing time.     

Effect of Gadolinium(III) Ions on the Phase Behaviour of Dimyristoylphosphatidyl Serine Multilamellar Liposomes

The effects of low concentrations of Gd³⁺ on dimyristoylphosphatidyl serine (DMPS) multilamellar liposomes were studied by differential scanning calorimetry (DSC). At low ionic strength merely a shifting upscale and a broadening of the main transition peak were observed. At high ionic strength, Gd³⁺ provoked the formation of a few clearly-discernible high-temperature components. Increase of the Gd level affected the relative intensities of these components, whereas the corresponding midpoints and half-widths remained unchanged. At the same time, in the presence of about 20 mol% dimyristoylphosphatidyl choline in the mixture with DMPS, similar secondary peaks appeared, but their positions were markedly shifted, to extents dependent on the Gd concentration. Interpretation of the data in terms of two-dimensional crystal structures is suggested. This revised version was published online in July 2006 with corrections to the Cover Date.     

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.     

Minmax p-Traveling Salesmen Location Problems on a Tree

Suppose that p traveling salesmen must visit together all points of a tree, and the objective is to minimize the maximum of the lengths of their tours. The location–allocation version of the problem (where both optimal home locations of the salesmen and their optimal tours must be found) is known to be NP-hard for any p2. We present exact polynomial algorithms with a linear order of complexity for location versions of the problem (where only optimal home locations must be found, without the corresponding tours) for the cases p=2 and p=3.     

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.