生产调度概述分析研究.doc

生产调度概述分析研究来源：磁铁 第一节 生产调度概述 一、生产调度定义 广义地讲，调度问题考虑的是随着时间的变化，如何调度有限的资源在执行任务的同时满足特定约束。资源可能就其本质是很不相同的，如人力、金钱、机器、工具、材料、能源等等。任务也可以有很大的不同，从制造系统的机器划分到计算机系统的信息处理等。一项任务通常可以由下面的因素来表示特征：完成时间、预期时间、相对紧急权重、处理时间和资源消耗。生产调度的含义，是指在生产作业的过程中，针对运行中出现的矛盾与问题，对生产活动与相关资源所进行的调节与协调，是指根据生产的实时数据以及历史资料数据，现场动态的协调人员、物料、设备以最大可能的优化生产 。生产调度就是对一个可用的加工机床集在时间上进行加工任务集分配，以满足一个性能指标集。从数学规划的角度看，生产调度问题可表示为在等式或不等式约束下，对目标函数的优化。典型的生产调度问题包括一个要完成的作业集，每个作业由一个操作集组成，各操作的加工需要占用机床或其它资源，并且必须按一些可行的工艺次序进行加工；每台机床可加工工件的若干操作，并且在不同的机床上能加工的操作集可以不同。调度的目标是将作业合理地安排到各机床，并合理地安排作业的加工次序和加工开始时间，使约束条件被满足，同时优化一些性能指标。因此生产调度不但要考虑作业调度问题，同时还应该考虑资源的有效分配问题。 二、生产调度内容 生产调度是对企业日常活动进行检查、控制、调节和指挥的工作。即在生产作业计划执行过程中对已出现的和可能出现的偏差及时了解、掌握、预防和处理，保证整个生产活动协调地进行。它是组织实现生产作业计划的一种主要手段，也是生产作业计划的补充和延续。通过生产调度，解决日常生产中的不平衡和矛盾，克服生产中断脱节现象，使各生产单位和各环节的工作保持相互协调。调度工作要做到准确、及时、有效，要有预见性，要把问题解决在萌芽状态，使生产保持均衡。生产调度工作的内容一般包括： 1)控制生产进度和在制品流转； 2)督促有关部门做好生产准备和生产服务； 3)检查生产过程的物质供应； 4)监督设备的运转； 5)合理调配劳动力； 6)组织厂部和车间的生产调度会议并监督有关部门贯彻执行调度决议； 7)做好生产完成情况的检查、记录、统计、分析工作。 三、生产调度在企业生产中的重要性 生产调度在生产系统中起着重要的作用，随着市场竞争的日益激烈以及产品向多样化、个性化发展，多品种小批量的生产模式成为制造业的主流。缩短产品周期、确保产品交货期、降低生产成本，以适应多变的市场需求，对企业来说是十分重要的。在多品种小批量生产环境下生产调度显得尤为重要，其重要性主要体现在以下几个方面： 1）生产调度是生产管理的核心，生产管理任务顺利实施与完成，最终要靠合理的生产调度来保证。2）他研究的是如何合理地配置加工过程的各种资源，减少零件的加工准备、等待与运输时间，从而提高设备利用率，降低生产成本。3）及时准确的生产调度对生产系统的高效运行有着重要的影响，主要表现在生产调度可以保证：生产计划的有效实施；高效低耗地使用生产资源；均衡生产，减少在制品的资金占用。 四、生产调度的特点 (一)复杂性：车间中的制造过程是一个复杂的系统工程，调度问题是一个复杂的难问题，包括建模的复杂性和计算的复杂性。用系统的观点来看，既要考虑系统整体目标的实现，又要注意针对子系统的具体特性及其具有的局部目标的实现，加以协调和平衡，才能实现整个系统的最优调度。 (二)多约束：在研究调度问题时，不仅要考虑机器约束和加工过程的时间约束，同时还要考虑其他约束条件，如人员、工具、物流系统等。 (三)多目标：调度的目标多种多样，在实际的调度中需要综合考虑各种目标。一次调度往往具有多个目标，如加工时间最短、利润最大、生产成本最低等，而且这多个目标之间有时互相冲突，需要对不同目标加以协调；再次调度时，目标可能变化，因此，需要动态调整目标。 (四)动态性：在车间调度中，异常情况下任务的重新分配具有明显的动态随机特性。在调度时，首先根据生产车间的当前状态制定作业计划，当车间的正常运行状态受到干扰时，必须重新调度，以维持系统的趋优运行。 五、生产调度的分类 生产调度问题根据侧重点不同，有多种分类。以下是常见的几种分类： 按照资源约束的数量，可以分为单资源调度、双资源调度和多资源调度。如果生产系统中受约束的资源数是一个，通常这个约束条件就是生产机器，我们称这样的生产系统为单资源生产调度。如果受约束的资源数为两个，这样的生产调度问题成为双资源生产调度。现在广泛研究的就是机器和工人两种资源受限制的生产调度问题。如果受约束的资源数超过两个就称为多资源生产调度问题。 按照生产方式而言，调度问题可分为开环车间型和闭环车间型。开环调度问题，即加工排序问题，是研究工件的加工顺序，不考虑库存的设立。闭环调度问题除研究工件的加工顺序外，还涉及各产品批量和相应的加工顺序下的生产性能指标最优，其中顾客需求的产品均由库存提供，生产任务一般只由产品存储策略来决定。 按照生产加工的特点可分为静态生产调度和动态生产调度，静态调度是指在所有零件在开始调度时刻已经准备就绪。调度不考虑零件在加工过程中出现的意外情况，如机器突然损坏、零件的交货期提前、有更紧迫的零件要求被加工等。动态调度是指生产系统的调度要求考虑到零件在加工过程中出现的各种意外情况。要求调度能够随时响应生产系统加工能力的变化，在有突发事件后能够立即对待加工零件重新展开调度，以确保在任何时候，生产系统的加工性能指标都处于最优或次优状态。 根据研究对象的不同，生产调度问题可以分为四类：1单机器调度：单机器调度指的就是加工系统只有一台机器的生产调度，单机器调度是最简单的生产调度，是研究其他更复杂调度问题的基础。单机器调度可以看作是其他几种调度的一种特例，例如在平行机调度中若机器的数量为一，那它就等同于单机器调度。在单机器调度研究中获得的结论不仅适用于单机器环境下的调度问题，也对更复杂调度问题的研究提供了很多启发。在实际的调度问题中，许多复杂的调度问题都可以分解成可用单机器调度方法来解决的子问题。2平行机调度生产系统有一组功能相同的机器，每个工件只有一个操作并且可以在任意一台机器上加工。平行机调度分为三类：(1)机器速度相同的称为同型机。(2)机器速度恒速不同的称为同类机。(3)机器速度根据作业不同而不同的称为非同类型机。3流水调度流水生产调度研究m台机器上n个工件的流水加工过程，每个工件各个机器上的加工顺序相同，每个工件在每台机器上只能加工一次，每台机器在某一时刻只能加工一个工件，每个工件还可能具有多个工序，每个工序在不同的机器上加工。通常并行机生产调度运用先进先出调度规则。运用先进先出调度规则的并行机生产调度被称为数列生产调度。4车间作业调度生产系统拥有一组功能不同的机器，各个工件按照工艺路线以特定的次序在机器上加工。每一时刻每台机器只能加工一个工件，且每个工件只能被一台机器所加工，同时加工过程为不间断，整个加工过程中机器均有效。与流水调度相同，车间作业调度的每个工件也可能具有多个工序，每个工序在不同的机器上加工。通常假设整个加工过程中，每个工件不能在同一台机器上加工多次。 第二节 生产调度问题的主要研究方法及研究策略 一、研究方法 在对调度问题进行研究的方法上，最初是集中在数学规划、仿真和简单的规则上，这些方法不是调度结果不理想就是难以解决复杂的调度问题随着各种新的相关学科与优化技术的建立与发展，在调度领域出现了许多新的优化方法，比如基于人工智能、计算智能和实时智能的各种调度方法，这些方法已经成为调度方法的主流。 (一)数学规划方法 数学规划方法就是运筹学方法，它将生产调度问题简化为数学规划模型，采用整数规划、动态规划以及决策分析等方法来解决调度最优化或近似优化问题，也称为优化调度方法。生产调度中广泛使用的是混合整数线性规划和混合整数非线性规划方法。 数学规划方法的优点是任务分配和排序的全局性比较好，所有的选择同时进行，因此可以保证求解凸和非凸问题的全局优化，但是，数学规划方法是一种精确求解方法，它需要对调度问题进行统一的建模，任何参数的变化会使得算法的重用性很差，因此，对于复杂多变的生产调度来说，单一的数学规划模型不能覆盖所有的因素，存在求解空间大和计算困难等问题。 (二)启发式搜索方法 启发式搜索方法最初是作为人工智能中问题求解程序的搜索器而被开发出来的启发式搜索方法依靠任务无关信息来简化搜索过程，在很多情况下，问题求解可视为系统化地构造或查找解答的过程。 启发式搜索方法的优点是利用了面向特定问题的知识和经验，因而可以产生好的解决方案，求解时间也可以接受。启发式搜索方法的缺点是用来评估解决方案的质量手段还较少，如何提高搜索效率并减少内存使用以解决规模较大的问题，还需要进一步探索。 (三)系统仿真方法 基于仿真的方法不单纯追求系统的数学模型，它侧重于对系统中运行的逻辑关系的描述，而且与数学规划采用全局的而且经常是简化的视图相比，它对所有分配、排序和时间选择决策的结果提供局部的分析，通过分析能够对生产调度方案进行比较评价，并选择效果最优的生产调度方法和系统动态参数，系统仿真方法经常与其他方法结合使用。 由于生产系统的复杂性，很难用一个精确的解析模型来进行描述和分析，而通过运行仿真模型来收集数据，则能对实际系统进行性能和状态等方面的分析，从而能对系统采用合适的控制调度方法，之所以把仿真方法与其他方法结合使用，是因为纯仿真方法有以下局限性：应用仿真方法进行生产调度的费用很高，不仅在于产生调度的计算时间上，而且在于设计、建立和运行仿真模型上；仿真的准确性受人员的判断和技巧的限制，甚至很高精度的仿真模型也无法保证通过实验总能找到最优或次优的调度。 (四)人工智能方法 人工智能在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)是一类通过模拟生物界自然选择和遗传机制的随机搜索算法。遗传算法对求解问题本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并根据适应性进行选择，使适应性好的染色体比适应性差的染色体有更多的繁殖机会，经过反复迭代，直到达到某种形式的收敛遗。传算法尤其适用于处理传统搜索方法难以解决的复杂的非线性问题，可广泛用于组合优化、机器学习和规划设计等领域。已经有一些研究人员把遗传算法应用到生产调度问题中，使用遗传算法求解生产调度问题的主要工作有：生产问题到遗传编码的转换、字符串操作符的选择和限制搜索空间的约束描述等。 遗传算法已经成为一种比较通用的优化算法，主要原因是其编码技术和遗传操作比较简单，