基于禁忌搜索的启发式任务路径规划算法

基于启发式搜索和禁忌搜索技术,提出一种用于解决有限资源、不同重要性要求的任务路径规划问题的有效算法,通过对不同重要程度的任务进行分层调度,得到较为满意的决策结果.该算法具有搜索空间小、求解速度快的优点.仿真结果验证了算法的有效性.     

基于禁忌搜索的启发式任务路径规划算法

基于启发式搜索和禁忌搜索技术，提出一种用于解决有限资源，不同重要性要求的任务路径规划问题的有效算法，通过对不同重要程度的任务进行分层调度，得到较为满意的决策结果，该处具有搜索空间小，求解速度快的优点。仿真结果验证了算法有效性。     

基于多蚁群并行优化的网络路径规划研究

在军事后勤、应急救灾中,需要同时为多个任务、多批次物资运输制定保障方案,该问题可归结为多源多汇问题,是NP-C的。本文提出一种基于多蚁群并行优化的网络路径规划算法,按照一定的策略对关键网络资源进行调度分配,尽可能为每一个任务规划满足网络属性约束及用户服务质量要求的独立网络路径,使任务完成率最高。仿真示例验证了该模型和算法的正确性。     

考虑通信竞争的任意处理机网络表调度算法

任务调度是高性能计算系统中的基本问题之一。解决此类NP难问题的经典启发式算法都假定目标处理机全互连,调度任务时可忽略节点间通信,这显然与实际计算环境不符。为此,文中提出一种在调度任务时同时考虑通信边调度的表调度算法。在边调度时,提出了一种基于最短路径搜索算法的最早通信完成路径查找算法(EFCS),并采用插入式链路策略实现通信边的动态调度,而对处理机网络异构环境下的任务优先级计算问题,受HEFT算法启发,提出异构系统递归优先权计算方法,按非升序排列获得各任务优先级。为了降低算法的执行时间,文中还提出了理论加速比为O(PPE)的并行算法。以随机产生程序任务图和DSP应用程序实例为数据源,在两类不同任意处理机网络目标系统上进行的模拟实验结果表明:本算法明显优于考虑通信竞争的静态表调度算法和不考虑通信竞争的表调度算法,特别是在高通信率应用程序中优势更明显。     

改进遗传算法的并行任务调度

并行任务调度是一个NP完全问题,它关注资源的分配和并行任务调度,要求具有高性能的调度算法,且能求解出高质量的解。提出了一种基于改进遗传算法的并行任务调度算法,在算法初始化种群产生时引入任务向量矩阵来表示任务、资源以及调度的关系,并采用启发式方法得到初始化种群,提高种群质量;采用规则约束的交叉和变异操作,提高个体的质量;提出了加速进化策略,有效地避免了早熟。仿真实验结果表明,该改进算法能更有效地求解并行任务调度问题。     

单调比率(RM)调度算法及应用

介绍了任务死线不大于其周期的任务集调度条件分析及算法实现。这种约束条件放松, 有利于周期与非周期任务混合模型调度。同时,分析了以往调度算法中单调比率调度算法约束条件, 并指明了计算时间复杂度的缺点。因而,在RM算法基础之上提出一种实时系统调度算法及实现流 程图,并对提出的现场级实时调度算法进行了对比测试。     

临近空间飞行器对地观测调度方法研究

临近空间飞行器对地观测调度是军事应用中的重要问题,对于最大化地满足对地观测任务需求、提高飞行器资源利用率具有重要作用。针对临近空间飞行器观测系统的调度问题,考虑任务需求约束、载荷约束等条件下,为实现快速高效侦察任务,构建了临近空间飞行器对地观测的数学模型。然后分析了观测任务之间存在的可能冲突,利用任务可能冲突概念,这一概念将整个任务集分割为可能冲突任务集。随后给出了任务执行冲突度的计算方法,通过对给定任务序列冲突度的计算,提出了一种基于冲突消解的遗传模拟退火算法。通过仿真实例验证了算法的有效性。     

人工蜂群算法求解资源受限项目调度问题

针对资源受限项目调度问题,提出了一种基于人工蜂群算法的优化方法。人工蜂群算法中每个食物源的位置代表一种项目任务的优先权序列,每个食物源的位置通过扩展串行调度机制转换成可行的调度方案,迭代中由三种人工蜂执行不同的操作来实现全局最优解的更新。实验结果表明,人工蜂群算法是求解资源受限项目调度问题的有效方法,同时扩展调度机制的引入可以加速迭代收敛的进程。     

基于优先规则的空间资源约束项目调度算法

任务组占用空间资源项目调度问题需满足组内任务的序关系和人力、设备等常规资源约束,以及空间资源这一特殊资源的约束,同时任务组之间也需满足上述约束,使得该调度问题异常复杂。以船舶建造分段制造问题为背景,建立任务组占用空间资源受限的项目调度问题数学模型,基于并行调度生成方案提出基于优先规则的启发式调度算法,实现对该调度问题的综合求解。实例测试结果表明了该算法的正解性和有效性。     

调度Fork-Join任务图的贪心算法

任务调度算法的目标是把组成并行程序的一组任务分配到多个处理器以使得程序的完成时间最短,这是一个NP完全问题.虽然许多算法在任务满足某些条件时能产生最优调度,但大多都忽略了节省处理器个数和最小化程序总的完成时间等问题.Fork-Join结构是一种并行处理的基本结构.因此,专门针对Fork-Join任务图,提出了一个能产生最优调度的新的贪心调度算法,该算法具有高的加速比和总体效率,时间复杂度为O(v2),其中,v表示任务集中任务的个数.实验结果表明,相比其它算法,该算法具有较短的调度长度、较短的完成时间,使用的处理器数较少.     

基于改进遗传算法的星地任务优化调度研究

星地任务优化调度是利用特定的星地资源合理地安排星地任务。由于星地任务众多而资源有限,而且星地任务受星地可见性以及多方面约束,星地任务调度问题十分复杂。针对星地任务的特点,建立了星地任务调度问题模型,提出了基于改进遗传算法的星地任务优化调度算法。算法采用按适应度排名轮盘赌选择、顺序交叉、随机对换变异的算法要素。针对遗传算法局部搜索能力弱的特点,提出了利用爬山算法优化新一代个体的方法,以增强遗传算法的局部搜索能力,给出了基于改进遗传算法的星地任务调度算法。     

面向多星任务规划问题的改进遗传算法

卫星数量的快速增加为管控卫星的工作增加了很大的难度,如何有效地进行任务规划,有效管理卫星资源,成为了卫星领域的一个重要问题.针对此问题,本文构建了多星任务规划的数学模型,将最大化任务收益作为优化目标.本文分析了问题的难点并提出了一种包含两种优化策略的改进遗传算法,包括全局优化和局部优化两部分.全局优化和局部优化根据种群改进情况进行自适应切换.通过两种优化方法的结合可以提升任务规划的效果.本文还提出了一种任务规划算法,用于为改进遗传算法得到的任务序列选择合适的任务执行时间.仿真实验证明本文提出的改进遗传算法可以很好地解决多星任务规划问题,与对比算法相比可以得到更优的规划结果.改进遗传算法有很好的工程应用前景.     

Integration of process planning and scheduling using chaotic particle swarm optimization algorithm

Process planning and scheduling are two of the most important manufacturing functions traditionally performed separately and sequentially. These functions being complementary and interrelated, their integration is essential for the optimal utilization of manufacturing resources. Such integration is also significant for improving the performance of the modern manufacturing system. A variety of alternative manufacturing resources (machine tools, cutting tools, tool access directions, etc.) causes integrated process planning and scheduling (IPPS) problem to be strongly NP-hard (non deterministic polynomial) in terms of combinatorial optimization. Therefore, an optimal solution for the problem is searched in a vast search space. In order to explore the search space comprehensively and avoid being trapped into local optima, this paper focuses on using the method based on the particle swarm optimization algorithm and chaos theory (cPSO). The initial solutions for the IPPS problem are presented in the form of the particles of cPSO algorithm. The particle encoding/decoding scheme is also proposed in this paper. Flexible process and scheduling plans are presented using AND/OR network and five flexibility types: machine, tool, tool access direction (TAD), process, and sequence flexibility. Optimal process plans are obtained by multi-objective optimization of production time and production cost. On the other hand, optimal scheduling plans are generated based on three objective functions: makespan, balanced level of machine utilization, and mean flow time. The proposed cPSO algorithm is implemented in Matlab environment and verified extensively using five experimental studies. The experimental results show that the proposed algorithm outperforms genetic algorithm (GA), simulated annealing (SA) based approach, and hybrid algorithm. Moreover, the scheduling plans obtained by the proposed methodology are additionally tested by Khepera II mobile robot using a laboratory model of manufacturing environment.     

基于PDDL的对地观测卫星任务规划建模研究

传统的数学模型方法是解决复杂卫星任务规划问题的一种途径,但其抽象性给建模人员带来很大难度。PDDL(Planning Domain Definition Language)可以针对卫星任务规划问题建立清晰有效的模型,并能把模型的知识转化成计算机易于接受的形式。用PDDL描述对地观测卫星的任务规划问题,分析了卫星执行任务时涉及的约束、相关活动和所需的资源,建立任务规划模型的域文件(domain file)和问题(problem file)文件,并针对所建模型提出求解模型的算法流程,最后通过一个算例验证模型和算法是有效地。     

Applications of particle swarm optimisation in integrated process planning and scheduling

Integration of process planning and scheduling (IPPS) is an important research issue to achieve manufacturing planning optimisation. In both process planning and scheduling, vast search spaces and complex technical constraints are significant barriers to the effectiveness of the processes. In this paper, the IPPS problem has been developed as a combinatorial optimisation model, and a modern evolutionary algorithm, i.e., the particle swarm optimisation (PSO) algorithm, has been modified and applied to solve it effectively. Initial solutions are formed and encoded into particles of the PSO algorithm. The particles “fly” intelligently in the search space to achieve the best sequence according to the optimisation strategies of the PSO algorithm. Meanwhile, to explore the search space comprehensively and to avoid being trapped into local optima, several new operators have been developed to improve the particles’ movements to form a modified PSO algorithm. Case studies have been conducted to verify the performance and efficiency of the modified PSO algorithm. A comparison has been made between the result of the modified PSO algorithm and the previous results generated by the genetic algorithm (GA) and the simulated annealing (SA) algorithm, respectively, and the different characteristics of the three algorithms are indicated. Case studies show that the developed PSO can generate satisfactory results in both applications.     

Improved genetic algorithm based on multi-layer encoding approach for integrated process planning and scheduling problem

Integrated process planning and scheduling (IPPS) is of great significance for modern manufacturing enterprises to achieve high efficiency in manufacturing and maximize resource utilization. In this paper, the integration strategy and solution method of IPPS problem are deeply studied, and an improved genetic algorithm based on multi-layer encoding (IGA-ML) is proposed to solve the IPPS problem. Firstly, considering the interaction ability between the two subsystems and the multi-flexibility characteristics of the IPPS problem, a new multi-layer integrated encoding method is designed. The encoding method includes feature layer, operation layer, machine layer and scheduling layer, which respectively correspond to the four sub-problems of IPPS problem, which provides a premise for a more flexible and deeper exploration in the solution space. Then, based on the coupling characteristics of process planning and shop scheduling, six evolutionary operators are designed to change the four-layer coding interdependently and independently. Two crossover operators change the population coding in the unit of jobs, and search the solution space globally. The four mutation operators change the population coding in the unit of gene and search the solution space locally. The six operators are used in series and iteratively optimized to ensure a fine balance between the global exploration ability and the local exploitation ability of the algorithm. Finally, performance of IGA-ML is verified by testing on 44 examples of 14 benchmarks. The experimental results show that the proposed algorithm can find better solutions (better than the optimal solutions found so far) on some problems, and it is an effective method to solve the IPPS problem with the maximum completion time as the optimization goal.     

基于差分进化算法多处理机任务调度研究

本文主要基于现代启发式差分算法讨论多处理机调度,多处理机调度是NP组合优化问题,目前多采用启发算法。差分进化算法是最近提出的进化算法,主要根据父代个体之间矢量差构造下一代,是一种全局优化搜索方式。本文考虑采用差分进化矢量优先级模型描述调度顺序进行调度,与模拟退火算法比较得到较好调度结果。     

工序间存在零等待约束的复杂产品调度研究

针对实际装配生产中工序之间存在零等待约束的复杂产品的调度问题, 提出了一种把存在零等待约束的工序虚拟成一个工序的方法. 该方法在提出复杂产品、标准工序、虚拟工序、零等待和扩展加工工艺树的概念基础上, 对扩展加工工艺树中的标准工序采用拟关键路径法和最佳适应调度的车间调度算法进行调度, 对虚拟工序采用移动交换算法在相应设备上分离调度, 将存在零等待约束的调度问题转化为存在虚拟工序的无零等待约束的调度问题. 实例表明, 所提出的调度算法能够较好地解决具有实际意义的工序间存在零等待约束的复杂产品的调度问题, 且易于实现.