基于供应链的协同生产调度研究 .doc

基于供应链的协同生产调度研究 一、引言 知识经济时代国际竞争的日趋激化，使企业受到了前所未有的挑战。企业间合作的重 要性日益凸显，其组织边界逐渐延伸到有业务关系的合作伙伴和客户，形成了整个价值 链上企业内及企业间网络的集成。现在不断出现的虚拟企业、敏捷制造、动态联盟等概 念都是强调了企业间的合作和优势互补，以提高制造系统的敏捷性。其实质都是供应链 环境下的企业集成。 对于制造业来说，面对日益激化的国际竞争，单个企业的生产计划、生产调度问题的 解决已经不能完全满足现在供应链环境中企业协作生产的需要。多代理系统(Multi-Agent System，简称MAS)在供应链和生产调度方面的研究已经成为当前的热点之 一。但是大部分的研究局限在企业内部，考虑供应链环境下企业生产调度的论文相对较 少。而在现代化大生产中，企业已经不单单是一个孤立的个体，而是供应链中的一个部 分，这是一个更加广阔的企业级结构模式。 运用基于MAS对于充分发挥车间制造系统的功能、调度过程中完善调度策略、供应链环 境下多企业协同生产以及生产过程的高效、稳定运行都是有很大帮助的。因此，为满足 企业在国际化生产的前提下进行合理的生产计划和生产调度，本文提出了基于供应链环 境下的两层MAS体系结构，建构了解决企业在供应链环境下的动态调度以及调度优化问 题的模型。 二、供应链下的协同生产调度 生产调度问题可以描述为：在一定的时间范围内为完成特定的生产任务而分配共享资 源，并使得预定的某些生产指标最优1。传统的生产调度问题基本属于一个企业内部 的生产调度。车间调度问题有以下特点：(1)复杂性。由于车间调度问题是在等式或不 等式约束下求性能指标的优化，在计算量上往往是NP完全问题，因而使得一些常规的最 优化方法往往无能为力。(2)动态随机性。(3)多目标。实际的车间调度往往是多目标的 ，并且这些目标间可能发生冲突。调度目标一般分为基于作业交货期的目标、基于作业 完成时间的目标、基于生产成本的目标三大类。 生产制造车间的计划与调度是一个非常复杂的、需要多方面知识与信息的决策过程， 近年来，人工智能技术、Agent技术在车间计划与调度中得到广泛应用，且应用的类型 很多。Riyaz sikora等2介绍了在敏捷企业中，车间的生产组织方式发生变化，不再 是传统的固定式阶梯型方式，以及如何利用MAS来根据任务的变化对资源进行动态调整 。Kap Hwan Kim等3介绍了一个用于制造系统调度与车间控制的框架结构。框架中引 入了资源代理、零件代理、工程控制代理和事件管理代理。各类代理间均存在错综复杂 的通信关系。Saad A等4分析研究了柔性制造系统中的分布式调度，建立了分布式调 度模型，在制造系统中建立了机床和工件智能代理，采用基于合同网协议的机制，将以 零件为中心的谈判机制和以机床为中心的谈判机制相结合。郭文胜等5提出了基于Multi-Agent的虚拟车间调度作业原理与算法，利用动态形成Agent对资源进行动态调整 。杨根科等6提出了在动态联盟下，从销售代理的角度，研究供应链的最小成本制造 规划的问题。傅小华等7研究了现代生产作业调度的特殊要求，既要满足系统整体目 标，也要注意各子系统的具体特征及局部目标的实现，以及MAS的运用。 而供应链下的协同生产计划调度优化过程是一个复杂的随机、多目标、动态调度问题 ，不同于单个企业的生产调度。供应链环境中，车间的生产组织方式发生了变化。随着 市场需求向小批量、多品种和短交货期的发展及企业生产的横向联合，现代制造系统往 往具有异地分布和异构化的特征。供应链环境下进行生产调度，要同时兼顾企业内部生 产调度的合理性以及供应链中各企业之间的生产衔接、利益分配等。 SCOR(Supply-Chain Operations Reference-model)是第一个标准的供应链流程参考模 型，是供应链的诊断工具，涵盖所有行业。SCOR模型的第一层描述了五个基本流程：计 划(Plan)，采购(Source)，生产(Make)，交货(Deliver)和退货(Return)，如图1所示。 它定义了供应链运作参考模型的范围和内容，并确定了企业竞争性能目标的基础。我们 可以看到，供应链上游企业交货直接影响到下游企业的生产计划和调度，而现在的很多 企业供应链的设计，都是面向订单进行生产的。 三、基于Multi-Agent的体系结构 MAS是一个高度交叉的研究领域，对于Agent，现在还没有一个统一的定义，一般认为 ，Agent是由具有知识、信念、意向、期望等因素组成的一个实体8。但是Agent的核 心概念自治性已经被普遍接受。Michael Wooldridge9认为Agent是具有智能性、 自治性、理解力、学习能力、可以代替用户完成特定功能的软硬件系统。目前的Agent 研究主要在计算机软件领域展开，Agent是一个具有自治性的计算实体，能根据动态变 化的环境信息做出决策。MAS利用Agent来表示制造中的各种资源，通过网络及Agent通 讯协议将它们连接成一个MAS，然后采用MAS的理论和方法对Agent进行研究。而在大规 模定制生产方式下的供应链计划调度优化过程是典型的随机、动态、多目标优化过程1 0，进一步根据计划进行生产调度就更加复杂。根据Agent的特点，我们可以将Multi-Agent技术运用在供应链环境下的生产调度中。 现在，MAS被认为是模拟和支持这些分布式的复杂系统和环境的一个比较好的方法。MAS是一个包括若干个代理的、并以特定方式相互作用的复杂处理系统。MAS中的组织结 构主要有以下几种：黑板结构、团体结构、合作规划结构、基于合同网协议的组织结构 等。而基于合同网协议的结构在MAS被广泛采用，它模拟了合同行为中的招标、投标、 中标者。合同网中的代理具有多个层次，可以既是下层代理的管理者，同时又是上层代 理的承包者。 因此，对于供应链下的各企业协同生产调度，我们可以利用Agent来表示生产中的各类 资源，通过网络和协议组成一个MAS系统，并利用MAS的方法通过协议、合作来完成各个 企业的协同生产。基于MAS系统实现供应链企业协同生产的系统体系结构见图2所示。 由于供应链下的企业生产调度关系到多企业、多车间调度策略的确定，因此，我们可 以把模型划分成企业级和车间级进行区分。企业级代表了整个企业进入供应链的网络， 与其他企业的Agent进行协商、合作和调度。企业内部车间级别的Agent主要是在企业内 部发挥作用，保证了企业优化生产调度的最终实现。进行这种两级划分的好处是使得企 业可以灵活地选取需要的部分，在供应链环境下企业选择两级的Agent体系架构，保证 了供应链下的总生产计划制定和各个企业根据总生产计划进行内部生产高度，为最终完 成生产计划提供了有力的保证。而在单个企业中，也可以利用车间级别的Agent体系架 构进行单个企业的生产调度，完成生产订单的生产。 Agent体系架构中企业级包括了计划Agent、企业级资源Agent、物流Agent。车间级中 包括了订单Agent、任务Agent、调度Agent、车间级资源Agent。本系统架构中，Agent 通过相互协作而达到全局目标实现。同时，Agent尽力获取局部的自身利益，可以作为 一个自律的、自治的独立实体存在于整个系统之中。在两级资源Agent之间协作谈判的 实现方法主要是采用仲裁机制和招投标机制相结合。各代理的含义和功能如下： (1)计划Agent(企业级) 计划Agent主要有对内和对外两方面的职责。 对内职责：负责根据企业接到的生产订单制订生产计划，并根据生产计划产生一系列 的订单下发到车间级的订单Agent，根据企业知识库和企业级的资源Agent信息将企业总 的生产计划分解成车间级别的订单下发到车间级。 对外职责：由于企业是处在供应链的环境之中，所以，企业的生产可能依赖于其他企 业的产品，因此，计划Agent还要根据企业级资源Agent的信息对外招标，发出生产资料 的需求订单给别的企业的计划Agent，与别的企业的计划Agent在合同网结构中进行招标 、投标和协商。 企业级的计划Agent的任务比较复杂，包括了对内生产计划制定、生产计划根据企业资 源细分订单下发到车间订单Agent，对外产生需求并进行招标等等工作。因此，下一步 的工作中，可以考虑进一步细分企业级计划Agent的功能。 (2)资源Agent(企业级) 企业级的资源Agent代表了企业的生产资料和生产能力，可以代表企业进行计划Agent 之间的投标、协商工作。横向可以与其他企业进行任务的转包，具有很大的灵活性。 企业级的资源Agent与车间级的资源Agent相互通讯，代表了企业车间的总生产资料和 生产能力，并根据车间级资源的变动而变动。同时根据计划Agent进行任务分配的协商 ，来分配企业级粗粒度的任务调度。 (3)物流Agent(企业级) 物流Agent作为供应链的一个环节，负责把生产出的产品在适当的时间，以适当的数量 ，运送到适当的地点。如果企业不是制造型企业，那可能就只需要计划Agent、资源Agent、运输Agent，不需要车间级的各类Agent。 (4)订单Agent(车间级) 订单Agent处理企业级计划Agent发出的计划，并根据计划以及企业车间的情况进行任 务划分，根据车间资源对接到的订单计划细分成一系列任务，发到任务队列等待调度和 处理。 订单Agent进行处理的时候，必须和其它车间级的Agent进行协商，进行分配，而且需 要接受调度Agent因实时监控中产生异常信息而对任务的分配进行必要的调整。 (5)任务Agent(车间级) 任务Agent在车间级Agent中是比较重要的环节，主要包括两方面的任务。一方面，任 务Agent负责利用Agent组织结构中的合同网协议的结构向企业级的资源Agent进行招标 ，并进行投标的处理和决策，确定参与完成每个任务的资源Agent的集合，并利用与资 源Agent之间的通讯，决定资源Agent空闲的能力。 另一方面，任务Agent需要监督和管理任务执行的全过程，如果任务完成过程有问题， 或者有紧急订单下达，需要和资源Agent、调度Agent进行协商，并进行任务的重新调度 。 (6)调度Agent(车间级) 具体实现车间的生产调度计划。主要根据下发任务的开始、截止时间和约束关系作为 初始条件，调用调度的算法库选择合适的调度算法，最后输出合理的工序进程队列。同 时，调度Agent还要完成实时的车间控制，检测工作实时完成的状况，如果不能完成， 或者出现问题，及时进行反馈和错误输出。根据异常情况进行再调度。 (7)资源Agent(车间级) 资源Agent直接代表了生产资料，根据生产资料的运行状态跟外界进行协商和谈判。对 于任务Agent发出的任务按照自身的能力进行投标。资源Agent之间也可以进行协商和谈 判以解决相互之间的冲突。而且通过Agent之间横向的协商，可以进行任务的转包。 车间级别的Agent与企业级别Agent进行通讯，反馈本车间的生产资料状况和生产能力 。 四、合同网协议的决策方法 为了选择执行特定子任务的Agent，必须按照一组相关的属性和判断标准对投标的Agent进行对比评价，可以考虑采用决策矩阵的构造和使用合适的决策规则。 决策矩阵构造：A = (a,ij),ij(i = 1，2，n；j = 1，2，m)，其中， 行表示候选的Agent，而列表示属性或者判别准则。每个元素a,ij表示第i个Agent对 应判决准则j的属性值。 决策规则：决策规则用以选择最佳的候选Agent，以决定中标的Agent完成子项目的任 务。我们可以设置被评价 五、MAS系统实现 MAS各Agent单元之间采用KQML语言作为通讯语言，KQML是基于消息的Agent通信语言， KQML对信息定义了公共的格式。KQML的消息可以大致认为是一个对象，每条消息有一个 语用词以及多个参数9。KQML支持Agent之间高层次的通讯，并且可以根据实际MAS系 统的需要对原语进行扩充。 当某个Agent需要与其他Agent进行通讯时，利用KQML协议，把实际的信息封装在KQML 消息中发送给其他Agent进行数据交换。使用CORBA独立于各种编程语言的IDL语言来定 义出统一的接口。利用CORBA和KQML的完美结合，使得分布式的多Agent系统易于使用、 扩展而且有很好的柔性。 系统可以采用JAVA语言实现，系统通讯的底层采用TCP/IP协议，以支持Internet范围 的通信和协作。MAS中的组织结构采用合同网协议的组织结构，Agent之间的协调可以基 于多种方式：基于对策论、基于协商、基于规则。在实际系统中我们可以采用协商和仲 裁相结合的方式。 具体原型系统的实现可以参考一些Internet上基于Agent，而且开放源代码的项目。现 在提供基于JAVA的Agent体系结构的项目有很多，主要可以考虑采用的开源代码项目主 要有以下几个： (1)Cougaar是一个基于JAVA体系结构的开源项目，用于构造大型的、分布式的多Agent 系统。即能够支持小规模的系统，也能支持大规模、分布式的Agent系统。Cougaar包括 了一套先进的核心架构、多样的中间件支持开发、可视化、以及对于复杂的分布式系统 的管理工具。 (2)JADE是一个完全由JAVA实现的软件架构，它提供了一些系列的完全符合FIPA规范的 中间件，能够简化多Agent系统的实现，还提供了一系列的调试和发布的工具。而且JAD E平台能够分布在多种不同的系统上。 (3)英国电信基于JAVA的项目ZEUS，ZEUS为快速地开发以及发布Agent系统提供了软件