虚拟单元内外运输能力受限的异质并行机调度研究

高龙龙, 韩文民

(江苏科技大学 经济管理学院,江苏 镇江 212100)

0 引言

虚拟制造单元(以下简称“虚拟单元”)作为柔性制造的一个重要分支,近年来引起了许多关注。虚拟单元是指根据生产任务的相似性,并考虑各项生产条件或约束,从备选设备资源中选出需要的设备,组成逻辑生产单元,通过物流系统的连接,无需改变设备和资源的物理布局,而形成逻辑相互关联的虚拟动态生产实体,其具有减少生产准备时间和在制品库存,提高设备利用率等优点。虚拟单元多适用于大型复杂产品生产,其生产及物流组织复杂,工件的运输多采用平板运输车、行车、叉车等大型运输设备。由此可以看出,虚拟单元的有效实施,依赖于生产物流系统的有效流转,运输组织方式对调度方案的有效制定与实施具有重要的影响。

但是,目前大部分虚拟单元研究对运输组织问题的考虑是不充分的。如FORGHANI和GHOMI[1]以总加工成本和单元内工件的平均加工时间之和最小为目标研究了虚拟单元构建、调度与布局问题。ZANDIEH[2]以最大完工时间和总运输距离之间的加权和最小为目标,研究了虚拟单元调度问题。在单元调度(设备物理位置可变的单元)和柔性作业车间调度中,有学者对该问题展开了进一步的讨论。曾程宽和刘士新[3]研究了运输空间约束下的多单元协作调度问题。DELIKTAS等[4]研究了具有序列相关和单元间运输时间约束的单元调度问题。王亚昆等[5]考虑了设备间的运输时间因素,对柔性作业车间节能调度问题进行了研究。但是,以上这些研究都假定设备的运输能力是无限的,但该假设过于简单,脱离了生产实际。在现实生产环境中,工件的每一道工序完成加工后,存在部分运输设备被占用、运输设备无法在工件被完成加工后立刻或提前在当前加工设备前等待执行运输任务等情况,致使工件不能全部被立即运输。

上述状况在大型复杂产品生产组织中表现得更为突出,这是由于其大型工件的运输准备及运输时间一般都较长,且由于运输设备大型化、价值高、所需作业场地大,这就使得这类企业车间运输能力受限的情况更为常见。

因此,有必要研究在运输能力受限的情况下,运输组织与虚拟单元调度的交互影响,并进行相应的决策。

针对该问题有部分学者展开了讨论。MIHOUBI等[6]以最大完工时间最小为目标,研究了运输资源数量和能力受限的柔性作业车间调度问题。LIU等[7]以设备加工与运输能耗最小和总加工时间最小为目标,研究了运输受限的柔性作业车间和起重机运输的绿色集成调度问题。GOLI等[8]研究了AGV能力受限的单元构建与调度问题。但是,上述研究大都忽略了空载运输时间(运输设备不运载工件时在车间内的移动时间)对生产调度的影响。在实际生产过程中,运输设备存在大量的空载时间,而该类空载时间影响了运输设备的循环使用和其可利用性,进而影响了生产物流的连续性和调度方案的制定与执行。因此,有必要将空载运输时间作为制约因素,研究运输能力受限的虚拟单元运输组织与调度联合决策问题。

另外,目前关于虚拟单元并行机问题的研究,大部分学者都假定并行机的类型为一致并行机,即同一阶段上的并行机完全一致,具有相同的处理速度[2,9]。然而实际工业环境下,通常存在新老设备交替使用的情况。同时,虚拟单元多属于单件小批生产,设备的通用性较高,不同设备常可承担相同的加工任务,但其加工效率和工时耗费存在着差异性。

通过以上分析可以发现,虚拟单元的有效实施,依赖于生产物流系统的有效流转。现有虚拟单元相关研究忽略了单元内外运输能力限制、空载运输时间等因素,对并行机的异质性考虑也够不充分。这导致所得到的调度方案往往与实际生产组织过程产生较大的偏差,甚至不可行。本文综合考虑以上因素,以最大完工时间最小和总运输时间最短为目标,构建了虚拟单元内外运输能力受限下的运输组织与异质并行机调度联合决策模型。同时提出了改进的NSGA-II算法对所构建的多目标模型进行求解。所提算法将粒子群算法与NSGA-II的交叉、变异过程相融合,以提高算法的搜索能力。并将模拟退火算法的进化机制应用于NSGA-II的变异过程,以避免NSGA-II容易陷入局部最优的问题。通过小、中、大规模算例验证所提算法的有效性。

1 问题描述和模型构建

1.1 虚拟单元异质并行机调度问题描述

虚拟单元异质并行机调度问题可以描述为:在加工车间中共包含K个虚拟单元,n个待加工工件和M台加工设备。每个虚拟单元包含多台加工设备,承担特定工件族的工件的加工任务。一台加工设备可以属于多个单元,且设备的物理布局是已知的。每个工件在加工过程中包含了有限次、顺序一定的工序,每道工序只能在一台加工设备上完成加工,具有加工每道工序能力的加工设备至少一台。同一工序选择的设备不同,完工时间可能不同,每道工序在每台设备上的加工时间是已知的。每个工件族中的工件大部分工序都可以在所属的单元内完成加工。如果工件族中的某道工序无法在所处单元内完成加工,则需要在具有该工序加工能力的加工设备所属的单元进行加工,由此产生跨单元加工。具体假设如下:

(1)所有工件在0时刻都准备就绪。

(2)每个工件都有相同的优先级。

(3)车间内所有的加工设备在0时刻可用。

(4)同一时间内,每台设备只能加工一个工件。

(5)每道工序在加工设备上开始加工后不能中断。

(6)加工设备和工件所属的单元已知。

1.2 虚拟单元运输组织问题描述

虚拟单元运输组织的问题可被描述为:每个虚拟单元内有σk台运输设备,虚拟单元内的运输设备除了完成本单元内的运输任务外,还可根据需要,完成本单元内工件的跨单元运输任务。车间内运输设备集中停放区域θ个,以供车间内运输设备的停放。每个加工设备附近都有一个运输设备停放区域,以停放运行至该加工设备的运输设备。虚拟单元内的运输设备能力是有限的,部分工件被加工完成后,存在等待被运输的情况。具体假设如下:

(1)所有的运输设备在0时刻可用。

(2)每辆运输设备都有相同的优先级。

(3)每辆运输设备在同一时刻,只能运输一个工件。

(4)如果运输设备正在进行运输作业,则运输作业不能中断。

(5)虚拟单元内的运输设备,完成跨单元运输后,立刻返回距离所属单元较近的运输设备集中停放区域,除非当前任务的运输完成时间与该运输设备下一任务的空载开始时间相同。

(6)加工设备附近的运输设备停放区域,每次只可停放一台运输设备。

(7)运输设备完成当前运输任务后,距离下次被安排的运输开始时间超过返回集中停放区域的2倍时,需要运输设备返回集中停放区域。否则,在当前加工设备附近的运输设备停放区域等待。

(8)当加工设备附近的运输设备停放区域被占用,导致后续运行至该加工设备的运输设备无法停放时,停放在该区域的运输设备需要返回集中停放区域。

在实际生产过程中,运输设备在车间内的移动时间包括:运输设备实际运输工件的时间和空载时间。为了清晰区分在生产加工任务中运输设备的运输类型,以便在运输组织与调度联合决策模型中区别考虑,参考YAN等[10]的研究,将运输时间共划分为3种类型,即运输设备运行至工作地的空载运输时间、运输设备返回集中停放区域的空载运输时间和运输设备的实际运输时间。

1.3 符号说明

j为车间内待加工工件编号j=1,2,…,n;i为工件的工序编号i=1,2,…,i(j);k为车间内虚拟单元编号k=1,2,…,K;m为车间内的加工设备编号m=1,2,…,M;α为车间内运输设备集中停放区域编号α=α1,α2,…,θ;T为每个虚拟单元内的运输设备编号T={σ1,σ2,…,σk};t=1,2,…,σk;φ为在加工设备m上加工的工序编号φ=1,2,…,φm;δ为运输设备t上被安排的工序编号,δ=1,2,…,γ。

hjk表示如果工件j属于虚拟单元k则为1,否则为0;gijkt表示如果Oij由虚拟单元内运输设备t负责运输则为1,否则为0;Bijm表示如果Oij在加工设备m上加工则为1,否则0;xmk表示如果加工设备m属于单元k则为1,否则0;Eiji′j′m表示如果Oij在设备m上先于Oi′j′被加工则为1,否则0;gijφm表示如果Oij是加工设备m上被安排的第φ个加工任务则为1,否则为0;gijδkt表示如果Oij在虚拟单元k中的运输设备t上被安排在第δ个被运输则为1,否则为0。

1.4 目标函数和约束条件

目标函数:

minf1=maxCij

(1)

(2)

约束条件:

(3)

(4)

(5)

STijkt≥C(i-1)j当i=2,3,…,i(j)

(6)

Sij≥ETijkt

(7)

(8)

ETijkt=STijkt+BijmB(i-1)jm′tmm′

(9)

(10)

(11)

(12)

(13)

目标函数(1)表示最大完工时间最小,目标函数(2)表示总运输时间最短。约束(3)表示Oij只能在一台加工设备上进行加工。约束(4)表示一道工序的开始加工时间与完成加工之间的关系,且不可中断。约束(5)表示工件的工序约束。约束(6)表示工件的实际开始运输时间大于等于该工件上一道工序的加工完成时间。约束(7)表示Oij的加工开始时间与实际运输结束时间之间的关系。约束(8)表示Oij的空载结束时间与实际运输开始时间的关系。约束(9)表示工件的实际运输结束时间与开始时间的关系。约束(10)表示运输设备返回空载与实际运输结束时间之间的关系。约束(11)表示每个工件的每道工序只能在一台运输设备完工运输。(12)表示返回空载开始时间与结束时间的关系。(13)表示开往工作地的空载开始时间与结束时间之间的关系。

2 算法设计

NSGA-II算法在调度模型的求解方面展现出较大的优势,其主要原因在于NSGA-II在全局搜索能力上表现出较高的优势。但是,NSGA-II也存在一定的局限性,如容易陷入局部最优和收敛较慢等问题。模拟退火算法具有很强的局部搜索能力,而粒子群算法具有操作简单,收敛速度快等优点。因此,将粒子群算法与NSGA-II的交叉、变异过程相融合,以提高算法的搜索能力。并将模拟退火算法的进化机制应用于NSGA-II的变异过程,以避免NSGA-II容易陷入局部最优的问题。

2.1 编码和解码

在编码过程中,采用三层编码设计,第一层为工序层、第二层为加工设备层,第三层为加工设备所属的单元层。具体编码方式如图1所示。

图1 染色体编码

考虑到运输时间对调度的影响,具体解码方式为:从τ=0时刻开始,根据染色体编码选取待加工工件的工序,若该工序所选加工设备被占用,则挂起该加工任务,直到被安排的加工设备被释放。根据公式(4)计算当前工序的完工时间。当所有的待加工工件被挂起,则τ=0时刻结束,令τ=τ+1。每个工件的第一道工序不需要被运输,运输时间为0。在之后的每个时刻,遍历所有工件族中的待加工工件的工序。当τ时刻,工件j的第i道工序被加工完成后,如果工件j的第i+1道工序在当前设备上加工,运输时间为0;如果该工件的第i+1道工序在其它设备上进行加工,判断本单元内运输设备是否可用。如果运输设备不可用,则挂起运输任务,直到有运输设备可以执行该加工任务。如果运输设备可用,根据公式(12),(13)计算运输设备的空载时间,并向前插入,尽可能保证工件j的第i道工序被加工完成后,运输设备恰好到达工件j的第i道工序加工设备前,并根据公式(9)计算当前工序的实际运输时间。如果单元内多台运输设备均可用,则随机选择一台运输设备完成当前运输任务。依次类推,直到所有工件所有工序被加工完成。

2.2 选择、交叉与变异操作

在选择过程中,选择二元锦标赛算法对种群进行选择操作。采用单点交叉和变异进行交叉与变异操作,在此期间,加工设备号与对应的加工设备所在的单元号一同变换。并将粒子群算法的更新规则融入到NSGA-II的交叉、变异过程中,以提高遗传算法的收敛速度。具体见章节2.4。

2.3 基于模拟退火的子代保留规则

当子代为父代的支配解时,为了扩大了种群的多样性,避免NSGA-II陷入局部最优。将模拟退火算法引入到NSGA-II和粒子群算法的融合算法中改变子代保留规则。具体步骤如下:

步骤1设定初温度T=ξT。

步骤2通过遗传算法的选择、交叉、变异操作得到新的子粒子群。

步骤4父代与子代合并形成新的种群。

2.4 算法流程

所提算法的总流程如下所示。

步骤1随机化初始种群。

步骤2对初始种群进行非支配排序,同时,找出全局最优个体。

步骤3父代与全局最优个体交叉、变异生成一代子粒子群。

步骤4设定退火温度T=ξT,更新全局最优个体。

步骤5各个粒子先后与全局最优个体进行交叉、变异操作。

步骤6若子代为父代的支配解,执行基于模拟退火的子代保留规则;否则舍弃子代。

步骤7对新的粒子群进行支配排序和计算拥挤度,并保留精英个体形成新的父代,更新全局最优个体。

步骤8判断是否达到最大代数,若是算法终止,否则返回步骤4。

3 数值仿真

3.1 算例及仿真数据与参数设置

算例采用FENG等[11]的算例数据生成方式和所划分的单元,对所构建的虚拟单元内外运输能力受限下的运输组织与异质并行机调度联合决策模型及所设计的改进NSGA-II算法,进行数值仿真和有效性验证。以小规模数据为例8×8×3表示车间有八个工件、八台加工设备、三个单元组成,中规模为10×10×4,大规模为15×10×4。三种规模的工件族划分别为:小规模(J1,J3,J5;J2,J7;J4,J6,J8),中规模(J1,J9;J2,J5,J8;J3,J7;J4,J6,J10),大规模(J1,J5,J12;J2,J9,J11,J13,J15;J4,J6,J8;J3,J7,J10,J14)。在移动距离生成方面,采用YAN等[10]的移动距离生成方式,运输距离属于[0,1]。为使所研究的虚拟单元内外运输能力受限下运输组织与调度联合决策问题既有典型性又不致过于复杂,在算例中暂假设每个单元内运输设备为2台,运输设备集中停放区域2个。

在算法参数设置方面,以反世代距离(IGD)为评价指标,并采用田口实验[12]进行参数设置。由于,本算例获得真实的Pareto解集比较困难。本研究采用所提算法与NSGA-II算法得到的非支配解集作为真实的Pareto解集,以对IGD进行计算。最终,得到的参数设置为:初始种群数100,交叉概率0.7,变异概率0.15;并设置迭代代数200,退火初始温度100,Boltzmann常数ξ=0.95。

计算机配置为:Windows 10系统,Intel(R)Core(TM)i7-7700 CPU@3.60GHz,16GB RAM,编程软件MATLAB R2017a。

3.2 算法对比

为了验证所提算法的性能,在同样的参数设置下,将其与标准NSGA-II算法进行结果对比。评价指标选取大部分多目标算法评价常采用的覆盖率指标(C-metric)、分布性指标(Δ)和综合指标IGD等三个指标[13,14]。在不同数据规模下,将每个算法均独立运行10次,分别计算出每个算法的三个性能指标的平均值。结果如表1所示。

表1 算法性能指标

通过覆盖率指标来看,所提算法的C测度值均大于NSGA-II,说明所提算法相较于NSGA-II能获得更好的解。尤其在中、大规模问题中,所提算法的C测度值明显优于NSGA-II算法,说明在中、大规模问题中所提算法具有明显优势。同时,算法的性能不受数据规模的改变而改变,具有较高的鲁棒性。从分布性指标来看,所提算法的分布性值更小,说明所提算法具有更好的搜索能力。同时,随着问题规模的增大,所提算法的分布性指标逐渐变小,说明其搜索能力对大规模问题更强。其原因在于NSGA-II与模拟退火算法的结合增强了算法的全局和局部搜索能力,避免了NSGA-II容易陷入局部最优的问题。

从IGD指标来看,所提算法在收敛性上具有较高的优势。另外,从运算时间上来看,所提算法在三种规模下的平均运算时间分别为135s,321s,532s,要明显优于NSGA-II算法的356s,673s,938s。这就说明NSGA-II与粒子群算法的融合提高了算法的收敛速度。

综上,所提算法明显提高了NSGA-II算法的综合性能。小规模算例所得到的甘特图如图2所示。

注:图中黑色矩形框代表工件的实际运输时间;m代表该工序被安排的加工设备,c代表该设备所属的单元图2 所提算法(15×10×4)甘特图

3.3 运输距离大小灵敏度分析

为了分析运输距离大小的变化和运输能力对调度结果的影响,采用YAN等[10]所采用的三种运输距离生成方式对运输距离和运输能力对虚拟单元生产调度结果的影响程度进行分析。在每种数据规模下,采用所提算法分别运行5次得到的运输距离大小对平均最大完工时间的影响曲线如图3所示。

图3 不同运输距离和运输能力下的最大完工时间平均值

从图3可以看出,随着运输距离的增大,工件的最大完工时间逐渐增大。同时,随着问题规模的增大,运输距离对调度结果的影响越大。从运输能力来看,运输能力受限情况下的最大完工时间相较于运输能力充足下的最大完工时间具有较大的差异性。因此,在大型复杂产品加工调度方案制定过程中对运输时间和运输能力的考虑是非常必要的。

4 结论

本文综合考虑虚拟单元内外运输能力受限、空载运输时间和异质并行机等因素,研究了虚拟单元运输组织与异质并行机调度联合决策问题。所构建的虚拟单元运输组织与调度联合决策模型更贴合企业生产实际。同时,提出了基于NSGA-II、粒子群算法和模拟退火算法的融合算法来对模型进行求解。通过小、中、大规模的算例测试来看,所提算法的鲁棒性、收敛性和解集的质量、多样性等方面表现出较好的优势。

在实际生产中,相同运输距离下,不同工件的运输时间可能存在一定差异性,且每个工件加工和运输任务的优先级也可能不同。在未来的研究中,可以进一步提高算法的求解能力,同时将不同工件的运输组织方式的差异性、每个工件加工和运输任务的优先级等因素纳入到虚拟单元内外运输组织与异质并行机调度联合决策问题中进行考虑。