考虑优先级的IPPS紧急订单处理问题研究

苗志鸿，杨明顺，王雪峰，李 言

(西安理工大学机械与精密仪器工程学院，陕西西安710048)

工艺规划与车间调度集成(integrated process planning and scheduling,IPPS)是在有多个订单工件需要加工的情况下，每个工件可以有多条工艺路线，每道工序可以有不止一台的可用加工设备，通过对工件工艺路线及工序加工设备的选择和工件加工工序的排序，得到符合工序约束、满足特定优化目标的调度方案。实际生产过程中，由于订单的不确定性，经常会出现紧急订单插单的情况[1]。在考虑紧急订单情况下，如何制定合理有效的生产计划和调度方案，尽可能满足客户需求和实际生产条件，就显得十分关键[2-3]。

文献[4]引入订单完成难度系数的概念，提出基于订单完成难易程度的两阶段多属性决策方法，以订单综合权重与影响因素权重偏差最小为目标建立优化模型，根据各待插订单的综合权重向量获得最优插单序列。文献[5]、[6]分别对紧急订单的插单决策和重排插单方法进行研究，提高了生产计划的灵活性。文献[7]、[8]针对紧急订单问题，分别构建了供应链优化模型和紧急订单接单模型，以满足客户的需求。针对交货期紧急程度不同的订单，文献[9]提出了一种订单动态产品替补算法，并通过实验进行验证，在满足生产实际的条件下获得最优解。文献[10]考虑紧急订单扰动因素，以完工时间和交货惩罚为优化目标，建立动态仿真模型，实现了并行流水线的动态调度。针对混流装配线上的紧急订单插入问题，文献[11]提出一种动态调度策略，通过对未上线产品队列的重调度以及在制品队列的动态调度，实现紧急订单的最大程度优先交付和生产目标的最优化。文献[12]从订单紧迫程度、客户重要程度和订单交货期等方面考虑，确定订单加工优先级并进行排序，为制造订单的排产提供重要依据。

目前针对订单不确定问题的研究，通常只考虑一般作业车间调度问题，没有将工艺规划和车间调度集成在一起研究。本文针对紧急订单条件下的IPPS问题，构建订单优先级评价指标体系，通过灰色关联度进行评价；基于评价所得的订单优先级，建立以成本和完工时间的线性加权之和最小为目标的数学模型，并设计遗传算法进行求解，以保证满足生产条件下优先级高的订单按期完工。

1 紧急订单问题描述

紧急订单是正常生产计划以外的订单，最显著的特点表现为时间紧迫[13]。制造企业面对紧急订单的巨大利润诱惑，通常都会对其进行选择性的接受。企业为了满足紧急订单的生产，原生产订单常常会出现暂停、延期或取消的现象，必定会导致原有订单不能按照原有的方案进行排产，从而可能会延迟原订单交货期，同时也会额外增加人力、物力等成本，造成客户满意度的降低。对企业而言，订单的增加、取消、重排会给企业的生产部门带来很多不便，使生产的困难系数增大，甚至需要否定原有生产调度方案而重新设置。

针对紧急订单情况，企业在正式接受紧急订单时需要事先进行预判断处理，首先确定紧急订单的优先级别，并做出是否接受订单的初步决策；若接受订单，则预先编制车间生产计划，并权衡多方面因素，确定订单的加工顺序和完工时间，通过计算出来的完工时间等参数最终判断出订单是否满足客户要求。因此，为了更好地处理紧急订单，确定订单优先级成为解决紧急订单问题的关键。本文采用灰色关联方法进行订单优先级的评价。

1.1 灰色关联分析的订单优先级确定

灰色关联方法在解决多目标响应方面具有显著的优越性[14]。本文采用灰色关联进行订单评价时，首先确定理想订单，然后将未排订单与其进行比较，关联程度越高，则对应订单的重要程度也越高。

根据工艺规划与车间调度集成生产特性及订单评价特点，建立订单优先级评价指标体系，如图1所示。

图1 订单评价指标Fig.1 Order evaluation index system

在指标值的处理过程中，由于所有评价指标的单位各不相同，为了便于数据的整合，需要对其进行无量纲处理。

效益型指标的处理方式：

(1)

成本型指标的处理方式：

(2)

式中：xab为第a个订单第b个指标的评价值，a=1,2,…,f，b=1,2,…,g；maxxb和minxb分别为第b个指标的最大值和最小值；f、g分别为待排订单数和评价指标数。

将所有数据进行归一化处理后，可以计算灰色关联系数μa(b)：

(3)

式中：λ为分辨系数，可通过校正λ的值来控制关联系数的偏差区间，一般λ=0.5；r0b为理想订单指标所对应的评价参数b的数值。

通过求解关联系数，得到关联系数矩阵。为了方便比较，求解关联系数矩阵的平均值来比较订单的优先级，该平均值称为灰色关联度，可表示为：

(4)

式中：ka为订单灰色关联度，其值越高表明对应订单的优先级越高。

1.2 确定加权灰色关联度

为了更合理地确定每个订单的优先级，计算每个订单的加权灰色关联度[14]：

(5)

式中：ωa(b)为r0b与rab的关联系数在指标b点的权重，且：

(6)

加权灰色关联系数权重确定，定义加权灰色关联熵H(Ra)：

(7)

式中：pb为每一个比较列的加权灰色关联系数分布的密度值。

(8)

运用拉格朗日极值法计算pb，解得：

(9)

针对每一个比较列xa(b)(a=1,2,…,f)，记ωa(b)为ωb，μa(b)为μb，由式(6)和式(9)可得：

(10)

将式(10)表示为矩阵形式：

ΓW=b

(11)

式中：

反解式(11)，可得权重向量：

W=Γ-1b

(12)

2 考虑订单优先级的IPPS模型建立

考虑订单优先级的IPPS问题可以描述为：有多种订单产品需要在给定交货期内完成，每种产品可以有多条工艺路线，每道工序可以有多台可用加工设备。现有新的订单要安排到生产当中，通过对所有订单进行重新排产，确定后续各工序的加工顺序以及各工序所使用的加工设备，以获得使目标值最优的加工方案。考虑订单优先级，对工件的提前完工和拖期完工进行惩罚，以惩罚成本和完工时间的线性加权之和最小为目标函数，建立调度优化模型。

建模参数定义如下：

Jc：表示已有订单；

Jd：表示紧急订单；

J：表示所有订单；

Ji：表示第i个订单；

Ci：表示订单Ji的完工时间；

di：表示订单Ji的交货期；

Qi：表示订单Ji所有可能的工艺路线的数量；

Rij：表示订单Ji的第j条可行的工艺路线；

Oij：表示工艺路线Rij的所有工序数目；

Oijp：表示订单Ji的第j条工艺路线的第p道工序；

Cijpk：表示工序Oijp在设备k上的最早完工时间；

i：表示工件号，i=1,2,…,n；

j：表示生产线号，j= 1,2,…,Qi；

p：表示工序号，p=1,2,…,Oij；

k：表示设备号，k=1,2,…,m；

Z：表示完工时间和提前拖期惩罚成本归一化后的线性加权之和；

T：表示所有订单的完工时间；

Y：表示考虑优先级的所有订单的提前拖期惩罚成本；

αi：表示订单Ji提前完工的惩罚成本；

Yc：表示紧急订单到达时原订单的生产时间；

L：表示紧急订单加工前，原生产计划所加工的工序数；

Ocjp：表示紧急订单到达时，工件Jc正在加工的工序数；

Sijpk：表示工序Oijp在设备k上的开始加工时间；

Tijpk：表示工序Oijp在设备k上的加工时间；

Sdj1k：表示计划期初，紧急订单的加工完成工序数；

Scj1k：表示计划期初，原始订单的生产情况；

基于以上参数的定义，考虑订单的优先级，建立目标函数，如式(13)所示。每个工件何时完工，是否提前和拖期，对企业来讲，都会造成资金的损失。式(13)中，θ1和θ2分别表示两个子目标项权重，表明对两个子目标的关注程度，例如可设θ1=1，θ2=1.1。

(13)

T=Sijpk+Tijpk×Xij×Zijpk

∀i∈[1,n],∀j∈[1,Qi],∀p∈[1,Oij],

∀k∈[1,m]

(14)

(15)

式中：α和β分别表示提前和拖期惩罚权重。

考虑工件提前完工时，对企业所造成的主要是库存成本，而工件拖期完工造成的惩罚成本远比库存成本大，例如，可设置α=1，β=1.25，即当工件提前1 min完工时，提前惩罚成本为1元；当工件拖期1 min完工时，拖期惩罚成本为1.25元。工件在加工过程中所要满足的约束条件为：

1) 每个工件在加工过程中只能选择一条工艺路线：

(16)

2) 每个工件的每道工序只能选择一台设备进行加工：

(17)

3) 同一工件的不同工序不能同时加工，在不同设备k1、k2上加工时：

Sijpk1XijZijpk1-Sij(p-1)k2XijZij(p-1)k2≥

Tij(p-1)k2XijZij(p-1)k2k1,k2∈[1,m]

(18)

4) 当工件Ji的工序Oijp1在Oijp2之前加工，要使同一机器在同一时刻只能加工一道工序，则应满足：

Sijp2kXijZijp2k-Sijp1kXijZijp1k≥

Tijp1kXijZijp1kp1,p2∈[1,Oij]

(19)

5) 针对工件Ji的第j条工艺路线的第一道工序，即当工序p=1时：

Cij1k×Xij×Zij1k≥Tij1k×Xij×Zij1k

(20)

6) 针对工件Ji的第j条工艺路线的最后一道工序，即当工序p=Oij：

Cijoijk×Xij×Zijoijk≤Z

(21)

7) 每个工件的完工时间：

Ci=Cijoijk×Xij×Zijoijk

(22)

8) 所有工序的加工时间均大于等于0：

(23)

式(16)表示工件Ji只能选择一条柔性工艺路线进行加工；式(17)为机器约束，每道工序只能选择一台设备进行加工；式(18)为工件工序约束，即同一时刻只能加工给定工件的一道工序；式(19)表示各个工件每道工序之间只能有一种优先级，而且一台设备同一时刻只能加工一道工序；式(20)和(21)表示各个工件必须按指定工序顺序进行加工；式(22)表示每个工件的完工时间；式(23)为加工时间约束，每个工件的开始加工时间、加工时间以及完工时间都必须大于等于零。

订单在加工过程中除了满足上述约束条件外，当有新订单投入生产时，还需满足以下约束条件：

1) 在计划期初紧急订单的加工完成工序数为0：

Sdj1k=0

(24)

2) 用于判断在计划期初，原始订单的生产情况：

Scj1k≥0

(25)

当Scj1k= 0时，说明紧急订单到达时，原生产订单还未加工；当Scj1k>0时，说明当紧急订单到达时，原始订单已经开始加工。

3) 当紧急订单到达时，原生产订单已经开始生产，那么原生产订单已生产的工序数为：

(26)

3 算法求解

IPPS问题本身是一类复杂的NP-hard问题，本文需要考虑插单情况下，将工艺规划和车间调度问题集成优化[15]，并求出近似最优解，在此设计一种基于多层编码结构的遗传算法[16]对该问题进行求解。

1) 编码

分别对工件、工艺路线、机器和加工时间进行编码，形成一种多层编码结构，各层编码的含义如下。

工件染色体：基因位上的数字表示工件的序号，每个相同基因出现的次数表示工件的工序数。

工艺路线染色体：基因位上的数字表示工件所选择的加工工艺路线，遗传变异过程中，同一工件所选择的工艺路线相同，且每个工件只能选择一条可行工艺路线进行加工。

设备染色体：基因位上的数字表示设备编号，基因位上数字要与工件染色体、工艺路线染色体一一对应。

加工时间的染色体：基因位上的数值表示某一工件在特定加工工艺路线下某道工序所用的加工时间。

例如，对于A、B、C3个工件，共有6条工艺路线和4台加工设备，则其多层编码如图2所示。

图2 编码后的染色体Fig.2 Encoded chromosomes

对于工件层而言，C出现三次，分别表示工件C的第一道、第二道和第三道工序；对应其他编码层，分别表示工件C选择第5条工艺路线，第1道工序用设备2加工，其加工时间为5。

2) 适应度函数

本文采用目标函数的倒数作为适应度函数。

3) 选择操作

采用联赛选择和精英选择相结合的选择机制。设种群规模为N，联赛个体选择总数目为D(D

4) 交叉操作

为避免产生非法解，采用一种优先交叉策略对个体进行交叉。以工件层中的工件C为例进行说明，工艺路线层、设备层和加工时间层随工件层变化，同时发生交叉操作，如图3所示。

需要指出的是，由于不同工件选择的工艺路线不同，不同工艺路线对应的工序数目也不同，父代染色体交叉操作后，子代染色体的长度、基因位数可能会发生变化。

图3 染色体交叉Fig.3 Chromosomes overlapping

5) 变异操作

采用基于邻域搜索的变异操作。以工件染色体为例，从父代染色体中选择u个基因且每个基因必须为不同的值。取u=3，并选择基因位置1、2、5，然后对所有邻域染色体适应度进行评价，选择最优个体作为子代染色体，如图4所示。

图4 染色体变异Fig.4 Chromosome variation

工件层发生变异时，工艺路线、加工时间和设备染色体(机器层)也发生相应的改变，从而可能导致不合理解的产生。在此情况下，对不合理工件进行重新分配，使其拥有合理的工艺路线、机器和时间。例如，对第一条邻域染色体而言，将其父代染色体工件C所在的列提取出来，并复制到邻域染色体中工件C所在的位置上，为工件C匹配正确的加工时间。父代染色体编码如图5(a)所示，变异后第一条邻域染色体编码如图5(b)所示，修正后的邻域染色体编码如图5(c)所示。同理，从机器层中随机产生变异位置，假设该变异发生在位置6上，然后对其匹配正确的加工时间，则可得到新的子代，其变异结果如图5(d)所示。

其他邻域染色体同样根据上述过程进行变异操作，然后通过评价选择最优个体，具体算法流程如图6所示，图中N为种群规模，G为迭代次数，Pc为个体交叉概率Pc∈(0,1)，Pm为个体变异概率Pm∈(0,1)。

图5 各层染色体变异过程Fig.5 Chromosomal variation in each layer

图6 遗传算法流程图Fig.6 Genetic algorithm flow chart

4 实例验证

4.1 确定订单优先级

某制造企业在月初接到了3批紧急订单，考虑到紧急订单的巨大利润和企业的产能状况，决定对其采取接受的态度，在紧急订单到达之前，企业还有部分订单有待生产。其中原有订单为1、2、3，紧急订单为4、5、6。订单1、2、3、4、5、6的交货期分别为140 min、155 min、105 min、120 min、100 min、110 min，订单1、2、3、4、5、6的可选工艺路线和加工参数分别如图7和表1所示。图7中，S、E分别表示开始和结束；①～⑥表示机器号，代表六台机器。每批订单包含10个产品，紧急订单到达时，原订单尚未进行生产。

图7 各订单可选工艺路线Fig.7 Optional process route for each order

表1 订单各道工序可选机器及其加工时间
Tab.1 Order optional machine and machining time for each process

订单工序编号可选加工设备设备加工时间/min订单工序编号可选加工设备设备加工时间/min111,2,52,1,221,3,52,3,232,5,62,3,341,43,3.553,52.5,262,34,3411,2,52.5,3,321,3,52,3,232,5,63,2,341,42,3.553,52,3211,2,53,2.5,321,41.5,233,52.5,441,42.5,252,5,64,3,563,56,4511,2,53,2.5,221,42.5,2.533,52.5,441,42.5,255,64,361,3,53,6,5311,2,54,4.5,321,44.5,532,34,642,62,456,43,3.5611,2,53,4.5,321,2,44.5,3,532,34,341,2,62,2,456,45,3.5

无量纲化处理后，各个订单的评价指标值如表2所示。指标值归一化处理的结果如表3所示。在完成数据归一化处理后，根据式(3)可计算出订单的关联系数，如表4所示。在得出订单的关联系数的基础上，根据式(4)可计算出订单的灰色关联度，如表5所示。

表2 订单的评价指标Tab.2 Evaluating indexes of the orders

表3 归一化处理数据Tab.3 Normalized processing data

表4 关联系数表Tab.4 Table of correlation coefficients

表5 订单灰色关联度Tab.5 Grey correlation degree of the orders

根据表5中求解出的订单灰色关联度的大小关系，即k5>k4>k6>k3>k1>k2，可以确定订单优先级顺序依次为5、4、6、3、1、2，据此考虑对所有紧急订单都采取接受的态度。

4.2 求解结果及分析

根据建模过程，考虑订单的优先级，确定每个订单的生产排产以及每个订单生产时使用的设备情况，其计算结果可以直观地通过甘特图表示。图8为算法迭代过程图，图9为调度结果甘特图。

图8 算法迭代图Fig.8 Iterative graph

图9 调度甘特图Fig.9 Gantt chart of Scheduling

从调度结果可以看出，订单1、2、3、4、5、6的完工时间分别为150 min、150 min、115 min、120 min、100 min、110 min，所有订单的最大完工时间为150 min。其中紧急订单都按期完工，订单1、3拖期完工，两者都拖期10 min，订单2提前完工5 min。由结果可知，将工件优先级考虑在调度排产方案内，可以尽可能保证优先级高的工件按期完工。

5 结 论

1) 分析了IPPS环境下的插单问题，给出了一种基于订单优先级的处理策略，考虑订单评价的客户重要性、订单收入、原材料的可替代性、工艺复杂程度等7个指标，建立了指标体系，并利用加权灰色关联度进行订单优先级的评定。

2) 以订单提前或超期引起的惩罚成本和完工时间的线性加权之和最小为目标函数，考虑设备约束、工序约束等条件，建立了考虑订单优先级的IPPS模型；针对模型求解的复杂性，设计了一种包含工件层、工艺路线层、设备层和加工时间层的多层编码结构的遗传算法，并对算法中的各个模块进行了详细设计。

3) 通过实例验证了所建模型的正确性和求解算法的有效性。结果表明，将订单优先级考虑到IPPS问题当中，可以尽可能保证订单优先级高的订单按期完工，因此将灰色关联方法和遗传算法结合，可以很好地解决考虑订单优先级的IPPS问题。