Single‐machine scheduling with deadlines to minimize the total weighted late work

We consider scheduling a set of jobs with deadlines to minimize the total weighted late work on a single machine, where the late work of a job is the amount of processing of the job that is scheduled after its due date and before its deadline. This is the first study on scheduling with the late work criterion under the deadline restriction. In this paper, we show that (i) the problem is unary NP‐hard even if all the jobs have a unit weight, (ii) the problem is binary NP‐hard and admits a pseudo‐polynomial‐time algorithm and a fully polynomial‐time approximation scheme if all the jobs have a common due date, and (iii) some special cases of the problem are polynomially solvable.     

目标宽频带RCS的快速算法研究

目标宽带RCS预估算法一直是计算电磁学的一个研究热点,本文分别研究了渐近波形估计技术（AWE）与最佳一致逼近技术在宽频带RCS预估领域内的应用。首先,介绍了传统矩量法计算RCS的原理,并分析了两种快速算法的计算过程。然后,采用这两种技术,分别计算了简易飞机模型的RCS值,并对这两种方法进行比较。计算结果表明相比传统的矩量法,这两种方法在不影响精度的前提下大大提高了计算效率。同时,相比渐近波形估计技术,最佳一致逼近技术在节省内存,节约时间方面更具优势。最后,采用最佳一致逼近理论,结合电磁计算软件,实现较大尺寸目标的宽频带RCS的计算。     

关于半鞅向量随机积分的两个结果

首先利用半鞅Girsanov定理与闭图像定理证明了:若{Xn}是带滤基的完备概率空间(Ω,F,F,P)中的一列半鞅,其中滤基F=(Ft)t≥0满足通常条件,且{Xn}在关于P的Emery拓扑空间中收敛于X,则当概率测度Q相似文献   

A dual criteria sequencing problem with earliness and tardiness penalties

We consider the problem of sequencing n jobs on a single machine, with each job having a processing time and a common due date. The common due date is assumed to be so large that all jobs can complete by the due date. It is known that there is an O(n log n)‐time algorithm for finding a schedule with minimum total earliness and tardiness. In this article, we consider finding a schedule with dual criteria. The primary goal is to minimize the total earliness and tardiness. The secondary goals are to minimize: (1) the maximum earliness and tardiness; (2) the sum of the maximum of the squares of earliness and tardiness; (3) the sum of the squares of earliness and tardiness. For the first two criteria, we show that the problems are NP‐hard and we give a fully polynomial time approximation scheme for both of them. For the last two criteria, we show that the ratio of the worst schedule versus the best schedule is no more than . © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 422–431, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10020     

用线性规划法设计复系数FIR滤波器

讨论了在复Chebyshev逼近意义下设计复系数FIR滤波器问题。直接把复Chebyshev逼近问题离散化成有限维线性规划问题 ,再用单纯形法求解这种方法一直被认为只能设计实系数滤波器 ,而且计算量大、收敛速度慢。本文从直接离散化出发 ,推导出一种求解此问题的改进的单纯形算法 ,适用于设计复系数滤波器 ,极大地减小了计算量 ,提高了收敛速度。并证明了它与通过求解半无限线性规划的对偶问题而得到的改进的单纯形法是等价的。最后给出了算法的仿真结果     

氙原子在铂表面散射的分子动力论方法

运用分子动力论方法研究气体分子 (Xe)在固壁表面 (Pt)的散射。在构造了合理的气体分子与固壁表面相互作用势模型之后 ,运用随机经典轨道方法求解气体分子及固壁原子的运动方程 ,得到气体分子运动轨迹及散射后的运动状态。结果表明 ,气体分子散射后的角度分布与Maxwellian模型存在较大差异 ,而速度基本服从半空间的Maxwellian分布。     

Polynomial‐time approximation scheme for concurrent open shop scheduling with a fixed number of machines to minimize the total weighted completion time

In this article, we consider the concurrent open shop scheduling problem to minimize the total weighted completion time. When the number of machines is arbitrary, the problem has been shown to be inapproximable within a factor of 4/3 ‐ ε for any ε > 0 if the unique games conjecture is true in the literature. We propose a polynomial time approximation scheme for the problem under the restriction that the number of machines is fixed. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Coherent systems based on sequential order statistics

The sequential order statistics (SOS) are a good way to model the lifetimes of the components in a system when the failure of a component at time t affects the performance of the working components at this age t. In this article, we study properties of the lifetimes of the coherent systems obtained using SOS. Specifically, we obtain a mixture representation based on the signature of the system. This representation is used to obtain stochastic comparisons. To get these comparisons, we obtain some ordering properties for the SOS, which in this context represent the lifetimes of k‐out‐of‐n systems. In particular, we show that they are not necessarily hazard rate ordered. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

北斗卫星伪距信号质量评估及偏差校正

针对北斗卫星信号存在系统性伪距偏差的问题,从多路径角度评估北斗三频信号的质量,验证了该项偏差与卫星轨道类型、卫星仰角及信号频率有关。为消除这一系统性偏差的影响,采用连续分段线性函数建立北斗三频伪距偏差校正模型。与现有的改正模型所不同,所提模型不仅采用了更长时间范围内的北斗实测数据,更为重要的是它顾及了改正数的精度信息。基于动态精密单点定位的实验结果表明,采用所提方法修正后,接收机定位性能有明显提升。     

Single batch machine scheduling with deliveries

We consider the problem of scheduling a set of n jobs on a single batch machine, where several jobs can be processed simultaneously. Each job j has a processing time p_j and a size s_j. All jobs are available for processing at time 0. The batch machine has a capacity D. Several jobs can be batched together and processed simultaneously, provided that the total size of the jobs in the batch does not exceed D. The processing time of a batch is the largest processing time among all jobs in the batch. There is a single vehicle available for delivery of the finished products to the customer, and the vehicle has capacity K. We assume that K = rD, where and r is an integer. The travel time of the vehicle is T; that is, T is the time from the manufacturer to the customer. Our goal is to find a schedule of the jobs and a delivery plan so that the service span is minimized, where the service span is the time that the last job is delivered to the customer. We show that if the jobs have identical sizes, then we can find a schedule and delivery plan in time such that the service span is minimum. If the jobs have identical processing times, then we can find a schedule and delivery plan in time such that the service span is asymptotically at most 11/9 times the optimal service span. When the jobs have arbitrary processing times and arbitrary sizes, then we can find a schedule and delivery plan in time such that the service span is asymptotically at most twice the optimal service span. We also derive upper bounds of the absolute worst‐case ratios in both cases. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 470–482, 2015