应用于流水时序调度的归一化定时数据流图理论

流水时序调度是专用数字信号处理器高层综合中的一个困难而急待解决的问题 ,文中提出了一种有着鲜明物理意义的归一化定时数据流图 ,基于节点移动研究了合法流水调度变换的内部机理 ,从而证明从任一合法的初始流水调度出发 ,通过合法的节点移动可以搜索到设计空间中任何一个合法的流水调度。一个合法、完备的变换集 ,为寻优搜索的算法应用于流水调度解决了理论和算法实现问题。文中还给出了一些实验结果。     

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

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

基于蚁群算法的直线边缘提取方法

提出了一种基于蚁群算法的直线边缘提取方法.利用相邻边缘点的相位信息作为蚁群搜索的启发信息,同时引入终止概率,在不满足搜索条件时终止搜索.迭代搜索完成后,最后根据边缘点上的信息素遗留,提取出直线边缘.实验结果表明,该方法在检测直线边缘的同时,还可以保留边缘的细节,定位直线边缘的端点.     

舰载机多机一体化机务保障调度研究

针对舰载机多机一体化机务保障调度问题,以出树、入树的形式描述实际保障过程中并行工序的约束关系,以最大保障完工时间和资源负载均衡性为目标,构建了舰载机多机一体化机务保障非线性多目标混合流水车间调度模型,并设计了一种结合基于Insert的动态邻域爬山搜索策略和并行工序的同步化修正的Memetic算法求解该模型。最后通过实例仿真验证了模型和所提算法的可行性和有效性。     

电子侦察卫星联合侦察的混合调度算法

针对电子侦察卫星的使用约束,及不同任务的调度需求,建立了电子侦察卫星联合侦察的多目标混合整数规划模型.利用进化算法的全局搜索能力和变邻域搜索的局部优化能力,提出了一种多目标进化算法和变邻域搜索相结合两阶段混合调度算法MOEA VNS.针对问题多时间窗组合优化特点,设计了进化算子与邻域移动算子,在确保解多样性的同时使算法...     

改进遗传算法的相控阵雷达自适应调度算法及仿真

多功能相控阵雷达因其阵列天线的波束捷变能力,可执行对多个目标交替搜索、验证、跟踪等任务,而如何在时间约束下分配任务,对雷达性能有着决定性的影响。使用一种有效的调度算法能够使雷达资源合理分配,能够让雷达整体性能优化。在分析自适应调度算法的设计原则基础上,给出了具体的性能评估指标。针对多功能相控阵雷达,改进了传统的遗传算法作为调度算法。算法能够在雷达调度间隔约束下,选择综合效能最好的方案安排一个调度间隔内的雷达事件序列,并通过仿真结果验证了算法的有效性。     

考虑随机回放的卫星数传调度问题的一种求解方法

针对考虑随机回放的卫星数传调度问题,从置换空间到调度解空间的映射方法和置换空间的搜索算法两方面进行了研究.提出了一种时间窗优先的置换序列映射算法,并证明该映射算法可以将置换序列映射到调度解空间上的最优解.提出了一种遗传随机搜索算法,基于有记忆功能的随机邻域搜索,在置换空间上搜索产生优化调度的置换序列.仿真计算表明,遗传随机搜索算法可以增强遗传算法的局部搜索能力,在搜索结果上平均获得了2.72%的改进.     

基于改进布谷鸟算法的目标分配问题

针对防空作战中目标分配的实时性、动态性、高效性以及作战决策的稳定性需求,基于种群协同进化思想提出一种免疫-布谷鸟算法。通过建立种群协同进化机制,利用两个种群进行不同方向的搜索并实时进行信息交互,加快算法收敛速度;利用布谷鸟算法参数少、易实现及较好的全局搜索能力,以及基于免疫机制的高斯变异算子较强的局部搜索能力,实现了求解速度和解的精度的平衡问题,提高算法的进化活力和求解效率。仿真实验表明,改进的布谷鸟算法与传统的目标分配算法相比,求解效率和性能上有明显提高,新算法求解目标分配问题是有效可行的。     

部队铁路输送路径选择算法研究

根据部队铁路输送要求和铁路路网特点,设计了基于辅助信息的双向A＊路径搜索算法,采用二次读入边数据方法表示路网,利用前向关：联边存储结构存储路网,应用经验知识限制算法的搜索区域,通过使用常量系数β提高了启发函数的信息性。实验结果表明,算法的改进是有效和实用的。     

基于改进蚁群算法的飞机航路规划研究

由于飞机在遂行作战任务时面临的飞行环境较为复杂,针对飞行区域内地形特征多样、威胁信息不确定的问题,提出了一种改进的蚁群算法,将飞行区域和威胁源映射到三维空间中以实现飞机规避威胁源的航路规划,该算法的特点主要是可变的搜索步长和信息素动态更新机制,设计了合理的启发值和适应度值计算方式,使规划出的航路能够利用地形优势隐蔽自身.仿真结果表明,该算法能够合理规划出满足飞行任务的航路,有效躲避威胁源.     

Bicriteria scheduling on a single batching machine with job transportation and deterioration considerations

We study a single batching machine scheduling problem with transportation and deterioration considerations arising from steel production. A set of jobs are transported, one at a time, by a vehicle from a holding area to the single batching machine. The machine can process several jobs simultaneously as a batch. The processing time of a job will increase if the duration from the time leaving the holding area to the start of its processing exceeds a given threshold. The time needed to process a batch is the longest of the job processing times in the batch. The problem is to determine the job sequence for transportation and the job batching for processing so as to minimize the makespan and the number of batches. We study four variations (P1, P2, P3, P4) of the problem with different treatments of the two criteria. We prove that all the four variations are strongly NP‐hard and further develop polynomial time algorithms for their special cases. For each of the first three variations, we propose a heuristic algorithm and analyze its worst‐case performance. For P4, which is to find the Pareto frontier, we provide a heuristic algorithm and an exact algorithm based on branch and bound. Computational experiments show that all the heuristic algorithms perform well on randomly generated problem instances, and the exact algorithm for P4 can obtain Pareto optimal schedules for small‐scale instances. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 269–285, 2014     

嵌入式操作系统多策略调度模型

分析了目前嵌入式操作系统调度策略的现状,指出了传统调度方法的不足之处,给出了多策略调度模型,该模型根据进程的属性参数决定采用哪种调度算法。多策略调度模型采用两级调度方案,即在原传统调度方法的基础上增加一级调度。一级调度确定多个调度算法的优先顺序;二级调度确定同一种调度算法中,的进程优先顺序。该模型使进程调度更加灵活和高效,应用范围更广。     

Server scheduling on parallel dedicated machines with fixed job sequences

We consider server scheduling on parallel dedicated machines to minimize the makespan. Each job has a loading operation and a processing operation. The loading operation requires a server that serves all the jobs. Each machine has a given set of jobs to process, and the processing sequence is known and fixed. We design a polynomial‐time algorithm to solve the two‐machine case of the problem. When the number of machines is arbitrary, the problem becomes strongly NP‐hard even if all the jobs have the same processing length or all the loading operations require a unit time. We design two heuristic algorithms to treat the case where all the loading times are unit and analyze their performance.     

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

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

Alternate methods of project scheduling with limited resources

The applicability of critical path scheduling is limited by the inability of the algorithm to cope with conflicting resource demands. This paper is an assessment of the effectiveness of many of the heuristic extensions to the critical path method which resolve the conflicts that develop between the resources demanded by an activity and those available. These heuristic rules are evaluated on their ability to solve a large multiproject scheduling problem.     

SpaceFibre网络服务质量时隙资源分配算法

为保证SpaceFibre星载数据网络大量实时数据流的超高速确定性传输,提出一种包含两个子算法的SpaceFibre网络服务质量时隙资源分配算法。形式化描述网络服务质量机制,给出调度矩阵相关定义;创建网络服务质量排队模型,定量分析时隙资源分配对网络时延性能的影响;考虑网络兼容性和算法鲁棒性,给出改进二进制序列调度子算法;采用提高初始种群进化程度和增加遗传算子等方法,给出改进混合单亲遗传调度子算法;利用Opnet网络仿真平台建立网络服务质量仿真模型,对比不同算法下网络时延性能。仿真结果表明,该时隙资源分配算法与其他算法相比,网络平均延时降低,网络性能得到显著改善,对构建低延时SpaceFibre网络具有参考意义。     

Scheduling of depalletizing and truck loading operations in a food distribution system

This paper studies a scheduling problem arising in a beef distribution system where pallets of various types of beef products in the warehouse are first depalletized and then individual cases are loaded via conveyors to the trucks which deliver beef products to various customers. Given each customer's demand for each type of beef, the problem is to find a depalletizing and truck loading schedule that fills all the demands at a minimum total cost. We first show that the general problem where there are multiple trucks and each truck covers multiple customers is strongly NP‐hard. Then we propose polynomial‐time algorithms for the case where there are multiple trucks, each covering only one customer, and the case where there is only one truck covering multiple customers. We also develop an optimal dynamic programming algorithm and a heuristic for solving the general problem. By comparing to the optimal solutions generated by the dynamic programming algorithm, the heuristic is shown to be capable of generating near optimal solutions quickly. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2003     

An exact branch‐and‐price algorithm for multitasking scheduling on unrelated parallel machines

We consider the multitasking scheduling problem on unrelated parallel machines to minimize the total weighted completion time. In this problem, each machine processes a set of jobs, while the processing of a selected job on a machine may be interrupted by other available jobs scheduled on the same machine but unfinished. To solve this problem, we propose an exact branch‐and‐price algorithm, where the master problem at each search node is solved by a novel column generation scheme, called in‐out column generation, to maintain the stability of the dual variables. We use a greedy heuristic to obtain a set of initial columns to start the in‐out column generation, and a hybrid strategy combining a genetic algorithm and an exact dynamic programming algorithm to solve the pricing subproblems approximately and exactly, respectively. Using randomly generated data, we conduct numerical studies to evaluate the performance of the proposed solution approach. We also examine the effects of multitasking on the scheduling outcomes, with which the decision maker can justify making investments to adopt or avoid multitasking.