2. 普渡大学印第安纳波利斯分校 工程技术学院,印第安纳波利斯 46202;
3. 辽宁轻工职业学院 机电工程系,辽宁 大连 116110
2. School of Engineering and Technology, Indiana University Purdue University Indianapolis, Indianapolis 46202, USA;
3. Department of Mechanical Engnieering, Liaoning Uocational College Light Industry, Dalian 116110, China
包装印刷设备行业属离散制造业, 典型的生产模式是多品种、小批量和定制化.目前行业内以中小规模企业居多, 企业对于生产过程中的波动性应对不足, 加工车间和装配车间缺乏必要的信息沟通, 当处于生产高峰时, 装配过程常因缺少必要的组件而中断, 拖期交货时常发生, 导致成本增加.本文旨在利用多agent技术, 在自主开发的生产管理系统上解决拖期问题.
agent-based modelling and simulation (ABMS)技术, 在动态大规模复杂系统仿真及应急行为观察方面的重要价值, 获得了各学科众多领域的广泛认同[1].多agent系统的分布式特点能将复杂的问题分解成多个简单的子问题分布求解, 利用其智能性可以很好地适应当前制造系统对于柔性、敏捷性和重构能力的需要, 在制造企业协作、生产计划与调度、车间层控制等方面获得了广泛应用[2].
对于半导体晶元探测中心的混合单元化制造系统, Kim等[3]将multi-agent system (MAS)应用于车间级探测单元间及单元内的实时调度, 4种设定情景下的仿真表明, 单元间调度agent和单元内调度agent借助两个启发式规则, 最早完工时间规则和最高效率规则, 能够缩短探测周期, 高效利用资源, 但其局限是未考虑单元间的动态优化重组, 不完全适用于资源受限的中小企业.鉴于制造环境分散和动态的特点, Wang等[4]集成射频标签技术和MAS技术开发了生产计划与控制系统, 借助于制造部件和资源设备的射频标签提供的实时信息, 该系统能够实现生产过程的可视化和可追溯, 响应性和柔性也因三模块中各agent的自治和协同而优于层级式排产.射频标签使用成本高, 不适用于大规模零件级加工过程的管理, 现阶段还无法在对成本很敏感的中小规模企业推广使用.
针对模具行业生产过程随机性强、各信息系统异构的现状, Liu等[5]应用MAS技术, 基于状态演进(部件在设备间的加工流转过程)的随机模型, 给出资源不确定情况下交货期配额在4类订单中的分配决策方案, 以签约阶段订单管理能力的提高来减少拖期现象.方案侧重于对交货期概率分布的分析预测, 若要解决生产中的拖期还需与实时调度相结合.
对于半导体检测调度中的典型例子, Wang等[6]提出了基于知识库的多智能体进化求解算法, 将可行解封装为agent, 进化迭代中运用了互助和竞争机制.与其他文献方法进行比较, 该文中的算法在保证解的多样性和避免早熟等方面的表现更佳.因进化算法自身的局限, 此算法在复杂大规模实际排产中还无法直接应用.王越等[7]采用对象过程建模语言OPM对MAS进行建模, 重在提高模型的表意能力, 并应用于钢铁企业的生产调度.
虽然学术界和工业界对基于MAS的排产调度进行了大量的研究和应用, 但已有方法在通用性方面依然有限, 几乎每个MAS系统的开发都是个案[8].为此, 本文依托地区合作企业, 中小规模包装印刷设备制造厂, 研究面向装配的多agent车间排产优化模型, 以解决拖期问题, 提升企业竞争力.
首先, 为保证生产连续按期交付订单产品, 排产约束中不只考虑加工工艺的约束, 还考虑装配工艺的约束, 即基于各订单产品的交货期将装配工艺约束转化为各部装及其子部装的交货期, 为任务排序和合批处理等提供依据, 当受加工工艺约束而出现拖期时, 以加班和外包来优先保证各部装交货期; 其次, 鉴于大规模排产是non-deterministic polynomial (NP)难题, 无法直接应用优化算法在多项式表示的时间内给出满意解, 借助兼具自治和协同能力的agent, 构建与3个排产周期(季/月、周和日)相对应的三层框架模型.运用规则逐层降低问题规模, 直至可用优化算法寻优, 再依优化结果递次向上更新, 即以任务分解和归并更新的策略迭代优化, 直至拖期问题得到解决, 即拖期代价与外包费用持平.本文重点阐述此三层排产框架模型中agent的交互机制及其在排产过程中的运用.
文献[7]给出的OPM/MAS模型在逻辑上实现了与钢铁制造工艺流程的吻合, 但未见清晰的寻优过程.文献[9]对于制造过程的大规模排产也给出了三层递阶结构, 以最优瓶颈设备利用率为目标进行迭代优化.相较而言, 本文所采用的三层框架因结合了多agent分布结构, 在一定程度上可使系统更具敏捷性.文献[9]在优化时假设资源是不受限的, 这仅对所分析的案例即大型企业适用, 难以应用于中小规模企业.本文针对更具代表性的有限资源情景, 采用动态重组解决瓶颈资源需求冲突, 并保持设备负荷的均衡.
1 基于多agent的三层排产框架模型本文所研究的排产和调度主要面向季度任务(此类企业通常按季度管理订单), 其特点是数据规模大、影响因素众多, 任何单一的优化算法都难以直接采用.为此, 结合MAS的分层递阶结构和分布式控制, 提出如图 1所示的基于agent的三层排产框架.根据产品工艺结构, 按任务产能匹配原则, 季度任务分解为月任务、周任务和日任务, 基于规则和算法优化排产, 再依结果迭代更新, 直至订单拖期最小化, 或拖期代价(拖期罚金与额外的仓储费用之和)与外包费用持平, 即获得全局近优解.
这种自顶向下分解和自底向上更新的策略, 不仅有利于生产计划的快速制定, 还能依据对计划执行情况的监控进行周期性调整, 及突发情况下(如订单变化、机器故障和人员变化等)的事件驱动性调整, 即基于agent构建的三层框架能够同时解决排产和调度问题.计划执行情况在每道工序的质检环节, 经对质检数据的采集和分析进行监控; 资源管理模块负责对设备和人员的异常情况进行告警.
所开发的生产管理系统利用此三层排产框架对车间生产实时监控及调度控制, 其中任务逐级分解和周期计划更新都依赖于每个agent的自治、同一层agent之间的交互和不同层agent之间的协商.
如图 1所示, agent的组建采用混合法[2], 即将物理实体映射为具有反应型结构的实体agent, 如订单agent (OA)、产品agent (PA)、任务agent (TA)和设备agent (MA)、制造单元agent (MUA)等, 而系统级功能模块则被封装为慎思型功能agent, 即调度agent (SA)和资源agent (RA).
文献[7]中指出, 借助OPM/MAS的模型元素mobilizing, agent的角色在运行时可转换, 交互关系可改变, 本文中各agent因与物理实体或功能模块一一对应而不必转换, 彼此采用信息传递进行交互, 所用语言为knowledge query and manipulation language (KQML)[10], 如图 2所示.
为减轻每个agent的信息存储和传递的负荷, 采用统一的数据库管理相关数据, 如订单信息、产品结构信息和资源信息等, 而agent的知识库只需存储相应的数据库地址.当功能agent (FA)的感知器接收到从物理实体agent (PEA)的执行器发来的任务执行(perform)指令时, 如排产或资源分派, FA的分析器和决策器将基于自有的规则库和知识库给予处理; 所需数据经数据库访问来获取, 同时依处理结果更新对应数据; 再由FA的执行器告知(tell) PEA的感知器发生了什么, 访问数据库的哪个地址以获得所期待的结果.
1.1 基于ATC规则的季/月任务排产季度排产中, 需解决的问题是订单产品加工次序的确定, 并分解为各月度任务.订单OA的感知器首先感受到制造任务的下达; 然后计算求解各订单的权重, 这里采用层次分析法(analytic hierarchy process, AHP)[11], 依据交货期的紧迫度、客户重要性来确定权重, 加权订单经与PA交互分解为加权产品; 最后, 决策器允许OA的执行器向SA的感知器发送对加权产品排序的指令.
指令接收后, SA规则库中的优选规则apparent tardiness cost (ATC)[12]将发挥作用, 即通过排序指数(processing sequence index, PSI)的计算迭代进行加权产品的排序, 每次只选未排产品中PSI最大者为当前待加工产品, 直至所有产品都被选取. ATC规则采用贪婪启发的思想, 继承weighted shortest processing time (WSPT)和minimum slack (MS)规则优点的同时, 通过参数化方法使其发展为兼具前瞻性特质的动态规则, 以最小化加权拖期代价为性能指标时可获得近最优排产解, 且在各种任务负荷下都表现出较好的鲁棒性.
当前时刻t各产品排序指数Ij(t)由产品权重、加工时间和交货期计算而得, 表示为
(1) |
(2) |
(3) |
按指数折算交货期松弛度(slack)对最大加权拖期代价wj/pj的影响, 其中wj、dj、pj分别是N个待排产品中第j个产品的权重(AHP方法确定)、交货期和加工时间; 规则的前瞻性特质由KP体现, P为未排产品的平均加工时间; 当交货期符合一致分布时, 比例参数K可依式(2)确定, 即只考虑交货期范围因子R (由最大、最小交货期Dmax、Dmin和预计最大完工时间Cmax按式(3)确定), 忽略紧度因子τ的影响[13].
依据ATC规则求解确定加权产品的排序, 并由此构成季度计划, 再按照任务工时与产能匹配规则(task-capacity-matching, TCM), 将其分解为月任务.在知识库的支持下, SA与PA交互, 再由执行器将部装级月任务发送给月任务agents (MTA).同时, 季度订单的总拖期时间计算如下:
(4) |
其中: T为季度内M个订单总拖期时间, Ti、Ci、Di分别为第i个订单的预计拖期时间、完工时间和交货期.
通常, 包装印刷设备的部装和零件具有很高的相似性.如凹印机的色组数虽是定制化的, 但某一型号的各色组部装却是相同的, 因此可利用合批规则简化部装级和零件级排产[14].各部装和零件的交货期在装配工艺约束下按倒排规则由产品交货期来确定, 在交货期一致的前提下, 各月任务队列中相同部装将被合批, 合批后同一批次部装的加工优先权等于其中的最高值.相较而言, 相同零件的合批时间段的选取则要复杂一些, 在周任务排产中将重点介绍.部装合批后的月计划按TCM规则向下分解为各周任务, 并由各周任务agents (WTA)感知.
1.2 基于零件合批规则的周任务排产各WTA接收任务后, 如图 1所示, 需与PA、SA、RA及MUA交互以完成合批处理及向各MUA的任务分派, 即周任务排产, 并进一步分解为各日任务.其中, 零件合批有利于节省工序之间的准备时间和相应的物流成本, 但因工艺约束, 合批量过大又易导致设备空闲和资源(设备和人员)利用率的降低, 对车间的均衡生产造成影响.考虑到合批量的大小取决于合批时间段, 在运用零件合批part batching (PB)规则时, 就要特别关注一周内时间段的选择, 在获得可行解的同时节省成本.
由车间现场调研可知, 周计划拖期若超过各周的加班限额9小时(3×3加班模式)则为不可行排产.为此, 在保证周计划可行的前提下, 应使所选时间段内的合批量最大, 即最大化合批时间段.按经验, 合批时间段应为整数天, 即下限为1天, 上限为6天.换言之, 时间段集合只有6个元素.为简化优选求解过程, 采用PB规则时可根据任务特点, 从大到小遍历选取集合元素, 直至获得当月可行的周计划解.
另外, 任务中常常包含大工时零件, 即有1~3道工时大于50的工序, 从而总工时大于100.据现场统计, 此类零件数量约占5 %, 因工艺约束, 平均加工周期为1~2周.本文按照longest processing time (LPT)[15]规则, 对周计划中大工时零件进行优先级调高, 而小工时零件(总工时小于100)的保持不变.
PB规则和LPT规则的运用, 即WTA与SA及PA的交互合作, 可初步确定月内的各周计划. WTA再基于TCM规则, 与RA及MUA交互, 将各周计划的任务队列分割为与制造单元(manufacturing units, MU)数量相当的任务段, 并分派给各MU; 接着, 在各MU内将任务段进一步分解为工序级的日任务, 并告知给日任务agent (DTA).
1.3 基于GA和MU动态重组的日任务排产第三层的日排产需完成更有效的优化, 为自底向上的计划更新提供基础.因各MU内日排产的任务量规模相对较小, 可应用遗传算法(genetic algorithm, GA)来优化求解, 目标是最小化日任务的最大完工时间.采用基于工序的编码方案时, 染色体由任务工序次序和所分配的设备来组成, 初始种群随机生成.每次迭代进化时, 在选择步骤采用轮盘赌方法, 而交叉算子选为precedence operation crossover (POX), 迭代终止条件由加工周期的变化情况, 或代数上限来决定.
一般地, 主动调度解集常常比所有可行解集小很多, 且包含的调度解子集中必然有最优解集[16].鉴于此, 为获得主动调度解, 在GA算法的解码环节运用插入式贪婪解码算法[17], 使任务在最早的可行时间分派给设备.
然而, 实际中却有可能所需设备并没有可用时间段来排产某工序, 这主要是两个原因导致的.一是设备属于瓶颈类设备, 只能在DTA提出需求时在加工所需时间段内将其隶属于对应的MU, 而当需求存在冲突时由RA负责仲裁, 此过程需RA与MA和MUA协商完成; 另一是设备负荷过重, 虽然依据TCM规则MU的产能总工时与所分派的日任务是匹配的, 但因工艺约束, MU内会出现某设备空闲而另一则超负荷.对此, RA将负责评估其他MU的同类设备或具备该工序加工能力的设备能否暂时归属此MU.
文献[9]的上层长周期排产以优化瓶颈设备利用率为目标, 在中层短周期排产时则假设其他设备产能为无穷大, 即以外包或加班弥补产能之不足.相比于文献[9]所研究的大型国有企业, 包装印刷制造业的中小企业对外包和加班费用的敏感却不可忽视.本文借助agent的协商机制给出资源动态重组方案, 可同时解决瓶颈设备的需求冲突和设备空闲时段的分布调控.与尹翔和卢少磊等分别在文献[18]和文献[19]中给出的agent联盟形成机制相比, 在相近规模的重组中, 本文不仅同时考虑了加工任务需求和设备agent自身能力, 更兼顾了加工装配工艺约束下资源负荷均衡的目标.
在MU的动态重组dynamic reconfiguration (DR)求解过程中, RA要借助shortest processing time (SPT)和least work in next queue (WINQ)的组合规则SPT/ WINQ进行仲裁评判[20].其中, WINQ规则[21]是以均衡设备负荷为导向的分派规则, 其理念是虽然设备的总空闲时间不受优选规则的影响, 但空闲时间的分布是可以调控的, 从而控制制造周期.在设备分配时考虑的是未排任务队列中相同零件同一工序工时的总合, 最小者将优先获得可用设备; 而SPT规则作为工序排序的常用规则, 在设备利用率方面也表现优越.此组合规则同时考虑了待排任务量总和和当前任务加工时间, 并允许加权系数根据当前车间资源均衡情况而动态调整, 从而使其在GA的解码环节, 保证资源利用率的同时缩短加工周期.
2 基于三层排产框架的车间排产仿真为验证本文所提排产框架模型的有效性, 以合作企业, 汕头市华鹰软包装设备总厂有限公司, 2013年二季度的凹印机订单数据为例, 在自主开发的生产管理系统上进行排产仿真.系统在微软Visual Studio 2010环境下采用C语言开发, 数据库由微软Access 2000建立, 查询语句是SQL.因现有文献算法还无法直接应用于此实际排产, 这里仅将仿真结果与调度员凭经验的调度结果相比较.
二季度订单有4个, 包含10台客户定制的凹印机, 其中订单1和订单2允许的最大拖期为7天, 订单3和订单4不允许拖期; 10台凹印机包含的非标零件约4.5万, 所需工时约63万; 车间现有设备49台, 季度产能工时约85万, 考虑工艺约束, 产能平均利用率约70 %, 即有效产能约60万工时.
粗略而言, 任务总工时超产能9 %, 季度订单会出现拖期.实际中由调度员人工调控生产, 企业确实因超出允许的拖期上限一周交货而被罚.具体情况是主轴箱零件的加工不及时延误了装配过程.相较于此, 生产管理系统所采用的三层排产框架的良好性能将在如下的仿真中给予说明.
在第1层, 采用ATC规则所得的季度计划, 即有加工次序的订单产品序列如图 3所示, 另表 1中列出了OA各内部状态的具体值.可见, 因订单1的严重拖期, 总拖期时间TTT超出允许上限3天.虽然拖期现象未能避免, 但此结果比人工调度的略好些, 这要归功于性能较佳的优选规则ATC规则的运用.
第2层中, 零件的合批使排产规模得到了进一步降低.当合批时间段选为最大值6天时, 季度内仅有6月合批后的各周计划是可行的; 接下来减为5天, 5月的各周计划也可行了, 只有4月的还不可行; 最后, 如图 4所示, 4月的各周合批时间段需降至3天, 此时前两周的最大合批量可达116.
然而, 从表 2的数据可知, 周排产使TTT达到了最恶劣情况, 即18.625天, 严重超期, 除订单1外, 订单3和订单4也发生了延误.究其原因主要是依TCM规则分解任务时并未考虑加工和装配工艺的约束, 因约束而必然存在的设备空闲被忽略了, 所以计划完工时间就被延长了, 且产能利用率也被降低至67.5 %.值得注意的是, TCM规则也是人工调度中主要采用的规则之一, 而正是这个原因使拖期问题更难以控制.
日排产中采用GA算法优化可以一定程度地减轻TCM规则引发的拖期更长和低利用率的问题.为了使解具有多样性, 随机生成的初始种群规模为100, 选择步骤采用轮盘赌的方法, POX交叉概率设为0.8, 变异概率为0.1.当连续两次迭代后加工周期都没有再减少, 或代数达到20时, 终止进化过程.为均衡设备负荷, 在解码环节采取的MU动态重组可对设备空闲时间段重新组合, 从而将资源利用率提高到73 %.
除独立的加工中心自身即是一个MU外, 一般每个MU包含2 ~ 4种加工设备, 每种包含1 ~ 4台同类设备.对于龙、刨和割等非常用工序, 加工设备数量有限, 这类瓶颈设备由RA采用SPT / WINQ规则在工序加工时间段内分派给提出需求的某MU; 而车、钳、铣、镗、磨和钣金等常用工序的设备数量略充足, 当一个MU内某工序负荷过重时, 也能够通过RA、MA和MUA的交互将其他单元的同类设备暂时归属于此单元, 实现按需在各MU间的设备共享.运用SPT / WINQ规则时, 以设备负荷量相差在5 % ~ 10 %以内作为均衡生产的衡量标准.
在二季度排产例子中, 自底向上的更新一般不需超过20次就可达到如表 3所示的结果, 仅订单1尚有拖期, 且拖期被控制在允许范围内, 而其他订单均提前完成, 总拖期时间减少至上限以下. 表 3中完工时间的值为负数时, 代表提前完工.
为了解决包装印刷设备制造产业中小规模企业的拖期成本问题, 本文针对车间排产的大规模优化难题, 以装配工艺为导向, 提出了基于多agent技术的三层排产框架模型, 将复杂的排产问题逐层分解以适应于优化算法.基于agent的自治和协商机制, 在各层对应建立了产品/部装、零件和工序级的排产模型, 运用规则及算法进行优化.采用合作企业凹印机订单历史数据进行仿真, 验证了该模型为企业的拖期罚金问题提供了一个有效的解决途径.基于此框架模型所开发的生产管理系统, 在合作企业上线试运行期间曾使拖期问题大大缓解.针对该模型也能适应动态调度的特点, 在下一步的研究中, 将重点分析基于事件驱动调度的模式识别及在线更新, 使系统更加智能和敏捷.
[1] |
Abar S, Theodoropoulos G K, Lemarinier P, et al. Agent based modelling and simulation tools:A review of the state-of-art software[J]. Computer Science Review, 2017, 24(1): 13-33. DOI:10.1016/j.cosrev.2017.03.001 |
[2] |
Shen W, Hao Q, Yoon H J, et al. Applications of agent-based systems in intelligent manufacturing:An updated review[J]. Advanced Engineering Informatics, 2006, 20(4): 415-431. DOI:10.1016/j.aei.2006.05.004 |
[3] |
Kim J, Chung S Y, Yoon H J. Multi-agent-based scheduling methods for hybrid cellular production lines in semiconductor industry[J]. Proceedings of the Institution of Mechanical Engineers Part B-Journal of Engineering Manufacture, 2014, 228(12): 1701-1712. DOI:10.1177/0954405413518517 |
[4] |
Wang L C, Lin S K. A multi-agent based agile manufacturing planning and control system[J]. Computer & Industrial Engineering, 2009, 57(2): 620-640. DOI:10.1016/j.cie.2009.05.015 |
[5] |
Liu J J, Chen Q X, Mao N, et al. A multi-agent-based mould due date setting approach in stochastic production[J]. International Journal of Production Research, 2011, 49(5): 1353-1371. DOI:10.1080/00207543.2010.518737 |
[6] |
Wang S Y, Wang L. A knowledge-based multi-agent evolutionary algorithm for semiconductor final testing scheduling problem[J]. Knowledge-Based Systems, 2015, 84: 1-9. DOI:10.1016/j.knosys.2015.03.024 |
[7] |
王越, 苏宏业, 沈清泓, 等. 基于OPM/MAS的钢铁企业多agent生产调度模型[J]. 控制与决策, 2014, 29(11): 1927-1934. (Wang Y, Su H Y, Shen Q H, et al. Multi-agent production scheduling model of steel enterprise based on OPM/MAS[J]. Control and Decision, 2014, 29(11): 1927-1934.) |
[8] |
Giret A, Trentesaux D, Salido M A, et al. A holonic multi-agent methodology to design sustainable intelligent manufacturing control systems[J]. Journal of Cleaner Production, 2017, 167: 1370-1386. DOI:10.1016/j.jclepro.2017.03.079 |
[9] |
Wang G L, Lin L, Zhong S S. Task-oriented hierarchical planning and scheduling for discrete manufacturing enterprise[J]. Applied Mechanics and Materials, 2008, 10/11/12: 114-120. |
[10] |
Finin T, Frtizon R, Mckay D, et al.KQML-A language and protocol for knowledge and information exchange[R].AAAI Technical Report WS 94-02, 1994.
|
[11] |
Saaty T L. The analytic hierarchy process[M]. New York: McGraw-Hill International Book Company, 1980: 11-25.
|
[12] |
Vepsalainen A P J, Morton T E. Priority rules for job shops with weighted tardiness costs[J]. Management Science, 1987, 33(8): 1035-1047. DOI:10.1287/mnsc.33.8.1035 |
[13] |
Lee Y H, Bhaskaran K, Pinedo M. A heuristic to minimize the total weighted tardiness with sequence-dependent setups[J]. IIE Transactions, 1997, 29(1): 45-52. DOI:10.1080/07408179708966311 |
[14] |
Wang Y H.Research on the floor shop planning and scheduling for the small-and-medium-sized discrete manufacturing industry[D].Shantou: College of Engineering, Shantou University, 2015: 36-38.
|
[15] |
Pinedo M. Scheduling:Theory, algorithms, and systems[M]. 3rd ed.New York: Springer Science+Business Media, 2008: 414-417.
|
[16] |
Giffler B, Thompson G L. Algorithms for solving production-scheduling problems[J]. Operations Research, 1960, 8(4): 487-503. DOI:10.1287/opre.8.4.487 |
[17] |
Zhu C J, Cao J, Hang Y, et al. Applying genetic local search algorithm to solve the job-shop scheduling problem[J]. International Journal of Industrial Engineering Theory Applications and Practice, 2012, 19(9): 341-349. |
[18] |
尹翔, 李斌, 于萌. 一种多agent网络中的分布式联盟形成算法[J]. 控制与决策, 2015, 30(3): 536-540. (Yin X, Li B, Yu M. Distributed coalition formation algorithm in multi-agent network[J]. Control and Decision, 2015, 30(3): 536-540.) |
[19] |
卢少磊, 方浩. 一种改进的多agent分布式联盟形成算法[J]. 控制与决策, 2017, 32(4): 632-636. (Lu S L, Fang H. An improved distributed coalition formation algorithm in MAS[J]. Control and Decision, 2017, 32(4): 632-636.) |
[20] |
Pereira A. FMS performance under balancing machine workload and minimizing part movement rules[J]. International Journal of Simulation Modelling, 2011, 10(2): 91-103. |
[21] |
Conway R W.An experimental investigation of priority assignment in a job shop[R].Santa Monica: Rand Corporation, 1964.
|