基于预定作业周期的航母作战部署调度研究

为科学筹划航母作战部署调度,优化航母作战兵力的运用,对航母作战部署调度问题进行建模研究。介绍航母预定作业周期,重点阐述航母综合训练期、维修保障期和人员/作战节奏等相关内容;在此基础上,分析航母作战部署调度的约束条件,在满足对作战区域有效时间覆盖条件下,以最小化航母作战兵力数量为目标函数,构建航母作战部署调度优化模型,并通过实例进行验证。结果表明,该模型是有效、实用的,可为科学决策航母作战部署调度提供依据和方法。     

带时间窗的相控阵雷达实时任务调度方法

为了解决传统相控阵雷达任务调度中采用基于工作方式优先级的方法而存在忽略任务时间紧迫性和重要性的问题,提出了一种基于任务自身工作方式优先级、截止期和空闲时间3个特征参数的相控阵雷达任务调度方法,通过调整参数的权重来适应调度器不同的负载情况,并采用时间窗处理发生冲突的任务请求,确保更多的高优先级任务在调度间隔内被调度。仿真结果表明,所提出的方法能够有效提高任务的调度成功率,明显改善调度器性能。     

On competitive analysis for polling systems

Polling systems have been widely studied, however most of these studies focus on polling systems with renewal processes for arrivals and random variables for service times. There is a need driven by practical applications to study polling systems with arbitrary arrivals (not restricted to time-varying or in batches) and revealed service time upon a job's arrival. To address that need, our work considers a polling system with generic setting and for the first time provides the worst-case analysis for online scheduling policies in this system. We provide conditions for the existence of constant competitive ratios, and competitive lower bounds for general scheduling policies in polling systems. Our work also bridges the queueing and scheduling communities by proving the competitive ratios for several well-studied policies in the queueing literature, such as cyclic policies with exhaustive, gated or l-limited service disciplines for polling systems.     

基于改进型粒子群算法的航空多项目调度方法

多项目并举状况下的资源有限-工期最短问题求解,是提高航空企业资源利用率、缩短项目周期的关键。在项目网络计划的基础上,提出了一种改进型粒子群算法对多项目实施并行资源调度,求解多项目最优资源调度方案。该方法通过改进的交叉和变异操作,提高了解的多样性,保证了算法的全局搜索能力。最后,通过对某型飞机的2个并行装配计划进行实例计算,验证了方法的有效性。     

面向点及区域目标的遥感卫星任务调度

遥感应用需求中存在点目标和区域目标两类任务,遥感卫星对两类任务的调度方式存在很大区别,将二者统一调度困难.本文将点目标视为特殊的区域目标,将它们按照卫星观测机会分解,构建元任务,将两类目标在元任务层次进行统一;根据任务类型分别构建收益函数,兼顾了二者在收益计算上的差异,并建立了面向点及区域目标的遥感卫星任务调度模型,实现了对两类任务的综合调度.仿真实例证明,此方法能够提高卫星的观测效率.     

Scheduling a maintenance activity on parallel identical machines

We study a problem of scheduling a maintenance activity on parallel identical machines, under the assumption that all the machines must be maintained simultaneously. One example for this setting is a situation where the entire system must be stopped for maintenance because of a required electricity shut‐down. The objective is minimum flow‐time. The problem is shown to be NP‐hard, and moreover impossible to approximate unless P = NP. We introduce a pseudo‐polynomial dynamic programming algorithm, and show how to convert it into a bicriteria FPTAS for this problem. We also present an efficient heuristic and a lower bound. Our numerical tests indicate that the heuristic provides in most cases very close‐to‐optimal schedules. © 2008 Wiley Periodicals, Inc. Naval Research Logistics 2009     

天基预警系统资源调度方法

对面向导弹预警任务的天基预警系统中的低轨卫星资源调度问题进行了研究.对预警任务的特性进行分析,提出了一种预警任务规划与分解方法以减少任务对资源占用时间的需求;在此基础上建立了该问题的约束满足CSP调度模型;针对该模型变量多、解空间规模庞大的特点以及对求解算法时效性的要求,设计了一种基于局部解空间跳出机制的改进型遗传算法MGA.仿真表明该模型与算法在给定时间内能够得到满意的调度方案.     

动态规划在消防增援调度中的应用

由于各消防中队一般规模较小,对于较大规模的火灾需要多个消防队共同救护,此时若能够实现增援调度的最优化可以提高这些同时出现的火灾被全部扑灭的概率。利用多阶段动态规划对增援调度进行了研究,并分析了具体案例。通过分析得出此方法有助于改善消防资源分配状况,以实现最大程度地减小经济损失。     

支持并行工程的造船分段作业计划系统

针对传统造船模式下,车间作业计划与工艺设计串行工作方式的缺点,基于并行工程的原理,提出了分段作业计划与工艺设计的集成运行模式,为实现造船CAPP系统与PPC系统的集成化和并行化提供了实现的基础。针对集成模式的特点,建立了分段作业计划系统资源优化的数学模型,应用遗传算法解决了针对任意分段装配工艺方案的多资源平衡优化问题,可以得到每项作业最优的开工时间,同时能够给出多种资源的最优分布结果,满足了多工艺方案之间资源利用率的比较。最后,给出了计算实例,计算机模拟结果说明了这一方法的有效性。     

Scheduling parallel dedicated machines with the speeding‐up resource

We consider a problem of scheduling jobs on m parallel machines. The machines are dedicated, i.e., for each job the processing machine is known in advance. We mainly concentrate on the model in which at any time there is one unit of an additional resource. Any job may be assigned the resource and this reduces its processing time. A job that is given the resource uses it at each time of its processing. No two jobs are allowed to use the resource simultaneously. The objective is to minimize the makespan. We prove that the two‐machine problem is NP‐hard in the ordinary sense, describe a pseudopolynomial dynamic programming algorithm and convert it into an FPTAS. For the problem with an arbitrary number of machines we present an algorithm with a worst‐case ratio close to 3/2, and close to 3, if a job can be given several units of the resource. For the problem with a fixed number of machines we give a PTAS. Virtually all algorithms rely on a certain variant of the linear knapsack problem (maximization, minimization, multiple‐choice, bicriteria). © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008