基于改进定向搜索算法的作业车间瓶颈控制研究

,

(浙江工业大学 工业工程研究所，浙江 杭州 310014)

随着市场经济的发展，使得企业生产受到越来越多不确定性因素的影响，如订单需求的减少、产品生命周期的缩短、生产异常等.这些不确定因素导致了生产过程的不稳定，形成了生产瓶颈，如何在这种复杂多变的制造环境下对作业车间瓶颈进行控制，已经成为当前车间控制技术研究的一个重点[1-2].近年来，有很多学者对其进行了不同方向的探索，文献[3]以设备利用率最大为生产物流瓶颈定义，同时在采用工艺路径和工序分割的方法基础上，应用遗传算法对生产系统进行排程.文献[4]利用改进的微粒群算法构建一个加权工期和最小的初始调度计划，并基于关键链管理方法对初始调度计划进行合理地缓冲设置，消除了车间内瓶颈的影响.文献[5-6]采用启发式规则和遗传算法相结合的方法对车间进行了重调度的研究.这些研究在车间重调度方面有很大的优势，但往往存在原调度方案破坏程度大，作业调整范围广的问题，并且在重调度中并未考虑设备完成任务的能力指标.在此基础上，以柔性作业车间为研究对象，采用改进的过滤定向搜索算法，以瓶颈产生触发重调度，可以最小程度影响原调度方案，大大降低重调度实施难度，具有重要研究意义.

1 作业车间瓶颈问题模型

为确定作业车间瓶颈，建立基于瓶颈的动态调度模型，需要对作业车间进行数学描述.对于一作业车间S，有n个作业在m台设备上加工，并且每个作业Ji有s道工序需要加工.令J为作业集合，并有J={Ji|0

选择以完工时间和设备利用率双目标因素作为优化目标，并进行以下符号定义：cijk为工件j的i工序在设备k上的完工时间；sijk为工件j的i工序在设备k上的开始加工时间；pijk为工件j的i工序在设备k上的加工时间；W为优化目标；Fm为完工时间目标因素；Fe为关键设备负荷因素；wm为完工时间目标因素加权值；we为关键设备负荷因素加权值.定义变量为

则作业车间瓶颈优化模型为

W=min(wmFm+weFe)

(1)

其中

(2)

(3)

s.t.wm+we=1

(4)

∑αijk=1,∀Mk∈Mij

(5)

sijk≥cljk，且i>l

(6)

sijk≥cghk，且βijghk=1

(7)

i,j,k,g,h,l≥1

(8)

式(4)表示了双约束的加权值和为1；式(5)表示了同一个工序只能在一台设备上加工；式(6)表示了每个工件中各工序的顺序约束；式(7)表示了每台设备中加工的各工序的顺序约束.

2 作业车间瓶颈的控制方法

2.1 作业车间瓶颈控制模型

为了描述作业车间瓶颈控制的动态特征，采用Petri网建模技术进行建模.黑色粗线表示变迁(transition)，以t表示，代表各个车间活动，圆圈表示库所(place)，以p表示，代表作业车间活动的状态.作业车间瓶颈控制模型见图1.

图1 作业车间瓶颈控制模型

2.2 作业车间瓶颈控制策略

当瓶颈产生时，会导致原有调度策略发生不可逆的破坏，并且随着设备数量、工件数量以及扰动影响工序数量的增加，作业车间的瓶颈问题模型会呈指数级增长，一般的车间管理办法无法解决，所以提出应用过滤定向搜索算法的基于不可预测瓶颈的控制策略.

2.2.1 算法描述

过滤定向搜索算法(Filtered-beam-search,FBS)是分支定界法的一种改进方法，其原理是对问题进行逐层搜索，并从搜索树中选取最有优势f(定向过滤宽度)个节点作为候选节点，其余节点在本层搜索中将永久删除，再从候选节点中选取b(定向搜索宽度)个节点(定向搜索节点)作为调度节点，其他没被选中的节点在本层搜索中也将被永久删除，最后以定向搜索节点为调度节点应用分支策略进行可调度节点分支，形成新的一层调度方案.为了能够从全局中搜索到定向搜索节点，需要引用局部评价函数(Local evaluation function)和全局评价函数(Global evaluation function).局部评价函数用来在可行节点中选取f个候选节点，而全局评价函数用来在f个候选节点中选取b个定向搜索节点.

2.2.2 算法设计

1) 分支策略.每一层的节点包含两方面的信息，一是该节点必须是该层可调度的节点，二是每个节点需确定加工设备和加工开始时间.为此，采用改进的可调度工序优先策略.作为分支策略.假设Dl是一个已经有l层的局部调度集合，Pl为第l层可调度工序集合，sij为工序Oij∈Dl的加工开始时间，有sij=s(i-1)j+p(i-1)jk.令时间TMijk为可加工工序Oij的机床Mk最早可使用时间，TM*=min{TMijk}，且Oij∈pl+1，Mk∈Mij则有TMijk∈TM*的工序Oijk形成集合O*，l+1层的可调度工序为O*∈pl+1，sijk=max(sij，TMijk).

2) 评价函数.为了在不可预测瓶颈的扰动下尽可能快的恢复生产，以及能够在多个选择中平衡资源负载，采用最小加工时间规则(Shortest processing time，SPT)[7]和机床负载平衡规则(Machine load balance，MLB)[8]双层调度规则作为全局评价函数，而为保证加工设备完成生产任务的可靠性，采用SPT、信用能力评价指标Ejt和MLB双层调度规则作为局部评价函数，即首先应用SPT和Ejt加权评价指标LE对节点进行局部评价，选取f个局部调度节点，若有大于f个节点，再应用MLB对剩下节点的选择进行过滤.为了对局部调度节点进行全局评价，首先应用SPT形成全局调度，选取b个定向搜索节点，若有大于b个节点，再应用MLB对剩下的节点进行第二次筛选.其公式为

LE=θSPTESPT+θEEjt+N

(9)

其中

(10)

ξk为该加工设备完成第k次任务的信用质量奖励因子；ρk为该加工设备完成第k次任务的信用质量惩罚因子，并且ρk>ξk，θSPT和θE为加权系数，且θSPT>0，θE<0，N为足够大的正数.

2.2.3 算法流程

图2为改进的过滤定向搜索算法流程，具体描述为：

Step1初始化算法，设定算法参数b，f，工序数q，调度层标识l，解数量标识m，以及瓶颈问题模型参数.

Step2应用分支策略生成子节点，确定pl初始值，节点数量n，并且层标识l+1.

Step3判断节点数是否大于定向搜索宽度b，若大于或等于执行下一步，若小于则返回上一步.

Step4为保证调度全局最优，首先对初始调度节点进行全局评价，并更新pl.

Step5可行解数量循环.可行解数量标识m+1，判断可行解的数量是否大于b，若是则执行Step11，若否执行下一步.

Step6调度层循环.调度层标识l+1，判断层标识是否大于工序数量，若是执行Step10，若否执行下一步.

Step7应用分支策略生成子节点，节点数量为n′.

Step8对节点进行局部评价，局部评价函数为LE.

Step9对局部调度节点进行全局评价，评价策略为SPT和MLB，并更新pl.

Step10形成调度解.

Step11对所有调度解计算目标函数W，选择最优解.

图2 过滤定向搜索算法流程

3 实例应用

3.1 实例选取

3.1.1 基本加工信息

为了验证瓶颈控制策略的有效性，选取了某千斤顶生产企业作为应用实例.该企业作业车间共有8台设备资源，分别为M1，M2，M3，…，M8，其自制件共有8种，分别为：J1,J2,J3,…，J8,每种工件有3—4个工序，每种工序可由不同的设备进行加工，属于较典型的离散型制造系统.表1工序加工时间和信用能力评价指标表，表2为各工件的交货期.

表1 工序加工时间和信用能力评价指标表1)

表2 工件交货期

3.1.2 初始调度

该企业根据内部生产计划生成作业车间初始调度方案，如图3所示.初始调度方案为静态调度，并未考虑系统中可能发生的动态事件.图中任务矩形标识格式为“工件-工序”，如图3中“3-1”表示了作业3的第一个工件O13.矩形下方为该任务的开始时间和结束时间.

图3 初始调度甘特图

3.1.3 动态事件

为了评价瓶颈控制策略对系统中动态事件的处理能力，选取在日常生产中发生频率较高的设备故障事件进行仿真，在时间t=5的时刻，设备M6发生故障，并在当前生产周期中无法恢复投产.

3.2 瓶颈控制策略验证及评价

根据企业历史数据，设置算法的参数值如表3所示.

表3 算法参数

采用2.2中提到控制策略进行重新调度.根据表3中的算法参数，进行过滤定向搜索算法计算，得出设备M6故障下的重调度甘特图，如图4所示.

图4 M6故障下的重调度甘特图

由瓶颈控制策略对动态事件的控制，可以得出初始调度、动态事件下的重调度完工时间对比结果，如表4所示，以及重调度设备负荷对比结果，如表5所示.

表4 重调度完工时间对比

表5 重调度设备负荷对比

由表4可知：在动态调度下的最大完工时间均为15，较扰动前增加了1 h，但并未超出各工件的交货期，可以接受.由表5可知：经过重调度设备负荷极差仅为5，具有较大幅度的提升.由此可见，在动态事件的影响下，瓶颈控制策略能够很好的处理作业车间中的扰动，具有有效性.

4 结 论

为了对作业车间瓶颈进行控制，并减少瓶颈对系统的影响，提出了基于改进的过滤定向搜索算法的离散车间瓶颈控制研究.结果表明：给出了作业车间瓶颈问题模型，以完工时间和设备利用率作为优化目标建立了目标函数；给出了作业车间瓶颈控制方法，建立了瓶颈控制模型，给出了基于改进的过滤定向搜索算法的瓶颈控制策略；进行了实例验证.选取某千斤顶生产企业作为实例，说明了基于改进的过滤定向搜索算法的瓶颈控制策略有效性.但研究中未考虑瓶颈对生产系统的影响程度，只对具有破坏性影响的瓶颈进行控制，还可以针对瓶颈的影响程度做进一步研究.

参考文献：

[1] JIN Feng, WU Cheng. Research status and prospects for massive production scheduling[J]. Computer Integrated Manufacturing Systems,2006,12(2):161-168．

[2] BASSETT M H, PEKNY J F, REKLAITIS G V. Decomposition techniques for the solution of large-scale scheduling problems[J].AIChE Journal,1996,42(12):3373-3387．

[3] 何文锦,鲁建厦,李修琳.基于生产物流瓶颈的生产排程研究[J].轻工机械,2013,2(1):101-110.

[4] 张沙清,陈新度,陈庆新,等.基于改进微粒群算法的模具多项目动态调度[J].计算机集成制造,2011,17(3):622-629.

[5] 肖志娇,常会友,衣杨.启发式规则与GA结合的优化方法求解工作流动态调度优化问题[J].计算机科学,2007,34(2):157-191.

[6] 魏英姿,谷侃锋.基于性能预测的遗传强化学习动态调度方法[J].系统仿真学报2010,22(12):2809-2820.

[7] 应晨,鲁建厦,汤洪涛.一种基于加工优先级的在制品控制方法[J].浙江工业大学学报,2012，40(6):679-684.

[8] 陆汉东,何卫平,周旭.基于禁忌搜索的柔性作业车间分批调度[J].上海交通大学学报,2012,46(12):2003-2008.

[9] 王世进,周炳海,奚立峰.基于过滤定向搜索的柔性制造系统动态调度优化[J].上海交通大学学报,2007(1):94-101.

[10] 黄卓平,鲁建厦,李修琳.基于延迟惩罚成本的生产物流瓶颈辨识研究[J].浙江工业大学学报,2012,40(5):57-573.

[11] 孔令革,鲁建厦,詹燕.基于排队网络的生产物流瓶颈转移研究[J].浙江工业大学学报,2011,39(6):644-647.