考虑班组负荷均衡的智能制造车间工序级作业任务排程模型研究

周琪森，林 杰，白 翱

（中国工程物理研究院 机械制造工艺研究所，绵阳 621900）

0 引言

在需求多变的市场竞争环境中，制造企业的生产模式是多品种的、变批量的、面向订单的生产模式，呈现随机性强、干扰因子多、多目标和多约束的特点，排程问题往往是NP-hard难题。而实际生产过程中存在大量的不确定因素，对制造企业的日常生产活动产生干扰，影响企业效率。合理、科学地分配生产时间和资源的排产方法就是制造企业能够高效运行的关键，也是实现制造过程智能化的核心。现有的排产方法主要以各类智能算法为核心，其中包括基于约束理论算法[1]、模拟退火算法、遗传算法、人工神经网络[2]、粒子群算法[3]等、利用智能算法对排程问题进行建模和求解。

本课题的研究对象是制造企业下的工序级作业车间排程模型，在按单生产模式下，作业车间的主要生产需求来源于各类订单，而订单的批量、到达时间是随机的、无法预估的，无法通过提前进行成品的预测生产或者是零部件的预测生产来减轻或平缓生产负荷不均带来的生产组织管理压力。同时，由于产品复杂，并有高精度要求，带来了复杂多变的工艺路线，导致求解规模庞大，求解问题困难，目前基于现有的求解策略所得排产结果还不足以运用到实际生产当中。

1 混合集合规划方法

混合集合规划是在由实数、整数、布尔量、集合所构成的混合域上，以逻辑和集合推理作为算法结构框架的求解系统，优势在于能够精确描述实数、整数、布尔量、集合类型上的复杂约束。同时，基于混合集合规划求解优化问题的方法，提出的自然约束语言（Natural Constraint Language，NCL）能够利用数理逻辑对生产计划与排程问题进行简明的自然描述建模，提高求解效率并且有效的规避组合爆炸[4]。因此，混合集合规划可以应用于对大规模的复杂问题的求解，同时保证了求解问题的速率和精度[5～7]。目前，混合集合规划被应用于集装箱码头船舶靠泊和装卸过程干扰恢复[8]、高速铁路列车开行方案优化[9]、航空公司航班计划以及机位分配等问题[10～12]等大规模计划方案的研究当中，已经取得显著成果。

本课题在智能制造的背景下，引入混合集合规划方法以及自然约束语言来研究多品种变批量按单生产模式下的工序级作业车间的生产排程建模及求解，充分考虑优先级约束和装配约束，将车间任务合理、科学地分配到各个班组中，解决任务合理安排，资源合理分配的难题。

2 排产问题分析

2.1 作业车间生产流程分析

以某制造企业为例，如图1所示，该企业接收订单后，统计订单中的成品需求数量和需求时间，根据物料以及各车间加工技能和加工能力向车间传达任务，包括工艺路线信息（含工时）、零部件最早开工时间及最晚交货时间、工序优先级等。

图1 作业车间生产流程图

2.2 排产思路解析

作业车间由若干班组组成，而班组可认为是具有通用设备、通用工具的设备集，是制造车间的核心制造单元。而班组的负荷情况可以用班组负荷率来衡量，班组负荷率指的是在一个生产时间单元内班组计划加工负荷与该班组的加工能力的比值。车间根据班组内部人员及设备负荷情况和资源使用情况进行计算机辅助排程得到工序级作业任务计划，并传达到各个班组处，由班组长将工序任务安排到具体设备或人员负责。本课题基于某制造企业的实际生产需要，在制造车间将工序级生产任务安排到班组的实际生产背景下，建立数学模型及约束。作业车间生产周期为一周，排产最小时间单元为半天。

因此，班组长作为一级调度员，能够实时实地的掌握生产情况，能够根据生产实时情况作出针对性的调整。事先平衡各班组间的生产任务负荷，能够有效避免忙的忙，闲的闲这一不合理现象，有效提高车间的生产效率。先将工序任务安排到班组，再由班组将工序任务分配到班组内部的具体设备上，从而将大规模排程问题拆分为若干较小规模问题，降低排程数据规模，避免了人工排产耗时长且不科学的窘境。

之所以将排产最小时间单元定为半天，是考虑到由于安全、质量等问题的存在，当发生异常事件时可能导致生产变动甚至中断或停止生产，排产到小时甚至分钟没有实际意义。同时排产到半天已经足够满足该企业在日常的生产的调度管理需求，可以在规定的时间节点完成产品交付，也给班组长留有一定的调度空间。再者，在大规模的排程问题计算中，排程精度较宽泛可以降低求解复杂度，提高计算效率。

因此，在排产开始前需要将排产数据中工序定额加工工时以及班组能力工时换算成为半天的整数倍，不足半天者可以补至半天，这也是为了给排产结果留有余地。此倍率参数k的取值可以影响最终排产结果，可以由计调员根据车间生产情况进行设置。本课题中暂定参数取值方法如表1所示。

表1 工时换算规则

3 排产模型建立与求解

3.1 数据逻辑分析

生产排程的基础数据主要是班组、工序以及作业任务的相关属性，可以直接从实时生产数据库中读取。本文读取了该制造企业车间的班组-工种表、班组工时能力表、工作日历表、待排产工序表等四个生产原始数据表，将数据抽象为以下数学变量。

PERIOD：采用顺序号作为工作日历，比如新年第一天记为001，考虑法定节假日以及双休日，自动跳过后得到正常上班时间段集合；

OpTypei：第i道工序所用工种；

BatchIDi：第i道工序计划所属零件批次，对应调度问题中的作业（JOB）的概念；ManHouri：第i道工序计划所用工时，单位为半天；OpPriorityi：第i道工序的优先级参数（数值越大级别越高）；

idSucci：第i道工序的后继工序（NULL表示该工序为作业中最后一道工序）；

TeamOpTypej：第j个班组所对应的班组可加工工种集合；

TeamAbilityi：第j个班组内部设备半天内的累计在制工时即为加工能力，单位为半天；

DeptCodei：第i道工序计划所分配班组；

StartPeriodi：第i道工序计划开工时段；

EndPeriodi：第i道工序计划完工时段。

3.2 构建排产约束

基于上述生产数据，在考虑班组能力负荷的情况下，本文的主要工作是通过NCL语言将生产排程中的各类约束准确全面地描述清楚，确定每道工序的开始时间（投产时间）、完工时间以及加工班组。

3.2.1 资源日历约束

WorkTimeTaski是工序i的有效加工时间，定义为工序i的起止时间段TimeTaski与工作日历PERIOD交集。

3.2.2 工艺路线约束

工艺员编制的工艺路线必须严格遵守，原则上由车间计调，工人不能随意更改工艺约束。同时一道工序完工后需要其后继工序在下一个半天开工，为中间的准备生产活动留有一定的准备时间。

3.2.3 班组技术约束

班组内设备能加工何种工种即为班组可加工工种集合， 对应工序j。

3.2.4 班组能力约束

TeamAbilityi定义为第j个班组内部设备半天内的累计在制工时即为班组能力，单位是最小排产时间单元即半天。

3.2.5 优先级约束

当工序i的优先级小于工序j时，有两种情况，若工序i，j所分配班组相同，即占用priority资源冲突时，需要保证工序i的开工时间大于工序j的完工时间，即工序i在工序j之后进行加工。

3.3 优化目标

本次排产选取最小时间跨度为主要优化目标，同时考虑班组间一个生产周期内（本文定一周为一个生产周期）的负荷均衡，使得车间接受到的作业任务尽量安排在一周内完成，保证班组负荷率不会太低，同时又可以平衡一周内的加工负荷，避免生产任务集中所造成生产任务无法按部就班地进行。

最小化最晚完工时间表示如下：

各班组半天内加工负荷均衡如下：

3.4 求解策略

本次求解基于POEM平台逻辑优化引擎求解，求解过程基于上述约束条件对解空间进行切削，从而求得一系列可行解。同时根据优化目标设计相应的求解规则，改善约束模型，进一步提高求解效率。求解排产问题有如下步骤。

1）查询确定工序加工班组

2）查询确定工序开工时间

4 实例验证

本文以某制造企业下的某机加车间实际生产数据进行应用实例验证。

此车间共有六个班组，班组可执行加工工种总计25种，选取排产任务为计划加工时间在2016年12月到2017年4月总计1000道待加工工序，共分为386个不同的作业任务集。

程序运行环境：计算机运行Windows操作系统版本是Windows Server 2008 R2 Enterprise，安装处理器为双核，型号是AMD Opteron TM Processor 6168 1.90GHz，内存为32GB，POEM优化计算平台版本是Academic Vision 3.0。

实例验证求得可行解耗时228秒，作业任务安排自2016年12月1日上午起，3月16日下午完工，排产结果可以满足车间内班组调度需求。排产结果表格输出形式如表2所示。

表2 排产结果表格形式示例

续（表2）

由表2中排产结果表中分析统计各班组在2016年12月01日2016年12月07日共10个工作周期中的工作负荷情况表如表3所示。将班组负荷情况画成直方图，如图2所示。

图2 各班组负荷直方图

表3 各班组半天内负荷率统计结果

相比于该车间在2016年6月到9月的生产数据统计分析结果，前三个月内班组的平均负荷率在40%左右。可以看到本次排产中各班组每半天内的平均负荷率均在50%左右，既满足了该制造企业中较大的生产负荷，同时又给实际生产过程可能产生的突发状况留下了一定的人为干预空间。同时，将工序任务安排到班组之后，对于每个班组而言，排产到设备的生产排程问题规模已经缩小到了十几台设备，一百道工序左右，使得班组内排产到设备上的时间消耗和求解难度大大减少。

5 结束语

本文利用自然约束语言对作业车间工序级排产计划问题进行了数学建模，基于车间内班组并行加工的生产环境下，对排产问题进行求解，将工序任务安排到各班组中，减小了排产问题的规模。同时，在求解策略中考虑车间内各班组间的负荷平衡，使得排产结果能够将工序任务尽量均衡安排到班组中。实际应用证明了方法的可行性和有效性，有助于提升制造车间生产过程的运行效率，提升制造过程管控的科学化、智能化水平。

[1]何莺.基于约束理论的多生产线计划排程系统的研究和应用[D].上海交通大学,2009.

[2]范华丽,熊禾根,等.动态车间作业调度问题中调度规则算法研究综述[J].计算机应用研究.2016.

[3]周丹晨.基于粒计算和序列比对的典型工艺路线发现方法[J].计算机集成制造系统, 2015, 21(3):694-701.

[4]Zhou J. The NCL Natural Constraint Language[J].2013.

[5]刘轩,尚鋆,白翱.基于混合集合规划的作业车间生产排程模型研究[J].制造业自动化,2015,37(23):39-43.

[6]刘轩,尚鋆,白翱.设备故障驱动的作业车间生产任务重调度方法研究[J].制造业自动化,2016,38(12):26-30+60.

[7]Rahmati S H A, Zandieh M, Yazdani M. Developing two multiobjective evolutionary algorithms for the multi-objective flexible job shop scheduling problem[J].The International Journal of Advanced Manufacturing Technology, 2013, 64(5):915-932.

[8]韩子龙.基于自然约束语言的多目标泊位—岸桥计划干扰恢复研究[D].大连海事大学,2015.

[9]熊星.基于混合集合规划的高速铁路列车开行方案优化研究[D].北京交通大学,2012.

[10]杨年.国内空铁联合运输网络规划方法研究[D].南京航空航天大学,2012.

[11]朱博,朱金福.飞机计划恢复的混合集合规划方法研究[J].小型微型计算机系统,2012,33(11):2556-2560.

[12]王岩华,朱金福,朱博,唐昀.基于混合集合规划的机位分配约束规划模型[J].航空计算技术, 2014,44(06):18-21.