指定目标不延误条件下的拦截决策算法

从现有的拦截排序准则出发,根据实际作战中进袭目标的特点,应用现代排序理论,分别建立了动态目标拦截排序模型和总损失最小化模型,给出相应的求解算法。最后实例计算得出模型既体现了现有的拦截准则,又对现有的准则进行了推广。     

基于逆向分层的工作流时间-费用优化方法

针对效用网格下基于优先级因子的工作流时间-费用优化问题,基于工作流的同步完成特征对任务进行分层并提出三种实时调度算法:基于逆向分层的sufferage(BLSuff)、基于逆向分层的min-min(BLMin)及基于逆向分层的min-max(BLMax)。算法设计基于优先级因子的衡量标准对时间与费用同时进行优化,并为任务设置期望完成时间以达到充分利用费用优化空间进行费用优化的目标。实验结果表明这三种算法在各种优先级因子下都能对工作流的执行时间与执行费用进行较好的优化。     

某特种车辆TTCAN网络的静态调度设计

针对某特种车辆计算机控制系统对实时性的高要求,采用了TTCAN总线系统,为实现TTCAN系统的静态调度问题,提出了基于AL算法的改进算法——谐波周期算法,并通过MATLAB建立了系统的调度表。针对谐波周期算法的不足,结合该计算机控制系统的工作原理、信息传输的重要程度对静态调度表进行了适当的修改。通过与AL算法的对比分析,证实了改进的谐波周期算法在保证系统中周期型消息实时性能前提下,为非周期型信息获得了更大的传输带宽,又使系统信息传输的时间分配更加合理。     

卫星数传调度模型研究

卫星数传调度问题是一个具有多时间窗口、多资源约束的优化问题。针对该问题,建立了卫星数传需求模型、任务模型和调度模型。在建模过程中,采用了框架模型形式,把问题中的主要约束封闭于每个数传任务中,这在降低调度模型复杂度的同时,也降低了调度算法设计难度。还提出了调度算法设计思想,并设计了一基于灵活度的调度算法。仿真表明,所建立的模型及算法对解决卫星数传调度问题是可行的。     

Cyclic preference scheduling for nurses using branch and price

This paper presents a new methodology to solve the cyclic preference scheduling problem for hourly workers. The focus is on nurse rostering but is applicable to any organization in which the midterm scheduling decision must take into account a complex of legal, institutional, and preferential constraints. The objective is to strike a balance between satisfying individual preferences and minimizing personnel costs. The common practice is to consider each planning period independently and to generate new rosters at the beginning of each. To reduce some of the instability in the process, there is a growing trend toward cyclic schedules, which are easier to manage and are generally perceived to be more equitable. To address this problem, a new integer programming model is presented that combines the elements of both cyclic and preference scheduling. To find solutions, a branch‐and‐price algorithm is developed that makes use of several branching rules and an extremely effective rounding heuristic. A unique feature of the formulation is that the master problem contains integer rather than binary variables. Computational results are reported for problem instances with up to 200 nurses. Most were solved within 10 minutes and many within 3 minutes when a double aggregation approach was applicable. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007.     

Parallel machine scheduling with job assignment restrictions

In the classical multiprocessor scheduling problem independent jobs must be assigned to parallel, identical machines with the objective of minimizing the makespan. This article explores the effect of assignment restrictions on the jobs for multiprocessor scheduling problems. This means that each job can only be processed on a specific subset of the machines. Particular attention is given to the case of processing times restricted to one of two values, 1 and λ, differing by at most 2. A matching based polynomial time ε‐approximation algorithm is developed that has a performance ratio tending to . This algorithm is shown to have the best possible performance, tending to 3/2, for processing times 1 and 2. For the special case of nested processing sets, i.e., when the sets of machines upon which individual jobs may be assigned are non‐overlapping, the behavior of list scheduling algorithms is explored. Finally, for assignment restrictions determined by just one characteristic of the machines, such as disc storage or memory constraint in the case of high performance computing, we contribute an algorithm that provides a 3/2 worst case bound and runs in time linear in the number of jobs. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

科学工作流技术研究综述

科学工作流管理系统(Scientific Workflow Management Systems,SWfMS)为科学家提供一个管理大规模复杂科学计算的有效平台,通过管理复杂应用程序对海量科学数据进行管理、分析、仿真和可视化以帮助科学家进行科学发现.本文首先对科学工作流(Scientific Workflow,SWF)...     

Multi‐period maintenance scheduling of tree networks with minimum flow disruption

We introduce a multi‐period tree network maintenance scheduling model and investigate the effect of maintenance capacity restrictions on traffic/information flow interruptions. Network maintenance refers to activities that are performed to keep a network operational. For linear networks with uniform flow between every pair of nodes, we devise a polynomial‐time combinatorial algorithm that minimizes flow disruption. The spiral structure of the optimal maintenance schedule sheds insights into general network maintenance scheduling. The maintenance problem on linear networks with a general flow structure is strongly NP‐hard. We formulate this problem as a linear integer program, derive strong valid inequalities, and conduct a polyhedral study of the formulation. Polyhedral analysis shows that the relaxation of our linear network formulation is tight when capacities and flows are uniform. The linear network formulation is then extended to an integer program for solving the tree network maintenance scheduling problem. Preliminary computations indicate that the strengthened formulations can solve reasonably sized problems on tree networks and that the intuitions gained from the uniform flow case continue to hold in general settings. Finally, we extend the approach to directed networks and to maintenance of network nodes. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Cyclic scheduling in robotic flowshops with bounded work‐in‐process levels

This study addresses cyclic scheduling in robotic flowshops with bounded work‐in‐process (WIP) levels. The objective is to minimize the cycle time or, equivalently, to maximize the throughput, under the condition that the WIP level is bounded from above by a given integer number. We present several strongly polynomial algorithms for the 2‐cyclic robotic flowshop scheduling problems for various WIP levels. © 2010 Wiley Periodicals, Inc. Naval Research Logistics 58: 1–16, 2011     

遥感数据处理任务调度的Petri网模型及求解算法

为了对多源遥感数据的处理任务进行有效的调度和管理,提高处理资源的利用率,根据遥感数据处理任务调度问题的特点,采用Petri网对该问题进行形式化描述,建立了遥感数据处理任务调度的数学模型,根据该问题的多目标特性,采用蚁群算法进行求解.给出仿真实例,将蚁群算法的求解结果与启发式算法和模拟退火算法的求解结果进行比较,验证算法...