基于生产资源的柔性作业调度任务优选方法

施 烁，李蓓智，邹 攀，杨建国

（东华大学 机械工程学院，上海 201620）

0 引言

多品种小批量柔性敏捷制造企业，任意时刻可能都有计划外的任务到达。企业或车间调度任务池中的任务是连续的，往往会高于设备的生产能力。因此，生产任务的优先权问题成为制定生产排成的关键。

不少的研究人员对此类问题作了相关研究[1～4]，大多数的调度任务优选主要是以订单为研究对象，依据订单自身的优先级排列加工任务，忽略了生产任务与车间实际生产能力的匹配问题。因此，研究基于生产资源的柔性作业调度任务优选方法是十分重要的。另外，在有关柔性作业车间调度方法的大量研究中[5～7]，取得了令人满意的结果。

本文从订单的任务交货期富裕度、重要度以及工序难易程度三个方面对其进行优先级排序，通过构建车间生产设备的互换规则，综合考虑订单优先级、工件柔性工序及生产资源的协调优化，实现多目标柔性作业调度任务的自动优选和生产能力平衡，为提高柔性作业调度方法的适用性、工作效率，调度结果的有效执行，缩短生产周期和订单交货期，降低柔性敏捷制造成本等奠定良好的科学依据。

1 调度周期任务优选问题的描述

调度周期任务优选问题可以描述为：根据任务工件的优先级评价指标对各工件进行优先排序，按照先满足优先工件的原则，再兼顾充分利用车间设备资源的目标，自动选择工件进入调度任务池。

根据该问题建立了订单任务—车间资源—加工效益的数学模型为：工件任务池Pt中有n个工件{J1,J2,…,Jn}，需要在m台设备{M1, M2,…, Mm}上加工。每个工件由一系列工序Ojx(x=1,2,…,TOj)组成，Bj和Sj分别表示工件j的批量处理的工序（如热处理等）集合和单件处理的工序（如车、铣等）集合，Ojx和TOj分别表示工件j的第x道工序和工件j的总工序数，Bj+Sj∈Ojx；工序Ojx在可用设备集Mθjx内的任一设备Mijx上加工，Mijx∈Mθjx，Mθjx∈{M1, M2,…, Mm}，准备时间为t0ijx，加工时间为tijx；工件Jj的优先等级序列为Tpj，调度周期T内设备Mi的生产能力为TFMCi，设备集Mθ的生产能力为ΣTFMCi。求解的目标则是根据任务优先等级序列Tpj及设备生产能力自动选择任务进入调度任务池Ps，同时使得总任务最大完工时间最小，设备最大负荷Cm与设备平均负荷之差最小（均衡率最优）以及设备的利用率最大。

2 生产资源能力的定义及分析

2.1 机床集及其互换原则定义

根据机械加工的工艺类型及特点，结合车间资源信息，将车间机床划分为不同的大机床集系列，分别是车系列、铣系列、镗系列等；每一个大机床集系列又可划分为不同的加工类型集，将其定义为小机床集系列，如车系列又可分为普通车、数控立车、数控卧车及数车加工中心等。

小机床集内的机床（工艺类型相同）在满足加工尺寸范围及加工精度的要求下，可以进行互换；大机床集内、机床集间的互换，则还需考虑加工工艺类型的匹配等。根据实际需求，定义如下的机床互换原则：

1）小机床集内的互换性（加工规模原则）：小规格机床可以被大规格的机床代替，反之若加工零件超过机床加工范围则不可替换；

2）大机床集内（间）的互换性（加工类型原则）：可互换的机床必须具有相同的加工特征，如三轴加工中心可以替换数控立铣等；

3）机床间的互换性，应满足一些简单的互换原则条件，如加工规模原则应在加工精度匹配的情况下使用，满足加工类型原则的机床还应该满足加工规模原则等；

4）如果互换的代价较大时，不考虑互换。不考虑机床加工精度上有较大差别的互换，如高精密数控卧车替换普通车等；不考虑机床规格有较大差别的互换，如龙门刨床替换普通刨床等。

2.2 机床能力定义及描述

传统的生产调度方法中，将调度周期的每台机床初始工作时间统一设为0或调度周期的开始时刻，而在实际生产中，根据设备的不同情况及其加工任务，不一定能统一启动。

假定调度的起始日期为Ts，调度周期为t（单位：天），机床Mi每天的生产班次为mi，每班次工作的小时数为twi，数量为Qi，其已有工作负荷为Tri(单位：小时)工作量，并考虑机床最大能力的η(%)作为其实际的加工能力。定义机床Mi的生产能力为TFMCi，如式(1)所示，则机床集Mθ的生产能力TFMC即为该组所包含设备生产能力之和，如式(2)所示。

3 任务优先级评价指标及其优选算法实现

3.1 任务优先级评价指标的定义

1）交货期富裕度Tr%

订单能否按期交货，取决于订单的交货期和订单任务的生产周期。将工件的交货日期（Tf）与开始加工日期（Ts）之差（Tf-Ts）作为工件交货紧急度的描述显然是不够全面的，忽略了生产周期的影响。将Tr定义为订单工件的交货期富裕度（交货时间的冗余期），即为工件可剩余的加工时间占其总时间的百分比。

通过计算工件的冗余期，选择该指标衡量任务工件的优先级，是较为合理的方法。计算工件任务池Pt中工件j的冗余期Trj，冗余期的计算如式(3)～式(5)所示。

其中，Ts表示任务工件调度的指定起始日期，Tfj表示工件j的交货日期，Tbj表示工件j的批量处理工序时间总和，Tsj表示工件j的单件处理工序时间

总和，Uj表示工件j的数量。

2）重要度v

工件的重要度与很多因素有关，除了工件本身的属性，如属于某个关键件中的重要零件，还包括一些潜在的制约因素，如工件所属订单的客户属性，订单的利润等。因此，对工件重要度的评价可以根据企业具体情况进行规定，选取不同的衡量指标，各指标之间的相对权重，车间可根据实际的需求给出。

工件j的重要度用vj表示，vj的取值范围为[0，1)，根据vj的范围可以将工件的重要度分为很重要、重要、比较重要、一般、不重要等等级，比如(1)很重要，0.9≤vj；(2)重要，0.7≤vj<0.9；(3)比较重要，0.5≤vj<0.7；(4)一般，0.3 ≤vj<0.5；(5)不重要，vj<0.3。车间亦可根据实际需要更改工件重要度等级范围的值。

3）加工的难易系数L

不同的任务具有不同的加工难易程度，如新老产品的差别或属于试制工艺还是成熟工艺等。加工难度大的工件则属于难加工的工件，在加工过程中容易出现废品，对这一类废品率较高的工件，可通过增加其生产批次的方法来保证工件的合格数。工件的废品率越高，应投产的生产批次应越大，工件的加工时间会增加，冗余期就会相应减小。而在有限的生产时间内，为了保证工件按期交货，需要考虑更充分的调整时间。

本文根据工件j加工的难易系数Lj，通过取（1+Lj）影响因子来增大工件的投产量，从而减小工件冗余期。工件加工的难易系数Lj的取值范围为[0，1]，难度由0到1逐渐增大。Lj的取值主要参考车间该类工件的历史数据库并根据实际情况由车间有经验的人员指定。

3.2 任务优先级评价的计算模型

根据以上的评价指标，现建立任务优先级评价的数学计算模型。根据工件j加工的难易系数Lj，取（1+Lj）影响因子对工件的交货期富裕度Trj进行修正，得到修正后的工件交货期富裕度Trj'。Trj'的计算如式(6)所示。

由修正后的工件交货期富裕度Trj'及工件的重要度vj两个指标共同确定任务工件的优先等级，得到工件的优先级序列Tpj，其计算模型如式(7)所示。Tpj越小，表示工件j的优先级越高。

其中，α表示修正后的工件交货期富裕度指标的权值，β表示工件的重要度权值，α+β=1。

3.3 任务优选关键算法实现

调度任务优选模块主要分为任务的优先级计算及排序、任务-设备的综合遴选两个部分。算法流程如图1所示。本文算法采用C#语言编写，调度算法[8]采用MATLAB编写，后台采用SQL Server2008数据库。

图1 任务优选算法流程图

算法关键步骤描述：

步骤1：读取任务池工件信息及车间设备资源信息；

步骤2：计算每个任务工件的冗余期及优先级序列，并将任务按照优先级序列从小到大进行排列；

步骤3：读取车间动态设备信息库，统计各预定设备组在调度周期内可用的加工能力；

步骤4：按照工件的优先级顺序选取工件，并更新调度周期预选任务库，同时计算设备组剩余的加工能力，更新调度周期设备负荷库；

步骤5：如果出现某一设备组满负荷(TFMC≤0)，判断是否有可替换设备组可以提供加工能力，如果有，继续选择该工件，转入步骤3，否则转入步骤6；

步骤6：返回调度周期预选任务库，删除该任务的选择，转入步骤4；

步骤7：当任务池信息库中所有任务全部遍历完毕，或所有的设备组均到达满负荷时，算法终止，得到调度任务池工件，即优先选出的调度任务工件，否则，返回步骤4；

步骤8：结束。

4 测试案例设计与结果分析

4.1 标准案例的组合及其目标与约束设计

为了验证本文提出的任务优选方法与算法的有效性，将标准库中MK01（10×6）与FL5×6两个柔性调度案例进行组合，并对订单交货期和设备维修约束等进行假设，并按机床互换性原则，定义工序设备的互换性。

1）工件代号的归一化处理：令MK01中10个工件的代号为J1-J10，FL5×6中5个工件的代号为J11-J15。

2）任务交货期目标的假设：工件J11交货期的单位时间为20，工件J14为30。

3）调度周期假设：该批任务可在2～3个调度周期内完成，并令第1个调度周期为30。

4）资源信息约束假设：某机床在某个时间段内因故维修，并令为机床5在第1个调度周期0～3时间段内需要维修；其余机床从零时刻起可用。下一个调度周期的资源信息则根据上一周期各机床的剩余加工能力而定。

5）调度目标设计：任务总完工时间makespan最小，设备最大负荷Cm与设备平均负荷之差最小（均衡率最优）以及设备的利用率最大。

4.2 调度结果及分析

基于以上的约束假设和本文算法，对15个工件优选调度的甘特图如图2所示，细实线框表示第一个调度周期内的作业任务，粗实线框表示第二个调度周期内的作业任务。

1）第一个调度周期，完成J1、J3等8个工件全部加工，makespan为30，其中具有交货期目标约束的J11的最终完工时间为15，J14的最终完工时间为29，均满足交货期要求。M5在0～3时间段无加工任务，符合机床维修不可使用的约束。

2）第二个调度周期，完成J2、J6等7个工件的加工，makespan为28。

3）15 个工件的总完工时间为58，少于目前已知的最优解[9]40+27=67，可见即使增加了诸多目标和约束，本文调度结果仍可使makespan降低13%。

4）设备最大负荷Cm为52（机床4），与各台机床的平均负荷45仅相差7，设备的均衡性较优，设备的利用率达到269/327=82.3%。

图2 任务优选后调度甘特图

5 结束语

本文对基于生产资源的柔性作业调度任务优选方法进行了研究，对算法关键部分作了详细设计。考虑车间实际的生产状况，建立了任务优先级评价的计算模型，同时制定了车间设备可互换原则，考虑调度周期内资源的生产能力，实现对车间调度任务自动化优选的目的。该方法已在某航天设备制造企业得到初步应用，为解决实际的柔性作业车间调度问题提供了科学依据，具有良好的工程应用前景。

[1]唐丽春,蔡晓毅.供应链环境下订单优先权确定[J].系统工程理论与实践,2009(9):41-46.

[2]双兵,顾幸生.考虑订单优先级的连续过程生产调度[A].第五届全球智能控制与自动化大会会议论文集[C].(4).2004.

[3]张红,郭飞鹏.面向敏捷询单处理的订单优先级排序方法[J].计算机工程与设计,2012,33(3):963-967.

[4]李浩,沈祖志,邓明荣.订货型企业基于约束理论的订单排产优化研究[J].中国机械工程,2004,15(10):865-869.

[5]Collotta M,Gentile L,Pau G, et al.Flexible IEEE 802.15.4 deadline-aware scheduling for DPCSs using priority-based CSMA-CA[J].Computers in Industry,2014, 65(8): 1181-1192.

[6]Wang W, Wang X,Ge X,et al.Multi-objective optimization model for multi-project scheduling on critical chain[J].Advances in Engineering Software,2014,68:33-39.

[7]陈成,邢立宁.求解柔性作业车间调度问题的遗传—蚁群算法[J].计算机集成制造系统,2011,17(3):615-621.

[8]史峰,王辉,等.MATLAB智能算法30个案例分析[M].北京:北京航空航天大学出版社,2011.

[9]高亮,张国辉,王晓娟.柔性作业车间调度智能算法及其应用[M].武汉:华中科技大学出版社,2012.