崔晓光, 蔡鸿明, 步丰林, 鲍升伟

(上海交通大学 软件学院, 上海 200240)

基于准时制的模具生产调度模型研究及应用

崔晓光, 蔡鸿明, 步丰林, 鲍升伟

(上海交通大学 软件学院, 上海 200240)

模具生产过程具有离散化定制的特点, 使得在质量和产量约束下的准时交货较为困难. 结合准时制与动态规划设计了一种多级调度算法及相关系统, 将调度问题从车间排产扩展到整个产品生产流程, 并从信息建模出发建立了各模型的关联关系, 以便更完全地分配企业生产资源, 均衡开展生产, 从而缩短订单的生产周期. 根据试验及初步应用验证, 系统可以有效解决企业的离散化定制产品的调度问题, 缩短订单的生产周期.

模具; 作业车间调度; 准时制; 动态规划; 智慧制造

轮毂模具制造是汽车制造的上游产业, 业内企业普遍面临车间生产调度效率低下以及拖期严重的问题. 这是由轮毂模具制造的特点决定的: 一是生产离散化, 模具是用来成型批量产品的工具, 以定制为主, 由多个零部件装配组成, 零件加工工艺的差异也非常大; 二是质量要求高, 模具对于原料、结构设计、加工精度等都有很高要求; 三是时间要求紧, 订单的延误会对客户造成很大损失. 车间调度一方面需要保证交期, 另一方面为了保证质量, 要尽可能地避免赶工. 因此, 在诸多目标和约束下, 实现高效调度很困难, 企业产量和质量受到限制, 往往影响企业的快速发展和能级提升.

目前在资源约束下调度的研究模型是作业车间调度问题(job-shop scheduling problem, JSSP), 相关算法可分为全局算法和动态规划算法. 全局算法主要有遗传算法、蚁群优化算法(ant colony optimization, ACO)、神经网络等. 遗传算法求解柔性JSSP的结果[1]比较好, 可以将设备故障率纳入到问题模型中[2]. 蚁群算法能够很好地寻求复杂问题的较优解, 可实现自我学习[3]; 也可从设备负载均衡角度解决调度问题[4], 平衡资源利用, 最大限度地挖掘产能. 对于时间要求比较严格的无等待流水车间调度问题, 蚁群算法也能给出非常好的结果[5]. 神经网络一般用于求解复杂的混合问题, 如将JSSP与增量资金方法糅合, 作为软件项目的研究模型[6]. 但目前神经网络算法对设备要求高, 在大多企业中无法应用. 动态规划方法是一种求解最优化问题的方法, 相比全局算法更容易实现, 也能够保证结果符合实际需求. 准时制(just in time, JIT)思想也被用于JSSP的解决[7]. 准时制是一种生产方式, 又被称为“零库存”, 其基本思想是尽可能后延生产, 保证在交货时完工, 避免货物堆积. 将其用在车间调度上, 可从理论上最大化资源利用, 且计算速度更快、结果更加稳定[8]. JIT一般与其他方法相结合来求解JSSP[9 - 10].

以上算法研究在自动化程度高的条件下较为有效, 但在模具这种具有高度定制化的离散化过程却很难保证时间进度要求. 因此, 本文从准时制算法出发, 将准时制与动态规划结合, 给出了一种生产调度算法, 能够很好地分配企业生产资源, 缩短订单的生产周期, 实现了相关调度系统并开展应用.

1 企业生产过程的信息建模

模具的生产过程从接单开始到交货结束. 接单有两种模式: 客户提供图纸和企业负责设计图纸. 接单后的生产过程可以分为设计、采购、加工3个阶段. 设计阶段主要是图纸设计. 一般模具要求完成3份图纸: 备料图纸、设计图纸、3D分模. 备料图纸规定模具原料规格和数目; 设计图纸主要是制定模具物料清单(bill of material, BOM), 给定各部分的加工要求, 工艺员据此为零件编制工艺路线; 3D分模主要为装配提供参考. 采购环节在备料图纸完成后开始. 图纸完成并且采购后, 产品就可以进入加工环节. 调度员将模具加入工作序列中, 安排车间工人加工. 所有零件完成后, 装配工进行装配、封箱, 完成最终交货. 信息建模的难点在于构建的模型对调度算法的支持. 根据产品特性和调度特点, 本文采用三级展开方式. 将订单映射到单个模具, 再根据BOM列出模具的零件列表, 最后为每个零件指定工艺路线. 通过工艺路线将产品与生产资源联系在一起. 图1给出了主要信息模型类图. 其中符号“1..*”“1”表示映射关系中的实体数目. 订单与客户之间的映射关系: 一个客户可以拥有多个订单, 一个订单只属于一个客户. 模具与零件之间的关系: 零件是模具的一部分, 多个零件聚合构成一个模具.

图1 信息模型图Fig.1 Diagram of information model

2 基于准时制的作业车间调度算法

2.1 问题描述

(1)

s. t.

(2)

(3)

(4)

2.2 算法设计

图2是算法的流程图. 基本思路: 在现有的设备资源下, 计算出一个零件的完成时间, 如果明显早于交货日期, 就不加入生产队列. 最终实现是将JIT与动态规划相结合, 具体方法是试排找到最紧迫的零件, 将最后一道工艺的完成时间设为交货日期, 做前序遍历, 将工艺安排合适的设备. 排产结果尽可能使每一个零件恰好在交货期时完成.

图2 算法流程图Fig.2 Flow diagram of algorithm

2.3 算法扩展

算法实现中需要考虑更多因素, 比较典型的有以下两个因素.

一是上游环节管控. 由于在图纸完成后, 不同部门人员之间沟通有延迟, 这可能会导致后续工作无法开展, 严重的会导致订单的遗漏. 这个问题通过将相关系统接入本系统解决. 系统自动获取状态更新, 并将信息展示给相关人员. 同时记录这个过程中的所有时间点及相关操作, 方便追责.

上述问题导致在排产时, 某些工艺的开始时间增加了一个约束条件, 算法需要增加一个分支处理这种特殊情况.

图3 拓展算法流程图Fig.3 Flow diagram of expansion algorithm

2.4 试验及分析

试验数据为企业的生产数据. 首先介绍一下数据的处理方式, 生产环境下不断有订单加入, 而排产算法是在某一个时间点上做出的预测, 是无法考虑追加订单这种情况的, 因此, 试验数据与生产数据的数据环境无法完全一致, 只能寻求一个等价时间点. 具体做法: 将生产状态恢复到特定的某一天, 在这天之后接到的订单需要剔除, 之前交付的订单需要剔除, 这天之后的所有生产状态需要复位, 这就得到了算法的输入状态, 在此基础上计算得到订单交期的预测值, 与实际值有一定的可比性.

试验数据来自企业生产数据, 选取2015-10-21—2016-01-29接到的订单. 按照上述处理方式, 根据下单日期和实际交付日期的分布情况, 将恢复时间定为2016年1月14号.1月14号之前交付的订单、之后接到的订单均剔除, 1月14号及之后的所有生产状态清零. 经筛选共有166个订单, 这批订单经BOM展开后有2 054个非标件, 包含13 748道工艺. 其中132个订单在1月29号前完成交付, 将这批订单作为对比数据, 将实际生产周期与排产计算结果进行对比. 将数据恢复到1月14号之后, 这批订单的未完成工艺有8 419道, 分属于1 545个零件, 总计加工时长为35 336.8 h.

试验结果如表1所示. 由表1可知, 相比企业之前的调度方式, 试验中订单延误率降低了13.6%, 平均延误天数降低了37.0%, 按期交货率提高了21.2%, 平均生产周期降低了21.6%. 订单交货严重不均衡也得到了改善.

表1 实际生产结果与算法排产结果比较
Table 1 Comparison of production data and results of the algorithm

指标实际数据排产计算结果总加工天数/d27642168延误订单数/个8069平均延误天数/d9．25．8如期完成订单/个5263平均提前天数/d14．16．4

3 调度系统实现及验证

3.1 系统实现及展现

根据算法实现了相关的调度系统, 系统采用浏览器和服务器架构, 前端页面与调度相关页面分组包括订单管理、工艺编制、智能排产、生产管理、加工任务. 图4和5分别为调度页面和生产进度界面. 通过生产状态反馈等信息支持排产系统的执行监控和动态调整, 并开发实现手工设置、仿真优化预测、可视化展示、警示推送等功能模块, 构成一个可以实现具有动态适应能力的多策略排产系统. 随着生产管理的粒度细化, 逐步实现以班次排产为主, 并兼顾可变时间间隔, 以及零件动态批次的生产模式.

图4 调度页面Fig.4 Schedule interface

图5 生产进度界面Fig.5 Progress report interface

3.2 对比讨论

调度系统属于制造企业生产执行系统(manu-facturing execution system, MES), 核心是调度算法, 企业没有通用系统可选, 只能通过定制开发方式获得. 企业缺乏可选的成熟系统. 这是因为调度过程与企业业务关联度非常高, 不同企业业务差别非常大, 系统往往是针对特定企业定制开发. 本文主要与同类文献做对比, 结果如表2所示. 本文实现的系统是为轮毂模具企业定制开发, 针对模具生产过程做了优化, 贴合企业的生产实际, 实际使用效果比较好.

表2 本文系统与相关系统比较
Table 2 This article system compared with related systems

本文系统文献[9]文献[11]文献[12]设备规模142[2，10][5，10]任务规模8419[10，20][50，500]算法JIT，动态规划JIT，动态规划组合优化标记优先级，顺排

(续 表)

4 结 语

调度算法只是车间调度问题解决方案的一部分, 要彻底解决这个问题, 需要多个系统协同, 对整个生产流程施加影响. 本文设计实现了以基于准时制的调度算法为核心的车间调度系统, 通过与企业现有系统的对接, 对整个生产流程进行监控. 创新之处在于考虑到上游环节的问题, 消除部分调度问题产生的源头, 降低了延误的发生频率, 同时缩短了企业的生产周期.

下一步的工作将包括帮助企业进行接单前的产能分析, 避免超出产能的接单; 根据调度情况给出企业实际产能利用分析, 对资源重新规划分配; 将系统进一步扩展, 为未来企业实行智能制造提供一个系统基础.

[1] FAN S, WANG J. Scheduling for the flexible job-shop problem based on genetic algorithm (GA) [J]. Advanced Materials Research, 2012, 457/458(1): 616-619.

[2] AL-HINAI N, ELMEKKAWY T. Robust and stable flexible job shop scheduling with random machine breakdowns using a hybrid genetic algorithm [J]. International Journal of Production Economics, 2011, 132(2): 279-291.

[3] XING L, CHEN Y, WANG P, et al. A knowledge-based ant colony optimization for flexible job shop scheduling problems [J]. Applied Soft Computing, 2010, 10(3): 888-896.

[4] CHAUKWALE R, KAMATH R. A modified ant colony optimization algorithm with load balancing for job shop scheduling[C]// International Conference on Advanced Computing Technologies. 2013: 1-5.

[5] 潘全科, 赵保华, 屈玉贵, 等. 一类解决无等待流水车间调度问题的蚁群算法[J]. 计算机集成制造系统, 2007, 13(3): 1801-1804.

[6] IPSILANDIS P, TSELIOS D, GEROGIANNIS V. Consolida-tion of the IFM with the JSSP through neural networks as model for software projects[C]// International Conference on Artificial Intelligence, Modelling & Simulation. 2014: 33-38.

[7] 徐兵, 陶丽华, 胡月梅. 基于JIT的多车间混流装配计划排序问题 [J]. 组合机床与自动化加工技术, 2015 (1): 153-156.

[8] 宋娟. 基于JIT的面向JSSP的一种启发式快速搜索算法[J]. 制造业自动化, 2010, 32(11): 106-109.

[9] WANG S, LI Y. Variable neighborhood search and mathema-tical programming for just-in-time job-shop scheduling problem [J]. Mathematical Problems in Engineering, 2014, 71(3): 741-764.

[10] 芮执元，冯亚岗，刘军，等. 一种求解柔性多目标JIT作业车间调度优化问题的方法[J]. 机械与电子， 2009(6)： 10-14.

[11] KOUIDER A, BOUZOUIA B. Multi-agent job shop scheduling system based on co-operative approach of idle time minimization [J]. International Journal of Production Research, 2012, 50(2): 409-424.

[12] 肖波, 叶文华. 工装MES生产调度和进度跟踪模块的研究与开发[J]. 机械制造与研究, 2009, 38(2): 42-46.

文章编号： 1671-0444 (2016)04-0461-05

Research and Implementation of Mold Production Scheduling Model Based on JIT

CUIXiao-guang,CAIHong-ming,BUFeng-lin,BAOSheng-wei

(School of Software, Shanghai Jiao Tong University, Shanghai 200240, China)

The mold production process has the characteristic of the discrete customization, which makes it difficult to deliver the goods on time due to the restriction of quality and production. Combining JIT (just in time) and dynamic programming, a multilevel scheduling algorithm and the related system are designed. The scheduling algorithm extends the scheduling problem from the shop floor to the entire production process, and establishes the relationship of the model from information modeling, which makes the allocation of production resources more fully, and balances development of production, so as to shorten the production cycle of orders. According to the experimental study and preliminary application verification, the system can effectively solve the enterprise discretization constant product scheduling problem, and shorten the production cycle of orders.

mold; job-shop scheduling; just in time; dynamic programming; intelligent manufacturing

1671-0444 (2016)04-0455-06

2016-04-20

国家自然科学基金资助项目(71171132, 61373030)；上海市自然科学基金资助项目(13ZR1419800)

崔晓光(1989—)，男，河南郑州人，硕士研究生，研究方向为信息可视化、智能制造.E-mail：cxgenjoy@163.com 蔡鸿明(联系人)，男，副教授，E-mail：hmcai@sjtu.edu.cn

TB 497; TP 311

A