基于免疫和模拟退火原理的柔性JobShop调度研究*

为了研究柔性Job-Shop调度的不同解法,采用免疫和模拟退化原理求解柔性Job-Shop调度问题。研究了柔性处理问题,提出两种调度策略;分析了算法混合的思想,提出了免疫模拟退火算法。分别采用不同调度策略,使用不同调度算法对多种国际标准算例进行了仿真,仿真结果表明,该模型、策略和算法能够解决柔性Job-Shop调度问题。     

约束满足混合算法求解并行机Job-Shop调度问题

分析并行机Job-Shop调度问题的特点并建立其约束满足优化模型,结合约束满足与变邻域搜索技术设计了一个求解该问题的混合优化算法。该算法采用变量排序方法和值排序方法选择变量并赋值,利用回溯和约束传播消解资源冲突,生成初始可行调度,然后应用局部搜索技术增强收敛性,并通过结合问题特点设计的邻域结构的多样性提高求解质量。数据实验表明,提出的算法与其他两种算法相比,具有一定的可行性和有效性。     

一种求解Job-Shop调度问题的新型蚁群算法

Job-Shop调度问题是一类具有很高理论研究和工程应用价值的问题。针对使用蚁群算法求解Job-Shop调度问题时较难设置合适参数的问题,提出一种动态设置参数的新型蚁群求解算法。分析了蚁群算法中参数对求解结果的影响,给出了算法求解Job-Shop调度问题的关键技术和实现过程。最后对五个基本测试问题进行了仿真实验,并与遗传算法、模拟退火算法、基本蚁群算法进行了比较。结果表明,该算法能得到较优的结果,具有一定的应用价值。     

Job-Shop调度问题的仿真研究

Job-Shop是离散事件系统中典型的调度问题，通过计算机仿真能够动态地展现Job-Shop车间的状态，分析在不同调度方法下的系统性能，并运用知识和经验去选择合适的调度方法，从而改善调度性能。本文构造了Job-Shop的离散事件仿真模型，设计了基于事件驱动的仿真策略，并讨论了优先调度准则，为解决这一问题提供了一种现实可行的思路与方法。     

求解车间作业调度问题的混合遗传算法

针对Job-Shop调度问题,将自适应遗传算法与改进的蚂蚁算法融合,提出了自适应遗传算法与蚂蚁算法混合的一种优化算法。首先利用自适应遗传算法产生初始信息素的分布,再运行改进的蚂蚁算法进行求解。该算法既发挥了自适应遗传算法和蚂蚁算法在寻优中的优势,又克服了各自的不足。实验结果表明,该算法在性能上明显优于遗传算法和蚂蚁算法,并且问题规模越大,优势越明显。     

基于遗传算法的Job-Shop调度问题求解方法

调度问题是许多计算机应用领域的重要问题,Job-Shop调度是其中的一类典型的困难问题,它通常包含多个可并行实现的目标以及实现这些目标的多种方法与资源.本文以一类实用的Job-Shop问题模型为基础,给出了用遗传算法求解调度问题应采用的染色体表示方法,并针对问题的特点,给出了面向资源空间与面向规划空间的遗传操作的设计思想与方法.实验结果表明,基于遗传算法的Job-Shop调度问题求解方法具有较好的性能,同时也表明,对于求解过程中可能出现的提前收敛问题可通过改变遗传操作概率及调节适应度等方法予以解决.     

基于克隆选择的车间调度算法研究

Job-Shop调度问题(JSSP)是一个典型的N-Phard组合优化问题,作为一种性能优良的启发式并行优化算法,克隆选择算法适合用于快速求解大规模复杂多模态优化问题。文章将克隆选择算法应用于求解JSSP,获得了较好的效果。     

面向柔性工艺的作业车间调度问题混合遗传算法

针对离散制造业的许多产品采用柔性工艺设计增加作业计划调度的复杂性这一问题,对传统的FJSP进行了工序顺序柔性的扩展,将问题抽象为柔性工艺的作业车间调度问题（flexible process Job-Shop scheduling problem,FPJSP）。以缩短生产周期为目标,建立了该问题的整数规划模型,并设计了混合遗传算法。该算法针对FPJSP的特点设计了改进的遗传算法染色体编码方式和遗传算子,并结合变邻域搜索算法,设计了适合求解该问题的四种不同的邻域结构进行动态邻域搜索,以提高遗传算法的邻域搜索性能。通过应用实例验证了所提出的混合遗传算法在求解FPJSP的求解效率和优化性能方面的有效性。     

基于Petri网的IC制造调度优化

论文根据IC制造中存在的多制造路径、资源共享、可变晶片组及并发等特点,结合增强定时Petri网,提出了一种调度优化算法。该算法无论是对典型的Job-Shop问题,还是比此更复杂的问题,都能给出确实有效的优化结果,具有一定的通用性。该算法还具有较高的运行效率,文中的实验结果也充分显示了这点。     

半在线调度中约束求解算法研究

很多实际调度问题是半在线的. 尝试运用人工智能方法来求解半在线调度问题, 首先简要介绍了半在线调度问题并对其约束模型进行了分类, 通过引入单调性约束扩展的相关概念, 从约束建模角度形式化描述 了一类动态约束扩展, 并在此基础上设计了一个完备动态约束求解算法, 最后给出该算法在半在线离散资源约束调度求解的应用算例. 测试结果表明, 该算法是可行有效的.     

XML数据查询的CSP实现和算法改进

XML犤1犦正在迅速成为WWW上采用的信息交换、表示和存储手段之一,该文简单介绍了基于OEM数据模型犤2犦的离散XML数据模式概念和在此思想上发展起来的基于模式匹配的数据查询概念;通过将模式匹配转换到约束满足问题(CSP)来具体求解匹配实例,从而使WWW基于内容的查询转变为更为精确的基于结构的查询;接下来,从理论上证明了这种模式匹配到CSP转换的可行性;最后,讨论了求解CSP的算法的改进问题。     

The power of ants in solving Distributed Constraint Satisfaction Problems

Distributed Constraint Satisfaction (DCSP) has long been considered an important area of research for artificial intelligence and multi-agent systems. Also, Ant Colony Optimization (ACO) is an important evolutionary method for solving various optimization problems. This paper demonstrates the power of ants in solving DCSPs and describes a new approach for such a solution, showing how it differs from previous ACO-based DCSP solvers. The presented algorithm is designed to provide the special requirements that are important in the distributed form of Constraint Satisfaction Problem (CSP). The paper describes the important criteria for distributed CSP and then demonstrates how the presented algorithm stands out over similar DCSP solvers considering these criteria. Finally, the proposed approach is evaluated on random binary problems. The practical results show that this method, in most of the cases, outperforms the Asynchronous Backtracking Algorithm (ABT) and Distributed Breakout Algorithm (DBA) two important algorithms in this field of research.     

结合方向关系和拓扑关系的约束满足推理

结合定性空间推理中的区域连接演算（RCC）和基于区域的主方向关系模型,应用拓扑和方向关系上的复合表,将方向关系和拓扑关系的推理看作约束满足问题（CSP）,给出了结合RCC8和主方向关系的约束满足问题推理算法,该算法可结合拓扑关系和方向关系进行推理。     

A constraint propagation heuristic for the single-hoist,multiple-products scheduling problem

A heuristic algorithm for solving the single-hoist, multiple-product scheduling problem is presented. The algorithm uses a non-standard Constraint Satisfaction Problem model and employs variable ordering, forward checking and backtracking. Computational results, including comparison with existing algorithms in terms of solution quality and speed, are presented.     

约束满足问题中一致性算法的分析与研究

约束满足问题是人工智能领域的重要研究方向,其求解方法有三种,搜索、一致性算法和约束传播,其中一致性算法通常通过缩减问题域来提高搜索算法的效率.着重介绍了几种常用的一致性算法,并对几种常用算法进行了分析、比较和研究.     

基于改进的基因表达式编程算法在作业车间调度问题中的应用

文章提出一种新颖的方法一改进的基因表达式编程算法来求解作业车间调度问题。作业车间调度问题是许多实际生产调度问题的简化模型,基因表达式编程算法结合了遗传算法和遗传编程的优点,具有更强的解决问题能力,对基因表达式编程算法进行改进使其在作业车间调度问题的应用上更加有效;最后应用一个实例来验证提出方法的有效性。     

相关工件车间调度问题的拓扑算法

针对加工装配型离散制造企业实际生产的特点,提出了一类用于表示工序之间偏序关系的相关工件车间调度问题。为了利用已有的求解表示工序之间的线序关系的传统车间调度算法求解相关工件车间调度问题,设计了一种拓扑算法,该算法能够将工序之间的偏序关系转化为线序关系,将相关工件车间调度问题转化为传统的车间调度问题,通过实证研究,结果表明了拓扑算法是可行和高效的。     

基于改进烟花算法的密集任务成像卫星调度方法

传统卫星调度模型一般比较简单,当问题规模较大、任务比较集中时,往往会出现任务之间相互排斥,任务收益较低等缺点。针对这个问题,提出一种基于改进烟花算法（IFWA）的密集任务成像卫星调度方法。该方法在分析密集任务处理及成像卫星观测特点的基础上,首先对任务进行合成约束分析,然后基于合成任务综合考虑成像卫星可观测时间、任务间姿态调整时间、成像卫星能量和容量等约束因素,建立基于任务合成的多星密集任务调度约束满足问题（CSP）模型,最后改进烟花算法对该模型进行求解,利用精英选择策略在保证种群多样性同时加快了算法的收敛,得到较优的卫星调度方案。仿真结果表明该模型相比没有考虑任务合成因素,收益平均增加30%~35%,改进算法后效率上提升32%~45%,有效保证了调度方案的可行性和有效性。     

Introduction to planning, scheduling and constraint satisfaction

Planning, scheduling and constraint satisfaction are important areas in artificial intelligence (AI). Many real-world problems are known as AI planning and scheduling problems, where resources must be allocated so as to optimize overall performance objectives. Therefore, solving these problems requires an adequate mixture of planning, scheduling and resource allocation to competing goal activities over time in the presence of complex state-dependent constraints. Constraint satisfaction plays also an important role to solve real-life problems, so that integrated techniques that manage planning and scheduling with constraint satisfaction remains necessary. This special issue on Planning, Scheduling and Constraint Satisfaction compiles a selection of papers of CAEPIA’2007 workshop on Planning, Scheduling and Constraint Satisfaction and COPLAS’2007: CP/ICAPS 2007 Joint Workshop on Constraint Satisfaction Techniques for Planning and Scheduling Problems. This issue presents novel advances on planning, scheduling, constraint programming/constraint satisfaction problems (CSPs) and many other common areas that exist among them. On the whole, this issue mainly focus on managing complex problems where planning, scheduling, constraint satisfaction and search must be combined and/or interrelated, which entails an enormous potential for practical applications and future research. Furthermore, this issue also includes a complete survey about constraint satisfaction, planning, scheduling and integration among these areas.     

方位关系约束满足问题的推理求解

约束满足问题（Constraint Satisfaction Problems CSP）是人工智能的一个研究领域,诸如空间查找、规划等问题都可转化为约束满足问题。方位关系是空间关系的重要组成部分,用以确定空间对象间的一种顺序。本文研究了空间方位关系模型,给出了方位关系约束的一般表示形式。在此基础上,利用组合表推理给出了方位关系约束满足问题的一个推理求解算法,该算法的时间复杂度为O（n^2）。