Vehicle routing problems with regular objective functions on a path

We investigate the problem of scheduling a fleet of vehicles to visit the customers located on a path to minimize some regular function of the visiting times of the customers. For the single‐vehicle problem, we prove that it is pseudopolynomially solvable for any minsum objective and polynomially solvable for any minmax objective. Also, we establish the NP‐hardness of minimizing the weighted number of tardy customers and the total weighted tardiness, and present polynomial algorithms for their special cases with a common due date. For the multivehicle problem involving n customers, we show that an optimal solution can be found by solving or O(n) single‐vehicle problems. © 2013 Wiley Periodicals, Inc. Naval Research Logistics 61: 34–43, 2014     

Improved bounds for batch scheduling with nonidentical job sizes

Here, we revisit the bounded batch scheduling problem with nonidentical job sizes on single and parallel identical machines, with the objective of minimizing the makespan. For the single machine case, we present an algorithm which calls an online algorithm (chosen arbitrarily) for the one‐dimensional bin‐packing problem as a sub‐procedure, and prove that its worst‐case ratio is the same as the absolute performance ratio of . Hence, there exists an algorithm with worst‐case ratio , which is better than any known upper bound on this problem. For the parallel machines case, we prove that there does not exist any polynomial‐time algorithm with worst‐case ratio smaller than 2 unless P = NP, even if all jobs have unit processing time. Then we present an algorithm with worst‐case ratio arbitrarily close to 2. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 351–358, 2014     

Efficient algorithms for flexible job shop scheduling with parallel machines

Job shop scheduling with a bank of machines in parallel is important from both theoretical and practical points of view. Herein we focus on the scheduling problem of minimizing the makespan in a flexible two-center job shop. The first center consists of one machine and the second has k parallel machines. An easy-to-perform approximate algorithm for minimizing the makespan with one-unit-time operations in the first center and k-unit-time operations in the second center is proposed. The algorithm has the absolute worst-case error bound of k − 1 , and thus for k = 1 it is optimal. Importantly, it runs in linear time and its error bound is independent of the number of jobs to be processed. Moreover, the algorithm can be modified to give an optimal schedule for k = 2 .     

数字水印技术在高分辨率遥感数据安全保护中的应用

随着高分辨率遥感数据应用的不断扩展,其安全和版权问题也日益突出。利用数字水印技术保护高分辨率遥感数据安全是目前可行、可靠的技术手段。介绍了数字水印基本原理并分析了高分辨率遥感数据数字水印特征,研究了数字水印技术在高分辨率遥感数据安全分发管理、网络发布等方面的应用,探讨了高分辨率遥感数据数字水印系统设计,并对高分辨率遥感数据数字水印技术进行了展望。     

复杂系统维修性综合评估技术

分析了复杂系统使用期间维修性水平动态变化特点,研究了复杂系统在使用中维修性数据特点、类型和分布确定方法,建立了复杂系统使用期间维修性指标综合评估模型,提出了维修性增长极大似然评估方法,为复杂系统维修性指标计算和评估提供参考。     

基于改进遗传算法的舰载机出库调度优化方法

舰载机出库最优调度方案是合理编排一批次舰载机出库顺序,使目标舰载机在最短的时间内调出机库。提出舰载机出库调度方案4步单目标优化方法。第1步实现舰载机数量分配功能;第2步依靠遗传算法,实现舰载机选择功能,寻找最优出库组合方案;第3步根据优先级规则对舰载机出库作业进行排序,从而得到最优出库方案的舰载机调度序列;第4步找出需要倒机的舰载机并根据一定规则进行整理后,得到出库作业序列。最后,建立模拟机库验证调度方案的优化方法可行、高效。     

基于数据挖掘的海战场态势可视化平台构建

可视化和数据挖掘是进行海战场态势评估、实现战场可视化的两项关键技术。海战场态势可视化能提高指挥员的战场态势感知能力,有效辅助指挥员进行当前态势评估和未来态势预测。而数据挖掘技术是对海量战场态势数据进行知识发现的有效工具,基于数据挖掘技术从顶层构建了海战场态势数据可视化挖掘平台,并对其中的各子模块进行了具体研究。     

基于竞争式MAC接入的移动Adhoc网络建模与仿真

总结了具有代表性的竞争式MAC接入协议:冲突避免多址接入MACA、IEEE 802.11 DCF和信道获得多址接入FAMA传输介质访问控制接入的一般性规律,建立了一个竞争式MAC接入数学模型,研究哪些因素影响网络通信。通过NS2网络模拟实验,验证了这些影响的存在,并初步了解如何减少这些负面影响。与无线网络物理层或高层网络比起来,MAC接入对于无线网络高效可靠通信的负面影响容易被忽略,实际却存在,该研究对无线网络可靠通信具有一定参考价值。     

考虑航线交叉的救援直升机起飞时序规划方法

为解决多架救援直升机的起飞时序规划问题,以最小化最后一架救援直升机的起飞时间为优化目标,建立多直升机多起降点的数学规划模型。设计了基于任务优先级的快速启发式算法,提出航线交叉点的处理方案,给出起飞时间求解算法。以云南鲁甸6.8级地震的灾后救援为背景,设计了包含24架直升机和12个起飞点的起飞时序规划案例,对模型和算法进行了仿真验证,并对航线交叉的影响与处理措施进行了深入讨论。实验结果表明该模型和方法能有效解决多架救援直升机的起飞时序规划问题。     

Maintenance and flight scheduling of low observable aircraft

In this article, we focus on relatively new maintenance and operational scheduling challenges that are faced by the United States Air Force concerning low‐observable (LO) or stealth aircraft. The LO capabilities of an aircraft degrade stochastically as it flies, making it difficult to make maintenance scheduling decisions. Maintainers can address these damages, but must decide, which aircraft should be put into maintenance, and for how long. Using data obtained from an active duty Air Force F‐22 wing and interviews with Air Force maintainers and program specialists, we model this problem as a generalization of the well‐known restless multiarmed bandit superprocess. Specifically, we use an extension of the traditional model to allow for actions that require varying lengths of time, and generate two separate index policies from a single model; one for maintenance actions and one for the flying action. These index policies allow maintenance schedulers to intuitively, quickly, and effectively rank a fleet of aircraft based on each aircraft's LO status and decide, which aircraft should enter into LO maintenance and for how long, and which aircraft should be used to satisfy daily sortie requirements. Finally, we present extensive data‐driven, detailed simulation results, where we compare the performance of the index policies against policies currently used by the Air Force, as well as some other possible more naive heuristics. The results indicate that the index policies significantly outperform existing policies in terms of fully mission capable (FMC) rates. In particular, the experiments highlight the importance of coordinated maintenance and flying decisions. © 2015 Wiley Periodicals, Inc. 62:60–80, 2015