一种基于VCG拍卖的智能车间主动调度方法

摘要

本发明公开了一种基于VCG拍卖的智能车间的主动调度方法，该方法充分发挥了智能制造的主动调度特征，设计了两种基于知识驱动的工件估值函数，构建工件智能体的“大脑神经元”。工件自主对机器上不同的加工顺序进行估值，确定竞拍报价；机器根据社会效益最优选择工件，实现机器‑工件的自主匹配，实现智能车间自治运作。基于拍卖的智能车间主动调度方法规定智能车间运作规则，即排队工件对机器加工顺序自主估值，机器根据社会效益最优选择工件，实现机器‑工件主动调度，实现智能车间高度自治的运作模式。本发明的主动调度方法，能够实现工件真实报价、个体理性、有效分配和预算平衡。

说明书

技术领域

本发明涉及智能车间技术领域，特别涉及一种基于VCG拍卖的智能车间的主动调度方法。

背景技术

近年来智能制造已经成为学术界和业界关注的研究热点。随着制造车间中制造资源的互联互通和智能化，传统的“被动式”调度方法已经无法满足智能制造调度的需求。智能制造的一大特征是“主动”，如何发挥制造资源智能属性，实现资源自主决策、自主协商、自主维护，进而实现智能制造要素主观能动性，成为当前国内外制造业实现智能制造面临的共同挑战。

主动调度(Initiative scheduling)模式，正式给出了主动调度的定义，辨析了主动调度与被动调度(Passive scheduling)的区别与联系，阐述了主动调度使能体，分析了调度要素之间关系的演化模式，讨论了被动调度和主动调度各自的运作模式，探讨了主动调度的互调度行为，给出了主动调度的未来研究方向。基于生产趋势预测的主动调度方法，建立了实时状态模型表达生产过程中的历史信息及实时状态信息，并利用了贝叶斯网络进行推理，预测生产过程的加工趋势，再以趋势预测的结果作为实时调度的触发条件和依据，生成针对异常趋势的主动式调度方案。

当前智能制造的主动调度方面的研究仍然是发展初期，对于适应智能制造复杂环境的主动调度机制及智能体交互机理等关键技术缺乏深入的研究。

发明内容

本发明提出了一种基于VCG拍卖的智能车间主动调度方法，赋予制造资源智能决策的能力，实现了工件智能体自主评估加工顺序价值、机器-工件自主协商确定最优加工顺序。

为实现上述目的，本发明提供了如下方案：

一种基于VCG拍卖的智能车间主动调度方法，包括以下步骤：

S1、工件对机器上的不同加工顺序进行估值，工件的估值通过估值函数来计算，得到工件使用不同加工顺序的预估利润；

S2、工件基于所述预估利润向机器不同加工顺序提出报价；

S3、机器以最大化总利润为目标，构建整数规划模型IP；

S4、求解所述整数规划模型IP，确定各个加工顺序的中标工件；

S5、基于VCG支付方案计算得到中标顺序的最终支付价格，实现机器的加工顺序与工件的主动匹配。

优选地，所述S1还包括以下步骤：约定机器前的排队工件组、机器上的加工顺序为拍卖对象、排队工件组中的工件为拍卖者。

优选地，所述S1中估值函数分为两种：基于加工时间平均数的估值函数MPT-EF、基于交货期的估值函数DD-EF。

优选地，所述基于加工时间平均数的估值函数MPT-EF的构建方法为：

约定每个工件的加工时间为平均加工时间

优选地，所述工件根据所述加工顺序的预估利润进行竞价，其所述预估利润越大，对该加工顺序的竞价也就越大，所述加工顺序的竞价不会超过其预估利润，即：

优选地，所述基于交货期的估值函数DD-EF为：首先，计算工件的最大惩罚成本，即为工件第一个加工的惩罚成本和最后加工的惩罚成本的最大值，并且将工件的价格设为maxET；其次，根据工件交货期的早晚对工件进行排序，交货期排序为u的工件对机器上第u个加工顺序工件的竞价最高，确定工件在加工顺序上的预估利润；在JIT生产中，工件提前惩罚系数一般小于拖期惩罚系数，其他顺序的预估利润符合等差数列递减。

优选地，所述S3中整数规划模型IP的构建方法为：

其中决策变量是x

优选地，所述S4中求解整数规划模型IP，可以通过分支定界算法求解得到最优解。

本发明的有益效果为：

(1)本发明提出了一种基于VCG拍卖的智能车间主动调度方法，赋予制造资源智能决策能力，实现工件智能体自主评估加工顺序价值，机器-工件自主协商确定最优加工顺序，该方法区别于传统事先确定工件或机器调度规则等“半主动”调度做法。

(2)本发明设计了两种基于知识驱动的估值函数，从加工时间和交货期两个角度，构建工件智能体的“大脑神经元”，使得工件智能体能够逻辑推理，实现工件智能体对机器加工顺序的自主性估值。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的附图。

图1为本发明主动调度机制的智能车间运作模式图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

为使本发明的上述目的、特征和优点能够更加明显易懂，下面结合附图和具体实施方式对本发明作进一步详细的说明。

考虑5个工件智能体在单机情况下如何实现主动调度，分析基于VCG拍卖的智能车间主动调度方法(如图1所示)的有效性，并且比较两种估值函数的效果。工件组的基本参数包含：加工时间、交货期、提前惩罚函数系数和拖期惩罚函数系数见表2：

表2算例数据

首先对工件组的工件进行排序，每个工件自行评估各个加工顺序的价值，对加工顺序进行报价；

考虑基于加工时间平均数的估值函数，即MPT-EF对加工顺序进行估值；

设工件i∈U的加工时间为p

已知每各工件的加工时间，可求的每个工件的平均加工时间

计算工件i∈U的加工顺序j∈S加工的预估惩罚成本为

计算工件i∈U在加工顺序j∈S加工的预估利润为

预估利润见表3。该预估利润为工件的报价。

表3工件对加工顺序的报价(基于加工时间平均数的估值函数)

对机器来说，其目标是如何分配加工顺序使得整体利益最高，构建整数规划模型(IP 1)如下：

其中决策变量x

目标函数(1)表示总社会效益最大；约束(2)表示每个工件只能拍到一个加工顺序；约束(3)表示每个加工顺序只能满足的一个工件的加工请求。

根据模型(IP 1)求解得到每个加工顺序的中标者，即最优调度方案为B、C、A、D、E，目标函数值为422.2。同时，可以计算出此调度方案B、C、A、D、E的总提前/拖期成本为48。VCG工件的报价并不是最终支付价格，各个工件的支付价格分别为：工件B为顺序1支付0、工件C为顺序2支付0、工件A为顺序3支付8.6，工件D为顺序4支付25.8、工件E为顺序5支付16.0。

VCG定价机制鼓励说真话，避免虚假报价，既满足价格的可信，又可以满足社会福利最大。VCG工件的最终支付价格并不是最初的报价，而是由受损者的社会总效用损失决定，并且最终支付价格一定小于等于最初的报价，也一定小于等于估值价格，这样也满足了工件智能体个体理性的要求。

其次，考虑基于交货期的估值函数，即DD-EF对加工顺序进行估值，计算工件i∈U的最大惩罚成本，根据工件交货期对工件进行排序，因为交货期排序为u的工件对第u个加工顺序工件的竞价最高(交货期排序为1的工件对机器的第1个加工顺序竞价最高)，设定工件i∈U在加工顺序u上的预估利润为maxET。

得到工件对加工顺序的相应预估利润，如表4所示。

表4工件对加工顺序的报价(基于交货期的估值函数)

根据模型(IP 1)求解得到每个加工顺序的中标者，即最优调度方案E、D、B、A、C，目标函数值为356.0。同时，可以计算出此调度方案B、C、A、D、E的总提前/拖期成本为302。VCG工件报价并不是最终支付价格，各个工件的支付价格分别为：工件E为顺序1支付34.4、工件D为顺序2支付21.2、工件B为顺序3支付56.0，工件A为顺序4支付10.4、工件C为顺序5支付0。

另外，求解以总惩罚成本最小为目标函数调度模型MIP1，得到最优加工顺序为B、C、A、D、E，其总提前/拖期成本为48。

C

其中

目标函数(4)表示JIT生产的目标即总提前/拖期惩罚最小；约束(5)表示每个工件后面只有一个紧邻工件；约束(6)表示每个工件前面只有一个紧邻工件；约束(7)表示工件k的完工时间等于前道紧邻工件完工时间加上其加工时间。该约束同时限制了工件加工重叠情况。约束(8)设定虚拟工件完工时间为0时刻。

本发明提出的基于VCG拍卖的智能车间主动调度机制通过理论证明得到两点结论：第一，工件根据预估利润提供真实的报价(Truthful bidding)是VCG拍卖机制实现纳什均衡的前提。第二，VCG拍卖机制可以实现个体理性、有效分配和预算平衡。

以上所述的实施例仅是对本发明的优选方式进行描述，并非对本发明的范围进行限定，在不脱离本发明设计精神的前提下，本领域普通技术人员对本发明的技术方案做出的各种变形和改进，均应落入本发明权利要求书确定的保护范围内。