模糊交货期条件下的IPPS问题研究

马 静，李 言

（西安理工大学 机械与精密仪器工程学院，西安 710048）

0 引言

工艺规划和车间调度两个子系统在制造系统中具有重要的功能。工艺规划通过对产品工艺路线进行不断规划和改善，在不同的生产状况下，选择不同的工艺方案，来提高产品的生产效率和制造的柔性；车间调度对工件的加工顺序和资源利用进行合理分配，避免资源利用的冲突，以获得最优的调度结果。研究表明，将工艺规划和车间调度进行集成（Integrated Process Planning and scheduling，IPPS），可以克服二者独立运行时存在的效率低、目标冲突及规划与实施的过程中存在时间差等问题[1,2]。

Chrssolouris[3]首次提出将工艺与车间调度进行集成规划。Beckendorf[4]用可选工艺路线来增加系统的柔性。Khoshnevis[5]动态反馈的思想引入到工艺规划与车间调度集成之中，从而将动态调度和工艺规划有机地结合在一起。Zhang[6]Larsen[7]继承可选工艺路线和动态反馈思想的同时，采用分层规划的思想进行生产调度研究，并首次提出了面向功能的IPPS的集成。吕盛坪、乔立红[8]在工艺规划和车间调度的集成过程中，提出一种结合了面向接口与面向功能集成的复合式集成模型。

目前，研究人员对IPPS问题进行了诸多研究，但大多数都是基于确定条件下进行的，而在实际的生产加工过程中，存在诸多不确定因素，如：加工时间、交货期等，都会对调度的柔性和灵活性产生很大的影响。很多研究人员针对车间调度不确定因素进行了具体研究，引入区间数、随机数和模糊数等来表征这些不确定[9]Ishii[10]等针对开环车间的双机调度问题以及同型机的调度问题，首次将交货期看作模糊数，解决了在模糊交货期环境下基于不同目标函数的调度问题。Cheng[11]首次把交货期窗口的概念应用到提前/拖期调度问题中。徐新黎等[12]考虑纸盆车间调度中的不确定因素，通过构建的多智能体免疫算法，找到最优调度决策。刘明周等[13]采用模糊随机变量表示废旧件加工时间，利用混合优化算法解决制造加工车间最优调度问题。刘晓冰等[14]提出混沌量子粒群算法解决模糊环境下柔性作业车间调度问题。王春等[15]采用混合机器分配和工序排序策略，解决工序加工时间不确定的多目标调度问题。张铭鑫等[16]基于可信性测度的模糊变量表示再制造零部件的装配时间，建立模糊机会约束规划调度模型，通过混合智能优化算法求解该模型。彭运芳等[16]利用改进的遗传算法，用三角模糊数表示产品的处理时间，解决了生产调度问题，并且验证了算法的可靠性。

综上所述，目前对于模糊交货期的研究，大多针对单机或多机问题，很少考虑工艺路线和设备的柔性。对于交货期而言，一般都假设交货期为确定值。随着JIT（准时制）的发展，客户对工件的提前/拖期问题的关注度日益增强[17,18]。在实际的生产过程中，随着市场的不断变化，以及顾客需求的多样化，将交货期视为一个固定值已无法满足顾客的需求，将其考虑为一定范围内的不确定因素更加符合实际生产情况，更有利于提高顾客的满意程度和企业生产的效益[19,20]。因此，本文将在已有研究的基础上，考虑IPPS问题中交货期的不确定性，提出一种梯形模糊数表示工件的交货期；以工件的交货满意度加权之和最大以及最大完工时间最小为优化目标，建立集成优化模型，并设计相应的求解算法；最后，以实例对模型和算法进行验证。

1 IPPS问题描述

确定条件下的工艺规划与车间调度集成的问题描述：n个工件在m台设备上进行加工，每个工件有多条可选的工艺路线，每条工艺路线又有k台设备，其中部分设备可以进行替换。根据特定的目标，在考虑车间资源、工件工序等约束条件下，通过集成调度，最终选出最优的工艺路线和作业车间调度顺序。为了更好地描述IPPS问题并建立合适的数学模型，可对该问题做如下假设：

1）每个设备在同一时刻只能加工一道工序；

2）设备的初始状态均为空闲，且在零时刻，任意任务都是可行的，并且无设备故障，加工不会出现中断；

3）同一零件的不同工序不能同时被加工；

4）所有工件在加工过程中没有优先级，彼此之间相互独立；

5）任务在机器上执行的时间事先已知；

6）所有工序的准备时间均包含在工件的加工时间内，且与工序的加工顺序没有关系；

本文将在确定条件下的IPPS问题中，考虑交货期的不确定性，用梯形模糊数来表示工件的交货期；进而在该模糊环境下，进行问题的建模和算法设计。

2 问题建模

2.1 参数设定

为了方便建立工艺规划与车间调度集成的数学模型，设定参数如下：

n：表示工件数目；

J：工件集合；

Ji：表示第i个工件，i =1，2，…，n；

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

Rij：表示工件Ji的第j条可行的工艺路线，j=1，2，…，Qi；

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

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

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

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

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

Ci：表示工件Ji的完工时间；

Cimax：表示工件Ji的最大完工时间；

2.2 不确定交货期的表达

准时制生产过程中，零件的提前和拖期，都会给企业和产品客户带来很多问题。零件的提前完工将会导致企业资金的不必要占用和库存费用的升高等问题。零件的拖期完工，将会导致有关合同的违约惩罚和失去顾客信誉，也会在一定程度给客户带来巨大损失。

对于确定时间条件下的交货期，有时不能满足实际需求。因此将其视为不确定因素，显得很有必要。可在满足企业和客户需求的同时，将固定交货期值设置在一定范围内，这样有利于提高调度的灵活性，对企业和客户而言，都比较经济和科学。因此本文选择用梯形模糊数来表示零件的交货期。图1所示为梯形模糊交货期的线性隶属函数图。

图1 梯形模糊交货期的线性隶属函数

如图1所示，若工件在交货期[d2，d3]加工完成，则其满意度为1，不受惩罚。对于在交货期之外加工完成，其满意度将会小于1且呈线性变化，工件的提前和拖期惩罚根据实际情况而定。文中工件的完工满意度用线性隶属函数来表示，用μ（Ci）表示工件Ji的隶属函数，如式(1)所示。

2.3 模糊交货期条件下的IPPS问题建模

让工件在多条柔性的工艺路线中选择合理的工艺路线和合理的设备，并以所有工件的交货满意度加权之和最大而且所有工件的最大完工时间（Makespan）最小为目标，建立目标函数及相应约束条件。所有工件的交货满意度加权之和最大用公式表示如下：

公司所加工的工件，其面对的客户不尽相同，其重要程度也不一样，权重就不同。wj为工件J的权重，用来表示工件的重要程度。工件在加工过程中所要满足的约束条件如下：

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

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

3）同一工件的不同工序不能同时加工；

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

5）针对工件Ji的第l条工艺路线的第一道工序；

6）针对工件i的第l条工艺路线的最后一道工序；

7）所有工序的加工时间均大于等于0；

3 算法求解

本文求解IPPS问题的关键就是：在共同约束条件、目标函数和优化环境下，如何将工艺规划和车间调度集成在一起，并将模糊交货期考虑在内，最后求解出近似最优解。针对交货期不确定条件下的IPPS问题，本文采用一种多层编码结构的遗传算法。下面将对该算法的编码、选择、交叉和变异操作进行具体说明，并给出算法的具体流程图。

1）编码

本文采用一种四层编码结构的遗传算法。其各层分别为：工件层、机器层、加工时间层和工艺路线层。

工件层：各工件的编码；

机器层：各个机器的编码；

加工时间层：各个工件的不同工序在机器上的加工时间；

工艺路线层：不同工件所选的工艺路线。

本文采用多层编码结构将工件、机器、加工时间和工艺路线联系在一起。这里以3个工件、6条工艺路线、4台机器为例对算法进行进一步的说明。

表1 编码示例

表1中的编码，对于工件层而言，如第一个位置的3可解释为：第三个工件的第一道工序，第四个位置的3可解释为：第三个件的第二道工序。对于第一列编码，可表示为第3个工件选择第5条工艺路线，其第1道工序在机器2上加工，加工时间为5。

2）适应度函数

遗传算法通常用适应度函数来评估一个染色体相对整个群体优劣的相对值的大小。用适应度值的高低来决定其选择概率的大小，适应度值越高，则被选中的概率越大[15]。本文中染色体的适应度函数参考目标函数。

3）选择操作

选择联赛选择法和精英选择相结合的遗传算法选择机制。假设该遗传算法的种群规模为N，联赛个体选择总数目为L（L＜N）。首先从当前种群中随机性地选择一定数量的个体，然后根据适应度函数，从中选出个体适应度值大的个体进行交叉、变异等操作。最后，比较下一代个体的适应度值和当代个体的适应度值大小，将最佳个体复制到下一代种群中，随机替代下一代种群中相应数量的个体。

4）交叉操作

交叉就是指染色体基因之间的一种互换过程，种群中每一代个体之间按一定的交叉概率进行基因的交换，从而产生新个体。本文采用一种优先交叉策略，对个体进行交叉，以避免其产生非法解。以工件层的工件3为例进行说明，其它层随着工件层同时发生交叉，其交叉示例如下所示：

父代1：（3 2 2 3 1 3 1）

父代2：（2 3 2 1 3 1）

子代1：（3 2 2 3 1 1）

子代2：（2 3 2 1 3 1 3）

在不同的父代染色体中，由于工件所选择的工艺路线不同，而每条工艺路线所对应的工件工序数目也不尽相同，则导致染色体进行交叉操作后，其子代染色体的长度发生变化，基因个数也就不同。

5）变异操作

变异操作就是从种群中随机选择个进行变异操作，本文选择基于邻域搜索的变异操作。本文以染色体工件层为例进行具体说明，其交叉步骤如下：

步骤一：从父代染色体中选择n个基因，其中每个基因必须选择不同的值。文中n取3，并选择基因位置1、位置2、位置5。

步骤二：采用适应度函数评价所有的邻域染色体，从中选择最优的个体作为其子代染色体。

父代个体：（3 2 2 3 1 3 1）

邻域染色体：（1 2 2 3 3 3 1）

（1 3 2 3 2 3 1）

（2 1 2 3 3 3 1）

（2 3 2 3 1 3 1）

（3 1 2 3 2 3 1）

个体通过变异后，其所对应的工艺路线、加工时间和机器都会发生变化，从而产生不合理解。这时可将产生不合理解的工件重新取出来，并将其匹配合理的工艺路线、机器和时间。以第一条邻域染色体为例进行具体说明。

其工件3的加工顺序发生变化，产生了不合理解。这时可将父代染色体工件3所在的列提取出来，将其复制到邻域染色体中工件3所在的位置上。

表2 父代染色体

表3 第一条领域染色体

表4 修正后的领域染色体

对机器层进行变异：从机器层中随机产生变异位置，假设该变异发生在位置6上，然后对其匹配正确的加工时间，则可得到新的子代。其变异结果如表5所示。

表5 器层变异后的领域染色体

其他邻域染色体同样根据上述过程进行变异操作，然后比较，选出最优的个体。根据上述描述，可得到该IPPS问题的遗传算法流程图，如图2所示。

图2 交货期不确定条件下的遗传算法流程图

其中N为种群规模，T为迭代次数，Pc为交叉概率，Pm为变异概率。

4 实例仿真

某企业要生产一批轴类零件，该批零件共包括三种工件，图3和表6分别为工件1的可选加工路线以及每道工序可选机器及其加工时间，图4和表7分别为工件2的可选加工路线以及每道工序可选机器及其加工时间，图5和表8分别为工件3的可选加工路线以及每道工序可选机器及其加工时间。

1）工件参数

图3 工件1可选工艺路线

表6 工件1每道工序可选机器及其加工时间

图4 工件2可选工艺路线

表7 工件2每道工序可选机器及其加工时间

图5 工件3可选工艺路线

表8 工件3每道工序可选机器及其加工时间

2）算法求解结果及其分析

按照式(1)～式(9)，可以建立实例对应的模型。求解过程中，设置的初始参数如下：种群规模N=100，迭代次数G=200，交叉概率Pc=0.9，Pm=0.05。机器层变异概率为0.5。根据上述算法，搜索出最优的车间作业调度顺序。图6为模糊交货期算法迭代图，图7显示模糊交货期下每个工件的调度顺序。

每个工件分别用不同的形式来表示，工件1、2、3的完工时间分别为11min、12min、13.5min。所有工件的最大完工时间为13.5min，所有工件的满意度加权之和最大为0.75。

图6 模糊交货期下的算法迭代图

图7 模糊交货期下的调度甘特图

如果将交货期考虑为一固定值，假设工件1、2、3的交货期分别为11min、10min、14min。在满足目标条件的情况下，决策出最优的调度顺序。图8所示为确定交货期下算法迭代图，图9所示为确定交货期下的调度甘特图。工件1、2、3的完工时间分别为12min、13min、14min。所有工件的最大完工时间为14min，所有工件的满意度加权之和最大为0.33。

与确定交货期条件下的IPPS相比，通过使用梯形模糊数来表示工件的交货期，在一定程度上不仅有利于制造商合理安排生产计划，为公司提高经济效益，也可尽可能地满足顾客的需求，在交货期范围内，使其最大程度地完成工件的加工。如果是确定交货期条件下的IPPS问题时，其交货期为一固定值，相比模糊交货期而言，其最大完工时间变大，顾客满意度值也有所降低。

图8 确定交货期下算法迭代图

图9 确定交货期下的调度甘特图

5 结束语

针对工艺规划和车间调度中的交货期不确定问题，本文引入梯形模糊数来表示工件的交货期。以所有工件的交货满意度加权之和最大而且所有工件的最大完工时间（Makespan）最小为目标函数，最后，采用基于多层编码结构的遗传算法决策出了最优的调度顺序，并验证了算法的有效性和可行性。并与交货期确定条件下的IPPS相比，该研究更符合实际需求，亦可提高客户的满意度。该基于交货期不确定条件下的IPPS问题研究，将会对实际的生产调度有着很大的指导作用和实际参考价值。

在生产制造过程中还存在很多不确定性，在以后研究中，可将其他不确定性因素与交货期不确定联系起来，使其更好地为实际所用。除此之外，不确定因素的表示方法还有很多，研究人员可选择其他方法对此进行更深入的研究。