任务分配与调度中遗传算子的设计

应用遗传算法等进化方法进行任务分配与调度为越来越多的计算机学者们所关注。基于任务排列的知识表示 ,常规的标准遗传操作算子并不总是有效的。好的遗传算子对算法收敛性及收敛到好点是非常重要的。在列表编码的知识表示基础上 ,设计了三个有针对性的遗传算子 ,即改进的交配算子、内部交配算子和一种作为变异的迁移算子。模拟实验结果与分析表明这些算子对任务分配与调度是有效的。     

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     

两段探测目标的传感器任务调度问题0-1规划模型及算法

为解决指挥系统控制中的调度困难,研究了一类特殊的传感器资源调度问。主要分析了跟踪目标的探测次数、时间间隔和传感器资源等约束条件。用跟踪目标的重要程度之和作为目标函数,建立了一个0-1规划的数学模型,再利用变换将其转化为0-1线性整数规划模型。利用割平面法求解得出最优调度策略,其能在工作量饱和的情况下合理调度传感器资源。为提高求解速度,提出了对应的模拟退火算法。通过对一些不同规模实例的求解,在资源利用率和算法的求解速度等指标上,与割平面法及遗传算法进行对比分析,验证了模型的有效性和模拟退火算法求解的高效性。     

相控阵天线阵面两级备件优化配置模型

针对相控阵天线阵面备件配置存在的冗余性强、批量送修、多级维修等现实问题,综合考虑备件费用、维修能力以及库存策略之间的关系,建立了基于定期补给的两级备件优化配置模型。给出了系统的故障件维修周转过程和维修备件的定期补给过程,在分析备件、库存、维修能力之间关系的基础上,结合成批到达的排队理论,建立了系统的供应可用度模型。以备件配置费用最小为目标、以系统供应可用度为约束条件,建立了系统的备件优化配置模型,并通过边际效益分析法对模型进行了求解。通过算例仿真与分析对模型进行了验证。结果表明:构建的备件配置能够较好地解决相控阵天线阵面的备件配置问题,具有一定的优越性。     

基于协同相关度的作战任务分解优化

针对协同作战中任务分解的优化问题,构建了任务协同相关度的量化模型。对作战任务中几个基本概念进行定义,从时间、逻辑、功能3个维度对任务间的协同关系进行了形式化描述,在此基础上,建立了任务协同关系的综合度量模型。最后,通过设置任务协同度阈值的方法,对协同紧密的任务进行聚合,实现任务分解的优化。通过仿真实验验证了模型的可行性和有效性。     

基于军民融合条件的装备性能维修保障合同执行情况

在军民融合背景下,部分新获得承制资格企业在首批装备制造或维修保障任务中时有违约问题发生。为解决该问题,提出了以基于性能的采办理论为基础的合同违约预测方法研究。以陆军通用武器装备维修保障承制单位为案例,运用SPSS软件进行数据整理和因子分析,构建合同履行预测评价模型。然后利用新入民营企业试生产实验数据在量产前建立费用和可用度模型,通过费效比最优的方式预测各新入企业的首批装备可用度及花费等关键指标,进行综合评估。结论表明该方法能够对装备合同履行情况和违约风险进行预判。     

某型武装直升机武器系统故障诊断研究

战时快速准确地查找故障部件和制定排故方案是实施战场抢修的前提和基础。目前武装直升机武器系统结构组成日趋复杂,功能模块高度集成,仅凭人工经验进行维护难度较大。为了提高故障诊断效率,采用故障树分析与专家经验相结合的方法,建立了某型武装直升机武器系统故障模型,设计了一种快速故障诊断与辅助决策系统,有效减少了维修保障人员故障排除时间,提升了故障处置效率与准确度,具有重要的实际应用价值。     

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.     

复杂装备军民融合维修保障效益评价研究

针对军民融合维修保障中缺少对合同商效益评价,无法为合同商选择、合同续签等工作提供科学依据的情况,提出基于项目后评价理论的合同商维修保障效益评价理念。在分析了军民融合维修保障项目后评价内容的基础上,以效益评价为例对复杂装备军民融合维修保障效益评价进行分析。建立了合同商保障的费用分析模型和装备可用度模型。最后,通过算例对该方法进行了演示验证。     

禁忌单亲遗传算法的某指挥控制舱协同任务规划

指挥控制舱是武器系统中指挥控制的功能核心,通过多人协同交互完成指控任务。为提高人员协同效率和操控效率。建立了以完成所有任务的时间最短为目标函数的多人协同任务规划模型。在求解模型时,采用禁忌单亲遗传混合优化算法,通过无性繁殖的方法,减少了在子代中产生无效染色体的情况,提升了算法的效率,通过禁忌算法有效避免陷入局部极小值。通过实例分析,算法使总任务执行时间减少了12豫。本模型以及求解算法在解决指挥控制舱多人协同任务规划时具有可行性,对指挥控制舱任务流程设计具有一定参考价值。