为了利用规模效应,传统的生产调度往往将一个订单或者多个相同类型订单合并集中生产,在这种模型下部分订单会因较长时间的交货延迟而导致较高的拖期惩罚,同时集中生产单一产品易导致生产资金的大量占用,因而这种模型已经逐渐不能适应当今生产所呈现的订单多品种化的趋势。随着快速换模技术的发展,通过不同产品产线的快速切换来满足计划期内不同订单需求的生产模式已经被越来越多的生产企业所接受;另一方面,为了平衡各部门的需求和生产中的各种指标,单一的优化目标一般很难满足实际生产的各种需求,决策者需要综合考虑多种生产指标以满足不同的生产状况,力争达到整体利益的最大化。在这种情况下,决策过程需要纳入多个目标进行综合考量。
生产调度问题作为一种已经被证实的NP-hard问题:张会红等[1]运用免疫算法提高调度性能;何法江等[2]提出采用遗传算法解决并行机器系统工件调度问题;张烈平等[3]将基于惯性权重的粒子群算法应用到了流程工业的生产调度问题中;黄福令等[4]提出了基于改进差分算法和文化算法的混合算法。
上述研究都是针对单一目标进行调度优化,在如实反映生产状况方面有所欠缺。生产调度和预防性维护多目标集成优化已被越来越多的学者所关注:崔维伟等[5-6]综合决策工件的加工顺序和机器维护方式,并提出相应的算法联合优化了生产和维修部门各自的目标;吴悦等[7]研究了基于订单生产模式中订单完成时间对生产目标的影响,并据此提出适用于该模式的启发式规则;路飞等[8]采用粗糙规划理论建立调度模型,采用灾变型文化算法有效解决了不确定加工时间的工件生产排序问题;金玉兰等[9]以维修成本、最大完成时间、加权总完工时间、加权总延迟时间为优化目标,提出了多目标遗传算法;陶辛阳等[10]通过决策最小作业中断成本、最小最大期望延期成本、最小总期望延期时间三个目标实现全局优化;王世进[11]以总计作业加权完成时间和总计维护成本最小为优化目标,提出改进的蚁群算法求解。此外,王世进[12]在多目标优化的基础上,进一步提出了基于Lorenz非劣关系的改进NSGA-Ⅱ算法。
上述研究通过多目标决策对生产调度和预防性维护进行联合优化,并取得了较好的效果,但都是仅仅通过优化工件生产排序方案的方式来进行调度决策,却忽视了影响决策优劣的生产批量这一关键因素。生产调度中的工件加工顺序方案和批量决策都对调度结果起到关键性的作用,本文旨在建立一个综合决策工件集批量和生产顺序的生产调度和预防性维护集成优化模型,并首次提出了适合该集成模型的变长度染色体基因结构及其遗传方式,同时,考虑到鉴于NSGA-Ⅱ易产生早熟的缺陷,进一步引入灾变机制克服算法过早收敛的缺陷。
1 问题描述和模型建立以单机系统为研究对象,假设该调度期内订购m个不同类型产品的z个订单,可分为n个以1000件为单位的工件集,工件集不允许中断,假定所有工件集运输时间为零。
令xij为0/1变量,如果工件集j在第i个位置加工,则xij=1,否则xij=0。据此定义三维向量Ji表示第i个位置加工的工件情况,Ji包括三个特征变量:ai为实数变量,表示该工件集加工的产品类型;bi为实数变量,决定该工件集的加工数量;pi为0/1变量,如果在加工第i个位置工件之前进行预防性维护,则pi=1,否则pi=0。
本文其他变量的定义如下:i为工件集的编号,i=1, 2, …, n,其中n是工件集的数量;d为工件类型的编号,d=1, 2, …, m,其中m是工件类型的数量; k为订单的编号,k=1, 2, …, z,其中z是该调度期内订单的数量;tp为系统预防性维护时间;cp为系统预防性维护成本;tr为系统平均故障维修时间;cr为系统平均故障维修成本;Ni为加工工件集Ji期间机器故障次数的统计变量;t[i][j]为换模时间矩阵,表示从工件类型i变换至工件类型j所需的换模时间;e[i]为机器在加工工件集Ji之前的机器役龄;f[i]为机器在加工工件集Ji之后的机器役龄;c[d]为d类型产品的单位制造成本耗费;t[d]为d类型产品的单位制造时间;S[i]为工件集Ji所花费的库存成本;L[k],订单k所需支付的延期成本。
1) 机器故障模型。
机器在运行时会发生故障,机器故障会占用机器生产可用时间,降低生产效率。设λ(t)为故障率函数,β和η为二参数威布尔分布的尺寸参数和比例参数,则机器在t时刻时的可靠性为R(t)=e-(t/η)β。考虑到该机器失效形式属于制造过程的失效,取1.0 < β < 4.0。可见随着机器役龄的增加,机器的可靠率降低,发生故障的概率增大。假设进行预防性维护可以使设备“恢复如新”,则适时进行预防性维护会提高机器稳定性;然而即使进行预防性维护仍不能保证在生产过程中不会发生故障,当故障发生时采取应急维修,即仅恢复机器的使用功能而不改变其役龄。由于故障维修不改变机器役龄,故两次预防性维修间的故障发生的随机过程符合非齐次泊松分布,在(t1, t2)间的故障期望发生次数为:
$ E(N)=\int{\begin{matrix} {{t}_{2}} \\ {{t}_{1}} \\ \end{matrix}}\lambda \left( t \right)\text{d}t={{({{t}_{2}}/\eta )}^{\beta }}-{{({{t}_{1}}/\eta )}^{\beta }} $ |
对于工件集Ji,其加工期间的期望故障发生次数为:
$ E({{N}_{\left[i \right]}})=\int{\begin{matrix} {{f}_{\left[i \right]}} \\ {{e}_{\left[i \right]}} \\ \end{matrix}}\lambda \left( t \right)\text{d}t={{({{f}_{\left[i \right]}}/\eta )}^{\beta }}-{{({{e}_{\left[i \right]}}/\eta )}^{\beta }} $ |
加工该工件之前的机器役龄为:
$ {{e}_{\left[i \right]}}=\left\{ \begin{matrix} 0, \quad \quad \quad \quad &i=1\ \quad \ \quad \ \ \\ {{f}_{\left[i-1 \right]}}\cdot (1-{{p}_{\left[i \right]}}),&i=2, 3, \cdots, n \\ \end{matrix} \right. $ |
加工之后的机器役龄为f[i]=e[i]+t[ai]·b[i]。
2) 惩罚性的预防性维护时间。
当生产任务要求繁多的时候,生产计划往往存在为了赶工期而忽略预防性维护的倾向,从而导致更高频率的设备故障和机器使用寿命下降的问题。一般设备运行时间越长,所需的预防性维护时间也会增加,令预防性维护时间呈阶段性增加,其具体函数定义如下:
$ {{t}_{p}}\left( t \right)=\left\{ \begin{matrix} 1.5+t/4,&t\le 8\ \, \, \quad \\ 3+t/4, \ \, \,&8<t\le 14\, \\ 5+t/3, \, \, \ \,&14<t\le 20 \\ 16, \, \, \, \quad \quad \ &t>20\quad \ \ \\ \end{matrix} \right. $ |
cp=C·tp,C为单位预防性维护时间的维修成本。系统平均故障维修时间tr、成本cr取固定值。
3) 安装/更换模具时间。
在多品种生产任务中,即使机器具有通用性,但不同类型的产品需要不同的模具辅助生产,安装或更换模具需要占用机器可用时间,时间占用矩阵如下:
$ \mathit{\boldsymbol{A}}=\left[\begin{matrix} {{t}_{01}}&{{t}_{12}}&{{t}_{13}}&\cdots &{{t}_{1m}} \\ {{t}_{21}}&{{t}_{02}}&{{t}_{23}}&\cdots &{{t}_{2m}} \\ {{t}_{31}}&{{t}_{32}}&{{t}_{03}}&\cdots &{{t}_{3m}} \\ \vdots &\vdots &\vdots &{}&\vdots \\ {{t}_{m1}}&{{t}_{m2}}&{{t}_{m3}}&\cdots &{{t}_{0m}} \\ \end{matrix} \right] $ |
其中:tij表示由i类型产品更换至j类型产品时所需的模具更换时间,原则上,tij≠tji,t0j表示生产的第一类产品为j时所需的安装时间。安装或更换模具时可同时进行预防性维护。设V[i]表示在加工工件集Ji时是否需要更换模具:需要更换则V[i]=1;否则V[i]=0。
4) 存储/延期成本。
对于某个订单,若其过早地被生产,则会导致资金机会成本损失和仓储费用;但若延期交货,则会导致合同违约惩罚和失去顾客信任等费用。合理地安排生产任务,及时生产及时完工会带给企业额外的经济效益。丁佩雯等[13]提出的拖期惩罚隶属度函数合理地量化了不同程度的拖期完工带来的惩罚损失,具体如下:
$ p(t) = \left\{ {\begin{array}{*{20}{c}} {0,\quad \quad \quad \quad }&{t \in \left[ {0,{t^a}} \right]} \\ {\frac{{t - {t^a}}}{{{t^b} - {t^a}}},\quad \quad }&{t \in ({t^a},{t^b}]} \\ {v \cdot \frac{{{t^b} - t}}{{{t^a} - {t^b}}} + 1,}&{t \in ({t^b},\infty )} \end{array}} \right. $ |
其中v为拖期加速因子。
对于某个订单O[k],其有3个属性:产品类型m[k],订货数量l[k],交货期d[k]。设该订单共被分为e个工件集,则对于某个工件集iko,其所属订单的最后一个工件集为ike,该工件集的库存成本S[iko]=(f[ike]-f[iko])·b[iko]·caiko·R,其中R为单位时间库存费用率, 取0.0005。而对于该订单O[k],其延期成本为:
$ {{L}_{\left[k \right]}}=\left\{ \begin{matrix} 0, \quad \quad \quad \quad \quad \quad \quad \quad \ &\quad {{f}_{\left[{{i}_{e}} \right]}}-{{d}_{\left[k \right]}}\le 0 \\ {{c}_{\left[{{m}_{k}} \right]}}\cdot {{l}_{\left[k \right]}}\cdot p({{f}_{\left[{{i}_{ke}} \right]}}-{{d}_{\left[k \right]}}),&其他\quad \ \ \ \\ \end{matrix} \right. $ |
5) 目标函数。
总加工时间F1最短化:
$ {{F}_{1}}=\sum\limits_{i=1}^{n}{[{{t}_{\left[{{a}_{i}} \right]}}}\cdot {{b}_{\left[i \right]}}+{{t}_{r}}\cdot E({{N}_{\left[i \right]}})+\\ \ \ \ \ \ \ \ \ \ {\text{Max}}({t_p} \cdot {p_{\left[ i \right]}},{V_{\left[ i \right]}} \cdot {t_{\left[ {i - 1} \right]\left[ i \right]}})] $ |
总制造成本F2最小化:
$ {{F}_{2}}=\sum\limits_{i=1}^{n}{({{c}_{p}}\cdot {{p}_{\left[i \right]}}+{{c}_{r}}\cdot E({{N}_{\left[i \right]}})+{{c}_{\left[{{a}_{i}} \right]}}\cdot {{b}_{\left[i \right]}}})+\\ \ \ \ \ \ \ \ \ \sum\limits_{i=1}^{n}{{{S}_{\left[i \right]}}}+\sum\limits_{k=1}^{z}{{{L}_{\left[k \right]}}} $ |
该模型包含以下约束:
$ \sum\limits_{i = 0}^n {{x_{ij}}} = 1;j = 1,2, \cdot \cdot \cdot ,n $ | (1) |
$ \sum\limits_{j = 0}^n {{x_{ij}}} = 1;i = 1,2, \cdot \cdot \cdot ,n $ | (2) |
$ {a_i} \in \left\{ {x|1 \leqslant x \leqslant m} \right\};i = 1,2, \cdot \cdot \cdot ,n $ | (3) |
$ {b_i} \geqslant 1;i = 1,2, \cdot \cdot \cdot ,n $ | (4) |
$ \sum\limits_{o = 1}^e {{b_{\left[ {{i_{ko}}} \right]}} = {l_{\left[ k \right]}}} ;k = 1,2, \cdot \cdot \cdot ,z $ | (5) |
式(1)表示一个工件集只能在一个位置被加工;式(2)表示一个位置只能包含一个工件集;式(3)保证了工件集生产的产品种类是在订单要求范围内的;式(4)保证了每个工件集都有实际的意义,不是一个批量为0的假工件集;式(5)表示生产任务符合订单需求,保证在调度期内足额生产。
2 灾变型NSGA-Ⅱ算法设计考虑到本文综合优化制造成本和加工时间两个指标,故采用由Deb等[14]提出的改进非支配排序方法作为评价种群个体优劣的工具。对于有目标集w的模型求最小值的最优化问题,若满足∀i∈w, fi(x1)≤fi(x2);
1) 编码。
为了不以订单为单位进行生产调度,优化排产结果,设计如下的编码以灵活地安排生产种类和数量:K代表产品种类,N代表该工件集的数量,这两个变量采用实值编码;P代表是否进行预防性维护,为0/1变量,故采用二进制编码,若P=1,则代表在加工该工件集之前需要进行预防性维护操作。图 1染色体编码表示依次生产2类产品3000件,1类产品7000件,6类产品2000件,2类产品5000件,其中,在生产第2批和第4批工件集之前要对机器进行预防性维护。
2) 初始解生成。
种群数目N是影响算法运行速度和效率的关键因素之一,一般采用20~200或者两倍的基因位数,在本文算法中染色体因为数目被纳入决策变量,故其长度不定,采用种群数目为固定值N。为保证种群多样性,初始解随机生成。
3) 遗传操作。
考虑到采用传统的交叉过程会导致染色体代表的个体方案不可行,如果在交叉后加入修正操作又会很大程度上破坏父代染色体遗传下来的基因特征,由遗传操作变为随机搜索,因而采用单亲遗传算法来保证解的可行性,同时运用基于变长度染色体的截断算子和拼接算子,达到遗传操作的目的。以某个染色体PC为例,具体的算子规则如下:
$ \begin{gathered} {\text{PC:(2,3,0) - (1,7,0) - (6,2,1) - (6,3,0) - }} \hfill \\ {\text{(3,4,0) - (4,11,0) - (1,4,1)}} \hfill \\ \end{gathered} $ |
① 截断算子。
对某个基因(k, n, p)进行截断操作时,先随机生成在1~(n-1)范围内的截断数x,则生成两个子代基因(k, x, p)和(k, n-x, p),p位继承父代,后将分离出的基因(k, x, p)随机插入染色体中,原父代基因位(k, n, p)替换成(k, n-x, p),生成子代染色体。n=1时无法进行截断操作。如对(1, 7, 0)进行截断操作,若截断数k=3,则会概率产生如下子代:
$ \begin{gathered} {\rm{NC1:(2, 3, 0)-(1, 4, 0)-(6, 2, 1)-(6, 3, 0) - }} \hfill \\ \;\;\;\;\;\;\;\;{\rm{(1, 3, 0) - (3, 4, 0) - (4, 11, 0) - (1, 4, 1)}} \hfill \\ \end{gathered} $ |
② 拼接算子。
对某个基因(k, n1, p1)进行拼接操作时,随机选择染色体中另外一个具有相同产品类型k的基因(k, n2, p2),用基因(k, n1+n2, p2)替换基因(k, n2, p2),并将基因(k, n1, p1)移出。若未找到具有相同产品类型的基因,则无法进行拼接操作。如对(1, 7, 0)进行拼接操作,则会产生如下子代(此例中情况唯一):
$ \begin{gathered} {\rm{NC2:(2, 3, 0)-(6, 2, 1)-(6, 3, 0)-(3, 4, 0) - }} \hfill \\ {\rm{(4, 11, 0) - (1, 11, 1)}} \hfill \\ \end{gathered} $ |
③ 基本位变异算子。
对于基因(k, n, p)中代表预防性维护点的p位,采取基本位变异,则该基因变为(k, n, 1-p)。
4) 灾变机制及荣誉空间。
改进非支配排序遗传算法(NSGA-Ⅱ)采用了精英策略和父子代共同竞争策略,使种群的最优值得到了有效的保留,局部搜索能力强,但也产生易于陷入局部最优解的缺陷,为了解决这个问题,增强算法的广域搜索能力,故提出基于荣誉空间的灾变模型。所谓灾变,就是杀死当前所有的优秀个体以跳出局部极值,从而让远离当前极值的点有充分的进化余地。具体规则如下:在子代产生后将父子代合并并进行Pareto排序,将所得Pareto前沿加入荣誉空间,然后合并荣誉空间中新老成员并进行Pareto排序,取Pareto前沿,以此更新荣誉成员。若所得新荣誉空间中有新成员加入,则说明该次迭代子代中产生了更优异的个体。若持续r代未产生新成员,则视为该种群陷入进化陷阱,需要进行灾变。若连续灾变u次未产生新成员,则视为该种群已充分进化,此时荣誉空间中成员则为最优解。只要有新成员产生,则灾变和停滞计数器清零。
2.2 算法流程为了验证所提算法的有效性,现将灾变型NSGA-Ⅱ与Deb的标准算法在内存4 GB,主频1.8 GHz的Inter Core i5的Window 8系统中通过Java平台进行比较。随机订单生成如表 1所示。
各参数服从一定区间的平均分布,具体设置如下:t[i][j]=U(0.2, 1.5)、tr=U(1.5, 3.5)、cr=U(3, 6)、c[d]=U(2, 17)、t[d]=U(1, 14)、η=U(80, 100)、β=U(1, 4)、r=U(30, 100)、u=U(3, 6)。预防性维护成本率C=1.7,截断概率pc=0.35、拼接概率pj=0.35、变异概率pv=0.01,种群规模N=100, 150, 200,每种规模设置随机生成10个算例,则共有30个算例。
为了比较两种算法的优劣,将两种算法的种群Q1、Q2合并,生成2N规模的种群Qc,对其进行非支配排序,从中挑选出N个较优异个体组成M。定义B(Q1, M)为种群M个体来自种群Q1的比例,C(Q1, M)为种群M的Pareto前沿中个体来自Q1的比例。前者度量了Q1结果的整体优异程度,后者度量了Q1算法的最优值的优劣。因此,B(Q1, M)和C(Q1, M)大于0.5且越接近1,表明Q1的Pareto前沿较之Q2更好,即Q1更优异。表 2为种群规模下随机5个算例的B值、C值和两种算法的运行时间差。从表 2可以看出每个算例中灾变型NSGA-Ⅱ都具有比标准NSGA-Ⅱ更优异的结果,同时运算时间无较大差异。
为了具体对比算法的优劣性,从种群规模N=200的算例中随机挑选一组生成Pareto前沿点分布图,从图 4中可以清晰地看出灾变型NSGA-Ⅱ算法拥有更优异的前沿分布。
在考虑批量大小的基础上,本文研究了多品种生产任务下的车间调度和预防性维护集成优化问题。针对该问题的特征,基于NSGA-Ⅱ算法提出一种变长度染色体灾变性非支配排序多目标遗传算法对集成模型进行求解,通过各种规模的数据实验表明,基于灾变和荣誉空间机制的改进算法拥有比标准NSGA-Ⅱ算法更优异的广域搜索能力和寻优能力。本文采用随机生成染色体的方式初始化种群,初始解的特征分布对算法能力影响的研究及对最终解鲁棒性的探讨将是下一步的研究方向。
[1] | 张会红, 顾幸生, 汪鹏君. 基于免疫算法的生产调度现状与展望[J]. 计算机集成制造系统, 2008, 14(11): 2081-2091. (ZHANG H H, GU X S, WANG P J. Status & outlook of immune-algorithm-based production scheduling[J]. Computer Integrated Manufacturing Systems, 2008, 14(11): 2081-2091.) |
[2] | 何法江, 王明红, 汤以范. 遗传算法在车间流水作业调度中的应用[J]. 计算机应用, 2010, 30(S2): 274-276. (HE F J, WANG M H, TANG Y F. Application of flow shop scheduling based on genetic algorithm[J]. Journal of Computer Applications, 2010, 30(S2): 274-276.) |
[3] | 张烈平, 张云生, 杨桂华. 基于粒子群算法的流程工业生产调度研究[J]. 计算机工程及应用, 2012, 48(6): 225-228. (ZHANG L P, ZHANG Y S, YANG G H. Research on production scheduling problems in process industry based on particle swarm optimization algorithm[J]. Computer Engineering and Applications, 2012, 48(6): 225-228.) |
[4] | 黄福令, 高慧敏. 基于文化算法和改进差分进化算法的混合算法[J]. 计算机应用, 2009, 29(5): 1264-1267. (HUANG F L, GAO H M. Hybrid algorithm based on cultural algorithm and modified differential evolution algorithm[J]. Journal of Computer Applications, 2009, 29(5): 1264-1267.) |
[5] | 崔维伟, 陆志强, 潘尔顺. 基于多目标优化的生产调度与设备维护集成研究[J]. 计算机集成制造系统, 2014, 20(6): 1398-1404. (CUI W W, LU Z Q, PAN E S. Production scheduling and preventive maintenance integration based on multi-objective optimization[J]. Computer Integrated Manufacturing System, 2014, 20(6): 1398-1404.) |
[6] | 崔维伟, 陆志强. 单机系统的生产调度与预防性维护的集成优化[J]. 上海交通大学学报, 2012, 46(12): 2009-2013. (CUI W W, LU Z Q. Integrating production scheduling and preventive maintenance planning for a single machine[J]. Journal of Shanghai Jiaotong University, 2012, 46(12): 2009-2013.) |
[7] | 吴悦, 汪定伟. 交货期窗口下带有附加惩罚的单机提前/拖期调度问题[J]. 控制理论与应用, 2000, 17(1): 9-18. (WU Y, WANG D W. Single machine earliness/tardiness scheduling problem with additional penalties about due window[J]. Control Theory and Applications, 2000, 17(1): 9-18.) |
[8] | 路飞, 顾幸生. 基于灾变型文化算法的不确定条件下中间存储时间有限Flow Shop调度[J]. 华东理工大学学报, 2010, 36(5): 708-716. (LU F, GU X S. Finite intermediate storage flow shop scheduling under uncertainty based on cultural algorithm with catastrophe[J]. Journal of East China University of Science and Technology, 2010, 36(5): 708-716.) |
[9] | 金玉兰, 蒋祖华. 预防性维修计划和生产调度的多目标优化[J]. 哈尔滨工程大学学报, 2011, 32(9): 1205-1209. (JIN Y L, JIANG Z H. Multi-objective optimization research on preventive maintenance planning and production scheduling[J]. Journal of Harbin Engineering University, 2011, 32(9): 1205-1209.) |
[10] | 陶辛阳, 夏唐斌, 奚立峰. 基于健康指数的预防性维护与多目标生产调度联合优化建模[J]. 上海交通大学学报, 2014, 48(8): 1171-1174. (TAO X Y, XIA T B, XI L F. Health-index based joint optimization of preventive maintenance and multi-attribute production scheduling[J]. Journal of Shanghai Jiaotong University, 2014, 48(8): 1171-1174.) |
[11] | 王世进. 集成预防性维护计划的单机调度蚁群优化研究[J]. 工业工程与管理, 2011, 16(6): 60-65. (WANG S J. Ant colony optimization for integrated single-machine production scheduling and preventive maintenance planning[J]. Industrial Engineering and Management, 2011, 16(6): 60-65.) |
[12] | 王世进. 生产调度与维护集成的多目标Lorenz非劣遗传优化[J]. 工业工程与管理, 2012, 17(2): 1-7. (WANG S J. Multi-objective optimization for integrated production scheduling and maintenance planning with Lorenz non-dominated genetic algorithm[J]. Industrial Engineering and Management, 2012, 17(2): 1-7.) |
[13] | 丁佩雯, 蒋祖华, 胡家文, 等. 带有交货期时间窗的生产与维护联合调度优化[J]. 上海交通大学学报, 2015, 49(4): 524-530. (DING P W, JIANG Z H, HU J W, et al. Integrating production scheduling and preventive maintenance for a single machine with due window[J]. Journal of Shanghai Jiaotong University, 2015, 49(4): 524-530.) |
[14] | DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multi-objective genetic algorithm:NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197. DOI:10.1109/4235.996017 |