第二节  生产调度问题的主要研究方法及研究策略

一、研究方法

在对调度问题进行研究的方法上，最初是集中在数学规划、仿真和简单的规则上，这些方法不是调度结果不理想就是难以解决复杂的调度问题随着各种新的相关学科与优化技术的建立与发展，在调度领域出现了许多新的优化方法，比如基于人工智能、计算智能和实时智能的各种调度方法，这些方法已经成为调度方法的主流。

(一)数学规划方法

数学规划方法就是运筹学方法，它将生产调度问题简化为数学规划模型，采用整数规划、动态规划以及决策分析等方法来解决调度最优化或近似优化问题，也称为优化调度方法。生产调度中广泛使用的是混合整数线性规划和混合整数非线性规划方法。

数学规划方法的优点是任务分配和排序的全局性比较好，所有的选择同时进行，因此可以保证求解凸和非凸问题的全局优化，但是，数学规划方法是一种精确求解方法，它需要对调度问题进行统一的建模，任何参数的变化会使得算法的重用性很差，因此，对于复杂多变的生产调度来说，单一的数学规划模型不能覆盖所有的因素，存在求解空间大和计算困难等问题。

(二)启发式搜索方法

启发式搜索方法最初是作为人工智能中问题求解程序的搜索器而被开发出来的启发式搜索方法依靠任务无关信息来简化搜索过程，在很多情况下，问题求解可视为系统化地构造或查找解答的过程。

启发式搜索方法的优点是利用了面向特定问题的知识和经验，因而可以产生好的解决方案，求解时间也可以接受。启发式搜索方法的缺点是用来评估解决方案的质量手段还较少，如何提高搜索效率并减少内存使用以解决规模较大的问题，还需要进一步探索。

(三)系统仿真方法

基于仿真的方法不单纯追求系统的数学模型，它侧重于对系统中运行的逻辑关系的描述，而且与数学规划采用全局的而且经常是简化的视图相比，它对所有分配、排序和时间选择决策的结果提供局部的分析，通过分析能够对生产调度方案进行比较评价，并选择效果最优的生产调度方法和系统动态参数，系统仿真方法经常与其他方法结合使用。

由于生产系统的复杂性，很难用一个精确的解析模型来进行描述和分析，而通过运行仿真模型来收集数据，则能对实际系统进行性能和状态等方面的分析，从而能对系统采用合适的控制调度方法，之所以把仿真方法与其他方法结合使用，是因为纯仿真方法有以下局限性：应用仿真方法进行生产调度的费用很高，不仅在于产生调度的计算时间上，而且在于设计、建立和运行仿真模型上;仿真的准确性受人员的判断和技巧的限制，甚至很高精度的仿真模型也无法保证通过实验总能找到最优或次优的调度。

(四)人工智能方法

人工智能在20世纪60年代就将计划和调度问题作为其应用领域之一，但直到20世纪80年代，以Carnegie Mellon大学的M Fox 为代表的学者们开展基于约束传播的智能调度和信息系统的研究为标志，人工智能才真正开始应用于实际调度问题。基于人工智能的调度方法主要有智能调度专家系统、约束规划(constraint programming， CP)及基于Multi-Agent技术(multi-agent system， MAS)的合作求解方法等。

1.智能调度专家系统

专家系统在20世纪80年代早期和中期非常流行，它在许多领域也得到了应用，如果要建立一个专家系统，首先需要构建相关的知识库，就是从知识源获取知识然后以数字化形式存储它们，在调度问题中，知识源一般指的是人类专家和模拟数据。

调度专家系统主要的优点在于：在决策过程中，它既可以使用定量的知识，又可以使用定性的知识;它能够产生比简单的分配规则复杂得多的启发式规则，然而，调度专家系统也有其不可克服的缺点：构建和验证系统比较耗费时间;难以维护和升级;求解结果可能会严重偏离最优解或次优解;知识获取和推理速度存在瓶颈。

2.约束规划

约束规划是一种旨在应用限制变量选取顺序和变量赋值顺序来减少搜索空间有效大小的方法。当一个值赋给一个变量时，产生的不一致性就消除了，消除不一致性的过程称做一致性检测，而消除以前做的工作称做回溯。

约束规划可以用来实施柔性的和有效的调度系统，因为它把各种不同的算法包装成传播器，使得可以对可重用的求解器进行规划。约束规划不局限于一定的约束集合，因为它使用了一个纯声明的(declarative)模型，每一个传播器定义问题的一个独立视图，但是这一方法的求解代价比较大，而且由于考虑了多种约束，求解难度很大。

3.基于MAS的合作求解方法

专家系统很难用来解决大规模的复杂的实际调度问题，因为它们的知识和问题求解能力是有限的。为了解决这些复杂问题，研究人员使用“分而治之(divide and conquer)”的方法来开发分布式调度系统，这需要一种分解调度问题的技术以及能够协作求解整个问题的相关的知识系统的集合，这些可以通过MAS来实现。

MAS技术可以弥补调度理论的不足，可以增强调度理论在实际应用中的灵活性;MAS可以和其他各种生产控制技术如企业资源计划(enterprise resources planning，ERP)、最优生产技术(optimized production technology， OPT)和制造执行系统(manufacturing executing system， MES)等结合起来使用。MAS的不足之处就是在理论上有待进一步完善，标准化工作不够，导致重复劳动。

(五)计算智能方法

计算智能是在神经网络、模糊系统、进化计算3个分支发展相对成熟的基础上，通过相互之间的有机融合而形成的新的科学方法，也是智能理论和技术发展的崭新阶段。这些不同的成员方法从表面上看各不相同，但实际上它们是紧密相关、互为补充和促进的，因而，将三者结合起来研究已经成为一种发展趋势。主要的计算智能调度方法有人工神经网络、混沌搜索、模拟退火和随机机、禁忌搜索、模糊逻辑、遗传算法、进化规划和进化策略等。

1.人工神经网络

“人工神经网络”(artificial neural network， ANN)是在对人脑组织结构和运行机制认识理解的基础上模拟其结构和智能行为的一种工程系统。

人工神经网络具有很强的分布式存储能力和很大的存储空间，而且具有自学习能力;再者容错性好，其特有的高维空间使多体效应更加复杂和显著，易于分类。但是，人工神经网络在实际生产中的应用不是很多，而且存在学习效率比较差、难以表达符号知识以及其他知识、计算速度比较慢和计算精度不高等缺点，这些都需要进一步改进。

2.模拟退火方法

自从Kirkpatrick， Gelatt Jr和Vecchi在前人对统计力学研究的基础上发表了他们开创性的论文“Optimization by Simulated Annealing ”以来，模拟退火算法(simulated annealing， SA)被赞誉为解决许多高难度调度和组合优化问题的“救星”，它是根据液态和固态材料中粒子的统计力学规律与复杂组合优化问题求解过程的相似之处而提出来的，已经应用到许多领域。

模拟退火算法显示出了求解优化问题的强大威力，它可以突破局域搜索的限制，转移到代价较高的解答，而且如果选择参数得当，会在很快的时间内收敛。但是，模拟退火算法在实际应用中往往不能产生较优的结果，而且各个参数选择起来比较困难，如果选择不得当，就会使得计算时间很长，而且可能得不到好的结果。模拟退火算法和其他算法结合使用会得到很好的效果，如和遗传算法、人工神经网络结合等。

3.模糊逻辑

1965年，美国控制论专家Zadeh 教授首先提出模糊集合的概念，发表了开创性论文“模糊集合论(fuzzy sets)”他提出，模糊数学的核心思想就是运用数学手段，仿效人脑思维，对复杂事物进行模糊处理。1973年，Zadeh教授又提出模糊逻辑(fuzzy logic)的理论，并积极倡导将模糊理论向人工智能方向发展。模糊集理论对于建模和求解Job-shop调度问题是非常有用的，因为它就具有许多模糊特征，比如不确定的加工次数、不确定的约束数量以及不确定的加工时间等。

模糊系统的显著特点是能够直接地表示逻辑，适于高级知识表达，具有较强的逻辑功能。但它没有本质的获取知识的能力，模糊规则的确定也比较困难，通常需要领域专家知识的指导，因此如何实现模糊规则的自动提取和模糊变量隶属度函数的自动生成及优化，一直是一个难题。模糊调度方法通常和其他方法结合使用，如模糊神经网络和基于模糊规则的分枝定界法等。

4.遗传算法

美国Holland 教授1975年首次提出的遗传算法(genetic algorithm， GA)是一类通过模拟生物界自然选择和遗传机制的随机搜索算法。遗传算法对求解问题本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并根据适应性进行选择，使适应性好的染色体比适应性差的染色体有更多的繁殖机会，经过反复迭代，直到达到某种形式的收敛遗。传算法尤其适用于处理传统搜索方法难以解决的复杂的非线性问题，可广泛用于组合优化、机器学习和规划设计等领域。已经有一些研究人员把遗传算法应用到生产调度问题中，使用遗传算法求解生产调度问题的主要工作有：生产问题到遗传编码的转换、字符串操作符的选择和限制搜索空间的约束描述等。

遗传算法已经成为一种比较通用的优化算法，主要原因是其编码技术和遗传操作比较简单，优化不受限制性条件的约束，但是遗传算法也有其明显的不足之处：对于大规模的组合优化问题，搜索空间大，搜索时间较长;往往会出现早熟收敛的情况;对初始种群很敏感，初始种群选择不好会影响解的质量和算法效率。为了进一步改进遗传算法，人们主要从两方面入手：一是对遗传算法本身进行改进;二是与其他算法结合，取长补短。

(六)实时智能方法

将实时技术和人工智能相结合，形成一个新的技术领域，人们称之为“实时智能”。可以这样通俗地定义实时智能：“实时智能是指在一定的时间范围内能够实现的人工智能”。实时智能主要应用于实时系统的调度中，其中的调度算法又是实时调度的核心部分，也是实时系统的研究热点。有些生产调度问题对实时性要求很高，因此，研究实时智能方法在生产调度中的应用也是非常必要的。

二、生产调度问题的研究策略

调度策略是车间调度高层次的决策部分，由于调度问题的复杂性，因而在实际的研究过程中逐渐形成了不同的调度策略支持，大致可分为以下几种：

(一)并行或分布策略适应不同车间控制结构与调度问题复杂性的实际需要，不少学者提出并行或分布策略来解决调度问题。

(二)分解与成组策略利用分解生产计划或GT的调度策略可以大大降低问题的计算复杂性和规模，求得调度问题的较优解，同时优化系统的一些性能指标。

(三)人机协同策略调度问题的性质、现有研究方法的缺陷以及人类独特的思维能力决定了人机协同策略的生命力。大量的研究成果表明：人机协同交互的策略可以减少系统的搜索空间，可在有限时间、背景知识条件下解决困难的问题。

(四)实时或动态重调度策略车间制造过程的随机性、不确定性需要不断地进行重调度，以处理突发的事件。基于目前的研究，对于动态调度的具体策略有：周期调度，连续调度，事件驱动调度，周期与事件驱动混合调度，周期与连续调度混合的策略等。

这篇关于生产调度概述分析研究的文章，希望给正在阅读本文的你带来帮助!

相关推荐：

高速地铁隧道内风压变化研究  

浅谈机械企业外贸管理策略