卫星任务调度问题的约束规划模型

卫星任务规划与调度是空间资源管理的重要内容之一,其目的在于为卫星系统的任务计划编制提供科学合理的决策手段与依据。卫星任务调度问题的重要特点在于,调度任务存在可见时间窗口约束。只有在可见时间窗口内,调度任务才可能执行并完成。在进行合理假设的基础上,建立卫星任务调度问题的约束规划模型。对基本禁忌搜索算法进行改进,提出了模型求解的变邻域禁忌搜索算法。应用结果表明,约束规划模型的建立与求解是合理的。     

C2组织结构设计:平台-任务关系设计

以联合作战战役为例建立作战平台和任务模型,对C2(Command and Control)组织结构设计中平台-任务关系设计问题分析了传统多维动态列表规划算法(Multidimensional Dynamic List Scheduling,MDLS)在解决作战平台资源调度(平台-任务分配)问题的不足,提出了在平台-任务分配过程中采用任务选择平台组、平台选择任务以及两者选择冲突消除改进的MDLS算法,以解决MDLS算法的不足,并对不同方法的结果进行了比较.     

链约束下加工时间恶化的Flow Shop排序问题

讨论作业具有线性加工时间,作业间具有链约束的两台处理机流水作业排序问题,目标函数为极小化完工时间。在作业加工时间简单线性恶化下,提出作业的非负开始和停止延迟恶化率,构造了满足约束条件的复合作业。在此基础上,给出作业间具有平行链约束的两台处理机流水作业排序问题的最优多项式算法。     

Minimizing weighted earliness and tardiness penalties in single‐machine scheduling with idle time permitted

In this paper, a single‐machine scheduling problem with weighted earliness and tardiness penalties is considered. Idle time between two adjacent jobs is permitted and due dates of jobs could be unequal. The dominance rules are utilized to develop a relationship matrix, which allows a branch‐and‐bound algorithm to eliminate a high percentage of infeasible solutions. After combining this matrix with a branching strategy, a procedure to solve the problem is proposed. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 760–780, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10039     

Branch‐and‐price‐and‐cut for the manpower routing problem with synchronization constraints

In this article, we propose a branch‐and‐price‐and‐cut (BPC) algorithm to exactly solve the manpower routing problem with synchronization constraints (MRPSC). Compared with the classical vehicle routing problems (VRPs), the defining characteristic of the MRPSC is that multiple workers are required to work together and start at the same time to carry out a job, that is, the routes of the scheduling subjects are dependent. The incorporation of the synchronization constraints increases the difficulty of the MRPSC significantly and makes the existing VRP exact algorithm inapplicable. Although there are many types of valid inequalities for the VRP or its variants, so far we can only adapt the infeasible path elimination inequality and the weak clique inequality to handle the synchronization constraints in our BPC algorithm. The experimental results at the root node of the branch‐and‐bound tree show that the employed inequalities can effectively improve the lower bound of the problem. Compared with ILOG CPLEX, our BPC algorithm managed to find optimal solutions for more test instances within 1 hour. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 138–171, 2016     

A bidirectional heuristic for maximizing the net present value of large‐scale projects subject to limited resources

We consider the scheduling of large‐scale projects to maximize the project net present value given temporal and resource constraints. The net present value objective emphasizes the financial aspects of project management. Temporal constraints between the start times of activities make it possible to handle practical problem assumptions. Scarce resources are an expression of rising cost. Since optimization techniques are not expedient to solve such problems and most heuristic methods known from literature cannot deal with general temporal constraints, we propose a new bidirectional priority‐rule based method. Scheduling activities with positive cash flows as early and activities with negative cash flows as late as possible results in a method which is completed by unscheduling techniques to cope with scarce resources. In a computational experiment, we compare the well‐known serial generation scheme where all activities are scheduled as early as possible with the proposed bidirectional approach. On the basis of a comprehensive data set known from literature containing instances with up to 1002 activities, the efficiency of the new approach is demonstrated. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2003     

Replacing nonidentical vital components to extend system life

We consider a system that depends on a single vital component. If this component fails, the system life will terminate. If the component is replaced before its failure then the system life may be extended; however, there are only a finite number of spare components. In addition, the lifetimes of these spare components are not necessarily identically distributed. We propose a model for scheduling component replacements so as to maximize the expected system survival. We find the counterintuitive result that when comparing components' general lifetime distributions based on stochastic orderings, not even the strongest ordering provides an a priori guarantee of the optimal sequencing of components. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

SpaceWire网络混合路由机制设计

针对星上系统总线多元性导致的星载网络接口和协议不能标准化的发展瓶颈,基于SpaceWire总线协议,通过将静态路由(时间触发)与动态路由(事件触发)机制结合,实现了控制数据和载荷数据共用网络。静态路由完全遵循SpaceWire-D协议,在保证确定性传输的同时,通过启发式调度算法首次实现了多时间窗并行调度,并提出利用最大公约数法设计时间窗,以提高网络吞吐量;动态路由通过对随机事件和载荷数据分配优先级,实现传输路径冲突时对紧急任务的优先处理。在OPENT中搭建网络系统仿真模型,对所提出的路由机制进行了仿真。实验结果表明,静态路由时段网络吞吐量较现有调度算法有明显提高,动态路由实现了紧急事件优先传输。     

面向多星观测调度的分层迭代算法

提出一种基于分治策略的多星观测分层调度框架,在该框架下,用蚁群优化算法把任务分配至各轨道圈次上,并利用自适应模拟退火算法求解各轨道圈次的调度问题。根据各轨道圈次调度结果的反馈情况,再调整任务分配方案,重复上述过程直到达到算法终止条件。为了提高算法的性能,在设计蚁群算法的启发式信息模型时,应充分考虑卫星调度问题的领域知识;在模拟退火算法中设计两个邻域结构,采用动态选择策略在优化过程中确定最佳邻域搜索结构。仿真实验表明,该方法有效地降低了问题求解的复杂度,尤其在求解大规模多星观测调度问题时表现出优异的性能。     

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

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