On the cardinality of the Pareto set in bicriteria shortest path problems

Computing shortest paths with two or more conflicting optimization criteria is a fundamental problem in transportation and logistics. We study the problem of finding all Pareto-optimal solutions for the multi-criteria single-source shortest-path problem with nonnegative edge lengths. The standard approaches are generalizations of label-setting (Dijkstra) and label-correcting algorithms, in which the distance labels are multi-dimensional and more than one distance label is maintained for each node. The crucial parameter for the run time and space consumption is the total number of Pareto optima. In general, this value can be exponentially large in the input size. However, in various practical applications one can observe that the input data has certain characteristics, which may lead to a much smaller number—small enough to make the problem efficiently tractable from a practical viewpoint. For typical characteristics which occur in various applications we study in this paper whether we can bound the size of the Pareto set to a polynomial size or not. These characteristics are also evaluated (1) on a concrete application scenario (computing the set of best train connections in view of travel time, fare, and number of train changes) and (2) on a simplified randomized model. It will turn out that the number of Pareto optima on each visited node is restricted by a small constant in our concrete application, and that the size of the Pareto set is much smaller than our worst case bounds in the randomized model. A preliminary short version of this paper appeared in the Proceedings of the 5th Workshop on Algorithm Engineering (WAE 2001), LNCS 2141, Springer Verlag, pp. 185–197 (2001) under the title “Pareto shortest paths is often feasible in practice.”     

关于循环等待协议提出的一种方法

在前期关于循环等待协议的研究基础上,对于在主从网络方式下,循环等待协议中,如何建立等待环以及计算机站点如何进、出等待环的问题进行了讨论,并提出了一种较理想的解决方法。并且把这种方法和作者在另一篇文章中所提出的基于平等站方式下的解决办法进行了比较,对它们的优缺点进行了详细的讨论。     

Optimal control of single-server queueing networks

A general single-server queueing network model is considered. It is well-known that an optimal policy is determined by the largest-index policy. There is an index for each given queue and one allocates the server to a queue with largest current index. Using discounted dynamic programming we give a new and short proof of this result and derive some characterizations and bounds of the indices. Moreover, it is shown that an approximate largest-index policy yields an approximately optimal policy. These results lead to efficient methods for computing the indices. In particular, we present a general largest-remaining-index method.     

Relativistic calculations of coalescing binary neutron stars

We have designed and tested a new relativistic Lagrangian hydrodynamics code, which treats gravity in the conformally flat approximation to general relativity. We have tested the resulting code extensively, finding that it performs well for calculations of equilibrium single-star models, collapsing relativistic dust clouds, and quasi-circular orbits of equilibrium solutions. By adding a radiation reaction treatment, we compute the full evolution of a coalescing binary neutron star system. We find that the amount of mass ejected from the system, much less than a per cent, is greatly reduced by the inclusion of relativistic gravitation. The gravity wave energy spectrum shows a clear divergence away from the Newtonian point-mass form, consistent with the form derived from relativistic quasi-equilibrium fluid sequences.     

Open Superstring Star as a Continuous Moyal Product with B Field

In this paper, we recast the matter part of the open superstring star in the present ofa constant B field. Byusing a different coordinate representation the matter part of the open superstring star is identified with the continuousMoyal product of functions of anti-commuting variables. Fortunately we find it does not depend on the value of the Bfield.     

Neural networks for prediction of acoustical properties of polyurethane foams

This paper presents a study of neural networks for prediction of acoustical properties of polyurethane foams. The proposed neural network model of the foam uses easily measured parameters such as frequency, airflow resistivity and density to predict multiple acoustical properties including the sound absorption coefficient and the surface impedance. Such a model is quite robust in the sense that it can be used to develop models for many different classes of materials with different sets of input and output parameters. The current neural network model of the foam is empirical and provides a useful complement to the existing analytical and numerical approaches.     

星和完全等二部图联图的点可区别均匀边染色

研究了星与完全等二部图的联图Sm∨Kn,n的点可区别均匀边染色。     

A new heuristic for resource-constrained project scheduling in stochastic networks using critical chain concept

This paper presents a newly developed resource-constrained project scheduling method in stochastic networks by merging the new and traditional resource management methods. In each project, the activities consume various types of resources with fixed capacities. The duration of each activity is a random variable with a given density function. Since the backward pass method is implemented for feeding-in resources. The problem is to determine the finish time of each activity instead of its start time. The objective of the presented model is defined as minimizing the multiplication of expected project duration and its variance. The values of activities finish times are determined at decision points when at least one activity is ready to be operated and there are available resources. If at a certain point of time, more than one activity is ready to be operated but available resources are lacking, a competition among ready activities is carried out in order to select the activities which must be operated first. This paper suggests a competition routine by implementing a policy to maximize the total contribution of selected activities in reducing the expected project duration and its variance. In this respect, a heuristic algorithm is developed and compared with the other existing methods.     

Performance analysis of single stage kanban controlled production systems using parametric decomposition

We present a new approach that permits efficient performance analysis of kanban systems with general demand processes, material arrival processes, and service times. The approach is based on parametric characterization of the traffic processes (arrival and departure) in the network and uses two-moment approximations to estimate performance measures at individual stations. We derive traffic flow constraints that are particular to closed queuing networks with synchronization stations and use these to establish relationships between the parameters characterizing arrival and departure processes at the stations in the network. The resultant set of non-linear equations is solved to estimate network performance measures. Numerical studies show that the approach is not only fast but also reasonably accurate when compared to simulation. These studies also provide insights with respect to the impact of different types of variability on the performance of a kanban system. This work also provides a fundamental building block that can be used in the analysis of multi-stage kanban systems. AMS Subject Classifications 68M20, 60K20, 90B05, 90B30