APP下载

基于非合作博弈和RFID的紧急加单下柔性作业车间动态调度方法

2018-07-20彭琰举罗庚合

制造技术与机床 2018年6期
关键词:工序柔性车间

王 晋 彭琰举 罗庚合

(①西安航空学院机械工程学院,陕西西安710077;②西北工业大学现代设计与集成制造技术教育部重点实验室,陕西西安710072)

车间调度问题作为提高企业竞争力的一个核心问题,吸引着大量的学者进行广泛而深入的研究。在传统的柔性作业车间生产调度问题中,学者们主要对静态环境下的车间调度问题进行了研究,并没有考虑车间环境本身的不确定性和动态性。但在实际的柔性作业车间制造环境中,一些不可预见或随机的内外扰动事件的发生使得原有的调度计划不可行。例如:机器故障[1]、工人缺勤[2]、工序加工时间相对于计划延长或者缩短[3]、物料未能及时送达[4]、新的订单加入[5]或订单取消[6]等,因而需要采取动态调度的方法,以快速响应环境变化,修复原有调度计划,使生产调度持续优化运行。由于生产过程和动态调度是并行的,因此要求对原调度的修复时间尽可能短,使之对调度系统的性能影响降到最低;并且重调度和原调度之间要衔接合理,保证生产过程的高效性[7]。这就对柔性作业车间动态调度算法稳定性和算法对异常事件的响应能力提出了更高的要求。

近年来,随着信息和传感技术的快速发展和广泛应用,很多企业已经开始采用这些技术对车间中生产情况进行实时的追踪和追溯,以改善车间调度系统的性能。现今,许多学者通过将云制造和物联制造技术应用到工业制造中,使得生产中的实时数据已经变得无处不在,这将使各种制造资源的实时状态能够被容易的感知。因此,在真实的制造环境中,实时的制造数据将会挑战传统的多目标动态调度问题。例如Pach等[8]提出了一种在动态环境中的完全反应式方法来对柔性制造系统进行调度,他们考虑的3个目标,分别是时间、能耗和资源转换数。Cuihua等[9]提出了一种新的方法来处理简单的调度问题,该方法采用RFID来获取车间中的实时制造信息,用来增加调度结果的可行性并且能够提高制造过程的智能化和有效性。

尽管这些研究有着重大的意义,但是在实时制造车间中,伴随着生产任务的复杂性,生产异常的随机性,柔性作业车间的调度方法仍然有以下的问题。

(1)如何设计一种新的紧急加单下柔性作业车间的分配方法来实现紧急加单的任务分配。一般来说,现有的紧急加单处理方法是遵循给定的目标集中式的将加单进行分配。然而,在生产执行阶段,伴随着加单数量和加单频率的增加会导致生产调度系统的性能出现下滑,因此需要设计一种新的基于实时数据的紧急加单下柔性作业车间调度方法来避免或者减少对调度系统性能的影响。

(2)如何在物联制造车间中对调度系统的快速性和稳定性进行优化。当前,对于紧急加单下的柔性作业车间的问题已经吸引了大量的学者进行研究。一般来说,解决紧急加单下柔性作业车间的方法分为两种:反应式调度和预测反应调度。预测反应式调度是指在调度的生成阶段不考虑制造环节的不确定性,只在不确定因素发生时重新进行调度。这种调度模式是目前众多学者研究的重点。在预测反应式调度中,大部分研究将时间作为优化的目标。但是近年来,对于稳定性和快速性的优化越来越受到学者们的关注。然而,现有的文章多数考虑在传统的制造车间中进行调度,并没有考虑车间中的实时数据。

基于上述分析,针对路径柔性和工艺柔性的柔性作业车间调度问题,本文首先建立了基于非合作博弈和RFID的紧急订单下柔性作业车间动态调度方法体系框架,然后以柔性作业车间生产调度系统的快速性和稳定性为目标,在考虑有紧急加单发生的动态生产环境基础上,建立了基于非合作博弈的柔性作业车间动态调度模型;然后,结合完全信息下的静态博弈理论,提出了基于非合作博弈的柔性作业车间动态调度算法,并给出了一种紧急加单任务的分配策略。

1 基于非合作博弈和RFID的紧急订单下柔性作业车间动态调度方法体系框架

在传统的柔性制造车间动态调度问题中,当有紧急加单时,生产调度系统会将所有的加单集中地分配给相应的机器。在这种集中调度的模式下,机器不能和其它的制造资源进行实时的交互,所以当有紧急加单进行调度时,制造资源的实时数据并没有被考虑。本文针对以上问题,提出了在紧急加单发生时,基于机器和制造资源相互感知情况下的实时调度分配策略,共包含3个模块:(1)物联制造车间模块。(2)紧急加单下柔性车间动态调度的分配策略模块。(3)基于博弈论的紧急加单下柔性车间动态调度方法模块,如图1所示。首先将RFID的读写器以及标签贴在机器以及相应的制造资源上,那么一个RFID驱动的实时制造车间就被建立起来。在这个实时数据驱动的车间环境中,将所有的紧急加单放入一个订单任务池,选取订单任务池中的两道工序放入待调度任务池,然后待调度任务池中的每道工序将会自动地发送它自己的实时状态信息并且请求相应的机器。此时工序和机器通过RFID持续进行交互。按照机器以及工序的实时状态信息,加单的工序通过博弈的方法被分配到最优的机器上。通过这种机器和制造资源感知的分配策略,当有紧急订单发生时,每道加单的工序都可以被分配到最优的机器上。并且因为每一时刻只有两道工序被分配到最优的机器上,所以伴随着紧急加单量和机器数的增加,调度问题的复杂性不会变化。又因为工序的分配是实时状态信息驱动的,故此分配策略可以尽可能地消除在传统的分配策略中发生的当有大量加单时对原调度计划的影响。

2 基于博弈论的紧急加单下柔性作业车间动态调度模型

柔性作业车间动态调度问题描述为:有n个工件{O1,O2,…,On}在 m 台机器{m1,m2,…,mm}上加工,每个工件Oi有ni道工序组成,工件的每道工序可由m台机器中的多台机器加工,Mij表示可以加工工件i的第 j道工序的机器集合,Mij{1,2,…,M},工序 Oij可使用Mij中的任一机器加工,加工时间随所选择机器的不同而不同[10]。然而,工件在生产过程中常常存在一些突发事件,如紧急加单等。因此,本文正是基于上述问题,为紧急加单的每道工序选择合适的机器,并确定每台机器上各紧急加单工序的最佳加工顺序和开工时间,使生产调度系统快速性和稳定性达到最优。为了研究的可操作性,给出如下假设:

(1)每台机器在任何时刻最多加工一道工序。

(2)每道工序在一个时刻只能在一台机器上加工。

(3)所有的工件必须按照一个给定的顺序加工。

(4)紧急加单中的工序具有加工的优先权。

为了建立数学模型,对一些符号和变量定义如表1所示。

表1 符号和变量定义

2.1 博弈模型建立

在柔性作业车间动态调度中,当有紧急加单进行重调度时,调度系统的快速性和稳定性是两个考虑较多的性能指标。但是这两个指标在一般情况下是相互矛盾的,不能同时满足。也就是说当其中一个指标达到最优时,另外一个指标可能变坏。因此,如何在车间动态调度过程中安排工序,使得调度结果的快速性和稳定性达到满意的效果需要进行深入研究。本文从博弈论的角度出发,建立了基于非合作博弈的调度模型,如图2所示。

在建立模型之前,首先要确定模型的3个基本元素:参与者、决策集以及收益函数。调度模型可以用以下三元组表示:

N是参与者的集合。就本文而言,因为待调度任务池中的工序是变化的,故该博弈分为K个阶段。在每个阶段的博弈中,将待调度任务池中的工序作为参与者,每个参与者都能够独立做出决策而不相互影响。因此该模型是一个完全信息下两人的非合作博弈模型。则在第k个博弈阶段,参与者集合描述如下:

在两人博弈中,按照每个参与者可采取的策略,收益函数可以写成一个大小为q1×q2的矩阵,如式(5)所示:

2.2 求解博弈模型

本文针对两人博弈的特点,给出了基于双矩阵的Nash均衡点求解方法。

对于任意的策略组合(αi,βj),记收益函数 U1(αi,βj)=aij,U2(αi,βj)=bij,则两个局中人的收益函数分别记为矩阵A和矩阵B:

以上两个矩阵,也可记为:

算法总体思想:

(1)对局中人 1,在矩阵(aij,bij)m×n的每一行 i中,找出对方支付矩阵B中该行的最大元素,即=max{bij|j=1,2,…,n}并记录。当不唯一时,均记录;

(2)对局中人 2,在矩阵(aij,bij)m×n的每一列 j中,找出对方支付矩阵A中该列的最大元素,即=max{aij|i=1,2,…,m}并记录。当不唯一时,均记录。

(3)如果存在一对(i*,j*),使得两元素和都被记录,则()是纯策略纳什均衡。

(4)对不存在满足(3)的数对(i*,j*),则该博弈无纯策略纳什均衡。

因为在此博弈模型下,无法保证纯策略Nash均衡点的个数:可能没有纯策略Nash均衡点或者存在多个Nash均衡点,故局中人无法知道采取何种行动。为了克服纯策略所带来的缺陷,本文提出了近似Nash均衡解的概念。近似合作Nash均衡解的概念如下:

设(aij,bij)为两个机器的收益值,满足下式的解为近似Nash均衡解:

基于上述定义,在多个Nash均衡解或无Nash均衡解的情况下,近似Nash均衡解的求解方法如下:

(1)如果算法1的输出是空值,则计算支付矩阵下每种策略[||+||]的值。

(2)按照式(6)获取CNE。如果此时CNE超过一个,则随机选取一个。

(3)如果算法1输出的Nash均衡点超过1个,则将这些Nash均衡点按照公式(6)进行计算。

(4)选取最合适的Nash均衡点。

3 动态调度策略

目前求解紧急加单下的柔性动态调度问题一般采用预测—反应式调度的方法。该方法分为两个阶段:预调度和重调度。在预调度阶段,调度考虑未来紧急加单的影响,通常是在每道工序之前插入一定长度的空闲时间,然后生成预调度;在紧急加单发生之前,所有工件按照预调度的结果进行加工。一旦出现紧急加单,则采用右移[11]、更改路径[12]或者完全重调度[13]的方法。鉴于此,本文基于预测—反应式调度,并且采用右移重调度方法,给出了一种基于博弈的紧急加单下柔性作业车间动态调度的策略,如图3所示。

3.1 调度任务池

在本文中,将调度的任务池分为订单任务池、待调度任务池和已调度任务池。订单任务池中存放着紧急订单的工序;待调度任务池放着需要进行调度的工序;已调度任务池则放着已经调度完的工序。初始时刻,按新进订单的交货期的先后排列,依次将每两个订单的第一道工序放入到待调度任务池中进行调度,直到所有订单的第一道工序分配完成;每当有两道工序加工完成后,则将这两道工序的下一道工序放入待调度任务池中进行调度;分配完成后的工序就转入已调度任务池中。

3.2 再调度策略

在原有生产调度执行过程中,当有紧急加单时,选取离交货期最近的两个订单的第一道工序Oi1和Oj1放入调度任务池中,进而进行机床匹配,则具有加工Oi1的机器集为{mi,mj,…,mk},具有加工 Oj1的机器集为{mo,mp,…,mq},其中{mi,mj,…,mk}∩{mo,mp,…,mq}可能为空集,也可能不为空集。然后工序Oi1和Oj1根据系统的快速性和稳定性指标进行博弈,将工序Oi1和Oj1分配到相应的机器,并根据右移重调度方法将工序Oi1和Oj1插入到原调度中生成新的调度计划。最后将工序Oi1和Oj1放入已调度任务池中。同理可将每个订单的第一道工序分配到最优的机器上。若出现订单数为奇数时,则最后一个新进订单的第一道工序加入到第二道工序的分配中去,并且第一道工序具有优选分配权。

若工序Og1和Oh1首先完成,则将工序Og2和Oh2加入到调度任务池中并进行机床匹配。通过博弈选取最优的机床并将按右移重调度方法将工序插入到调度计划中。每当有两个新进订单的工序加工完成时,则将这两道工序的下一道工序通过博弈的方法进行分配并插入到调度计划中,直到所有新进订单的工序分配完成。若新进订单的总工序数为奇数时,则最后一道工序不参与博弈,直接通过穷举法来选择最优的机床。按照上述流程,当所有新进订单的工序都加入到调度计划中,则动态调度结束。

本文研究的在紧急加单的柔性车间动态调度问题中,由第一阶段博弈生成的调度计划可看作原调度的重调度。而当前的重调度又可以看作是下一次重调度的预调度,同时产生新的重调度,以此类推。

4 仿真与分析

本文以某制造业加工车间为例,将生产数据进行了简化,设计了一个由6个工件,每个工件有3道工序,一共有6台机器完成加工任务的仿真实例。具体的任务信息如表2所示。其中J1~J6表示初始时刻的加工任务。J7和J8表示在t=12时刻的紧急加单任务。表中的数据(x,y)表示工序在机器上的加工时间为x,准备时间为y。图4给出了没有紧急加单情况下的预调度甘特图,采用本文给出的模型及其算法,动态调度甘特图如图5所示。

在t=12时刻,将J7和J8的第一道工序放入待调度任务池中,则可加工 O71的机器集为{M1,M2,M3},可加工 O81的机器集为{M4,M5,M6},并使 O71代表系统的快速性指标,O81代表系统的稳定性指标。通过博弈的方法将O71和O81分别分配给机器M3和M5,并插入到原有调度计划中,此时O43发生右移。同理,当O71和O81完成后,将 O71和 O81放入已完工任务池,将O72和O82放入待调度任务池中进行调度,并将O72和O82插入到第一阶段生成的调度计划中,此时O13的开始时间由原来的t=21变为t=24。通过上述方法,最终将O73和O83插入第二阶段生成的调度计划中,得到最终的动态调度结果。

表2 任务信息

为了说明本文提出方法的有效性,将提出的动态调度方法与现存的动态调度方法进行比较,例如用Fang[14]等提出的遗传周期性调度方法进行重调度,结果如图6所示。虽然Makespan和基于博弈的动态调度结果相同,但是每台机器的加工序列发生了变化,因此其使调度系统的稳定性性能下降。故当有紧急加单时,和现有的动态调度算法相比,本文的方法能够获得更优化的解。

5 结语

本文运用博弈的方法解决紧急加单下柔性车间动态调度问题,并通过仿真实验证明了本文提出博弈论在车间动态调度中的可行性。目前,对于车间动态调度中异常事件处理的研究主要集中在机器故障下的动态调度问题,对于紧急加单下的异常事件研究很少。

后续研究的主要方面有:(1)优化模型,添加模型中未考虑的某些因素,如绿色生产中需要考虑的碳排放等。(2)研究多种异常事件同时发生时的重调度问题,如紧急加单和机器故障同时发生等。

猜你喜欢

工序柔性车间
一种柔性抛光打磨头设计
品种钢的工序计划优化模式分析
120t转炉降低工序能耗生产实践
灌注式半柔性路面研究进展(1)——半柔性混合料组成设计
100MW光伏车间自动化改造方案设计
高校学生管理工作中柔性管理模式应用探索
大理石大板生产修补工序详解(二)
土建工程中关键工序的技术质量控制
招工啦
“扶贫车间”拔穷根