[0100] 步骤S3225:若在多台加工设备上都可进行插入,重复步骤S321~S324,计算每种方案的缓存率f1,选择缓存率f1最大值的方案的最为最优方案,对所述初始化种群进行解码。
[0101] 优选地,步骤S323的批处理阶段解码包括以下步骤:
[0102] 步骤S3231:设定所述批处理阶段的划分依据函数fb:
[0103]
[0104] 式中,f2'与f3'为加工调度方案包含的任务最多的集合,μ为权重系数;
[0105] 步骤S3232:确定每个工件批处理工序的前驱加工阶段的完成时间,基于所述完成时间,工件重量和批处理机的阈值,确定批处理机可处理的窗口大小;
[0106] 步骤S3233:基于所述窗口大小,进行批处理组合,形成多个批处理方案;
[0107] 步骤S3234:计算所述批处理方案的fb,选择fb最大的方案作为最优方案;
[0108] 步骤S3235:重复步骤S3232~S3234,划分完所有的批处理工序和加工机器,对所述初始化种群进行解码。
[0109] 优选地,步骤S35的具体过程如下:
[0110] 在GoodGroup中,选择种群中每个优化目标的最优值的个体作为老师集合,其它个体作为学生集合,进行种群的知识迭代更新;之后基于混合算子的排序,采用轮盘赌策略选择种群中的个体进行变异,生成新解,若产生的新解根据PCA占优计算占优于旧解,则替换旧解,若新解不占优于旧解,则进行领域搜索;
[0111] 所述领域搜索包括以下三种领域:
[0112] 1)基于关键路径的领域;
[0113] 2)基于并行工序重新分配的领域,随机选择若干道并行工序,交换该工序和与其并行的工序的位置,并为之重新分配加工机器;
[0114] 3)批处理阶段领域,随机选择若干道批处理工序,按交货期升序重新分配工序与机器位置;
[0115] 在BadGroup中,以概率x选择种群中排序排名第一的个体作为老师,其它个体作为学生集合,进行种群的知识迭代更新;以x的概率将新解与GoodGroup中的排序最后的个体进行占优比较,若该个体不占优,则选择种群中排序第一的个体作为父代,进行POX交叉,产生新解替换旧解。
[0116] 本发明的优点在于:
[0117] 本发明构建了铸造全流程生产车间生产调度问题模型,并针对该模型改进求解算法,为铸造企业提高生产效益问题提供一套可选择的解决方案。
[0118] 改进的分组教学优化算法IGTOA,用于求解在约束条件下的铸造全流程的多目标智能调度问题的有效性和优越性。
[0119] 1)本发明根据铸件实际生产过程中的工艺约束特征与多目标特征,提出一种铸造全流程的多目标智能调度方法,进而实现了铸造生产调度理论在实际铸件生产中的应用,弥补了铸造全流程车间调度相关学术研究领域上的空白。
[0120] 2)本发明构建了铸造全流程生产车间生产调度问题模型,并针对该模型设计改进求解算法,以实际铸造企业生产数据作为实例,开发一套铸造全流程生产调度管理系统,为铸造企业提供一套可选择的解决方案。
[0121] 3)GTOA是一种模拟学生向老师学习的过程的算法,在迭代过程中,学生的知识水平向着教师的知识水平靠近,最后容易导致大部分学生知识水平与教师相同或相近,从而陷入局部最优。本发明针对车间调度类离散型优化问题,将学生分为GoodGroup与BadGroup两个小组,针对不同的小组设计了不同的教师选择与教学方案。在种群个体更新阶段,加入一种基于变异与交叉的动态搜索策略,避免算法过早收敛,加强算法的全局搜索能力。
附图说明
[0122] 图1为本发明的算法流程图;
[0123] 图2为本发明的在并行工序阶段的解码示意图;
[0124] 图3为本发明在批处理阶段的解码示意图;
[0125] 图4为四种算法Pareto第一前沿分布图;
具体实施方式
[0126] 下面结合本发明实施例中的附图,对本发明实施例中的技术方案进行清楚、完整地描述,显然,所描述的实施例仅是本发明一部分实施例,而不是全部的实施例。基于本发明的实施例,本领域普通技术人员在没有作出创造性劳动的前提下所获得的所有其他实施例,都属于本发明的保护范围。
[0127] 如图1所示,本发明实施例提供了一种铸造全流程的多目标智能调度方法,包括以下步骤:
[0128] 步骤S1:对目标车间设定预设条件、基本参数和约束条件,并基于最小完工时间、碳排放、机器负载和拖期/提前惩罚四个目标设定优化目标函数,构建车间调度模型。
[0129] 本发明实施例所构建的车间调度模型需要设定以下的预设条件:
[0130] 1)在零时刻,任意设备均可被使用,任意铸件均可被加工;
[0131] 2)加工过程中不可被中断;
[0132] 3)不同铸件间没有加工顺序约束,同一铸件除并行工序外,其它工序之间存在加工顺序约束;
[0133] 4)不同的工件之间没有加工任务的优先级;
[0134] 5)加工机器在首个工件到达后启动,完成最后一个工件加工后停机;
[0135] 6)批处理过程中不能增加或减少该批次工件数目;
[0136] 7)忽略机器间运输时间与运输能耗;
[0137] 8)规定设备的启动时间和启动状态下的能耗和碳排放忽略不计;
[0138] 9)批处理阶段的每一个批次总重量为改批次加工工件的重量之和;
[0139] 10)批处理机器每一个加工的总重量不能超过批处理机的最大承受重量;
[0140] 11)并行工序阶段的加工时间位于前阶段加工完成时间和后阶段加工开始时间之间。
[0141] 具体基本参数设置如下:
[0142] n:工件总数量;
[0143] m:加工设备总数量;
[0144] i:工件编号,i=1,2,…,n;
[0145] j:工件i的工序号,j=1,2,…,s;
[0146] M:加工机器集合;
[0147] Mh:第h台机器;
[0148] Oij:工件i的第j道工序;
[0149] Wbk:批次总重量;
[0150] Wi:工件i的重量;
[0151] Q:批处理机容量;
[0152] b:批次总数目;
[0153] Cijh:工序Oij在机器h上的处理时间;
[0154] STij:工序Oij的开始时间;
[0155] ETij:工序Oij在机器h上的完工时间;
[0156] Fpij:工序j‑1与工序j组成并行工序阶段;
[0157] STFpij:Fpij的开始时间;
[0158] ETFpij:Fpij的结束时间;
[0159] Fbnj:n个工件的第j道工序组成批处理;
[0160] STFbnj:Fbnj的开工时间;
[0161] ETFbnj:Fbnj的结束时间;
[0162] ETi:第i道工序的结束时间;
[0163] Th:机器h上的待机时间;
[0164] Ph:加工设备h的额定运行功率;
[0165] Ph':加工设备h的待机功率;
[0166] B:电力标煤换算系数;
[0167] EF:电能碳排放系数;
[0168] Cmax:最大完工时间;
[0169] E:最大碳排放量;
[0170] Wm:最大机器负载;
[0171] ET:总拖期惩罚;
[0172] Ci:工件i的最后一道工作完成时间;
[0173] Di:工件i的标准完成时间;
[0174] Ei:工件i的提前完成惩罚值;
[0175] Ni:工件i的拖期完成惩罚值;
[0176] Ti:工件i的最大总加工时间;
[0177] Tij:工序Oij的最大处理时间;
[0178] 决策变量:
[0179] Xijh:0‑1变量,工序Oij在加工设备h上加工时则Xijh=1,否则为0;
[0180] Yijk:0‑1变量,工序Oij属于批次k,则Yijk=1,否则为0。
[0181] 设置约束条件如下:
[0182] 1)除并行工序阶段外,其他工序阶段之间有着严格的加工次序约束,如公式所示:
[0183]
[0184] 2)行工序阶段的加工时间位于前阶段加工完成时间后面,如公式所示:
[0185]
[0186] 3)并行工序阶段的加工时间位于后阶段加工开始时间之前,如公式所示:
[0187]
[0188] 4)任意一个工序只能于一台机器上加工,如公式所示:
[0189]
[0190] 5)每一个工序不能属于多个批次,如公式所示:
[0191]
[0192] 6)批处理阶段的每一个批次总重量为改批次加工工件的重量之和,如公式所示:
[0193]
[0194] 7)每一个批次总重量不能超过批处理机的最大承受重量,如公式所示:
[0195]
[0196] 8)批处理的最早开工时间不早于该批次中工件的前驱工序完工时间,如公式所示:
[0197] STFbnj≥maxETij‑1i∈Fbnj
[0198] 根据上述设定的基本参数、预设条件和约束条件,以最小完工时间、碳排放、机器负载和拖期/提前惩罚四个目标设定优化目标函数如下所示:
[0199] 1)最小化完工时间:
[0200] minCm=max(Ci)
[0201] 2)碳排放:
[0202]
[0203] 3)机器负载:
[0204]
[0205] 4)拖期/提前惩罚:
[0206]
[0207] 步骤S2:对所述目标车间所有的加工调度方案进行编码,得到可行解集合;
[0208] 本发明实施例中采用MSOS整数编码的方式,以一组向量S=[Sj|Sm]表示车间加工调度方案的一个解,其中,Sj表示工件工序段,Sm表示加工设备选择段。
[0209] 具体地,如表1所示,已随机的一个解S=[1 2 3 1 2 1 2 3 3 1 2 3|2 2 1 1 2 2 1 1 2 2 1 2 1 1 2]为例,Sj中第一个位置的1表示工件1的O11,第8个位置的并且第二次出现的3表示工件3的O32,O32可选的加工设备集为{M3,M4},对应Sm中第8个位置的1,表示O32在加工设备M3上进行加工。
[0210] 通过上述的编码方法,生成可行解集合。
[0211] 表1
[0212]
[0213] 步骤S3:利用改进的分组教学优化算法IGTOA,求得所述可行解集合中的最优解。
[0214] 步骤S31:基于所述可行解集合,构建初始化种群;
[0215] 为了求得可行解集合对于多目标调度中的最优解,本发明实施例首先进行种群初始化;
[0216] 构建种群规模为N维度为D的混沌序列Y={Yd,d=1,2,…,D},Yd={Yid,i=1,2,…,N},混沌映射函数表达式如下:
[0217] Yi+1=4Yi3‑3Yi
[0218] ‑1
[0219] 通过混沌序列映射到解空间生成初始化种群X={Xi,i=1,2,…,N},Xi={Xid,d=1,2,…,D},Xid通过如下公式得到,
[0220]
[0221] 式中,Xub和Xlb分别表示个体位置序列随机值的上下界。
[0222] 通过如下公式计算初始种群X的反向种群BX:
[0223] BXid=Xlb+Xub‑Xid
[0224] 初始种群和反向种群均计算完毕后,将反向解与初始解进行比较,若反向解优于初始解,则替换初始解形成新的种群X。
[0225] 步骤S32:基于所述车间调度模型,从并行工序阶段和批处理阶段两个阶段设定解码算法,对所述初始化种群进行解码,计算所述种群的适应度;
[0226] 解码是将矢量还原成实际问题信息的过程,为了提高算法的有效性,本发明针对多阶段问题设计了一种分段式的解码规则来得到实际的加工顺序。对于并行工序阶段,引用了一种基于机器空闲时间集的先排序后插入式方法进行解码;对于批处理阶段,设计一种改进前瞻窗口策略的解码方法;设计一种全局优化方法加强不同阶段的解码方案的联系。
[0227] 定义三个方案衡量的依据:缓存率f1,能耗变化率f2,装载率f3。其中f1衡量并行工序阶段,f2与f3衡量批处理阶段。
[0228] 缓冲率f1表示在交货期的前提下,每个批次加工完成后平均每个工件剩余的时间,计算公式为:
[0229]
[0230]
[0231] 式中,dij表示Oij的理论交货期,s表示该阶段加工的工件个数。
[0232] 能耗变化率f2表示该方案的与插入前的能耗变化。
[0233]
[0234] 装载率f3表示机器的利用率,计算公式为:
[0235]
[0236] 并行工序阶段内两个并行工序没有加工顺序约束,为保证优化时模型的准确性,首先在不考虑工序并行的状态下进行排序,然后对并行工序的加工机器选择进行判断,最后判断能否进行最早空闲时间的插入,若有x台机器可以进行插入,则有x个方案,计算每个方案的f1。
[0237] 具体地,如图2所示,O1i与O1i‑1构成并行工序阶段,O1i‑1为前驱阶段,O1i+1为后续阶段。t={t1,t2,…,tn}为机器的空闲时间集。具体解码步骤如下:
[0238] 步骤S3221:不考虑工序并行的情况下对工件的工序O1i与O1i‑1分配,并获取O1i‑1与O1i的加工时间段以及O1i选择的加工机器Mh以及该在该机器上的加工时间CTijh,并获取前驱工序O1i‑2的完工时间Ts以及O1i‑1的开工时间Te;
[0239] 步骤S3222:获取O1i的加工机器的空闲时间集合t。
[0240] 步骤S3223:求集合t与时间段Ts~Te的交集,并按时间顺序对交集进行排序得到集合T';
[0241] 步骤S3224:将O1i在机器M3上的加工时间ETij与集合T'中的每一个元素ti进行对比,若满足ETij
[0242] 步骤S3225:若在m台机器上都可进行插入,则形成m种插入方案,重复步骤S3221~S3224,计算每种方案的f1,选择最大值的方案的作为暂定的方案,进行解码。
[0243] 针对实际企业的订单式生产,提出一种基于交货期的改进前瞻窗口规则,进行批处理阶段的解码。窗口的开始时间为批处理机器的最早空闲时间与前驱阶段完成时间中的较大者,窗口的大小为批处理机的加工阈值。假设n个工件的前驱工序完工时间t={t1,t2,…tn},工件的交货期为d={d1,d2,…,dn},批处理机器的加工阈值为Q。假设在第i个工件完成前驱阶段加工时,有H个任务在前瞻窗口内到达,则可以形成1+H个方案,计算每个方案的f2与f3。
[0244] 由于量纲不同,对两个依据进行归一化处理,用于确定每个批处理批次的划分依据fb。其计算公式为:
[0245]
[0246] f2和f3为第s个工件到达时该方案的能耗量与装载率。f2'与f3'为方案包含的任务最多的集合,μ为权重系数。计算每一个方案的fb值,并选择最大的作为最后方案。
[0247] 具体地,如图3所示,M4为批处理机器,工件的第j个工序为批处理阶段。解码步骤如下:
[0248] 确定每个工件的前驱加工阶段的完成时间,并将其以升序排序得到排序后的时间集合t'={t'1,t'2,…t'n}。根据完工时间,工件重量和批处理机的阈值确定求窗口大小。
[0249] 在窗口内依次进行不同的组批尝试,并确定其加工时间。在窗口内形成多个备选方案,分别计算每个方案的fb,选择fb最大的方案作为最终的方案。同机器上下一个前瞻窗口的开始时间不早于本窗口的结束时间。
[0250] 依次重复上述步骤直到划分完所有的批次和其加工机器,且每个工件的后续加工阶段最早开工时间不得小于他所在批次的完工时间。
[0251] 通过上述的分段解码方案对初始化种群解码后,计算所有方案的适应度。
[0252] 步骤S33:基于所述适应度,应用Pareto排序和PCA占优比较对所述种群进行排序;
[0253] 本发明通过将PCA降维和pareto排序相结合,并采用拥挤度计算的方法,设计一种混合算子进行个体占优比较。PCA常用于高维数据降维,提取数据的主要特征分量。
[0254] 本发明对初始化种群的适应度值进行PCA降维,得到降维后每个目标的权重向量w={w1,w2,…,wm},则种群个体的支配关系按如下的标准:
[0255]
[0256] 式中,a与b表示两个个体,fi(a)表示个体a在目标i上的值,wj为目标j的权重,如满足这一不等式,则表示个体a占优于个体b。
[0257] 之后再对种群进行Pareto排序,计算种群中个体的拥挤度,在Pareto排序基础上进行拥挤度排序。
[0258] 对于同属于一个级别且拥挤度相同的个体进行PCA占优比较,若表明A优于B,则A排序靠前,反之亦然。若降维后数值相同,则随机选择一个个体位于前列,重复进行上述过程,直到种群中的所有个体排序完成。
[0259] 步骤S34:将所述种群进行分组,其中排序靠前的一半分配到GoodGroup组,排序靠后的一半分配到BadGroup组;
[0260] 步骤S35:采用动态领域搜索方法对所述GoodGroup组中的种群进行更新得到较优种群;采用动态全局搜索方法对所述BadGroup组中的种群进行更新得到较劣种群。
[0261] GTOA是一种全局优化算法,在所有迭代中知识量都会向着教师的知识量靠近,容易陷入局部最优。本文针对车间调度类离散型问题,对GoodGroup和BadGroup分别设计了不同的教师选择与教学方案。在更新阶段加入一种基于变异与交叉的动态搜索策略,避免算法过早收敛,加强算法的搜索能力。动态搜索策略包括动态全局搜索和动态领域搜索。
[0262] 在GoodGroup中,选择种群中每个目标的最优值的个体作为老师集合。在进行知识迭代过程中随机选择集合中一个作为老师。在进行老师阶段与学生阶段的更新后,进行一种动态触发领域的搜索机制。流程如图1所示,具体流程为在进行知识更新后,对该组的新解进行基于混合算子的排序,再采用轮盘赌策略选择个体进行变异,若产生的新解根据PCA占优计算占优于旧解,则替换旧解,若新解不占优于旧解,则进行领域搜索,排序越靠前,被选中的概率就越大。针对多阶段调度模型,采用3种领域搜索结构:
[0263] 1.基于关键路径的领域。
[0264] 2.基于并行工序重新分配的领域。随机选择若干道并行工序,交换该工序和与其并行的工序的位置,并为之重新分配加工机器。
[0265] 3.批处理阶段领域。随机选择若干道批处理工序,按交货期升序重新分配工序与机器位置。
[0266] 在BadGroup中,以概率x选择种群中排序排名第一的个体作为老师。在个体进行老师阶段与学生阶段的更新后,为了避免种群陷入局部最优,采用一种动态触发的全局搜索机制。以x的概率将新解与GoodGroup中的排序最后的个体进行占优比较,若不占优该个体,则选择种群中排序第一的个体作为父代,进行POX交叉,产生新的子代替换旧解。
[0267] 步骤S36:将所述较优种群和较劣种群进行合并,当达到设定的迭代次数时,输出最优解,否则将合并后的种群作为初始种群,重新执行步骤S32~S36。
[0268] 以实际的某铸造企业生产数据为例,通过对生产实例进行实验分析。为评估本发明所采用IGTOA算法的性能,将其与GWO算法、帝国竞争算法ICA、多目标粒子群算法DPSO以及原NSGA‑II算法进行对比。每种算法四种算法均在Windows 10系统、CPU主频四核2.3GHz、运行内存8GB的计算机中运行,实验实施条件为MATLAB R2016a on an Intel Core i7 2.30GHz PC with 8.00GB of memory。将每种算法每次运行后得到的Pareto第一前沿解记录下来,四种算法的Pareto第一前沿解的三维分布如图4中(a)和(b)所示,其第一前沿的二位维分布如图4中的(c)(d)(e)(f)。由图可知所提算法获得的前沿排列在其他3种算法第一前沿的前列,说明所采用的IGTOA算法较其它三种算法寻优能力更强,性能更好。