基于招投标机制的虚拟制造单元的作业计划研究

常志会

（江苏科技大学经济管理学院，江苏镇江 212003）

当今，面对竞争激烈、动态多变和订单驱动的市场，制造企业的竞争优势在于快速反应产品和需求的动态变化，在Zhang＆Sharifi的研究报告中指出，制造业为实现快速反应，问题集中在生产计划与控制上，尤其是作业计划和调度［1］。而采用机群或（常规）成组技术组织生产，无法根据任务的变化动态调整，不再是实现每一次加工任务的最佳配置，影响了系统柔性和快速反应的性能，同时还造成了资源的浪费，20世纪80年代美国提出虚拟制造的概念，虚拟制造单元主要的机器共享和布局上与传统的制造单元存在差异［2］，同时在成组技术基础上的虚拟单元在计划和控制能减少机器准备时间，采用虚拟制造单元组织生产能增强系统柔性，及时应对突变的情况［3］，而且虚拟制造单元还能有效利用企业内外部资源，提高系统生产率，通过对制造资源优化组合，可以缩短任务的完成时间，这是传统的单元化生产方式不能比拟的，其目标就是利用不同位置的现有资源，快速、高质量、低成本地完成加工任务。因此，如何组织虚拟制造单元以及在这种组织下如何安排作业计划与调度是面临的一个问题。

随着多代理技术在先进制造系统中的应用得到迅速发展，Agent所具有的自主性、交互性、反应性等特点为解决车间任务的计划与调度问题的求解提供了一个非常有效的方法。在已有文献中，基于代理的计划与调度可以分成两类:招投标的方法和非招投标的方法。二者均假设在分布式生产环境下，后者主要是代理之间直接的信息交换，以接收到的信息来决定调度方案，该方法的缺点是计划代理遵从一个固定的进程计划，如对每一个任务预先固定资源，Caridi and Sianesi［4］的研究中所采用的非招投标的方法，从案例得到结果并没有表现出比传统集中控制更优的性能。而前者是代理对任务的计划与调度进行招投标，代理（管理者）将任务分解为可操作的子任务，具有能力完成子任务的其他代理对这些子任务进行招投标，代理通过招投标满足目标函数。在基于Agent技术的招投标的方法的计划与调度的研究中，主要是任务Agent向资源Agent发布招标信息，后者根据自身生产能力自主决定是否竞标，最后由调度Agent从所有竞标资源中选择完成任务的最优资源［5－8］，从而进行动态的任务分配，但是这些研究都在系统中实现动态任务计划与调度，普遍采用都是由上层Agent（单元控制Agent等）直接根据工序任务对设备Agent进行招标，而设备Agent只考虑的是本工序的加工任务，忽略了整体任务的前后工序间的联系，最终产生不一定是最优的方案［7－11］，因此，本文采用虚拟制造单元的方式来组织生产，在任务计划时考虑前后工序的约束，为更好地满足交货期的要求，采用推动式/拉动式的招投标策略，在确定计划方案时，不能以某个竞标资源完成单个任务最优为评定依据，而应以整个任务总体完成效益最佳为目标。

1 虚拟制造单元

虚拟制造单元的概念是相对于传统的物理制造单元而言的，按照1982年，Mclean等人提出的概念，虚拟制造单元是指具体的制造对象在单元控制器中的逻辑组合。在车间中，虚拟制造单元是随着任务的产生而产生，随任务的结束而消亡的，具有一定的生命周期，其生成针对某一个具体的生产任务。本文在代理技术的基础上，采用招投标的形式确定任务的加工设备，由这些加工设备在逻辑上形成一个虚拟制造单元。

虚拟制造单元的组建的招投标过程中涉及到以下几种代理:

（1）虚拟单元控制Agent 一个虚拟单元控制A-gent封装了一个工件任务，它包含了任务的基本信息，如工序顺序，交货期，性能指标和数量要求等，是该工件所有工序的集合。每一个工件都有一个优先级，根据优先级的大小来顺序地启动招投标程序。

（2）物理制造单元Agent 对应车间中具体的设备资源，存储设备资源的加工能力、加工状态等信息。当物理单元Agent收到招标信息后，根据自身的判断选择合适的设备资源进行投标，中标后进行加工。

（3）任务调度Agent 负责接收虚拟单元控制A-gent的加工请求，对可能的物理单元Agent发送招标信息，招标结束之后并根据一定规则进行评标，获取计划调度结果。

2 任务计划的招投标策略

面向任务组建的虚拟制造单元的目的就是根据生产的实时信息进行任务动态分配，任务分配的结果就相应地形成了任务的作业计划。在准时化生产下，为更好地保证任务按时交货，在考虑任务前后约束的基础上，设计了拉动式与推动式招投标策略。

定义:工件Ji的第j道工序为当前工序，则工件Ji的第j道工序之前的所有工序称为前继工序，工件Ji的第j道工序之后的所有工序称为后续工序，Ji，j－1为Jij的紧前工序，Ji，j+1为Jij的紧后工序，工件Ji的第一道工序称为首工序，最后一道工序称为尾工序。

在生产中，车间中设备时间段是间断的，有些时间段是已经安排任务，有些则是闲置的，在招投标过程中，设备选择自身可用时间段内进行投标。

2.1 拉动式招投标

拉动式招投标机制是以任务的工序顺序为正向，任务调度代理根据任务交货期启动反向招投标，任务调度代理向各个尾工序可用设备招标。由于这些设备只有能力完成自己的任务工序，所以根据自己完成该道工序所需的加工时间推算出该工序的开始时间，并将不能完成的前道任务工序向紧前设备代理招标，依次循环，直至首工序完成招标活动。而投标则从首工序开始直至尾工序设备代理，除了首工序对应的设备代理外，每道工序的代理都对前一道工序的代理招标依据目标进行评估，最后尾工序向任务调度代理提交投标信息，由任务调度代理依据目标对投标信息进行综合评标，得到最佳结果。

2.2 推动式招投标

推动式招标从任务的首工序开始，直至尾工序结束，首工序的设备招标不给定招标参数，由物理单元Agent根据当前时刻确定本工序最早开始时间，并计算完成本工序的结束时间，以此作为招标参数向紧后工序招标。投标从尾工序开始，直至首工序结束，投标参数与拉动式投标的参数相同。由于推动式招标中紧前工序只是向紧后工序提供了自己的结束时间，并没有限制其开始时间，因此推动式招标一定有时间段安排工序，最终一定能得到计划结果。

现实生产车间中，由于拉动式招标比推动式招标能更好地满足准时制生产方式（JIT）对交货期的要求，因此在车间中往往首先采用拉动式招标。但是拉动式招标可能由于紧后工序限制了紧前工序的最迟结束时间而导致紧前工序找不到可用时间间隔，而导致招标失败，此时停止招标，同时调度Agent启动与拉动式招标过程相反的推动式招标。

3 任务计划的评标函数

招投标机制中最关键的一个环节就是评标。传统的评标方法，在很大程度上依赖于专家经验和工作经验，可靠性低、风险性大、外界干扰多、实用性差，主观判断差异大，选取的评价因素少，评价结果的准确性难以保证。在车间计划与调度决策性能评价指标多是注重加工时间，随着市场需求的变化，制造企业关注的指标出现多样化，如时间指标、经济指标和性能指标。实际生产中，不同的企业，甚至同一个企业在不同的时间、不同的环境下，其目标要求往往也不同，在任务的招投标过程中车间更注重的是任务加工时间短，同时生产成本低，有较大的获利空间，因而，评标函数关系着整个系统的性能是否能达到最优。

3.1 评标因子的选取

在车间中常用的评价指标主要有时间指标、经济指标和系统指标［12］。其中，时间指标有交货期、工件的平均流通时间、作业的完成时间等等;经济指标包括生产成本、延期－提前的费用等，系统指标主要有设备利用率等。在任务分配中，不可能满足所有的指标，而衡量生产效果的两个重要指标是时间和成本，所以根据本文所研究的对象，选取了加工时间、生产成本、运输费用等因子来评价投标信息。

3.1.1 加工时间

任务的加工制造过程具有显著的时间特征，能在短的时间内完成产品的加工并交付给顾客，实现完成加工任务占用的时间最短，能提高企业响应市场的速度。本文所考虑的加工时间主要由基本加工时间、缓冲时间和调整时间构成。即:Ti=tm+tw+ta。其中:Ti表示第i道工序的加工时间;tm表示基本加工时间;tw表示缓冲时间;ta表示调整时间。

3.1.2 加工成本

企业以获取最大经济利益为目标，产品的获利能力与产品的加工成本有密切的关系，因而加工成本是影响企业竞争力的很重要因素，本文中考虑的加工成本主要包括设备成本、人力成本和能源成本。即:Ci=cd+ch+cr。其中:Ci表示加工成本;cd表示设备成本;ch表示人力成本;cr表示能源成本。

3.1.3 运输费用

由于工件的所有工序并不是都在一个物理单元内加工完成，因此本文考虑了工序在单元间不同机器上加工时所产生的运输费用。即:Si=Z1ξts。其中:Si表示从工件的第i－1道工序的设备位置到第i道工序的设备位置所需要的运输费用;ξ表示时间相对费用的折算系数，它由车间的实际情况给出;ts表示从工件的第i－1道工序的设备位置到第i道工序的设备位置所需要的最短运输时间，它根据车间的时间情况给出。Z1=1，表示工件的第i－1道工序的设备位置与第i道工序的设备位置不在同一单元，否则为0。

3.2 综合评标

综合以上所考虑的因子，在任务分配时，由于时间和成本是不同量纲参数，不能直接根据这两个指标选择合适的资源。本文采用文献［13］中的无量纲化公式对时间、成本和运输费用进行无量纲化处理。即:

其中:ax表示处理后的指标值，bx表示处理之前的指标值。如，某道工序经招标之后，收到3个投标Agent对该工序的投标，其加工时间分别为17、18、20，那么无量纲化处理之后的加工时间分别为1、34、100。

经过招投标过程，对资源进行评判时并不是以单道工序任务的时间、成本最小为主，而是以完成整个任务的时间、成本为最小，需要把多目标问题转化成单目标问题，根据车间实际情况赋予时间和成本一定权重，那么综合评价指数变为

其中:α1、α2是时间和成本的加权系数，∑αk=1（k=1，2）。

由于拉动式招标采取正向投标，除首工序对应的单元Agent外，其余工序的Agent将收到的紧前工序Agent的投标信息无量纲化之后，计算综合评价指数，从中选择最小值并将其投标信息的任务参数放入任务参数队列尾部，确定自己的投标参数，向紧后工序A-gent投标，直至尾工序，当尾工序Agent向调度Agent的投标将意味着相应的工件得到了计划结果。最后调度Agent根据完成工件所有工序的综合指数最小来确定中标工序。推动式招标的评标过程与此相反。

4 结语

多品种小批量的生产方式下，为提高制造系统的柔性和快速反应能力，本文采用面向任务的虚拟制造单元的方式组织生产，针对以往基于Agent的调度研究中没有考虑任务前后工序之间联系的缺点，在满足交货期要求下，采用推拉式招投标策略，在评标中采用综合指标以使整体任务完成的时间和成本最小，实现了任务的动态分配。但是这种方式每次只能分配一个工件任务，在分配之前需要确定任务的投放顺序，当任务数量很少时，调度人员可以根据启发式工件规则确定任务投放顺序，当任务数量很多时，需要采用遗传算法确定最佳的任务投放顺序。

［1］Zhang Z，Sharifi H.A methodology for achieving agility in manufacturing organizations［J］.International Journal of Operations ＆ Production Management，2001，20（4）:496－512.

［2］Fung Rechard Y K，Liang Feng，Jiang Zhibin，et al.A multi－stage methodology for virtual cell formation oriented agile manufacturing［J］.Int J Adv.Manuf.Technol.，2008（36）.

［3］Gert Nomden，Durk－Jouke vall der Zee.Virtual cellular manufacturing:configuring routing flexibility［J］.International Journal of Production E-conomics，2008，112（1）:439－451.

［4］Caridi M，Sianesi A.Multi－agent systems in production planning and control:an application to the scheduling of mixed model assemble lines［J］.International Journal of Production Economics，2000（68）:29－42.

［5］Li Shujuan，Li Yan，Liu Yong，et al.A GA－based NN approach form akespan estimation［J］.Applied Mathematics and Computation，2007，185（2）:1003－1014.

［6］Parunak V D.Manufacturing experience with the contract net.Distributed Artificial Intelligence［J］.Huhns，M.N.ed.Pitman，1987，285－310.

［7］高锷，王治森.基于多Agent的网络化车间制造系统调度问题研究［J］.中国机械工程，2003，14（12）:1033－1036.

［8］黄萍，宋海生，朱金达.基于多Agent机制的制造单元调度系统的研究［J］.现代制造技术与装备，2008（5）:66－67.

［9］张宇，孙宪鹏.基于多代理结构的Job－shop动态优化调度策略的研究［J］.制造业自动化，2001，23（3）:22－24.

［10］Choi H S，Park K H.Shop－floor scheduling at ship building yards using the multiple intelligent agent system［J］.Journal of Intelligent Manufacturing，1997（8）:505－515.

［11］Jun Bin.Research and realization of production scheduling system based on multi－agent mechanism［J］.Computer Technology and Automation，2002（9）:105－108.

［12］Albert Jones.Luis rabelo job shop scheduling［M］.Encyclopedia of Operations Research and Management Science，Centennial Edition，Kluwer Academic Publishers，London，UK，2001:419－429.

［13］雷燕.基于合同网的多Agent协作技术在车间调度中的应用研究［D］.武汉:武汉科技大学，2009.