APS高级计划系统介绍

APS高级计划与排程基础理论知识

整理制作：人间烟火

2005-08-25

1

第一章APS概念、发展及构成

什么是高级计划与排程-APS？

被誉为供应链优化引擎，有称高级计划系统(Advanced Planning System)，也有叫高级计划与排程(Advanced Planning and Scheduling)。定义不是最重要的。最重要的是对所有资源具有同步的，实时的，具有约束能力的，模拟能力，不论是物料，机器设备，人员，供应，客户需求，运输等影响计划因素。不论是长期的或短期的计划具有优化，对比，可执行性。其将要采用基于内存的计算结构，这种计算处理可以持续的进行计算。这就彻底改变了批处理的计算模式。可以并发考虑所有供应链约束。当每一次改变出现时，APS就会同时检查能力约束，原料约束，需求约束，运输约束，资金约束，这就保证了供应链计划在任何时候都有效。也将采用基因算法技术，它是一种搜索技术，它的目标是寻找最好的解决方案。这种搜索技术是一种优化组合，它以模仿生物进化过程为基础。基因算法的基本思想是进化就是选择了最优种类。基因算法将应用在APS上，以获得“最优”的解决方案。现在APS 系统以将网络结构的APS主要是基于多层代理技术与制造内部的APS主要是基于模拟仿真结合起来，使得网络导向结构的APS解决制造同步化问题，模拟仿真APS的优化顺序器解决工厂的顺序冲突问题。这样，APS计划的编制与顺序的安排就可以提供给制造商解决全球的优先权和工厂本地的优化顺序问题，来满足制造业对客户响应越来越强烈的需求。

APS应包括哪那些内容？

1. 基于订单任务(Job-based)订单优先级计划

2. 基于事件(Event-based)资源利用率最大化计划

3. 基于资源(Resource-based，TOC)瓶颈约束计划

4. 基于物料约束的可行的计划

5. 基于历史，现在，未来的需求计划

6. 基于供应资源优化的分销配置计划

7. 基于运输资源优化运输计划

APS为制造业的四类制造模型提供解决方案:

1，流程式模型,APS主要是顺序优化问题.

2，离散式模型,APS主要是解决多工序,多资源的优化调度问题.

3，流程和离散的混合模型. APS同时解决顺序和调度的优化问题.

4，项目管理模型,APS主要解决关键链（资源约束）和成本时间最小化问题.

APS考虑不同行业的解决方案。APS的主要着眼点是工序逻辑约束和资源能力约束,物料和工序流程紧密联结.各种优化规则.计算最早可能开始时间和最迟可能开始时间.物料可重分配和可替代,资源可重分配和可替代.计划排程考虑柔性(缓冲),考虑成本约束,考虑非确定流程和统计概率论.考虑多种优化方案的比较分析.

一般APS软件都由5个主要的模块组成：需求计划、生产计划和排程、分销计划、运输计划，企业供应链分析等。

2

近年来，许多企业开始把注意力放在自己的核心竞争能力上，对一些非强项业务则尽可能外包给别的公司。结果，销售给顾客的产品或服务，其特征和质量在很大程度上取决于供应链上的所有相关企业。这便带来了新的挑战：如何实现供应链的集成？如何更有效地协调和控制企业间的物流、信息流和资金流？对于这些问题，需要有一个全新的管理理念和方法- 供应链管理。SCM方法的研究和实施为企业带来了很大的经济效益，今天，许多企业都选择了供应链和物流管理作为获取新的竞争优势所必须采取的战略步骤。

在过去十年中，信息技术(如强大的数据库管理系统)，通信手段(如通过Internet的电子数据交换)，以及复杂数学模型的各种求解方法(如数学规划)的发展为计划和控制供应链流程开阔了新的视野。顾客订单、需求预测或市场趋势可以被分解成必要的活动，立刻送到供应链各组织当中，并通过高级计划系统(APS)生成准确的生产计划和程序来保证按时完成订单。APS与传统的企业资源计划(ERP)不同，它试图在直接考虑潜在瓶颈的同时，找到跨越整个供应链的可行最优(或近似最优)计划。

二、什么是计划？

为什么要计划？整个供应链中每分钟都有成百上千个决策需要制定和协调，这些决策的重要性不尽相同，既有相当简单的问题如“下一步各机床计划完成哪项工作？”，也有非常重要的决策如是否新开或关闭一家工厂。一个决策越重要，就越需要更好地准备，这种准备工作就是计划。计划通过识别将来的各种可行活动，选择其中好的甚至最好的来支持决策。计划过程可分为几个阶段：认识和分析决策问题；定义目标；预测未来状况；识别和评估可行活动；最后是选择最优方案。

供应链非常复杂，现实中要处理的每个细节并非都能(或应当)在计划中考虑，因此，有必要根据现实建立一个模型，以此作为制定计划的基础。建模的艺术就是要尽可能简单、尽需要详细地表现真实，也即简单而又不忽略现实中的重要约束。预测和仿真模型用于预测未来的状况，解释复杂系统输入和输出之间的关系，但它不支持从大量可行活动中根据标准来选择最优方案，这一工作通常由优化模型来完成，它与前者的差别在于增加了一个可用来求最大或最小的目标函数。

计划不是一成不变的，计划的有效期受到预定计划范围的限制。当达到计划范围时，需要重新制定一个新的计划来反映当前供应链的状况。根据计划范围的跨度和所做计划的重要性，计划任务通常可分为三个不同的计划层次：

长期计划：这一层次的决策也称为战略决策，它制定了未来企业/供应链开发所必要的框架，通常涉及供应链的设计和结构，对今后几年有长期影响。

中期计划：在战略决策的范围内，中期计划决定常规运作的框架，特别是决定了供应链中流程和资源的总的数量和时间，其计划范围从6个月到24个月，考虑了需求的季节性变化。

短期计划：最低计划层应当把所有活动明确为可供立刻执行和控制的详细指令，因此，短期计划模型要求高度的详细和准确。短期计划范围在几天到3个月之间，受到来自上层有关结构和数量范围决策的限制。对供应链的实际性能(如提前期，顾客服务，和其它策略问题)而言，短期计划是一个很重要的因素。

最简单的计划方法是查看所有可选活动，按给定的标准进行比较，然后选择最好的方案。不幸的是这一简单计划程序至少会遇到三个主要困难：

首先，计划活动中常常同时有几个标准，目标之间存在冲突，各方案之间的优先选择也不明确。例如，顾客服务水平应尽可能高，而与此同时又要保持库存最少，这种情况就没有最优解(也即不能同时使两个目标最优)。处理这种多目标决策问题的常用方法是设定一个目标在最小或最大的满意水平，然后优化另一个目标。在上面的例子中，人们可以在保证一个最低顾客服务水平的同时使库存最少。另一种处理多目标问题的有用方法是对所有目标按财

3

务收入或成本定价，然后使结果的边际利润最大，但不是每个目标都能以财务价值的形式来表达(如顾客服务)。还有一个更常用的方法是给每个目标定义一个系数值，然后加权求和，这种方法的缺陷是有可能产生伪最优解，因为它在很大程度上取决于任意的权值。供应链高级计划系统(APS)从原理上支持上面各种多目标寻优方法。

其次，供应链计划的可行方案数量巨大。例如，对连续决策变量(如订单大小或工作的开始时间)，可选方案的数量实际上是无限的。对离散变量也是如此，如几个工作在机床上的加工顺序，可选的数量是一个组合大数。在这些例子中想通过简单枚举来找到最优方案是不可能的，甚至要找到一个可行的方案都很困难。在这种情况下，可应用运筹学(operations research)的数学方法来支持计划流程。线性规划或网络流算法能找到精确的最优解，然而，大多数组合问题只能通过启发式算法(heuristics)来计算近似最优解(局部最优)，这些方法的成功也取决于问题的建模方法。

第三，最难的恐怕还是处理不确定性。计划通过分析与未来状况相关的数据来安排将来的活动，这些数据通过预测模型估计得到，或多或少存在预测误差。这种误差降低了产品的可用性(availability)，因而也降低了企业提供的顾客服务水平。为了改进服务，安全库存被用来缓冲实际需求与预测之间的误差。当然，安全库存并非处理需求不确定性的唯一方法。

需求的不确定性使计划与现实之间存在偏差，因此必须进行控制，如果偏差过大，计划就要重新修改。“滑动范围窗”(rolling horizon basis)的计划方法就是这种计划-控制-修改的交互实施。计划范围(如1年)被分成若干时间段(如12个月)，计划在1月份开始时制定，涵盖12个月，但只在第一个时段(1月份，称为冻结时段)计划才真正被付诸实施。新的计划在第二个时段(2月份)开始时重新制定，新计划考虑了第一个时段中的实际变化，并更新未来时段的预测。新计划的范围与原先的计划重叠，但延伸了一个时段(从2月份到第二年的1月份)，如此类推。在传统计划系统和APS中，这种方法是处理运作计划中不确定性的常用方法。图1 给出了这种不断滑动计划范围的计划方法。

另一种更有效地更新计划的方法是面向事件的计划(event-oriented planning)。新计划不是在正常间隔，而是在出现重要事件时制定，例如意外销售，顾客订单变化，机器故障等等。这种方法要求计划需要的所有数据(如存货，工作进程等)被连续更新，以便在事件发生的任何时刻都有数据可用。这种方法的一个例子就是APS，它利用来自ERP系统的数据，根据事件来更新计划。APS有下面三个主要特点：

它是整个供应链的综合计划，从企业(甚或更广泛的企业网络)的供应商到企业的顾客；

它是真正优化的计划，定义了各种计划问题的选择、目标和约束，使用精确的或启发式的优化算法；

它是一个层次计划系统，结合了上面两个特点：供应链最优计划既不能靠同时执行所有计划任务的单一系统形式获得(根本不切实际)，也不可能靠依次执行各种计划任务取得(达不到最优)。层次计划折衷考虑了实用性和计划任务之间的独立性。

值得注意的是，ERP系统中的传统物料需求计划(MRP)在概念上没有上面这些特点：MRP 只限于生产和采购领域，不做优化，在大多数情况下甚至不考虑目标函数，它是一个运作层面的连续计划系统。

层次计划的主要思想是把总的计划任务分解成许多计划模块(即局部计划)，然后分配给不同的计划层，每一层都涵盖整个供应链，但层与层之间的任务不同。在最顶层只有一个模块，是企业范围的、长期的、但却是粗略综合的发展规划。层次越低，计划涵盖的供应链局部受到的限制越多，计划时间范围越短，计划也越详细。在层次计划系统的同一计划层中，供应链各局部计划之间通过上一层的综合计划来协调。图2 给出了计划任务的层次结构框图。

4

在层次计划中向下(向上)分解(综合)数据和结果，可以取得计划详细程度的增加(减少)。综合主要涉及：产品(组合成批)，资源(组合成产能组)，和时间(把分段时间组合成更长的时间段)。各计划模块被水平和垂直信息流连接在一起，上层计划模块的结果为下属计划设定了约束，而下层计划也将有关性能的信息(如成本，提前期，使用率)反馈给更高的层次。层次计划系统(HPS)的设计需要仔细定义模块结构，模块计划任务的分配，和模块间信息流的详细说明。HPS通常采用滑动范围的计划方法，在不同层次上计划间隔和范围的复杂协调方法可参阅文献[2]。面向事件的计划简化了HPS的使用，使它更加灵活，但前提条件是有一个通信系统能对有关的计划层和任务模块发出“事件”报告，此外，一个计划任务的结果也应能其它计划任务发出事件报告。

APS有三个主要优点：信息可视化，减少计划时间，和允许方便地应用优化方法。正因为如此，许多计划人员或许会担心自己的工作会被计算机所代替。然而，模型只是现实的近似，人们的知识，经验和技能仍然需要来弥合模型和现实之间的差距。计划系统无论多么高级也只是支持人们制定决策的决策支持系统。在面向事件的计划中，通常要由计划人员来决定是否需要修改计划，此外，每一个计划模块也需要由人来负责它的功能、数据和结果。

三、供应链计划任务

整个供应链网络由网络中每个伙伴的内部供应链组成，内部供应链包括四个主要的供应链流程，其计划任务不尽相同。采购流程包括所有为生产提供必要资源(如物料和人力等)的子流程，资源的有限能力是生产流程的输入，生产流程也由许多子流程组成。分销流程弥合了生产地点和顾客(零售商或其它进一步处理产品的企业)之间的距离，销售流程确定顾客需求和订单数量，驱动其它三个流程。

供应链计划矩阵(SCP-Matrix)根据计划范围长短和供应链流程对计划任务进行分类(如图3 所示)，图3 给出了大多数供应链类型中常见的计划任务，任务的内容随各行业不同而不同。图中长期任务只用一个长方框，体现了战略计划内容广泛综合的特点，其他方框是矩阵输入，表示不同的流程计划任务。SCP-Matrix可供APS开发商用来定位他们的软件模块，以便涵盖矩阵中所有的供应链计划任务。

在层次计划系统中，各计划模块之间通过信息流协调和集成，可分为水平信息流和垂直信息流：

水平信息流：从供应链下游向上传递，包括顾客订单，销售预测，仓库补货订单，各部门之间的内部生产订单，和给供应商的采购订单，整个供应链受顾客需求驱动。计划模块之间(不仅限于相邻模块)更多信息的双向交换能够大大改进供应链性能(如“长鞭效应”)，这些信息主要包括实际库存，可用能力，提前期和销售点数据。

垂直信息流：从上层向下流动，通过高层计划的结果协调下层的从属计划，主要信息包括分配给生产车间、部门或流程的综合数据，而协调则通过能力分配和设定交付日期来取得。从下层向上流动，提供上层有关供应链性能更详细的数据，如实际成本，生产率和设备使用率，提前期等等，这些信息在上层计划中用来预测下层更详细的流程结果。

四、APS高级计划的历史

基于约束的高级计划和排程技术的是真正供应链优化的重要引擎,她给错综复杂的供应链丛林中的企业以敏捷的身躯,来快速反应与适应激烈竞争切变化多端的市场.实际上有多种需求导致APS的产生,其原因如下:

5

(1),业务系统是基于事物处理的,APS更多的是在业务层以上的分析,这些系统的结构限制了计划和排程的能力,如MRP,CRP等等.直到现在,对许多使用业务系统的人们来说高级计划APS还都是新的内容.

(2),APS的内部开发已经完成.技术已走向成熟,出现很多的供应商和产品的现象.

(3),许多咨询公司还没有涉足此领域,直到较好的产品和供应商出现.

(4),人们对APS的定义来源于较广的工业领域,APS在不同的时间,不同的运用点渗透到不同的工业领域.当公司有能力管理自己的数据与业务时,实时,优化就显得更加的重要.流程行业最先使用APS技术,离散行业较后才使用.

(5),许多用相似的方案的供应商已经很积极的声明自己是APS供应商.

(6),对APS技术的贡献有APICS,人工智能,计算机科学,决策支持系统,工业工程,物流,管理科学,运筹学,和生产运作管理,每一个领域都有自己的术语,此外,也导致了混乱.(甚至”计划”与”排程”都没有标准的意义),这也造就了创造新工具的机会.

APS已经从企业内部持续改善的优化工具到满足公司间协作的供应链新技术的进化.这个论题是John Layden,在他的<<排程逻辑的进化>>的文章描述的,让我们继续这个进化,看看有谁在此领域活跃了近二十多年.

计算机出现之前的APS

在计算机之前,一些关键的概念已经形成了.一个是甘特图,它让人们看到可视的计划并可以交互的更新.这个简朴的概念一直延续到今天,我们用有颜色的橡皮带,块,钉子和粉笔在墙上,纸作标识.用数学建模的方式来解决计划问题的想法出现在至少在1940年.美国和前苏联让人们手工应用这一新的优化技术,它叫线性规划,运用它来解决与战争有关的后勤问题.

1950-1960初,计算机已出现

APS的进化已经和计算机的进步紧密相连了,在1950末或1960年初,许多大公司开始租赁计算机计算和购得大型计算机.计算机被用于研究计划问题的一部分,如优化几个关键的物料和能力的平衡,基于产品的需求与能力约束.或者找出批量产品的最低成本的配方.他们一般都使用线性规划的算法.其数学模型就象现在的小型的电子表应用程序(40-60个方程式和60-100个决策变量).在此其间,有两个公司首先提供对计划的优化工具,他们是在1957成立的Bonner and Moore公司和1962年成立的Haverly Systems 公司.优化的处理可以避免混乱,优化技术的严格实施是一个较好的解决方案或方法,保证找到对问题的”最好”的答案且智能的知道何时发生,多长时间发生.

今天,我们使用优化技术常常是用于一个较简单的寻找提高的方法或方案且不能保证找到最好的方案.简单的寻找提高的技术叫启发式算法.它们经常用于时间的限制或容限.(在10分钟,找到最好的答案).当这些优化的技术用于交替的变化,容易出现混乱.线性规划较适合严格的优化约束和识别约束,经常是对一个问题用于经济上如成本和收入的约束来决定”最好”的方案.

1960中期-1970初计算机应用程序的进步

6

随着计算机的进步,人们有能力可以考虑更复杂的计划问题.先进的技术的工具可以考虑整个制造工厂和设置在最小化成本的运作且最大化利润.一些公司结合计算机程序对生产设备来优化他们的产品配方.人们也开始研究分销问题.如公司EXXON开发程序来集成库存,采购,制造,分销管理.

从1960初的几百个决策变量到1970的几千个变量,到1970年的后期的上万个变量.线性规划的这种技术也扩展到解决更困难的问题.如生产能力的决定,生产品种和生产线的选择和对分销中心的选址等.这些应用最早是出现在流程行业的计划层.许多大的化工公司如Amoco, Chevron, Exxon, Marathon和Shell都积极采购主机系统的计算机,部署到他们的制造工厂里,这些公司还采取了数据采集与集成数据的方法.由于业务的需求推动,优化技术较好的满足他们的许多流程和分销网络的特点.许多公司自己在大型机环境下开发自己的工具.开发线性规划的程序.也可以从几个供应商购买到.如IBM的MPS(后称MPSX),有些公司却使用现成的程序开发语言如Assembler, Cobol, FORTRAN,和PL/1是常用的开发语言.这些程序是以批处理的模式运行.EXXON甚至出版了关于一本关于他们计划系统的书.

计算机已成为解决排程问题的工具,模拟也被用于制造和分销设施的设计.模拟工具还开发成计算程序, 按照能力和物料的消耗, 顺序活动, 计算批量可以得到排程的结果.可以对特别的排程问题进行开发的,且这些程序界面可以为用户交互使用.

基于排程工具的模拟开始出现在1970年.Pritsker是一较早的供应商,另外一早期的产品是IBM的CPPS.主要是些化工公司,在1970年就积极使用了计划工具.其他行业也在积极使用计划和排程程序.

1980年初,轮胎制造商Kelly Springfield ,Philip Morris 已经使用了APS计划和排程程序.造纸公司如St Regis,和国际造纸也实施和运用了APS工具.

1980年-商业媒体发现了APS

约束理论的发明者高特拉德(1983年9月5日财富杂志人物)领导的创新产出公司(Creative Output),他们的产品OPT, 以批处理的模式,应用一系列的消除瓶颈的算法,这是一个非常积极的销售型组织,它获得了许多离散制造业的客户.创新公司在和M&M/Mars公司的法律争端之后,从市场很快的退出. 而高特拉德扩展了TOC(约束理论)的哲学,他本人却以出版和制造导师为职业.当时,和创新公司的同类I2公司仍然活跃在APS领域.财富杂志的文章提到Numetrix决策科学公司,以后又分拆为Numetrix公司和Chesapeake决策科学公司,这两个早期的APS供应商具有交互的产品和提供基于内寸分析技术.

在APS文章经常出现学术论坛和使用APS方案的期间,产品介绍开始出现在”商业周刊”,”Chicago Tribune”,”New York Times”,”Wall Street journal”, “Washington post”.媒体关注的中心是在1984年,由年轻的AT&T的研究者名为Narendra Karmarkar 开发的算法.这个新技术解决了线性规划的问题,是被AT&T作为”真正的突破”和”设计解决了以前未解决的问题”来推销.AT&T把这个算法绑定他们的计算机,价格近9百万美元.

1980,我们也看到了个人计算机和电子表格的引进.电子表是双刃剑,在积极的方面,他们引进了人们交互的使用预测,计划和排程.在很多公司使用的大型机时,用户使用简单近似存在的工具.不幸的是,当大型机系统出问题时,子系统也就不可能选择和验证详细的数据.许多化工公司积极开发计划排程系统,从1970年到1980年的后期,重视数据的质量和工具的精确性.

在1980年中期,许多大的化工公司认识到可用改善制造流程来阻止下降的利润.就开始检查他们供应链的活动.BASF,DOW, Du Pont和Rohm和Haas都开始积极使用计划和排程的工具.他们使用自己开发的产品和工具或自己修改过的APS产品.目的是想要管理真正的整个供应链而不是某一局部的方案如制造或分销.

7

许多MRPII的供应商,为了满足市场需求也进入流程行业.有些公司却延迟开发APS工具或使用APS工具,而他们决定用MRP,CRP来满足他们计划和排程的需要.但是,在1990年初,许多大的化工公司已经选择了APS的供应商.许多大的航空公司也实施了复杂的计划和排程系统,美国航空集团也为其它航空公司建立这些高级计划排程系统.

1980年后期,我们也看到了人工智能,专家系统的出现,许多公司把人工智能运用到计划排版程系统.投资者和客户期望的难题就此解决.Du Pont和IBM积极结合人工智能AI和存在的技术开发程序.IBM也开发了一个派工系统,Du Pont在他的来自Chesapeake决策科学公司的MIMI优化,模拟启发的产品里加入了专家系统.专家系统用它的数据验证,启发式的协作,方案解释的能力,为计划排程的制定起到有效的作用.实时的专家系统产品如G2在此时也出现了.人工智能AI世界同时也对APS的技术作出了贡献如基于规划的约束和基因算法.对人工智能AI的期待已经设置了极高的水平上了,用人工智能AI完全达到期望的要求,可能令人失望.不幸的是,有些人仍然认为是失败,许多人工智能AI的开发者感到他们的技术仅仅应用于纯技术时髦.于是, 在1960年到1970年,用许多时间和努力去重新开发一些功能,寻找其他的工具.

1980年后期,也出现了图形用户界面,有些供应商试图结合个人计算机来增加它的图形运用能力, 图形用户界面成为标准的预测,计划,排程工具的一部分.这个技术的革命巨大的影响了APS的市场化.

1990年-APS市场繁荣和产品增值

在1990年初,消费品公司(CPG)开始联系APS系统.虽然也有一些早期采用者,在此市场阶段,这个行业作为一个整体应用APS技术是很慢的.造纸业也是如此.一些已经有能力实施相对简单的制造排程的公司发现他们需要更复杂的系统,可以处理包括SKU数量,分销网络的地点的选择.许多公司也发现相似的问题,就是他们的预测能力,尤其是在SKU的数量的管理上, 简单的预测工具却阻碍了预测的准确性,他们需要集成供应链的多地点的详细的需求,来为了运作决策.

1990年初,SQL的引进,允许APS工具和关系型数据库更动态的互动.计算机能力的增强和成本的降低,导致新的方案的出现.同时也发现问题的复杂性,所以,基因算法出现了.它们立刻形成多重的方案以结合现存方案的最好的特征来创立新的方案.人们开始使用反复模拟,想要建立更好的方案,但是,随着开发的工具处理百万的决策变量,对计算机和应用程序是一大挑战.

1990年,APS的供应商已经繁殖到更广的工业领域,如I2,Fastman已经进入电子装配,金属品制造等离散制造领域,I2的市场导向品牌和销售战略,戏剧性的提高APS的空间,而这以前APS都是一直技术导向的市场.由于I2,Manugistics,等的市场的影响,引起了大咨询公司的注意,他们开始分配资源给这些产品作服务.但是,APS对大的咨询公司而言有两个挑战,一个是它需要较深的应用专家,而不是集中在IT的应用上.二是固定的,标准项目实施方法对APS项目不太有效,该领域的专家仍然需要决定如何更有效的实施APS.

1990年中期,许多供应商转向微软技术的视窗环境下的用户界面,C/S结构或整个转向Window NT 环境,除了提供更直观的用户界面,报告能力而且使APS应用程序的环境转向低成本的, 性能戏剧性的提高的计算机.1990年中期,也看到了APS运用到部分的半导体公司,这些公司在改变产品技术方面有着极大的进取心.使产品具有极短的生命周期,这就对提高基于知识需求的APS来说是一大挑战,特别是在计划和排程层次上.和流程行业同时使用APS 技术的公司有Harris半导体公司,IBM公司,Intel公司,Texas 仪器公司,用APS技术解决自

8

己业务的复杂问题.

最后,在1990年的中期,APS还吸引了大多数ERP供应商的注意,随着APS市场的快速成长.产生了ERP供应商的新一轮的收购APS公司和自己内部开发APS. 许多专家认为APS必须嵌入ERP系统.

供应链引擎APS产品的功能特征的演变有以下四个阶段:

第一阶段的功能特征:人机交互可视化排产,简单的有限资源计算.

1,向前,向后和双向的订单的加载计算.

2,可以定义简单加载规则如按完成日期排序和设定优先级)

3,工序间的人机交互拖拉,编辑,批量分割

4,根据资源和时间对单独工序加锁/解锁

5,可以按工序的最早开始日期或订单的最早完成日期计算.

6,可以人机交互的替换,增加工序,交互处理故障,计划维修.

7,可以处理单一的加工工序,平行工序,可以对工序的单一资源进行约束

8,根据物料,时间,批量的生产率来排生产计划

10,可以对有限资源和无限资源或单个班次或假日来计划排程

11,可以在工作中心里自动选择资源,用户也可以定义资源

12,可以显示图形,文本,报表,可以订单跟踪,甘特图,等待表.

第二阶段的功能特征:基于各种资源约束优化计算

1,用户可以定制,配置数据,菜单,报表.

2,可以按工序和计划增加约束使用率.

3,具有换装时间距阵的排序,可以选择最小化换装时间.

4,具有计算批量,计算运输批量和自动重复和自动停止订单的功能

5,具有CTP(能力可用量)的查询

6,可以自动连接其它软件.

第三阶段的功能特征:基于多重资源约束优化和建模

1,具有每个工序的多重约束

2,基于当前工序的子工序的约束

3,可以使用优先资源选择规则

4.最大工序跨度和间隔,也可以延迟到下一个工序

5,可以计算在每个加工过程的顺序和平行批量

6,可以对装配线的建模和子装配线建模.

第四阶段的功能特征: 多重资源约束,物料的动态约束,需求计划,分销网络配置计划,运输计划,全局CTP,ATP.

1,从MRP处自动物料分配(静态物料约束控制).

2,可以从不同的订单自动连接工序,可以从不同的订单排序,平行的负荷工序

3,具有标准的派工规则:优先顺序,关键率

4,可以处理订单,生产或资源的特别规则

5,可以让用户自定义建立规则

6,可以处理动态物料约束控制

9

7,可以处理供应链需求计划优化

8,可以供应链分销配置计划优化

9,可以供应链运输计划优化

10,可以对整个供应链的进行CTP和ATP的查询.

五、APS的技术现状

APS-高级计划与排程，并不是一个独立的管理软件，而是与ERP系统集成在一起的一个专门负责生产计划和生产排程、生产排程的软件。由于ERP生产功能的核心MRP在功能上有很多不足，APS的出现其实是弥补这种不足的必然。APS的最大特点就是其中的‘高级’二字，这种先进是基于其核心技术的高深和困难，因为它所涉及到的基本都是相关学科中的最前沿领域。一般需要集中物流、管理学方面的专家以及基础数学和计算机算法方面专家，至少几年时间的努力才能有所成就。而这对讲究投资收益和市场变化极为迅速的ERP企业是不太可能的选择。以至于极少ERP厂商自己开发APS，大都是直接购买专业公司的现成软件加以集成，即使SAP、ORACAL也不例外。

APS的目标就是追求生产计划的优化和能力的平衡，这本身是有难度的工作，但是最难的还在于‘约束’，优化和平衡的追求都是在多种约束条件之下的追求。约束与优化成为一对最大的矛盾，甚至在特别复杂的约束下到底有没有最优，能优化到什么程度，理论上都成为疑问。

APS的研究主要集中在车间的生产计划排程与生产调度程方面，许多学者作了大量研究，出了不少的研究成果。制造系统的生产排程和生产调度是针对一项可分解的工作（如产品制造），探讨在在尽可能满足约束条件（如交货期、工艺路线、资源情况）的前提下，通过下达生产指令，安排其组成部分（操作）使用哪些资源、其加工时间及加工的先后顺序，以获得产品制造时间或成本的最优化。在理论研究中，生产排程和生产调度问题常被称为排序问题或资源分配问题。方法可以简单分成静态和动态两种。

（1），静态排程是指所有待安排加工的工作均处于待加工状态，因而进行—次排程后、各作业的加工被确定、在以后的加工过程中就不再改变；

（2），动态排程是指作业依次进入待加工状态、各种作业不断进入系统接受加工、同时完成加工的作业又不断离开，还要考虑作业环境中不断出现的动态扰动、如作业的加工超时、设备的损坏等。因此动态排程要根据系统中作业、设备等的状况，不断地进行排程。实际排程的类型往往是 job shop型，且是动态的。

一般的排程问题都是对于具体生产环境中复杂的、动态的、多目标的排程问题的一种抽象和简化，因而，一个排程算法可以通过其如何表述这些复杂性来进行分类。由于实际生产环境是千差万别的，那末，一个排程算法就应该根据其是否能适合对应的生产环境的重要特征来进行评估。Frederick等人为了帮助区别不同的生产排程策略，给出了典型生产排程环境的五个特征，这将有助于我们了解各种不同的排程算法的应用环境。

1，边界条件：生产排程常常是一个重排程问题，即修改已有的生产排程去适应新的作业。为提供重排程，排程算法应能处理生产系统中有关的初始状态。类似的生产排程通常是在一个有限的时间区域里进行的，系统的最优解（或次优解）亦是在限定的边界范围内来获取。

10

2，分批大小和调整费用：为有效地解决实际生产中的排程问题，往往将任务分成多批进行，并考虑改变已有排程结果所付出的代价（调整费用）。

3，加工路径：在实际生产中，作业的加工路径可能需要动态改变，工艺顺序可能是半有序的(semiorder)。

3，随机事件和扰动：比如，出现关键作业、设备损坏、加工操作失败、原料短缺、加工时间/到达时间/交货期的改变等。

4，性能指标：追求不同的性能指标往往会得到不同的优化解

5，多目标：同时，系统目标也以多目标为主。

实际的排程问题有以下特点：

(1) 复杂性

由于装卸作业、装卸设备、库场、搬运系统之间相互影响、相互作用、每个作业又要考虑它的到达时间、装卸时间、准备时间、操作顺序、交货期等，因而相当复杂。由于排程问题是在等式或不等式约束下求性能指标的优化，在计算量上往往是NP完全问题，即随着问题规模的增大，对于求解最优化的计算量呈指数增长，使得一些常规的最优化方法往往无能为力，对于这一点 Garey等 [16]（见文后所附文献目录）给出了明确的证明。即便对单机排程问题，如果考虑 n个作业而每个作业只考虑加工时间及与序列有关的准备时间时，就等价于n个城市的 TSP问题。对于一般的装卸系统，问题就变得更为复杂。

(2) 动态随机性

在实际的生产排程系统中存在很多随机的和不确定的因素，比如作业到达时间的不确定性、作业的加工时间也有一定的随机性，而且生产系统中常出现一些实发偶然事件，如设备的损坏／修复、作业交货期的改变等。

(3) 多目标。

实际的计划排程往往是多目标的，并且这些目标间可能发生冲突。Oraves曾将排程目标分为基于排程费用和排程性能的指标两大类：Alia. S等人将排程目标分三类：基于作业交货期的目标、基于作业完成时间的目标、基于生产成本的目标。这种多目标性导致排程的复杂性和计算量急剧增加。

排程问题的研究方法如下：

—般的排程问题都是对于具体生产环境中复杂的、动态的、多目标的排程问题的一种抽象和简化，因而一个排程算法可以通过其如何表述这些复杂性进行分类。由于实际中生产环境是千差万别的，那么一个排程算法就应该根据其是否能适合对应的生产环境的重要特征进行评估。在对排程问题进行研究的方法上，最初是集中在整数规划、仿真和简单的规则上，这些方法不是排程结果不理想就是难以解决复杂的问题。随着各种新的相关学科与优化技术的建立与发展，在排程领域也出现了许多新的优化方法，比如神经网络、模拟退火法、遗传算法、禁忌搜索法等，使得排程问题的研究方法向多元化方向发展。下面我们分别对这些方法进行总结：

11

(1) 运筹学方法

运筹学方法是将生产排程问题简化为数学规划模型，采用基于枚举思想的分枝定界法或动态规划算法进行解决排程最优化或近优化问题，属于精确方法。文

[24][25][26][27][28]等提出了不同的分枝定界法，其不同点主要在于分析规则、定界机制和上界的产生这三方面存在差异。这类方法虽然从理论上能求得最优解，但由于其计算复杂性的原因、因而不能获得真正的实用。目前，Lenstra在文[15]中声明，对一个标准的10作业——10设备问题进行求最优解，需要在Prime 2655计算机上运行 1小时，并产生22000个结点。对于复杂的问题，这种纯数学方法有模型抽取困难、运算量大、算法难以实现的弱点，对于生产环境中的动态排程实现复杂，解决不了动态及快速响应市场的问题。

(2) 基于规则的方法

对生产加工任务进行排程的最传统的方法是使用排程规则（Dispatching rules），已经有许多排程规则被应用，因其排程规则简单、易于实现、计算复杂度低等原因，能够用于动态实时排程系统中，许多年来一直受到学者们的广泛研究，并不断涌现出新的排程规则。许多学者在这方面已进行了探索及大量工作，如研究与制定较优的单元零件加工排程算法，在减少等待时间、提高生产率等诸多约束条件下达到了一种较为科学有效的排程效果。

PanwaIkar和 IskaDder在文[30]中总结了 l13条规则，并将它们按形式分为了三类：简单规则、复合规则、启发式规则；M．MontazeIi等例举了常见的20条规则，并针对一个实际的FMS，分析了这些规则对系统性能（如作业的平均等待时间、设备的平均利用率、作业总加工时间等）的影响；文[47]将多种规则组合起来实现排程；文[48]讨论了决策规则解决FMS车间排程问题的方法与规则库的具体实现，分析了各种规则与性能指标的关系，对如何合理地选用规则提出了建议；为了提高规则排程的质量，文[50]通过分析拖期时间与两个作业排程决策间的关系，提出了一种比较复杂的规则，并在以拖期时间最小的目标下，与 LST、LPT、LDD、LWR、LSWR、LSOR等规则作了实验比较。随着计算机运算速度的飞速提高，人们希望寻找新的近似排程方法，它以合理的额外计算时间为代价，换得比单纯启发式规则所得到的排程更好的排程。在这方面比较有代表性的有移动瓶颈方法（Bottle neck Procedure），用来解决以最小化 Makespan为目标的 Job Shop排程问题，它通过不断地对移动的瓶颈设备进行单机排程，来获取更好的次优解。

总的说来，启发式规则直观、简单、易于实现。但是近十年的研究表明并不存在一个全局最优的排程规则，它们的有效性依赖于对特殊性能需求的标准及生产条件。它是局部优化方法，难以得到全局优化结果，并且不能对得到的结果进行次优性的定量评估。顾客需求的个性化及要求企业响应市场的敏捷性，往往在生产加工过程中加入了更多的不确定性及复杂性约束，寻找排程最优算法本身是一个NP完全问题，这些使得基于规则的排程思想已不能适合敏捷化制造的要求。

(3) 系统仿真的方法

基于仿真的方法不单纯追求系统的数学模型，侧重对系统中运行的逻辑关系的描述，能够对生产排程方案进行比较评价，分析系统的动态性能，并选择系统的动态结构参数。由于制造系统的复杂性，很难用一个精确的解析模型来进行描述和分析。而通过运行仿真模型来收集数据，则能对实际系统进行性能、状态等方面的分析，从而，能对系统采用合适的控制排程方法。仿真方法最早被用来作为测试排程启发式规则及分派规则的工具。后来，人们发现，通过将简单的优先权规则进行组合，或用一个简单的优先权规则将一些启发式规则进行组合，这样的排程优于单独的优先权规则。于是，仿真方法逐渐发展为一种人机交互的

12

柔性仿真工具，并用来进行车间排程。这样，就能通过仿真而动态地展现Job Shop车间的状态，分析在不同的排程方法下的系统性能，并运用知识和经验去选择合适的排程方法(规则)，从而改善排程性能。

Kiran等回顾和总结了在动态环境下基于纯仿真模型的 Job Shop排程问题的研究状况；Baker等人研究表明：机器数目对生产的相对效率影响不大；Nanot说明了优先规则的相对效率并不因机器的构成而改变；文[19]中提出了基于纯仿真模型的排程方法，即在一个较短的时间段内用仿真来评价一个分派规则集，选取最小代价的规则进行排程，以适应系统状态的变化；文[49]运用纯仿真模型，同时解决FMS中作业排程和搬运小车及刀具的资源分配问题；文[51]中提出了一种混合的仿真／解析模型，用于分析和设计具有缓存的不可靠生产线问题。

基于纯仿真法虽然可以包含解析模型无法描述的因素，并且可以提供给使用者一个排程性能测试的机会，但其不可避免地存在以下问题：1）鉴于其实验性，因此，很难对生产排程的理论作出贡献。2）应用仿真进行生产排程的费用很高，不仅在于产生排程的计算时间上，而且在于设计、建立、运行仿真模型上的高费用。3）仿真的准确性受编程人员的判断和技巧的限制，甚至很高精度的仿真模型也无法保证通过实验总能找到最优或次优的排程。

(4) 基于 DEDS的解析模型方法

由于制造系统是一类典型的离散事件系统，因此，可以用研究离散事件系统的解析模型和方法去探讨车间排程问题，诸如排队论、极大/极小代数模型、Petri网等。排程中的排队论方法是一种随机优化方法，它将每个设备看成一个服务台，将每个作业作为一个客户。作业的各种复杂的可变特性及复杂的路径，可通过将其加工时间及到达时间假设为一个随机分布来进行描述。文[33]针对 FMS中一类特殊的 DEDS，利用了极大代数方法对其进行建模，并进行了系统的稳定性分析。

总的说来，排队网络模型由于从随机统计的角度来描述FMS，难以表述系统中存在的某些特性（如有限的缓存空间等），同时，产生的输出是基于系统稳态操作的平均量，因此，很难得到比较具体的细节。Petri网作为一种图形建模工具可以形象地表示和分析FMS中加工过程的并发和分布特征以及多项作业共享资源时的冲突现象，具有很强的建模能力，对于描述系统的不确定性和随机性也具有一定的优越性。在制造自动化领域，利用 Petri网及其扩展形式的模型进行死锁分析、排程决策和性能评价等已有大量理论研究文献。赋时Petri 网是在以往Petri网的基础上又引入了时间元素，使其能够用于FMS中加工的组合优化、生产进程的实时排程和性能估计等。Tien─Hsiang Sun等人用赋时 Petri网为FMS建摸，它包括两个主要的子模型：静态的传送模型和变化的加工流模型。通过嵌人一个基于A*搜索算法，最后得到一个满意的作业加工排程。在此基础上还进行了一个实例研究。部分学者用赋时Petri网为FMS建模，通过优化变迁的发生序列来产生的搜索可标识集，从而得到较优的排程结果；甚或用赋时扩展着色 Petri网模拟FMS的动态运行。

(5) 基于排序的方法

该方法是先有可行性加工顺序，然后才确定每个操作的开工时间，并对这个顺序进行优化，它虽然属于近似算法，但有可能达到最优的排程方案。它主要包括邻近搜索法，它在生产排程领域得到了相当广泛的应用，在探索解空间时，仅对选定的成本函数值的变化做出响应，因而通用性强。这类方法包括局部探索（Local Search）、模拟退火法（Simulated Annealing）、列表寻优法（Table Search），遗传算法（Genetic Algorithms）。邻近搜索虽然可能得到最优的排程方案，但也存在各自的不足, 很多学者采取混合算法来弥补单一方法的不足。

13

（6）启发式图搜索法

对于表述为整数规划的排程问题，最初采用分枝定界法来解决，而后其他的启发式图搜索法也被应用于解决排程问题。在文[19]中 Balas将排程排序问题用一个disjunctive图来表示，首先构造一个可行解，采用基于隐枚举的搜索方法不断提高解的次优性；在文[40]中采用束搜索法(beam search)来识别瓶颈机器，进行排程；为了解决搜索空间太大的问题，在文[45]中通过对分枝定界法和束搜索法进行系统的分析，提出了一种过滤束搜索法(filter beam search)，用来解决单台机器提前／延期问题和加权延期的 Flow Shop问题；文[45][47]中研究了基于A*的优先树搜索法的优化作业排序问题：文[46]中针对基于树搜索的优先A*算法需要大量内存的问题，提出了一个图搜索法，并对两种方法作了比较；文[46]中为解决Job Shop排程问题对A*算法作了两点改进：1) 在搜索过程中只展开有限节点；2) 采用加权的评价函数。对于图搜索算法，如何提高搜索效率并减少内存使用以解决规模较大的问题，还需要进一步探索。

（7）模拟退火法

模拟退火算法(SA)将组合优化问题与统计力学中的热平衡问题类比，另辟了求解组合优化问题的新途径。它通过模拟退火过程，可找到全局(或近似)最优解。其基本思想为：把每种组合状态Si看成某一物质系统的微观状态，而将其对应的目标函数C(Si)看成该物质系统在状态Si下的内能；用控制参数T类比温度，让T从一个足够高的值慢慢下降，对每个T，用Metropolis抽样法在计算机上模拟该体系在此T下的热平衡态，即对当前状态Si作随机扰动以产生一个新状态s’，如果C(s’)模拟退火法的几个重要部分为：生成函数(generation)、容忍函数(acceptance function)、 Markov链长、降温过程和结束准则。模拟退火法的改进算法有加温退火法、有记忆的模拟退火法等。文[47]中为Flow Shop问题求解构造了一类模拟退火法，并通过六种不同的随机抽样方式分析了算法渐近收敛于全局最优解，分别解决了具有最小Makespan指标且具有无限中间存储(UIS)、有限中间存储(FIS)和无中间存储(NIS)的 Flow Shop排序问题；文[43]提出了一种改进的模拟退火法，用来解决具有最小 Makespan指标的 Flow Shop排序问题，并与禁忌搜索法等进行了比较；文[48]用模拟退火法进行机器分组；文[49]用模拟退火法求解有资源约束的排程问题。另外，模拟退火法也可与其他方法相结合进行求解，如文[42]中先用贪心法(greedy法)搜索，将得到的作业序列作为初始解，再用模拟退火法求解单机排程问题，其结果表明这种方法比单纯用模拟退火法和贪心法要好；文[44]中提出了将模拟退火法与启发式算法相结合的方法，求解具有交货期约束的Job Shop排程问题。由于模拟退火法能以一定的概率接受差的能量值，因而有可能跳出局部极小，但它的收敛速度较慢，很难用于实时动态排程环境。

（8）禁忌搜索法

对于复杂的组合优化问题，禁忌搜索也是一种通过领域搜索以获取最优解的方法，Glover曾在文[44][45]中叙述了它的基本原理。禁忌搜索是一种迭代方法，它开始于一个初始可行解 S，然后移动到领域 N(S)中最好的解s’，即s’对于目标函数F(S)在领域 N(S)中是最优的。然后，从新的开始点重复此法。为了避免死循环，禁忌搜索把最近进行的T 个移动（T可固定也可变化）放在一个称作 tabu list的表中(也称短期记忆)，在目前的迭代中这些移动是被禁止的，在一定数目的迭代之后它们又被释放出来。这样的tabu list 是一个循环表，它被循环地修改，其长度T称作Tabu size。最后，还须定义一个停止准则来终止整个算法。由于tabu list的限制，使其在搜索中有可能跳出局部极小。文[33][34]分别提出了解决flow shop排程问题的禁忌搜索算法。在文[37]中为了更有效地搜索解空间，引入了插入和移动相结合的机制提高了搜索效率。文[48]中采用了并行禁忌搜索法以加快搜

14

索速度。文[49]中针对求解公共交货期下带有等待时间惩罚的提前／拖期单机排程问题，提出了一种禁忌搜索法。

（9）神经网络优化

Hopfield神经网络模型的提出为求解各种有约束优化问题开辟了一条新途径，用Hopfield网络解决TSP问题就是其在组合优化问题中的最成功的应用之一。它的主要思路是：通过一个Lyaplmov能量函数构造网络的极值，当网络迭代收敛时，能量函数达到极小，使与能量函数对应的目标函数得到优化。文[44]介绍了一种随机 Hopfield网络来解决 Job Shop排程问题的方法；文[46]中为了解决大规模问题，又提出一种改进的Hopfield网络的整数线性规划神经网络方法来解决 Job Shop排程问题；文[51]中也提出了一种用于解决Job Shop排程问题的神经网络方法。

（10）遗传算法

美国Michigan大学的J.H.Holland于本世纪末提出了一种新的并行优化搜索方法：遗传算法(Genetic Algorithm)，它是一种基于进化论优胜劣汰、自然选择、适者生存和物种遗传思想的随机优化搜索算法，通过群体的进化来进行全局性优化搜索。它以其很强的并行性和很高的计算效率正日益受到人们的关注。它对组合优化问题求解的主要过程是：给定一组初始解作为一个群体，通过选择、交换和变异等遗传操作符来搜索问题的最优解。文[37]中提出了一种基于遗传算法的启发式方法，用于解决以最小化Makespan为指标的flow shop 排程问题；文[39]用遗传算法解决Job shop排程问题；有的学者将遗传算法与图搜索法相结合，利用遗传算法进行知识的推理、启发，再用过滤束搜索法(filter beam search)进行优化搜索，以得到高质量的 FMS静态排程；文[27]提出了一种并行遗传算法，试图解决常规遗传算法在解决FMS排程问题时产生的计算速度较慢及过早收敛等问题。

总的来说，遗传算法的最大优点是通过群体间的相互作用，保持已经搜索到的信息，这是基于单次搜索过程的优化方法所无法比拟的。但是，遗传算法也存在着计算速度较慢的问题。

(11) 基于智能的排程方法

近年来受实际需要的推动，基于知识的智能排程系统和方法的研究取得了很大的进展。人工智能在60年代就将计划问题作为其应用领域之一，但直到80年代，以Carnegie ─Mellon大学的M.Fox为代表的学者们开展基于约束传播的ISIS(Intelligent Scheduling and Information System)的研究为标志，人工智能才真正开始应用于排程问题。基于知识的排程方法是用专家系统自动产生排程或辅助人去排程。它是将传统的排程方法与基于知识的排程评价相结合的方法。在八十年代后期，几位学者先后开展了基于排程系统处于不同的状态，采用不同的排程规则策略的动态排程方法的研究。它们研究的共同特点是：在支持某些活动发生的资源条件具备时(称为决策点)，根据系统当时所处的属性状态，决定采取何种规则(策略)，确定或选择活动发生的顺序和时间，即状态指导的智能排程方法。

Doublgeri以一个柔性 PCB安装系统为实例，提出基于知识的排程方法 KBS，它采用分级方法并利用仿真技术，根据全局知识划分作业，再根据局部知识将作业分配到设备，通过满足一系列约束以及用户提出的总体和局部目标来产生实际排程。文[46]中探讨了一种基于知识推理的专家系统模型、以实现作业排序问题的求解，并给出了采用三种不同知识表示方式和分段推理的排序知识处理方法。文[45]用黑板模型来组织和维护动态数据库、在规划层用数学规划求解、在排程控制层用基于知识的排程方法。文[36]介绍了动态 Job Shop 排程的工具软件 OCS，提供了 Job Shop排程管理中的集成决策支持系统，它既能用专家知识自动产生和评价排程，也能提供图形界面使用户能进行手工排程。另外还有基于 ERAI网

15

的启发式决策支持系统、基于Petri网的决策支持系统、用专家系统实现的排程模型

SOJ437D、以及利用启发式知识进行资源优化分酸。

总的来说，主要包括智能排程专家系统、基于智能搜索的方法及基于多代理技术（Multi-Agent System 简称MAS）的合作求解的方法等。其中，智能排程专家系统是人工智能应用的体现，由于专家系统中知识获取和推理速度这两个瓶颈，使得神经网络逐渐被采用，但还存在训练速度慢、探索能力弱等缺点。基于多代理技术的合作求解方法是较新的智能排程方法，它提供了一种动态灵活、快速响应市场的生产排程机制，它以分布式人工智能（Distributed Artificial Intelligence简称DAI）中的多代理机制作为新的生产组织与运行模式，通过代理（Agent）之间的合作以及MAS系统协调来完成生产任务的排程，并达到预先规定的生产目标及生产状态。在这种研究方法中，在Agent内部也可采用基于规则及智能推理相结合的混合方法，来构造基于MAS的生产排程系统。

排程方法存在的问题：

排程领域中的大部分问题都具有NP问题，虽然对它的研究已有几十年的历史，但至今尚未形成一套系统的方法和理论，理论研究与实际应用之间还存在着很大差距。尤其随着JIT（Just-In-Time）思想的广泛采用，E/T（Earliness/Tardiness）排程问题，即使得工件尽量按交货期完成，变得越来越突出。实际应用中的排程方法能够响应系统的动态变化，但不能保证得到好的排程：一些理论上的最优化方法能提供最优排程，但由于其计算的复杂性，并且忽略了很多实际因素，离实际运用还有较大距离。基于最优化的方法，诸如动态规划算法与分枝定界算法等等，由于其大多数是建立在对可能排程的部分枚举上，因此只能解决小规模的排程问题，距离实用还有较大距离。

由于大多排程问题属于一类NP困难组合问题，因此寻找具有多项式复杂性的最优算法几乎是不可能的。但因其解的最优性、至今仍激发着学者们进行不断的探索。各种近似／启发式方法、诸如基于规则的算法等，由于能在合理的时间内产生比较满意的排程，因此广泛应用于实际排程中，但其往往对所得的排程解的次优性不能进行评估。在这方面有必要探索更好的近似最优排程算法，可以考虑增加合理的计算时间代价，提高解的次优性。各种基于统计优化的方法、诸如模拟退火法、遗传算法等，提供了一种解决排程优化问题的新途径，但同别的优化算法类似，其也存在着一定程度的校举、一般来说收敛到最优解很慢，并且对于判断解的最优性也很困难。在这方面也需要做进一步的研究。

在实际车间生产排程中，车间生产计划与车间生产排程往往是分层进行的，但这可能造成计划在实际排程中的不可行问题，如何将计划与排程结合考虑，以求总体的优化也是需要进一步研究的。另外，还有很多有待进一步研究的问题，比如实际车间排程的多目标性等。排程理论、方法与应用的研究是一项非常艰巨的工作，目前人们还在进行各种各样的探索性研究工作。

APS排程关键技术：

寻找车间排程的最优解从理论上将是NP-完全问题，没有一个确定的算法来解决这个问题。许多约束条件，使得实际的排程问题变得非常困难，比如：设备的可选性、制造环境的动态与不确定性、约束条件的矛盾（最小加工时间与最大设备利用率）等等，实际上，生产排程问题大部分是集中于简化问题，然后寻找最优解或次优解。研究与开发排程系统面临的关键问题主要有：

16

信息表达：包括排程任务及特殊信息（工作能力、可选生产计划等）的描述。

交互性设计：交互性不单指人机界面的问题，它应支持人对排程过程的直接参与，因为纯粹的自动化排程是不现实的，它忽略了具有最终决策职责的排程行家的重要作用。

多种排程方法的结合。

与已有信息环境的集成：现有企业都已具有了自己的信息技术基础结构，排程系统应能与现有环境进行通讯与信息交换，并作为信息系统的一部分，因此应提供与标准系统（如数据库、网络等）的通用接口。

典型应用：

由于排程问题的复杂性，实际生产排程的目标应定为寻找一个好的、可行的的解决方案而常常不是最优的方案。尽管有大量的解决排程的方案，但是只有少数的方法应用于实际。其中，基于智能的排程方法应用人类专家的经验及特殊领域的知识，在解决排程问题上已经做出了很多成绩。

德国Oldenburg大学的Jurgen Sauer教授及高级软件工程师Ralf Bruns联合研究基于知识的排程系统，为实际的排程系统建立了一个通用的框架，它支持算法的重用并把基于知识的技术应用于环境的组织，同时适应各种动态的变化。他们把这一思想成功地应用于实际，并建立了各种实用的排程系统，其中有连续过程的排程系统、医疗行业排程系统及最有普遍意义的——Job-Shop排程系统。在解决Job-Shop计划排程问题中，这些由大学研究人员及实际应用人员组成的项目组，首先实现了原型系统，并不断对其进行修改扩充，直到它能满足实际的要求，然后把该系统应用于生产管线零配件的Siekmann Fittings 公司，设计开发了PSY（生产计划与排程系统）。该系统使用Prolog语言在SunSparc工作站上开发，包括：人机界面、人机编程接口、与关系数据库（oracle等）的接口，排程系统能够做长期和短期排程计划，能显示排程表与排程过程，用户可以直接参与选择排程策略及修改命令与操作。该系统的使用，极大地减少了排程时间，满足用户的需求，功能强大，目前已开始商品化并走向市场。

近年来对DAI基础性研究与制造系统的应用研究，表明基于智能、自治的Agent 之的相互合作的分布式制造系统可以敏捷地响应环境变化。各国科学家在MAS技术应用于制造业上已做了很多工作，建立了各种各样基于Agent的制造系统原型或仿真系统。各国科学家在MAS技术应用于制造业上已做了很多工作，在生产动态排程的研究领域，KHALID KOUISS 等人[4]针对动态排程问题，设计了基于全局优化目标的Agent排程系统。A.kwork and D.NORRIE[5]把MAS设计思想应用于AGV，用Small-talk语言实现了rule-based object系统。ElpidaST[6]提出了基于订单生产的随机制造系统（RMS），该系统中包括可决定自动排程加工Agent，引入投标、招标机制进行排程，增加生产的柔性和适应性，满足动态变化的订单生产要求。

从系统分析方法学角度而言，解决车间作业优化排程与控制主要涉及：运筹学、复杂系统分析、各种数学模型的分析与建立、人工智能理论、神经网络的方法、基于智能搜索的方法、基于多代理技术的合作求解的方法、用于实时控制的动态排程及建模方法。从信息技术角度而言，车间作业排程与控制技术是计算机应用领域面临的一个非常重要的难题，主要涉及的关键技术有：计算机网络与通信技术、数据库技术、系统建模与仿真技术、人机接口、虚拟现实技术。

中国APS的发展概况：

17

在国外，欧美国家已有很多比较成熟的APS供应商活跃在市场，不仅给ERP软件提供生产模块核心技术，同时给多行业多领域提供很多实用软件和基础功能。相比而言，中国在这方面还没有真正起步。内地各大ERP公司，无论用友、金蝶、神州数码的生产模块都还停留在MRP的层次上。虽然大陆地区基本上从2001年起普及了ERP的概念，但是经过几年ERP实践之后，MRP和BOM还没有被很好利用起来，甚至MIS系统还在艰难代替手工劳动，APS更是很遥远的概念。所以说市场的不成熟也限制了大陆地区软件企业对APS的重视程度。与各大软件企业对APS还处于一片空白状态相比，学院派的专家学者却对研究生产排程极为热门，可以说这是研究CIMS、系统工程、计算机、运筹学、数学等方面学科的博士们以至院士们的老话题了。清华自动化系是这方面的权威，每年都发表大批论文。但是理论距离实用还有很大的距离，始终没有成熟的产品和成果出现，体现了中国在这方面的落后地位。唯一例外是最近出现的有海归和院士背景的北京小吉星公司发布了大陆第一个APS产品，从他们对一些模型问题的解上看拥有了约束和优化等APS的基本功能和特征，但是还看不到他们的软件在企业的实施效果，这可能需要一段时间，而且很难通过一两个特例说明中国APS 的整体水平。

国内情况比较好的要属台湾地区的企业。台湾从2000年已经开始普及SCM的概念，同时APS成为热门，很多加工制造企业从从那时起就开始引入国外的APS系统，很多台湾ERP公司也在不断研究开发APS系统。鼎新投资的鼎诚公司不久前已公开推出APS系统，用于印刷线路板和集成电路企业，从宣传上看是比较接近于真正意义上的APS系统，但是从其应用范围的限制和实际效果的有限，感觉核心技术没有本质的进展。台湾汉康的长项也在生产排程方面，但是基本还是围绕手工方法的简单排程和MRP，不是真正的APS系统。而03年用友2000万与汉康的合作，神州数码与鼎新的合作，都是在比较低的技术层次上，仍然在对MRP进行完善。也说明台湾生产管理水平整体上基本停留在MRP阶段，与APS有很大差距。

六、APS实例：i2 RHYTHM

位于德州达拉斯的i2 Techonolgy公司通过它的RHYTHM软件包提供各种APS软件模块。i2成立于1988年，它的第一个软件产品是Factory Planner，最初在金属工业中取得很大成功，目前i2为汽车、消费品和高科技工业提供各种优化B2B流程的软件模块。最近，i2推出一套新的解决方案TradeMatrix，提供公共和私营电子市场所必须的软件和服务。i2在2000年与Aspect Development公司合并，并与IBM和Ariba结成了伙伴关系。图4 根据供应链计划矩阵给出了i2 RHYTHM的部分APS模块，不同模块之间通过RhythmLink协调和集成，物料需求计划的任务则由其它ERP系统完成。

Supply Chain Strategist(供应链战略)：支持整个供应链上的"what-if"战略分析，决定生产地点、分销中心和其它设施的最优组合和定位，根据不同方案建立有关成本和约束的物流模型。

Demand Planner(需求计划): 提供各种统计方法，随机因素的包含，以及不同组织单位的多输入管理。提供POS(销售点)数据集成并能以不同方式查看需求信息。此外，OLAP(在线分析处理)工具能有效存取有关数据，PRO(产品关系对象)模块支持相关预测的生成。相关预测是指通过对产品组的预测来导出单个产品的预测。

Supply Chain Planner(供应链计划): 根据物料、能力、运输和顾客服务的约束建模和优化供应链。SDP(策略驱动计划)模块允许计划人员定义问题类型和应用适当的算法(如线性规划、启发式推理和基因算法)进行优化。

Demand Fulfillment(需求满足)：生成约束驱动计划，提供所有分销和生产地点的成品、

18

半成品、原材料和资源能力在整个供应链范围的可视性。

Factory Planner(工厂计划)：根据需要日期向后排产或当考虑物料和能力约束时从当前日期向前排产来生成最优生产计划。在生成无限能力计划之后，有限能力计划由i2的专利产品Constraint Anchored Optimization(约束优化模块)决定，不过计划人员也可以通过分析能力短缺和执行“what-if"分析施加影响。

Optimal Scheduler(最优排产)：建立基于基因算法的加工工序和排产计划。约束定义和优化算法的分开允许处理大量约束，这些约束包括车间能力，工作负荷平衡，物料可用性等等，此外，交互排产编辑器允许手动更改。

Transportation Modeler, Optimizer and Manager(运输建模、优化和管理)：是支持分销计划流程的工具。运输建模帮助企业有效地利用它的运输网络，实际数据被用来做"what-if"分析。运输优化根据交付、设备和人力约束自动建立和发送货物，决定装货和交付时间，此外，它也考虑了成组约束和自动选择接驳(cross-docking)机会。最后，运输管理器执行和管理从订单到顾客服务和财务结算的整个运输流程活动。

为了使供应链伙伴之间能互相协作，i2还推出了TradeMatrix和Global Logistics Manager(全球物流管理)模块。TradeMatrix支持采购服务(如电子商务市场)、协作计划流程、谈判和其他B2B解决方案。全球物流管理模块是一个流程建模和监控系统，它提供多模式多企业物流运作的可视性，这一模块的功能包括：订单和库存的可见和跟踪，性能测量，失效报警和改进顾客服务。

第二章由ERP生产提前期的设定引发的思考

我们在实施ERP的MPS/MRP计划时，首先要考虑其产品的加工周期，这常常有两种设定方法，一是把提前期作为一常数，当然预先考虑的是平均批量的平均提前期。二是把提前期作为动

态的数,随批量的变化而变化。

第一种方法的好处是对采购的提前期的影响较少，采购有顺序的先到给先需的生产定单。生产投料，在制品积压较少，但是，对生产定单的工期来说，就需要依赖能力计划CRP的分析

进行大量的调整。

第二种方法的好处是提前期在随批量的变化而变化。导致先投料的单，后产出.引起在制品堆压在车间。对半成品来说，由于某一半成品的周期的变化，会导致其他半成品的等待或滞后，对采购计划的影响也非常大。经常发生后下达的采购单的物料，反而先到。

19

实际上这两种方法都没有解决提前期的根本问题，生产理论界迄今为止也没有更好的阐述。这就导致ERP在计划和生产的实施运用中难度最大。这就给实施者带来很大困惑。为什么MRP的结果总是和实际不吻合或提前期不准？事先作的计划总是要修改，甚至有的管理书上说追求提前期的准确是无意义的。它本身就是一个经验值，或是一个统计值。那么，对我们实际生产管理者来说因如何应对呢？请看生产提前期是如何构成的：

每个工序分解成5个部分：

1, 加工后等待. 2, 运输. 3, 加工前等待. 4, 准备. 5, 加工.

实际上,许多生产专家如Tully 很早就得出如下结果：

等待时间占整个生产周期的比例为90%-95%

1,加工前等待时间75%

2, 运输时间 9%

3,检查时间7%

20

4, 加工故障时间3%

5,而加工时间只占6%

这就给我们显示了缩短生产周期的真正的焦点。我们应尽力缩短加工前后等待时间，运输时间，换装时间。

我们知道制造企业总是存在相互矛盾的目标。销售希望有较短的交货期和准时发货；生产部门希望有一定的批量生产，以提高生产率：财务部门，物料部门都希望有最低的原材料，半成品，成品。现在，快速准时的交货的目标以改变了这些目标的权重，更加强调交货期,产销率，低库存。由于企业实际的管理的难点是难以控制定单延迟，在制品与库存积压，对实际生产控制缺乏理解，出现所谓”车间经验”。对此，美国生产计划专家

G.W.Plossel 作过辛辣的描述并列出6个车间”神化”，对我们现在制造业实施ERP的生产方面有重要的警示：

(1),要想使一个车间的生产力提高，就要多给它下达一些任务。

遗憾的是，给一个超负荷的车间下达更多的任务，会使在正确的时刻完成任务更加困难。

(2), 为了使重要的任务按时完成，必须尽可能早地开始处理这个任务。

如下达更多的任务一样，这也会使车间内的在制品库存增加,从而使特定任务按时完成更加困难。

(3),如果计划生产周期不够长的话，就将它延长。

不可能通过修改计划数据的方法消除计划与实际生产周期之间的差距.重要的是要提高生产能力，消除超量的任务延迟。

(4),如果不能为装配按时提供零件的话，就将提供零件的时间提前。

这样肯定会造成更多的紧急任务，从而使处理任务的灵活性减小，使更多的任务与真正的紧急任务形成竞争，并且影响数据的正确性。

(5), 如果由同一台机床加工的几种零件都不够的话,就将这些零件的加工批量分得更小。

这样看起来情况会有好转，但如果涉及的是一个真正的瓶颈能力的问题的话，这样的做法将引起许多更严重的问题。

(6),如果几个紧急任务被很好的完成了，那么再多几个可能完成得更好。

这种方法企图解决糟糕的计划和控制造成的问题，但是一旦开始能力竞争时,这种加快方法马上就失败了。

21

本文来源：https://www.bwwdw.com/article/tdsq.html