一种新的批处理常模算法

详细分析了传统批处理常模算法的缺点,提出了一种新的批处理常数模算法——基于共轭梯度方向的批处理常模算法(CG-BPCMA).仿真结果表明,与最陡下降批处理常模算法(SD-BPCMA)和牛顿方向批处理常模算法(NT-BPCMA)相比,提出的新算法有效地克服了SD-BPCMA和NT-BPCMA的缺点,不仅获得了较低的算法复杂度,而且能快速收敛到常模代价函数的最小值点.     

高分辨率遥感影像的自优化迭代分类方法

针对高分辨率遥感影像提出了一种面向像斑的自优化迭代分类算法,基于半监督聚类算法获取训练样本,以支持向量机为核心设计了自优化迭代分类器。使用分型网络演化算法获取像斑,并从中选取少量标记样本;结合标记样本,利用半监督模糊C均值算法对像斑进行聚类,并基于密集度筛选得到训练样本;设计了自优化迭代支持向量机分类算法,对所有像斑进行迭代分类直到满足分类要求,并在分类过程中对近邻分类结果进行统计得到高可信度样本以自主优化训练样本集。基于以上方法分别对武汉市Quick Bird和World View影像进行分类实验,分类总精度分别达到94.67%与92%,与基于人工选取训练样本情况下进行分类的分类总精度(82%与82.67%)、常规支持向量机分类总精度(87.33%与88%)、最小二乘支持向量机分类总精度(88%与89.33%)相比,精度有明显提升,分类效果较好。     

基于动态时间规整下密度聚类的轨迹识别研究

为使地空导弹兵模拟训练系统获得的目标机动轨迹更加贴近实战、更有依据性,考虑对演习训练产生的轨迹数据进行分析,设计了DBSCAN(Density-Based Spatial Clustering of Applications with Noise,针对有噪声数据的基于密度的空间聚类)预分类的DBSCAN改进DTW(Dynamic Time Warping,动态时间归整)聚类算法来分析机动轨迹.并与未预分类的DBSCAN改进DTW聚类算法进行对比,发现其运行效率和分类准确度方面均较优.同时分析了数据结构和算法的参数对分类效果的影响,发现数据规模越大,DBSCAN预分类的DBSCAN改进DTW聚类算法的优势越明显.通过仿真得到了使DBSCAN预分类的DBSCAN改进DTW聚类算法发挥最高效率的参数.     

低错误平层数列分割移位低密度奇偶校验码构造算法

为降低LDPC(低密度奇偶校验码)码错误平层,提出一种基于环分类搜索的APPS-LDPC(数列分割移位的LDPC)码构造算法。该算法具有码长、码率和列重的任意可设性,同时该类码的Tanner图围长至少为8。循环移位因子可以通过简单的代数表达式描述,从而降低内存需求。仿真结果表明,当误码率达到10-5时,APPS-LDPC码(496,248)相对于PEG-LDPC(渐进边增长LDPC)码获得了约1.9 d B的性能提升;随着信噪比的升高,两条译码性能曲线之间的差距将更大。此外,列重为3的APPS-LDPC码(6144,5376)在信噪比4.6 d B以后并未出现明显的错误平层。该构造算法与PS-LDPC码相比,在误码率达到10-8时大约获得0.25 d B增益;与围长为4和6的PEG构造算法相比,在错误平层区域其译码性能极优;同时相较于此两者,其构造复杂度和耗时也展现出一定优势。通过基于Tanner图的诱捕集分析方法,统计APPS-LDPC码(496,248)中由8环组成的部分小型诱捕集并不存在,从而证明了其错误平层降低的原因。     

无源雷达杂波抑制与相干检测的联合优化处理

杂波抑制和相干检测是外辐射源雷达信号处理的两个关键环节,针对扩展相消批处理杂波对消算法和基于分段的多普勒谱分析的运动目标相干检测方法存在重复分块和冗余计算的问题,提出了扩展相消批处理算法与基于分段的多普勒谱分析方法的联合优化算法,推导了它们的数学原理,给出了分段数及滤波器阶数的设置方法。仿真结果表明,该方法在取得较好杂波抑制效果的同时,降低了系统整体的运算量。     

低错误平层数列分割移位LDPC码构造算法研究

为降低LDPC码错误平层,提出一种基于环分类搜索的数列分割移位LDPC码构造算法。该算法具有码长、码率和列重的任意可设性,同时该类码的Tanner图围长至少为8。循环移位因子可以通过简单的代数表达式描述,从而降低内存需求。仿真结果表明,当误码率达到10-5时,数列分割移位LDPC(496,248)码相对于PEG-LDPC码获得了约1.9dB的性能提升;且随着信噪比的升高,两条译码性能曲线之间的差距将更为增大。此外,列重为3的数列分割移位LDPC码(6144,5376)在信噪比4.6dB以后并未出现明显的错误平层。该构造算法与PS-LDPC码相比在误码率达到10-8时大约获得0.25dB增益,特别在错误平层区域其译码性能优于围长为4和6的PEG构造算法,其构造复杂度和耗时也相较于PS-LDPC码和PEG-LDPC码构造算法展现出一定优势。通过基于Tanner图的诱捕集分析方法,统计(496,248)APPS-LDPC码中由8环组成的部分小型诱捕集并不存在,从而证明了其错误平层降低的原因。     

一种基于Lorentzian函数的变步长LMS自适应滤波算法

为了改善传统的LMS类算法存在的缺点,提高算法的收敛速度和跟踪性能,提出了一种基于Lorentzian函数的变步长LMS自适应滤波算法.该算法采用Lorentzian函数来建立估计误差e(n)和步长因子μ(n)之间的非线性关系,以达到提高收敛速度和改善跟踪性能的目的.计算机仿真表明,算法与其他LMS类自适应滤波算法相比,在收敛速度和跟踪性能上都有较大的提升.     

面向像斑的高分辨率遥感影像自优化迭代分类方法

针对高分辨率遥感影像提出了一种面向像斑的自优化迭代分类算法,基于半监督聚类算法获取训练样本,以支持向量机为核心设计了自优化迭代分类器。使用分型网络演化算法获取像斑,并从中选取少量标记样本;结合标记样本,利用半监督模糊C均值算法对像斑进行聚类,并基于密集度筛选得到训练样本;设计了自优化迭代支持向量机分类算法,对所有像斑进行迭代分类直到满足分类要求,并在分类过程中对近邻分类结果进行统计得到高可信度样本以自主优化训练样本集。基于以上方法分别对武汉市QuickBird和WorldView影像进行分类实验,分类总精度分别达到94.67%与92%,与基于人工选取训练样本情况下进行分类的分类总精度（82%与82.67%）、常规支持向量机分类总精度（87.33%与88%）、最小二乘支持向量机分类总精度（88%与89.33%）相比,精度有明显提升,分类效果较好。     

一种面向自动化标检的文本分类方法

针对自动化标检中的段落文本分类问题,提出一种基于机器学习的改进朴素贝叶斯分类算法。该方法对朴素贝叶斯分类算法进行改进并作为分类器,采用遗传算法作为训练模型对分类器中的所有特征权重进行训练,并采用一种基于图表位置的修正算法优化分类结果。在实际的数据集中进行了实验,结果表明,该方法与传统KNN(K-nearest neighbor)算法和朴素贝叶斯算法相比具有更好的分类结果,能够有效的处理错误样本较多的情况,可大幅提升自动化标检的准确性。     

固定翼无人机多工况聚类及识别研究

针对固定翼无人机作业过程中多工况的分类以及一般模式识别算法时效性低,准确率不高的问题,提出了"聚类分析-模式识别"相结合的多工况分析技术路线,将工况分析分为离线和在线2个阶段.离线阶段,提出子一种基于分组的密度聚类算法,采用分而治之的聚类思想对无人机历史飞行数据进行聚类分析,并将聚类所得各抽象数据簇视为工况.在线阶段,...     

Minimizing makespan on a single batch processing machine with nonidentical job sizes

We deal with the problem of minimizing makespan on a single batch processing machine. In this problem, each job has both processing time and size (capacity requirement). The batch processing machine can process a number of jobs simultaneously as long as the total size of these jobs being processed does not exceed the machine capacity. The processing time of a batch is just the processing time of the longest job in the batch. An approximation algorithm with worst‐case ratio 3/2 is given for the version where the processing times of large jobs (with sizes greater than 1/2) are not less than those of small jobs (with sizes not greater than 1/2). This result is the best possible unless P = NP. For the general case, we propose an approximation algorithm with worst‐case ratio 7/4. A number of heuristics by Uzosy are also analyzed and compared. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 226–240, 2001     

Two‐agent scheduling on a single sequential and compatible batching machine

We study two‐agent scheduling on a single sequential and compatible batching machine in which jobs in each batch are processed sequentially and compatibility means that jobs of distinct agents can be processed in a common batch. A fixed setup time is required before each batch is started. Each agent seeks to optimize some scheduling criterion that depends on the completion times of its own jobs only. We consider several scheduling problems arising from different combinations of some regular scheduling criteria, including the maximum cost (embracing lateness and makespan as its special cases), the total completion time, and the (weighted) number of tardy jobs. Our goal is to find an optimal schedule that minimizes the objective value of one agent, subject to an upper bound on the objective value of the other agent. For each problem under consideration, we provide either a polynomial‐time or a pseudo‐polynomial‐time algorithm to solve it. We also devise a fully polynomial‐time approximation scheme when both agents’ scheduling criteria are the weighted number of tardy jobs.     

Bicriteria scheduling on a single batching machine with job transportation and deterioration considerations

We study a single batching machine scheduling problem with transportation and deterioration considerations arising from steel production. A set of jobs are transported, one at a time, by a vehicle from a holding area to the single batching machine. The machine can process several jobs simultaneously as a batch. The processing time of a job will increase if the duration from the time leaving the holding area to the start of its processing exceeds a given threshold. The time needed to process a batch is the longest of the job processing times in the batch. The problem is to determine the job sequence for transportation and the job batching for processing so as to minimize the makespan and the number of batches. We study four variations (P1, P2, P3, P4) of the problem with different treatments of the two criteria. We prove that all the four variations are strongly NP‐hard and further develop polynomial time algorithms for their special cases. For each of the first three variations, we propose a heuristic algorithm and analyze its worst‐case performance. For P4, which is to find the Pareto frontier, we provide a heuristic algorithm and an exact algorithm based on branch and bound. Computational experiments show that all the heuristic algorithms perform well on randomly generated problem instances, and the exact algorithm for P4 can obtain Pareto optimal schedules for small‐scale instances. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 269–285, 2014     

Determining optimal sizes of bounded batches with rejection via quadratic min‐cost flow

In this article, we consider a single machine scheduling problem, in which identical jobs are split into batches of bounded sizes. For each batch, it is allowed to produce less jobs than a given upper bound, that is, some jobs in a batch can be rejected, in which case a penalty is paid for each rejected job. The objective function is the sum of several components, including the sum of the completion times, total delivery cost, and total rejection cost. We reduce this problem to a min‐cost flow problem with a convex quadratic function and adapt Tamir's algorithm for its solution. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 217–224, 2017     

Machine scheduling with an availability constraint and job delivery coordination

In this paper we study the scheduling problem that considers both production and job delivery at the same time with machine availability considerations. Only one vehicle is available to deliver jobs in a fixed transportation time to a distribution center. The vehicle can load at most K jobs as a delivery batch in one shipment due to the vehicle capacity constraint. The objective is to minimize the arrival time of the last delivery batch to the distribution center. Since machines may not always be available over the production period in real life due to preventive maintenance, we incorporate machine availability into the models. Three scenarios of the problem are studied. For the problem in which the jobs are processed on a single machine and the jobs interrupted by the unavailable machine interval are resumable, we provide a polynomial algorithm to solve the problem optimally. For the problem in which the jobs are processed on a single machine and the interrupted jobs are nonresumable, we first show that the problem is NP‐hard. We then propose a heuristic with a worst‐case error bound of 1/2 and show that the bound is tight. For the problem in which the jobs are processed on either one of two parallel machines, where only one machine has an unavailable interval and the interrupted jobs are resumable, we propose a heuristic with a worst‐case error bound of 2/3. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Parallel machine scheduling with batch deliveries to minimize total flow time and delivery cost

Motivated by the flow of products in the iron and steel industry, we study an identical and parallel machine scheduling problem with batch deliveries, where jobs finished on the parallel machines are delivered to customers in batches. Each delivery batch has a capacity and incurs a cost. The objective is to find a coordinated production and delivery schedule that minimizes the total flow time of jobs plus the total delivery cost. This problem is an extension of the problem considered by Hall and Potts, Ann Oper Res 135 (2005) 41–64, who studied a two‐machine problem with an unbounded number of transporters and unbounded delivery capacity. We first provide a dynamic programming algorithm to solve a special case with a given job assignment to the machines. A heuristic algorithm is then presented for the general problem, and its worst‐case performance ratio is analyzed. The computational results show that the heuristic algorithm can generate near‐optimal solutions. Finally, we offer a fully polynomial‐time approximation scheme for a fixed number of machines. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 492–502, 2016     

On‐line algorithms for minimizing makespan on batch processing machines

We consider problem of scheduling jobs on‐line on batch processing machines with dynamic job arrivals to minimize makespan. A batch machine can handle up to B jobs simultaneously. The jobs that are processed together from a batch, and all jobs in a batch start and complete at the same time. The processing time of a batch is given by the longest processing time of any job in the batch. Each job becomes available at its arrival time, which is unknown in advance, and its processing time becomes known upon its arrival. In the first part of this paper, we address the single batch processing machine scheduling problem. First we deal with two variants: the unbounded model where B is sufficiently large and the bounded model where jobs have two distinct arrival times. For both variants, we provide on‐line algorithms with worst‐case ratio (the inverse of the Golden ratio) and prove that these results are the best possible. Furthermore, we generalize our algorithms to the general case and show a worst‐case ratio of 2. We then consider the unbounded case for parallel batch processing machine scheduling. Lower bound are given, and two on‐line algorithms are presented. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 241–258, 2001     

Scheduling jobs to two machines subject to batch arrival ordering

The problem considered is to assign n jobs to two processors so as to minimize the total flow time, with the constraint that a predetermined partial ordering (induced by batch arrivals) must be preserved within the subset of jobs assigned to each processor. An efficient algorithm of time 0(n⁵) is developed, and computational experience is reported.     

Batch scheduling on a two‐machine jobshop with machine‐dependent setup times

The problem of minimum makespan on an m machine jobshop with unit execution time (UET) jobs (m ≥ 3) is known to be strongly NP‐hard even with no setup times. We focus in this article on the two‐machine case. We assume UET jobs and consider batching with batch availability and machine‐dependent setup times. We introduce an efficient \begin{align*}(O(\sqrt{n}))\end{align*} algorithm, where n is the number of jobs. We then introduce a heuristic for the multimachine case and demonstrate its efficiency for two interesting instances. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

一种新型军用电源智能充电机控制算法

军用电源充电机是一个多参数、时变的非线性系统,传统的PID控制算法难以在线调节达到优化充电曲线的目的。针对该问题,提出了一种基于模糊和免疫机理的自适应PID控制算法。该算法通过模糊免疫反馈机理对PID控制的比例系数进行实时调整,采用模糊自适应控制器对PID控制的微分、积分时间常数进行在线整定。仿真结果表明,该算法具有响应时间短、超调量小,鲁棒性强等特点,极大地改善了系统的适应能力,达到了优化充电曲线的目的。