带两个服务等级的三台机最优在线算法

研究了带服务等级约束的三台平行机在线排序问题.每台机器和每个工件的服务等级为1或者2,工件只能在等级不高于它的机器上加工,即等级为1的工件只能在等级为1的机器上加工,等级为2的工件可在所有机器上加工.每个工件的加工时间为一个单位,目标是极小化所有工件的总完工时间.考虑两种情形:当一台机器等级为1,两台机器等级为2时,给出了竞争比为17/14的最优在线算法;当两台机器等级为1,一台机器等级为2时,给出了竞争比为43/36的最优在线算法.     

Four equivalent lot-sizing models

We study the following lot-sizing models that recently appeared in the literature: a lot-sizing model with a remanufacturing option, a lot-sizing model with production time windows, and a lot-sizing model with cumulative capacities. We show the equivalence of these models with a classical model: the lot-sizing model with inventory bounds.     

A partial differential equation connected to option pricing with stochastic volatility: Regularity results and discretization

This paper completes a previous work on a Black and Scholes equation with stochastic volatility. This is a degenerate parabolic equation, which gives the price of a European option as a function of the time, of the price of the underlying asset, and of the volatility, when the volatility is a function of a mean reverting Orstein-Uhlenbeck process, possibly correlated with the underlying asset. The analysis involves weighted Sobolev spaces. We give a characterization of the domain of the operator, which permits us to use results from the theory of semigroups. We then study a related model elliptic problem and propose a finite element method with a regular mesh with respect to the intrinsic metric associated with the degenerate operator. For the error estimate, we need to prove an approximation result.

     

Strong competition model with non-uniform dispersal in a heterogeneous environment

In this study, a strong competition model was considered between two species in a heterogeneous environment. For a system with two different constant diffusion rates for each competitor, the fast diffuser can be selected evolutionally under suitable assumptions if the competing interaction between the species is strong. We also claim that a strongly interacting competition leads to a more evolutionary selection than that with the same population dynamics if a species moves with a certain non-uniform dispersal. Furthermore, species with a certain non-uniform dispersal have a competitive advantage over linear random diffusers. In addition, a species with highly sensitive dispersal response to the environment may survive. These strongly competitive advantages were demonstrated by investigating the stability of semi-trivial solutions of the system with non-uniform dispersal and comparing it to the conditions of the model with constant diffusion.     

Spectrality of a class of self-affine measures with decomposable digit sets

The self-affine measure associated with an expanding matrix and a finite digit set is uniquely determined by the self-affine identity with equal weight.The spectral and non-spectral problems on the selfaffine measures have some surprising connections with a number of areas in mathematics,and have been received much attention in recent years.In the present paper,we shall determine the spectrality and non-spectrality of a class of self-affine measures with decomposable digit sets.We present a method to deal with such case,and clarify the spectrality and non-spectrality of a class of self-affine measures by applying this method.     

Sparse Linear Algebra and Geophysical Migration: A Review of Direct and Iterative Methods

The pre-stack depth migration of reflection seismic data can be expressed, in the framework of waveform inversion, as a linear least squares problem. Together with the precise definition of this operator, we detail additional main characteristics of the forward model, like its huge size, its sparsity and the composition with convolution. It ends up with a so-called discrete ill-posed problem, whose acceptable solutions have to undergo a regularization procedure. Both direct and iterative methods have been implemented with specific attention to the convolution, and then applied to a given data set: a synthetic 2-dimensional profile of revealing size with some added noise. The efficiency with regard to computational effort and storage requirements is evaluated. The needed regularization of the solution is thoroughly studied in both cases. From the point of the global inverse problem, the extra feature of providing a solution that can be differentiated with respect to a parameter such as background velocity is also discussed.     

Scalarization of Henig Proper Efficient Points in a Normed Space

In a general normed space equipped with the order induced by a closed convex cone with a base, using a family of continuous monotone Minkowski functionals and a family of continuous norms, we obtain scalar characterizations of Henig proper efficient points of a general set and a bounded set, respectively. Moreover, we give a scalar characterization of a superefficient point of a set in a normed space equipped with the order induced by a closed convex cone with a bounded base.     

Fredholm’s boundary-value problems for differential systems with a single delay

Conditions are derived for the existence of solutions of linear Fredholm’s boundary-value problems for systems of ordinary differential equations with constant coefficients and a single delay. Utilizing a delayed matrix exponential and a method of pseudo-inverse by Moore-Penrose matrices led to an explicit and analytical form of a criterion for the existence of solutions in a relevant space and, moreover, to the construction of a family of linearly independent solutions of such problems in a general case with the number of boundary conditions (defined by a linear vector functional) not coinciding with the number of unknowns of a differential system with a single delay.     

Spreading speeds and traveling waves for abstract monostable evolution systems

This paper is devoted to the development of the theory of spreading speeds and traveling waves for abstract monostable evolution systems with spatial structure. Under appropriate assumptions, we show that the spreading speeds coincide with the minimal wave speeds for monotone traveling waves in the positive and negative directions. Then we use this theory to study the spatial dynamics of a parabolic equation in a periodic cylinder with the Dirichlet boundary condition, a reaction-diffusion model with a quiescent stage, a porous medium equation in a tube, and a lattice system in a periodic habitat.     

Resource allocation in dynamic PERT networks with finite capacity

This article models the resource allocation problem in dynamic PERT networks with finite capacity of concurrent projects (COnstant Number of Projects In Process (CONPIP)), where activity durations are independent random variables with exponential distributions, and the new projects are generated according to a Poisson process. The system is represented as a queuing network with finite concurrent projects, where each activity of a project is performed at a devoted service station with one server located in a node of the network. For modeling dynamic PERT networks with CONPIP, we first convert the network of queues into a stochastic network. Then, by constructing a proper finite-state continuous-time Markov model, a system of differential equations is created to solve and find the completion time distribution for any particular project. Finally, we propose a multi-objective model with three conflict objectives to optimally control the resources allocated to the servers, and apply the goal attainment method to solve a discrete-time approximation of the original multi-objective problem.     

Systems of quasi-variational inequalities related to the switching problem

We prove the existence of weak solution for a system of quasi-variational inequalities related to a switching problem with dynamic driven by operator associated with a semi-Dirichlet form and with measure data. We give a stochastic representation of solutions in terms of solutions of a system of reflected BSDEs with oblique reflection. As a by-product, we prove the existence of an optimal strategy in the switching problem and show regularity of the payoff function.     

The adapted solution and comparison theorem for backward stochastic differential equations with Poisson jumps and applications

This paper deals with a class of backward stochastic differential equations with Poisson jumps and with random terminal times. We prove the existence and uniqueness result of adapted solution for such a BSDE under the assumption of non-Lipschitzian coefficient. We also derive two comparison theorems by applying a general Girsanov theorem and the linearized technique on the coefficient. By these we first show the existence and uniqueness of minimal solution for one-dimensional BSDE with jumps when its coefficient is continuous and has a linear growth. Then we give a general Feynman-Kac formula for a class of parabolic types of second-order partial differential and integral equations (PDIEs) by using the solution of corresponding BSDE with jumps. Finally, we exploit above Feynman-Kac formula and related comparison theorem to provide a probabilistic formula for the viscosity solution of a quasi-linear PDIE of parabolic type.     

On the construction of prefix-free and fix-free codes with specified codeword compositions

We investigate the construction of prefix-free and fix-free codes with specified codeword compositions. We present a polynomial time algorithm which constructs a fix-free code with the same codeword compositions as a given code for a special class of codes called distinct codes. We consider the construction of optimal fix-free codes which minimize the average codeword cost for general letter costs with uniform distribution of the codewords and present an approximation algorithm to find a near optimal fix-free code with a given constant cost.     

Variable electrical and thermal conductivity in the theory of generalized thermoelastic diffusion

This paper deals with the problem of a thermoelastic half-space with a permeating substance in contact with the bounding plane in the context of the theory of generalized thermoelastic diffusion with one relaxation time and with variable electrical and thermal conductivity. The bounding surface of the half-space is taken to be traction free and subjected to a time dependent thermal shock. The solution is obtained in the Laplace transform domain by a direct approach. A numerical technique is employed to obtain the solution in the physical domain. It is found that there exist two coupled waves, one of which is elastic and the other is thermal, and a third wave affects diffusion mainly. A comparison is made with the results obtained in a thermoelastic medium with and without diffusion in the following cases : (a) the electrical and thermal conductivities have constant values, (b) the presence of magnetic field and (c) the generalized theory in thermoelasticity. Received: June 1, 2005     

Cohomology,extensions and automorphisms of skew braces

The second cohomology group of a left skew brace with coefficients in a trivial left brace with non-trivial actions is defined, its connection with extensions of a left skew brace by a trivial brace is established and a Wells' like exact sequence relating the second cohomology group with inducible automorphisms of an extension of left skew braces is constructed.     

Coexistence in host–pathogen systems

Lanchier and Neuhauser have initiated the study of host–symbiont systems but have concentrated on the case in which the birth rates for unassociated hosts are equal. Here we allow the birth rates to be different and identify cases in which a host with a specialist pathogen can coexist with a second species. Our calculations suggest that it is possible for two hosts with specialist pathogens to coexist but it is not possible for a host with a specialist mutualist to coexist with a second species.     

The Buneman index via polyhedral split decomposition

The split decomposition of a metric using the so-called isolation index was established by Bandelt and Dress, and it is a theoretical foundation for certain phylogenetic network reconstruction methods. Recently, Hirai gave a geometric interpretation to the split decomposition, and provided an extension of the split decomposition for a distance, i.e., a symmetric nonnegative function with zero diagonal. By Herrmann and Moulton, such a geometric approach was further applied to polyhedral functions, called tight-spans in their style, defined on various vector configurations. This paper addresses the split decomposition with respect to a particular kind of vector configuration, which does not satisfy the assumption imposed by Hirai or Herrmann and Moulton. As a result, we obtain geometrically the Buneman index, which is also used to construct a phylogenetic tree. Moreover, this paper deals with the combinatorial aspect of the polyhedral split decomposition, and gives a combinatorial characterization of the split-decomposability with the aid of the matroid associated with the vector configuration.     

On Strategic Defense in Stochastic Networks

This paper deals with the detection and prediction of losses due to cyber attacks waged on vital networks. The accumulation of losses to a network during a series of attacks is modeled by a 2-dimensional monotone random walk process as observed by an independent delayed renewal process. The first component of the process is associated with the number of nodes (such as routers or operational sites) incapacitated by successive attacks. Each node has a weight associated with its incapacitation (such as loss of operational capacity or financial cost associated with repair), and the second component models the cumulative weight associated with the nodes lost. Each component has a fixed threshold, and crossing of a threshold by either component represents the network entering a critical condition. Results are given as joint functionals of the predicted time of the first observed threshold crossing along with the values of each component upon this time.     

Stochastic integration,trace and the skeleton of wiener functionals

It is shown that the notion of trace induced by a given complete orthonormal system relates the Skorohod integral with a corresponding Ogawa‐type integral evaluated with respect to the same orthonormal systems. Similarly the multiple Wiener‐Ito integral is shown to be related to a multiple Ogawa‐type integral induced by a complete orthonormal system via the Hu‐Meyer formula with suitably defined multiple traces. The notion of skeleton of a Wiener functional relative to a given orthonormal system is defined and yields what seems to be a “natural” extension of Wiener functionals to the Cameron Martin space and the Wiener processes with a different scale.