Dynasearch for the earliness-tardiness scheduling problem with release dates and setup constraints

A large dynasearch neighborhood is introduced for the one-machine scheduling problem with sequence-dependent setup times and costs and earliness-tardiness penalties. Finding the best schedule in this neighborhood is NP-complete in the ordinary sense but can be done in pseudo-polynomial time. We also present experimental results.     

An enhanced dynasearch neighborhood for the single-machine total weighted tardiness scheduling problem

Based on the work by Congram, Potts and Van de Velde, we develop for the single-machine total weighted tardiness scheduling problem an enhanced dynasearch neighborhood obtained by the generalized pairwise interchange (GPI) operators. Despite of the wider neighborhood considered, a fast search procedure using also elimination criteria is developed. The computational results significantly improve over those of Congram, Potts and Van de Velde.     

Fast neighborhood search for the single machine total weighted tardiness problem

Most successful heuristics for solving 1||∑w_jT_j are based on swap moves. We present an algorithm which improves the complexity of searching the swap neighborhood from O(n³) to O(n²). We show that this result also improves the complexity of the recently developed dynasearch heuristics.     

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.     

Single-machine scheduling problems with an actual time-dependent deterioration

In this paper, we consider the single machine scheduling problems with an actual time-dependent deterioration effect. By the actual time-dependent deterioration effect, we mean that the processing time of a job is defined by increasing function of total actual processing time of jobs in front of it in the sequence. We show that even with the introduction of an actual time-dependent deterioration to job processing times, makespan minimization problem, total completion time minimization problem, the total lateness, and the sum of the quadratic job completion times minimization problem remain polynomially solvable, respectively. We also show that the total weighted completion time minimization problem, the discounted total weighted completion time minimization problem, the maximum lateness minimization problem, and the total tardiness minimization problem can be solved in polynomial time under certain conditions.     

Minimizing the total completion time in a single-machine scheduling problem with a time-dependent learning effect

In this study, we introduce a time-dependent learning effect into a single-machine scheduling problem. The time-dependent learning effect of a job is assumed to be a function of total normal processing time of jobs scheduled in front of it. We introduce it into a single-machine scheduling problem and we show that it remains polynomially solvable for the objective, i.e., minimizing the total completion time on a single machine. Moreover, we show that the SPT-sequence is the optimal sequence in this problem.     

Equivalent time-dependent scheduling problems

We introduce a general transformation of parallel-machine time-dependent scheduling problems with critical lines. Using the transformation we define the class of equivalent time-dependent scheduling problems. We show that given an initial parallel-machine time-dependent scheduling problem with linear job processing times and the total weighted starting time criterion, the problem can be transformed in a unique way into another problem of this type in such a way that both these problems are mutually dual. We prove that a schedule is optimal for the initial problem if and only if the schedule constructed by this transformation is optimal for the transformed problem. The presented results explain remarkable similarities between different time-dependent scheduling problems and simplify the proofs of properties of such problems.     

Asymptotic Properties of Quasi-Maximum Likelihood Estimators for ARMA Models with Time-Dependent Coefficients

For about thirty years, time series models with time-dependent coefficients have sometimes been considered as an alternative to models with constant coefficients or non-linear models. Analysis based on models with time-dependent models has long suffered from the absence of an asymptotic theory except in very special cases. The purpose of this paper is to provide such a theory without using a locally stationary spectral representation and time rescaling. We consider autoregressive-moving average (ARMA) models with time-dependent coefficients and a heteroscedastic innovation process. The coefficients and the innovation variance are deterministic functions of time which depend on a finite number of parameters. These parameters are estimated by maximising the Gaussian likelihood function. Deriving conditions for consistency and asymptotic normality and obtaining the asymptotic covariance matrix are done using some assumptions on the functions of time in order to attenuate non-stationarity, mild assumptions for the distribution of the innovations, and also a kind of mixing condition. Theorems from the theory of martingales and mixtingales are used. Some simulation results are given and both theoretical and practical examples are treated. Received 2004; Final version 23 December 2004     

Convergence of the Marker-and-Cell Scheme for the Incompressible Navier–Stokes Equations on Non-uniform Grids

We prove in this paper the convergence of the Marker-and-Cell scheme for the discretization of the steady-state and time-dependent incompressible Navier–Stokes equations in primitive variables, on non-uniform Cartesian grids, without any regularity assumption on the solution. A priori estimates on solutions to the scheme are proven; they yield the existence of discrete solutions and the compactness of sequences of solutions obtained with family of meshes the space step and, for the time-dependent case, the time step of which tend to zero. We then establish that the limit is a weak solution to the continuous problem.     

The second order projection method in time for the time-dependent natural convection problem

We consider the second-order projection schemes for the time-dependent natural convection problem. By the projection method, the natural convection problem is decoupled into two linear subproblems, and each subproblem is solved more easily than the original one. The error analysis is accomplished by interpreting the second-order time discretization of a perturbed system which approximates the time-dependent natural convection problem, and the rigorous error analysis of the projection schemes is presented. Our main results of the second order projection schemes for the time-dependent natural convection problem are that the convergence for the velocity and temperature are strongly second order in time while that for the pressure is strongly first order in time.     

Robust a posteriori error estimates for subgrid stabilization of non-stationary convection dominated diffusive transport

We derive a robust residual a posteriori error estimator for time-dependent convection-diffusion-reaction problem, stabilized by subgrid viscosity in space and discretized by Crank-Nicolson scheme in time. The estimator yields upper bounds on the error which are global in space and time and lower bounds that are global in space and local in time. Numerical experiments illustrate the theoretical performance of the error estimator.     

A note on assessing agreement for frailty models

Assessing agreement is often of interest in biomedical sciences to evaluate the similarity of measurements produced by different raters or methods on the same subjects. We investigate the agreement structure for a class of frailty models that are commonly used for analyzing correlated survival outcomes. Conditional on the shared frailty, bivariate survival times are assumed to be independent with Weibull baseline hazard distribution. We present the analytic expressions for the concordance correlation coefficient (CCC) for several commonly used frailty distributions. Furthermore, we develop a time-dependent CCC for measuring agreement between survival times among subjects who survive beyond a specified time point. We characterize the temporal pattern in the time-dependent CCC for various frailty distributions. Our results provide a better understanding of the agreement structure implied by different frailty models.     

带准备时间的单机指数时间学习效应排序问题

研究带有准备时间的单机学习效应模型,其中工件加工时间具有指数时间学习效应,即工件的实际加工时间是已经排好的工件加工时间的指数函数。学习效应模型考虑工件的实际加工时间同时依赖于工件本身的加工时间和已加工工件的累计加工时间,目标函数为最小化总完工时间。这个问题是NP-难的,提出了一个数学规划模型来求解该问题的最优解。通过分析几个优势性质和下界,提出分支定界算法来求解此问题,并设计启发式算法改进分支定界算法的上界值。通过仿真实验验证了分支定界算法在求解质量和时间方面的有效性。     

Reconstruction of closely spaced small inhomogeneities via boundary measurements for the full time-dependent Maxwell’s equations

We consider for the full time-dependent Maxwell’s equations the inverse problem of identifying locations and certain properties of small electromagnetic inhomogeneities in a homogeneous background medium from dynamic boundary measurements on the boundary for a finite time interval.     

时变条件下带时间窗车辆调度问题的模拟退火算法

带时间窗车辆调度问题(VRPTW)是一类要求满足容积和时间窗约束的车辆路径优化问题,现 有大部分相关文献只考虑了车辆行驶速度恒定的情况,忽略了各种动态因素的影响.本文研究的时变条件下带时间窗车辆调度问题将车辆行驶速度考虑成时变分段函数,并利用模拟退火算法进行求解,最后通过实验结果说明算法的有效性.     

Asymptotics of a time correlation function in multiple recurrent scattering of scalar waves

We consider an integral that recently showed up in the calculation of the time-dependent field-field correlation function of the electric field inside polarizable (dielectric) particles. We derive new integral representations on which numerical algorithms can be based and which give information on the asymptotic behaviour for large values of a time parameter. We interpret the results of the paper in terms of the physical problem.     

Fast algorithms for scheduling with learning effects and time-dependent processing times on a single machine

We consider scheduling problems with learning/deterioration effects and time-dependent processing times on a single machine, with or without due date assignment considerations. By reducing them to a special assignment problem on product matrices, we solve all these problems in near-linear time. This improves the time complexity of previous algorithms for some scheduling problems and establishes the fast polynomial solvability for several other problems.     

Finite element methods of an operator splitting applied to population balance equations

In population balance equations, the distribution of the entities depends not only on space and time but also on their own properties referred to as internal coordinates. The operator splitting method is used to transform the whole time-dependent problem into two unsteady subproblems of a smaller complexity. The first subproblem is a time-dependent convection-diffusion problem while the second one is a transient transport problem with pure advection. We use the backward Euler method to discretize the subproblems in time. Since the first problem is convection-dominated, the local projection method is applied as stabilization in space. The transport problem in the one-dimensional internal coordinate is solved by a discontinuous Galerkin method. The unconditional stability of the method will be presented. Optimal error estimates are given. Numerical tests confirm the theoretical results.     

Some nonlinear parabolic variational inequalities

In this paper we study initial value problems for nonlinear parabolic variational inequalities involving time-dependent subdifferentials of convex functions on a Hilbert space. We shall show the existence of a solution by a semi-discretisation method with respect to the time.     

Boundary control of forced string vibrations by first directional derivatives on a short time interval

We solve a problem on the boundary control of forced vibrations of a homogeneous string by two first directional derivatives with time-dependent coefficients and noncharacteristic directions in the boundary conditions on a short time interval in the set of classical solutions. We obtain smoothness, coordination, and controllability conditions on the right-hand side of the equation and the initial and terminal data necessary and sufficient for the unique boundary control of the wave process.