Synchronizing time delay systems using variable delay in coupling

We present a mechanism for synchronizing time delay systems using one way coupling with a variable delay in coupling that is reset at finite intervals. We present the analysis of the error dynamics that helps to isolate regions of stability of the synchronized state in the parameter space of interest for single and multiple delays. We supplement this by numerical simulations in a standard time delay system like Mackey Glass system. This method has the advantage that it can be adjusted to be delay or anticipatory in synchronization with a time which is independent of the system delay. We demonstrate the use of this method in communication using the bi channel scheme. We show that since the synchronizing channel carries information from transmitter only at intervals of reset time, it is not susceptible to an easy reconstruction.     

Scheduling with partial rejection

We study a single machine scheduling problem with partial rejection. Each job is with an integer processing time. Partial rejection occurs when a job is only partly processed with penalty for the rejected part. We focus on integer size rejection. The objective is to minimize the total weighted completion time of processed jobs plus the total rejection cost. We develop a polynomial time optimal algorithm to solve the problem. We also present an easy-to-implement pseudopolynomial time optimal algorithm.     

Transmission dynamics of a two-strain pairwise model with infection age

We present and study a two-strain pairwise epidemic model with non-Markovian recovery process in which the recovery rate depends on infection age. The novel model is a hyperbolic system which can be transformed into a system of integro-differential equations by using the method of characteristics. For the two-strain pairwise model, the reproduction number with arbitrary recovery time distributions is obtained. We carry out rigorous analysis and obtain upper and lower estimates for the final epidemic size. Finally, the effects of three commonly used recovery time distributions on the reproduction number are compared by numerical simulations. We further present how the mean length of the infectious period affects the final epidemic size, the peak time and the duration of an epidemic.     

A Theory of Complexity for Continuous Time Systems

We present a model of computation with ordinary differential equations (ODEs) which converge to attractors that are interpreted as the output of a computation. We introduce a measure of complexity for exponentially convergent ODEs, enabling an algorithmic analysis of continuous time flows and their comparison with discrete algorithms. We define polynomial and logarithmic continuous time complexity classes and show that an ODE which solves the maximum network flow problem has polynomial time complexity. We also analyze a simple flow that solves the Maximum problem in logarithmic time. We conjecture that a subclass of the continuous P is equivalent to the classical P.     

极小化完工时间和的有界批调度问题

考虑m台并行批加工同型机上n个带有释放时间的工件的调度问题,目标是极小化完工时间和.给出了一个多项时间近似方案.     

Non-associative Lambek Categorial Grammar in Polynomial Time

We present a new axiomatization of the non-associative Lambek calculus. We prove that it takes polynomial time to reduce any non-associative Lambek categorial grammar to an equivalent context-free grammar. Since it is possible to recognize a sentence generated by a context-free grammar in polynomial time, this proves that a sentence generated by any non-associative Lambek categorial grammar can be recognized in polynomial time.     

无限批量调度中最小化加权完工时间和问题的一个线性时间近似方案

本文考虑n个工件的无限批量机器调度问题．一台机器可以同时加工B≥n个工件．每个工件具有一个正权因子、一个释放时间和一个加工时间．一个批次的加工时间是该批次所包含所有工件的加工时间的最大者．在同一批次中加工的工件有相同的完工时间，即它们的共同开始时间加上该批次的加工时间．对于最小化加权完工时间和问题，本文给出了第一个多项式时间近似方案(PTAS)．对任意给定精度，该算法的运行时间为线性的．     

On the complexity of scheduling unit-time jobs with OR-precedence constraints

We present various complexity results for scheduling unit-time jobs subject to OR-precedence constraints. We prove that minimizing the total weighted completion time is strongly NP-hard, even on a single machine. In contrast, we give a polynomial-time algorithm for minimizing the makespan and the total completion time on identical parallel machines.     

The clique-separator graph for chordal graphs

We present a new representation of a chordal graph called the clique-separator graph, whose nodes are the maximal cliques and minimal vertex separators of the graph. We present structural properties of the clique-separator graph and additional properties when the chordal graph is an interval graph, proper interval graph, or split graph. We also characterize proper interval graphs and split graphs in terms of the clique-separator graph. We present an algorithm that constructs the clique-separator graph of a chordal graph in O(n³) time and of an interval graph in O(n²) time, where n is the number of vertices in the graph.     

A note on single-machine scheduling with decreasing time-dependent job processing times

In this note we consider some single-machine scheduling problems with decreasing time-dependent job processing times. Decreasing time-dependent job processing times means that its processing time is a non-increasing function of its execution start time. We present polynomial solutions for the sum of squared completion times minimization problem, and the sum of earliness penalties minimization problem subject to no tardy jobs, respectively. We also study two resource constrained scheduling problems under the same decreasing time-dependent job processing times model and present algorithms to find their optimal solutions.     

Capacity planning with congestion effects

Important operational performance measures for a successful firm include not only price and quality, but also fast and on time delivery of customer orders. Capacity is a key issue in determining the lead time from customer order to delivery. However, capacity planning models seldom consider the impact of capacity levels on lead time performance. An important characteristic of this paper is the incorporation of congestion effects and their impact on lead time in making capacity acquisition decisions. It is especially important in a make-to-order environment, where customer orders arrive randomly and lead to high variability and congestion. This work was motivated by our observations of such tradeoffs at firms in several industries. We present a model to make equipment choice decisions in a multi-product, multi-machine, and single-stage production environment with congestion effects. The model is a nonlinear integer program. We present a heuristic solution procedure for this problem, which is based on a lower bound for the formulation that can be solved efficiently. The computational study shows that the solution procedure is quite effective in solving industry size problems. We illustrate the application of the model using data from a chemical-testing laboratory. We also discuss various extensions of the model.     

Forward-reserve allocation in a warehouse with unit-load replenishments

Many companies configure their warehouse with a forward area and a reserve area. The former is used for efficient order-picking, the latter for replenishing the forward area. We consider a situation in which orders are picked during a certain time period, referred to as the picking period. Prior to the picking period there is sufficient time to replenish the forward area. Our objective is to determine which replenishments minimize the expected amount of labor during the picking period. Further, we present a second model with a constraint on the replenishment activity. We model the problem as a binary programming problem and present efficient heuristics that provide tight performance guarantees. We compare the heuristics with procedures that are popular in practice and show that significant labor-savings are possible.     

A continuous space-time finite element method for the wave equation

We consider a finite element method for the nonhomogeneous second-order wave equation, which is formulated in terms of continuous approximation functions in both space and time, thereby giving a unified treatment of the spatial and temporal discretizations. Our analysis uses primarily energy arguments, which are quite common for spatial discretizations but not for time.

We present a priori nodal (in time) superconvergence error estimates without any special time step restrictions. Our method is based on tensor-product spaces for the full discretization.

     

Boundary control in critical time by elastic forces applied at two ends of an inhomogeneous rod for the case in which the wave propagation time over each of the inhomogeneity parts is the same

We study boundary control in critical time by elastic forces at two ends of an inhomogeneous rod consisting of two parts of distinct densities and elasticities for the case in which the wave propagation time over each of these parts is the same. We present a closed-form expression for the boundary control by elastic forces bringing the originally quiescent stick into a given terminal state specified by a given terminal displacement and a given terminal velocity in a given critical time.     

Optimal packet-to-slot assignment in mobile telecommunications

The problem of assigning information packets of different services to time slots of a radio frame is addressed. Packet sizes are divisible, and a maximum time slot to which a packet can be assigned is given. We present a polynomial-time scheduling algorithm maximizing the number of scheduled packets.     

Integración temporal explícita con grandes pasos de tiempo de la ecuación de transmisión del calor

We present a novel fully explicit time integration method that remains stable for large time steps, requires neither matrix inversions nor solving a system of equations and therefore allows for nearly effort-less parallelization. In this first paper the proposed approach is applied to solve conduction heat transfer problems, showing that it is stable for any time step as is the case with implicit methods but with a much lower computation time.     

Estimating arrival rate of nonhomogeneous Poisson processes with semidefinite programming

We present a summary of methods based on semidefinite programming for estimating arrival rate of nonhomogeneous Poisson processes from a finite set of observed data. Both one-dimensional time dependent, and multi-dimensional time and location dependent rates are considered. The arrival rate is a nonnegative function of time (or time and location). We also assume that it is a smooth function with continuous derivatives of up to certain order k. We estimate the rate function by one or multi-dimensional splines, with the additional condition that the underlying rate function is nonnegative. This approach results in an optimization problem over nonnegative polynomials, which can be modeled and solved using semidefinite programming. We also describe a method which requires only linear constraints. Numerical results based on e-mail arrival and highway accidents are presented.     

Anisotropic Brown-Resnick space-time processes: estimation and model assessment

Spatially isotropic max-stable processes have been used to model extreme spatial or space-time observations. One prominent model is the Brown-Resnick process, which has been successfully fitted to time series, spatial data and space-time data. This paper extends the process to possibly anisotropic spatial structures. For regular grid observations we prove strong consistency and asymptotic normality of pairwise maximum likelihood estimates for fixed and increasing spatial domain, when the number of observations in time tends to infinity. We also present a statistical test for isotropy versus anisotropy. We apply our test to precipitation data in Florida, and present some diagnostic tools for model assessment. Finally, we present a method to predict conditional probability fields and apply it to the data.     

Adaptive finite element methods for Cahn–Hilliard equations

We develop a method for adaptive mesh refinement for steady state problems that arise in the numerical solution of Cahn–Hilliard equations with an obstacle free energy. The problem is discretized in time by the backward-Euler method and in space by linear finite elements. The adaptive mesh refinement is performed using residual based a posteriori estimates; the time step is adapted using a heuristic criterion. We describe the space–time adaptive algorithm and present numerical experiments in two and three space dimensions that demonstrate the usefulness of our approach.     

Stabilization in elastic solids with voids

In this paper we study the asymptotic behavior and the analyticity of the solutions of the one-dimensional porous-elasticity problem with thermal effect. Our main result is to prove the lack of exponential stability in case of the porous-elasticity with thermal effect when viscoelasticity is present. We prove the analyticity of the problem when a porous viscosity is present. We conclude by showing the impossibility of localization in time of the solutions in the isothermal case.