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     

防空导弹对目标拦截的模糊二元对比排序

确定对空袭兵器的拦截次序是防空导弹火力分配的重要内容.定性分析和定量计算相结合,利用模糊数学中的模糊二元对比排序法确定防空导弹对多个目标拦截的优先次序,先对模型进行描述,给出模糊相似关系矩阵及相应的计算方法,再以4种空袭兵器为作战对象,运用模型进行计算,得出直观的目标拦截排序结果,变模糊的、复杂的问题为直观的结论.为指挥员科学分配防空火力,最大限度地发挥防空导弹的制空效能奠定基础.     

AHP法在舰空导弹作战通道分析中的应用

层次分析法(AHP)是一种简便、灵活而又实用的多准则决策的系统分析方法。运用该分析方法对舰空导弹武器各作战通道的性能进行综合分析,其中在对决策矩阵进行计算时,使用了三种不同的效用函数对方案层的各项指标进行了量化,最后得出了各作战通道的综合价值,此值可为指挥员决策提供参考。计算结果表明该方法用于作战通道评价是切实可行的。     

Scheduling to minimize the total compression and late costs

We consider a single-machine scheduling model in which the job processing times are controllable variables with linear costs. The objective is to minimize the sum of the cost incurred in compressing job processing times and the cost associated with the number of late jobs. The problem is shown to be NP-hard even when the due dates of all jobs are identical. We present a dynamic programming solution algorithm and a fully polynomial approximation scheme for the problem. Several efficient heuristics are proposed for solving the problem. Computational experiments demonstrate that the heuristics are capable of producing near-optimal solutions quickly. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 67–82, 1998     

舰载机回收任务的优化调度算法及仿真

针对舰载机回收过程中,飞行甲板跑道容量的瓶颈问题,比较了几种常见的排序算法,并运用Mat-lab和Lingo软件分别对先来先服务、基于最早到达时刻、滑动窗3种算法进行了计算机仿真。仿真结果表明,滑动窗排序法排序结果最好。最后,指出了滑动窗初始窗口飞机数目和移动步长对算法复杂度和排序结果的影响。     

依据部分属性值的空中目标威胁快速排序方法

针对空中目标威胁排序问题,提出了一种依据部分属性值即可对目标威胁进行快速排序的方法.首先选取具有代表性的样本数据作为案例库;然后确定条件属性和决策属性,在利用K-均值聚类算法对决策属性进行离散化后,提出了一种针对连续条件属性值的全局离散化方法,并对离散化后的案例库进行属性约简并得出决策规则;最后将待排序目标各属性值进行...     

Single machine sequencing with linear models of release dates

The paper deals with a problem of scheduling a set of jobs on a single machine. Before a job is released for processing, it must undergo some preprocessing treatment that consumes resources. It is assumed that the release date of a job is a linear decreasing continuous function of the amount of a locally and globally constrained, continuously divisible resource (e.g., energy, catalyzer, financial outlay, gas). The problem is to find a sequence of jobs and a resource allocation that will minimize the maximum job completion time. Such a problem appears, for example, in the ingot preheating and hot-rolling process in steel mills. It is shown that the problem is strongly NP-hard. Some polynomially solvable cases of the problem and approximate algorithms with both experimental and worst-case analysis are presented. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 99–113, 1998     

Probabilistic analysis of an asymptotically optimal solution for the completion time variance problem

Scheduling a set of n jobs on a single machine so as to minimize the completion time variance is a well‐known NP‐hard problem. In this paper, we propose a sequence, which can be constructed in O(n log n) time, as a solution for the problem. Our primary concern is to establish the asymptotical optimality of the sequence within the framework of probabilistic analysis. Our main result is that, when the processing times are randomly and independently drawn from the same uniform distribution, the sequence is asymptotically optimal in the sense that its relative error converges to zero in probability as n increases. Other theoretical results are also derived, including: (i) When the processing times follow a symmetric structure, the problem has 2^{⌊(n−1)/2⌋} optimal sequences, which include our proposed sequence and other heuristic sequences suggested in the literature; and (ii) when these 2^{⌊(n−1)/2⌋} sequences are used as approximate solutions for a general problem, our proposed sequence yields the best approximation (in an average sense) while another sequence, which is commonly believed to be a good approximation in the literature, is interestingly the worst. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 373–398, 1999     

Replacing nonidentical vital components to extend system life

We consider a system that depends on a single vital component. If this component fails, the system life will terminate. If the component is replaced before its failure then the system life may be extended; however, there are only a finite number of spare components. In addition, the lifetimes of these spare components are not necessarily identically distributed. We propose a model for scheduling component replacements so as to maximize the expected system survival. We find the counterintuitive result that when comparing components' general lifetime distributions based on stochastic orderings, not even the strongest ordering provides an a priori guarantee of the optimal sequencing of components. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008