控制与决策  2020, Vol. 35 Issue (10): 2475-2485  
0

引用本文 [复制中英文]

吴秀丽, 肖晓, 赵宁. 考虑装卸的柔性作业车间双资源调度问题[J]. 控制与决策, 2020, 35(10): 2475-2485.
[复制中文]
WU Xiu-li, XIAO Xiao, ZHAO Ning. Flexible job shop dual resource scheduling problem considering loading and unloading[J]. Journal of Southwest China Normal University (Natural Science Edition), 2020, 35(10): 2475-2485. DOI: 10.13195/j.kzyjc.2019.0267.
[复制英文]

基金项目

国家自然科学基金项目(51305024);国防基础科研计划项目(JCKY2018209C002)

作者简介

吴秀丽(1977-), 女, 副教授, 博士, 从事制造过程智能优化调度算法等研究, E-mail: wuxiuli@ustb.edu.cn;
肖晓(1995-), 女, 硕士生, 从事制造系统资源配置与调度的研究, E-mail: xiaoxiao3marbury@163.com;
赵宁(1978-), 男, 教授, 博士生导师, 从事复杂系统仿真与优化等研究, E-mail: nickzhao@me.ustb.edu.cn

通讯作者

吴秀丽, E-mail: wuxiuli@ustb.edu.cn

文章历史

收稿日期:2019-03-08
修回日期:2019-04-30
考虑装卸的柔性作业车间双资源调度问题
吴秀丽 , 肖晓 , 赵宁     
北京科技大学 机械工程学院,北京 100083
摘要:针对“研产混线”中各类制造资源利用率低、非加工时间过长、调度难度大的问题, 以生产中最紧缺的夹具资源为例, 提出考虑装卸的柔性作业车间双资源调度问题.首先, 以最小化完工时间和准结时间为目标建立该问题的数学优化模型; 然后, 设计快速非支配排序遗传算法对问题进行求解, 根据问题特性综合考虑两个目标并设计降准解码算法, 随机从交叉算子池和变异算子池中选择算子进行操作, 根据非支配等级和拥挤度选择进入下一代的个体; 最后, 通过数值实验表明, 针对考虑装卸的柔性作业车间双资源调度问题, 所提出算法能够有效求解该问题, 保证完工时间的同时降低准结时间.
关键词研产混线    柔性作业车间调度问题    双资源调度    夹具    准结时间    
Flexible job shop dual resource scheduling problem considering loading and unloading
WU Xiu-li , XIAO Xiao , ZHAO Ning     
School of Mechanical Engineering, University of Science and Technology Beijing, Beijing 100083, China
Abstract: To solve the problems of low utilization rate of manufacturing resources, long non-processing time and difficult scheduling in a "research and production mixed line" workshop, a flexible job shop dual resource scheduling problem considering fixture loading and unloading is proposed. Firstly, the mathematical optimization model of the problem is established to minimize the makespan and setup time. Then, a non-dominated sorting genetic algorithm is proposed to solve it. The decoding algorithm to reduce setup time is designed to balance the two objectives. The operator is randomly selected from the crossover operator pool and the mutation operator pool, and the next generation is selected according to the non-dominated level and the congestion degree. Finally, the results of numerical experiment show that the proposed algorithm can solve the problem effectively.
Keywords: research and production mixed line    flexible job shop scheduling problem    dual resource scheduling    fixture    setup time    
0 引言

造在研究型制造企业中, 研制件和批产件在同一条生产线上混合生产, 从而形成“研产混线”生产的制模式[1], 在我国尤以各类研究所的制造部为主.“研产混线”生产模式中, 科研试制产品和已经定型的批产件共同竞争同一条生产线上的制造资源, 如各种加工机器、工装夹具、刀具、量具等.已经定型的批产件工艺成熟, 所需制造资源明确; 研制件通常为最新研制产品的首次试制样件, 工艺尚需不断探索, 生产状态不稳定, 所需配套的生产资源也需要在试制过程中不断调整, 有时还需要设计专门的辅助工具, 如专门的夹具用于固定特殊外形的试制件.这种情况下, 专门夹具的不断更换造成了大量的非加工时间.国际生产与研究工程协会对欧美等国家的制造企业调查统计表明, 制造过程中95 %的时间消耗在非加工过程中[2].然而, 这些非加工过程并不创造价值, 反而造成了资源的浪费[3].因此, 如何高效调度“研产混线”生产过程中的各类生产资源, 减少非加工时间, 提高生产效率, 成为摆在决策者面前亟需解决的新问题.

此外, 研产混线车间产品种类多, 工艺复杂, 每道工序可在多台机器上加工, 属于典型的柔性作业车间调度问题(flexible job shop scheduling problem, FJSP).为此, 本文以“研产混线”生产中最紧缺的夹具资源为例, 探索考虑夹具装卸的柔性作业车间双资源调度问题(flexible job shop dual resource scheduling problem considering loading and unloading, FJSDRSP-LU).

装卸时间按照相关性可分为两类:一类是序列相关的装卸时间, 即装卸时间与机器前加工工序有关; 一类是序列无关的装卸时间, 即装卸时间仅与当前将要加工的工序相关, 与机器前加工的工序无关.第1类问题更加贴近实际的生产状况.

序列相关装卸时间还可细分成两种类型, 一种是装卸时间的长度与机器前一个加工工序和当前工序有关, 学者在各种生产模式中对其进行了研究. Heger等[4]在考虑序列相关装卸时间的动态流水车间中使用动态调整调度规则参数的方法对问题进行了求解. Benkalai等[5]利用迁移鸟算法求解了考虑序列相关装卸时间的置换流水车间调度问题. Nourali等[6]建立了考虑序列相关装卸时间的柔性作业车间调度问题的MIP模型, 并用粒子群算法进行求解. Sahin等[7]研究了U型装配线环境下的序列相关装卸时间以提高装配线的生产率.另一种是序列相关装卸时间与机器上历史加工工序相关[8], 这种情况常见于食品厂与化工厂, 需要对机器进行深度清理时发生.

针对序列无关装卸时间, Aydilek等[9]在两阶段装配车间的背景下, 考虑序列无关的装卸时间, 提出了一种新的混合模拟退火插入算法, 并通过实验验证了该算法与该领域的已知最优算法同样优秀.陶莎等[10]提出了集装箱码头上基于关键资源优先的装卸搬运策略. Aldowaisan等[11]针对考虑序列无关装卸时间的流水车间调度问题提出了改进的遗传算法和模拟退火算法, 证明改进算法优于标准的遗传算法和模拟退火算法.

综上所述, 学者研究了各种生产模式下序列相关和序列无关的装卸时间, 建立了各种问题模型, 并对不同模型设计了不同的方法进行求解.但现有研究中, 无论是序列相关装卸时间还是序列无关装卸时间, 都是工件的装卸时间, 很少有人研究夹具的装卸时间.而夹具的装卸造成车间存在大量的非加工时间, 影响车间的生产效率和设备的利用率.为此, 在“研产混线”生产模式的背景下, 本文考虑到紧缺资源夹具的装卸情况, 提出考虑夹具装卸的柔性作业车间双资源调度问题.

1 FJSDRSP-LU优化模型 1.1 问题描述

考虑装卸的柔性作业车间双资源调度问题可描述如下:有I个待加工工件, 共有M台机器, Q把夹具. Ji是工件i的工序集合, 每道工序可用机器为一个或多个, 且在不同机器上的加工时间不同; 工件在机器上的加工需要夹具资源, 不同工序可用夹具不同, 每道工序可用夹具为一个或多个.在加工时需要将夹具安装到机器上, 在加工结束需要将夹具从机器上卸载, 夹具在不同机器上的装卸时间不同.调度的目标是在满足约束的基础上, 选择每道工序的加工机器和夹具, 安排工序的加工顺序, 同时优化完工时间和准结时间.准结时间[12]是指为执行一项作业或加工一个工件, 事先准备工作和事后结束工作的时间, 即辅助作业时间.在本文中定义为夹具在机器上的装卸时间.

针对该问题的假设如下:

1) 同一时刻, 每台机器只能加工一道工序;

2) 同一时刻, 每把夹具只能安装在一台机器;

3) 每道工序的加工时间是确定的, 且事先已知;

4) 加工是非抢占式的, 每道工序一旦开始加工不能中断;

5) 夹具的装卸时间不可忽略, 且夹具在不同机器上的装卸时间不同;

6) 工件加工工艺顺序固定, 每道工序必须在其紧前工序完成之后才能进行后续工序.

为了便于理解, 给出一个3工件3工序5机器5夹具的例子, 如表 1表 2所示. 表 1展示了每道工序在可用机器上的加工时间及每道工序的可用夹具.如工件1的第1道工序O11, 可以在机器1和机器2上加工, 加工时间分别为14和12, O11可以用夹具1、夹具3、夹具5夹持进行加工. 表 2是各个夹具在不同机器上的装载时间和卸载时间.如夹具1在机器2上的装载时间是1.6, 卸载时间是0.7.

表 1 工件信息表
表 2 夹具装卸时间表
1.2 符号定义

模型中所涉及的符号定义如表 3所示.

表 3 符号定义
1.3 优化模型

在车间生产中, 决策者除了希望能够高效快速地完成所有加工任务之外, 还希望能够有效地利用生产设备.而夹具的装载与卸载时间是生产过程中必不可少的加工辅助时间, 却不创造生产价值, 是对资源的一种浪费.因此, 将完工时间和准结时间作为模型优化的目标.为了降低完工时间, 尽快完成所有加工任务, 车间在调度后续工序时会优先安排其在最早完工的机器上进行加工, 但并未考虑该机器上已经安装的夹具是否可用, 若机器上的夹具不可用, 则需要对夹具进行装卸, 这就造成了非加工时间.虽然完工时间减少, 但准结时间反而增加.二者存在“效益悖反”的关系, 在求解中需要同时兼顾这两个目标.

FJSDRSP-LU的数学模型如下:

(1)
(2)

s.t.

(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
(12)

式(1)和(2)是模型的两个目标:最小化完工时间和最小化准结时间.式(3)是工序Oij准结时间的计算公式, 是该工序所使用夹具的装载时间和卸载时间之和; 式(4)保证每道工序只能在一个机器上加工; 式(5)保证一道工序只能使用一个夹具; 式(6)表示工序Oij所用机器必须满足工件要求; 式(7)约束了工序Oij所用夹具必须满足工件可用夹具限制; 式(8)是工件的工艺约束要求; 式(9)表示工序开始时间必须在0时刻之后; 式(10)[13]表示同一机器同一时间只能加工一个工件; 式(11)约束同一夹具同一时间只能夹持一个工件; 式(12)是决策变量.

2 基于降准解码的NSGA-Ⅱ改进算法

双资源车间调度问题为Np-hard问题[14], 一般采用智能算法对其进行求解.如遗传算法[15-16]、免疫算法[17]等. FJSDRSP-LU在双资源的基础上考虑了夹具的装卸, 求解难度更大, 且FJSDRSP-LU问题同时考虑完工时间和准结时间两个目标, 是多目标优化问题.快速非支配排序遗传算法(non-dominated sorting genetic algorithm, NSGA-Ⅱ)在求解多目标优化问题上表现良好[18].因此, 选择NSGA-Ⅱ算法对问题进行求解.

2.1 编码

本文采用FJSP问题的经典编码方式——基于工序的编码方式.工件i出现的第j次, 即为工件i的第j道工序. 表 1中描述的问题, 可如图 1所示编码.采用此种编码方式能够有效地进行交叉变异, 减少不可行解的产生.

图 1 编码
2.2 降准解码算法

FJSDRSP-LU问题可分为机器分配、夹具分配、工件排序3个子问题, 在解决上述问题时要考虑资源之间的时间冲突, 包括机器资源的冲突和夹具资源的冲突, 同时还要将夹具的装卸时间考虑在内.在编码过程中只考虑了工序的调度顺序, 并未对每道工序指定加工机器和所用的夹具, 所以要在解码过程中为每道工序选择机器和夹具.本文在间隙挤压法[19]的基础上设计该问题的解码算法.该解码算法能够降低准结时间, 故将其称为降准解码算法.

间隙挤压法的核心是有效利用已安排工序之间的加工间隙.在该工序的可用机器上寻找所有可用间隙, 即间隙的开始时间要大于紧前工序的完工时间且间隙时长满足工序的加工时间, 优先将工序插入到间隙中进行加工.降准解码算法是在间隙挤压法的基础上, 考虑机器和夹具资源的使用情况, 在保证完工时间的前提下, 优先选择已安装可用夹具机器上的间隙, 以减少夹具的装卸次数, 达到降低准结时间的目的.降准解码算法的主要难点在于间隙前后资源使用情况的判断, 需要根据资源使用情况对已安排工序进行相应的修改.降准解码算法的流程如图 2所示.由图 2可以看出, 机器和夹具资源的使用可分为4种情况.

图 2 降准解码算法流程

情况1  机器未使用, 夹具未使用.对于该种情况, 该工序的开始时间为0, 需要先装载当前夹具, 加工工件, 再卸载夹具, 是一个完整的加工工程.

情况2  机器未使用, 夹具已使用.若当前机器未使用, 夹具已使用, 则需要寻找已安排使用该夹具的工序, 查找夹具资源上存在的间隙, 依次判断间隙情况, 根据情况在间隙前后夹具的工序上增加装卸过程.

机器未使用, 夹具已使用可能存在的3种情况, 如图 3所示.横坐标为时间, 纵坐标为机器, ‘1-2-3’表示工件1的第2道工序用夹具3夹持进行加工.每个工序一般由3部分组成, 即夹具的装载时间, 工序的加工时间和夹具的卸载时间.灰色框表示当前需要插入加工的工序, 斜线框表示增加的夹具装卸时间.在图 3(a)中, 当前组合选择的夹具3已在机器2上连续使用, 在间隙时间上也被占用.所以, 在使用时需先在机器2上卸载夹具3, 安装到机器1上加工工件1的第2道工序, 为了不影响间隙后工件的加工, 夹具3在机器1上使用完成后需卸载, 重新安装在机器2上.在图 3(b)图 3(c)中, 夹具3在间隙时间空闲, 在当前选择机器上可直接使用.

图 3 机器未使用, 夹具使用

情况3  机器已使用, 夹具未使用.若机器已使用, 夹具未使用, 则需要对已安排在此机器上加工的工序进行判断, 查找机器资源上存在的间隙.根据情况在间隙前后机器加工的工序上增加对应夹具的装卸过程.

机器已使用, 夹具未使用可能存在的3种情况, 如图 4所示. 图 4(a)图 4(b)中所选机器上无夹具资源, 可直接装载夹具进行加工. 图 4(c)中, 间隙前后工序使用相同的夹具3, 在间隙时间上机器也被夹具3占用, 在插入当前工序进行加工时, 需要卸载上一工序使用的夹具3, 为了不影响间隙后加工任务的进行, 在完成当前工序的加工后需要卸载所使用的夹具1, 并安装间隙后工序所需的夹具3.

图 4 机器使用, 夹具未使用

情况4  机器已使用, 夹具已使用.若机器已使用, 夹具已使用, 则需要查找机器资源和夹具资源共同的可用间隙, 结合夹具间隙前后和机器间隙前后的使用情况判断是否需要对夹具进行装卸.具体步骤如下.

step 1:当前资源组合下机器记为m, 夹具记为f, 以集合CP记录各工序的完工时间, 以集合TmTf记录机器m和夹具f上的间隙, 以Mf记录各时刻机器m上夹具情况, Fm记录夹具f各时刻所在机器情况.

step 2:对于工序Oij, 通过CP找到Oij紧前工序的完工时间ETi(j-1), 作为当前工序的最早开始时间, 找到当前资源组合下的工序加工时间tijm, 夹具装载时间sqm和夹具卸载时间dqm.

step 3:通过TmTf计算得到当前资源组合下的机器m和夹具f的共同间隙集合Tmf.

step 4:在Tmf中按照时间先后对间隙进行判断.根据MfFm判断间隙前后资源情况, 按照决策树(图 5)修改相应夹具资源的装卸情况.当前间隙工序加工和夹具的装卸所需时间为tall, 若修改后间隙满足间隙开始时间tmf'≥ETi(j-1), 则间隙长度LTmf'≥ tall, 工序Oij插入当前间隙加工.

图 5 决策树

step 5:若所有修改后间隙都不能满足所需时间, 则工序Oij安排在(机器m, 夹具f)组合排序队列的最后进行加工, 结束.

图 5是根据间隙资源情况判断是否需要修改间隙前后相应资源装卸情况的决策树.间隙前后m机器上的夹具记为f1f2, k1k2表示f1f2的装卸状态, k1k2为1表示夹具已卸载, 为0表示夹具未卸载; 间隙前后f夹具所在机器记为m1m2, k3k4表示fm1m2上的装卸情况, k3k4为1表示夹具已卸载, 为0表示夹具未卸载. m机器间隙前后工序的开始时间记为ST1和ST2, f夹具间隙前后工序开始时间记为ST3和ST4.

图 5所示, 根据资源使用情况判断后对应有以下处理方式.

A:在机器m上装载夹具f, 加工工序Oij, 卸载夹具f.

B:在机器m1上增加夹具f的卸载过程, 在机器m上装载夹具f, 加工工序Oij, 卸载夹具f, 在机器m2上增加夹具f的装载过程.

C:在机器m上增加夹具f1的卸载过程, 装载夹具f, 加工工序Oij, 卸载夹具f, 最后增加夹具f2的装载过程.

D:直接在间隙加工工序Oij.

E:在机器m上增加夹具f1的卸载过程, 装载夹具f, 加工工序Oij, 卸载夹具f, 增加夹具f2的装载过程; 在机器m1上增加夹具f的卸载过程, 在机器m2上增加夹具f的装载过程.

F:间隙前机器m省去f1的卸载过程, 加工工序Oij, 卸载夹具f1(ff1相同).

G:在机器m上装载夹具f, 加工工序Oij, 间隙后m机器省去夹具f2的装载过程(ff2相同).

对于(机器, 夹具)的K种组合, 按照规则选择合适的组合, 具体规则如下.

step 1:选择完工时间最小的组合, 如果组合不唯一, 则转入step 2;

step 2:选择准结时间最小的组合, 如果组合不唯一, 则转入step 3;

step 3:随机选择一个组合.

2.3 变异和交叉

NSGA-Ⅱ算法通过交叉产生新的基因组合, 生成新的染色体以扩大算法的搜索空间; 通过变异改善算法的局部搜索能力.不同的算子搜索方向和力度并不相同, 为尽可能全面地搜索解空间, 建立交叉算子池和变异算子池.当满足概率时从中随机选择一种算子作为当前算子进行操作.交叉算子和变异算子从文献[20]中选择.交叉算子包括线性次序交叉、基于位置的交叉和基于顺序的交叉.变异算子包括反转变异、多点变异、位移片段和插入变异.

2.4 快速非支配排序和拥挤度计算

通过非支配等级判断群体中个体之间的支配关系.非支配解是指不被任何其他可行解支配的解.将父子代种群合并后, 根据种群中个体之间的支配关系, 确定各个个体的非支配等级.拥挤度表示某一非支配等级中某个解与其他解的分布情况, 如图 6所示.

图 6 拥挤度

根据文献[21], 个体Xi的拥挤度crowdi定义如下:

(13)

其中: K是目标的个数, fmax(k)k目标的最大值, fmin(k)k目标的最小值, f(k)(i+1)和f(k)(i-1)是Xi+1Xi-1k目标值.

父子代种群合并后, 根据非支配等级和拥挤度在父子代合并后的种群中选择进入下一代的个体[22], 具体步骤如下.

step 1:最小非支配等级个体直接进入下一代种群, 若个体数量小于种群数量, 则进入step 2;若个体数量大于种群数量, 则随机选择两个个体, 淘汰拥挤度小的个体直到个体数量等于种群数量.

setp 2:从剩余个体中随机选择两个个体, 选择非支配等级小的个体进入下一代种群; 若非支配等级相同, 则选择拥挤度大的个体进入下一代种群, 直到下一代种群中个体数量等于种群数量.

选择非支配等级小的个体能够保留种群中的较优个体, 选择拥挤度大的个体能够保证种群的多样性.

3 数值实验 3.1 实验设计

本文算法在Intel Core i5-7200U, Windows 10操作系统和Matlab 2018b编程环境下编译通过.设置算法参数为种群规模Num=50, 迭代次数Iters=500, 交叉概率Pc=0.8, 变异概率Pm=0.2.

在柔性作业车间调度问题国际标准Brandimarte算例[23]的基础上增加夹具资源, 构造本文的实验算例MK-F系列.夹具数量和机器数量相同, Mmax为工序可用机器最大数量, 每道工序可用夹具数量服从U[0, Mmax]上的均匀分布, 根据夹具数量随机生成工序的可用夹具集, 夹具在机器上的装载时间和卸载时间均服从U[0, 2]的均匀分布.

为了验证算法在考虑装卸的柔性作业车间双资源调度问题上的求解性能, 设计如下数值实验.

1) 解码算法性能实验:通过对比降准解码算法与按完工时间解码算法和按准结时间解码算法, 验证降准解码算法的优化效果.

2) 算法对比实验:分别使用NSGA-Ⅱ算法与MODE算法求解MK-F系列算例, 以测试本文算法的寻优能力.

3.2 解码算法性能实验

通过对比降准解码算法与按完工时间解码算法和按准结时间解码算法, 验证降准解码算法的有效性.分别用3种解码算法求解MK-F01问题.运行结果如表 4所示.

表 4 解码算法结果对比表

Pareto结果分布对比图如图 7所示.由图 7可以看出, 降准解码算法求得的Pareto解分布优于其他两种解码算法.降准解码算法求得的解支配了按完工时间解码算法得到的解, 在相同的完工时间下, 降准解码算法求得的解的准结时间更小.与按准结时间解码算法对比, 虽然二者所得结果相互支配, 但按准结时间解码算法求得的解的完工时间过长.降准解码算法能够在保证完工时间的同时, 大大降低准结时间, 使车间能够在保证资源利用率的同时高效完成加工任务.

图 7 解码算法Pareto解对比图

为了更直观地分析这3种解码方式, 分别取3种解码算法得到的典型方案(图 7中已标出)进行对比. 图 8~图 11分别是按完工时间解码算法、按准结时间解码算法、按降准解码算法得到的解在机器资源上的调度甘特图和在夹具资源上的调度甘特图.图中横坐标为时间, 纵坐标为机器, 竖线框为夹具的装载过程, 横线框为卸载过程, 下排标号为工件号, 上排标号为工序加工所使用的夹具号.

图 8 按完工时间解码甘特图
图 9 按准结时间解码甘特图
图 10 降准解码甘特图
图 11 夹具资源甘特图

图 8可以看到, 按完工时间解码算法没有考虑准结时间, 导致夹具多次装卸, 尤其在机器3上, 非加工过程多, 造成资源浪费, 准结时间增加.而在图 9中, 按准结时间解码算法为了减少准结时间, 将工序尽可能地安排在已安装可用夹具的机器上进行加工, 造成机器负载不平衡, 大部分工序集中在机器2上, 完工时间过长.如图 10所示, 降准解码算法在保证完工时间的同时尽可能地减少夹具的装卸次数, 保证资源的利用率, 降低了准结时间.由此可见, 降准解码算法能够有效地平衡两个优化目标. 图 11图 10对应在夹具资源上调度甘特图.

3.3 算法对比实验

为了评估NSGA-Ⅱ算法的性能, 用多目标差分进化算法(multi-objective differential evolution algorithm, MODE)进行对比. MODE是一种基于群体进化的算法, 算法的基本思想是:通过差分变异和交叉产生新种群, 然后基于Pareto思想从父子代种群中选择合适的个体, 从而产生子代种群. MODE算法的编码选择基于工序的编码方式, 解码采用降准解码算法, 差分变异方式采用混合DE/best/1策略和DE/rand/1策略[24], 基个体从种群或Pareto解集中选择, 差向量从种群中随机选择两个个体计算得到. MODE算法全局搜索能力较强, 但是局部搜索能力较差, 所以, 设置缩放因子F随着迭代次数在[F0, 2F0]之间自适应变化, 使F在算法搜索前期为较大值, 能够充分探索解空间, 随着迭代次数的增加, F逐渐减小, 算法能够保留优良的基因, 避免最优解被破坏. F的计算公式[25]如下:

(14)
(15)

其中: Iters是算法的最大迭代次数, Cn是当前迭代次数, F0为缩放因子的初始值.

多目标优化一般从收敛性、多样性及分布均匀性3个层面来评价获得的解集.常用指标有当代距离[26]、超体积(Hypervolume)指标、理想解偏差、间隔距离(Spread)等等.本文选取两种较为公正的性能指标[27]来度量所得解集, 这两种指标分别是Hypervolume指标和Spread指标.

1) Hypervolume指标[27]: Hypervolume指标评价方法由Zitzler等[28]提出, 它表示解集中的个体与参考点在目标空间中所围成的超立方体的体积.选择坐标原点作为参考点, 并将两目标值分别归一化之后进行计算. Hypervolume指标可以度量解集的收敛性, Hypervolume指标越小, 算法的收敛性越好.

2) Spread指标[29]: Spread指标评估的是解的多样性及解的分布均匀性. Spread值越小, 解集的多样性及分布均匀性越好. Spread计算公式如下所示:

(16)

其中: Z是Pareto解集中解的个数, dii点与最近点的欧式距离, ddi的平均值.

MODE算法求得的实验结果与NSGA-Ⅱ算法求得的实验结果如表 5所示. 表 5展示了NSGA-Ⅱ算法和MODE算法在10个算例下求得的实验结果和性能指标结果, 包括完工时间、准结时间、Hypervolume指标和Spread指标.每个指标下左列是MODE算法的结果, 右列是NSGA-Ⅱ算法的结果.对于Hypervolume指标, NSGA-Ⅱ算法在10个算例下均优于MODE算法; 对于Spread指标, NSGA-Ⅱ算法得到了9组算例的较优结果.因此NSGA-Ⅱ算法在解的收敛性、分布性和多样性上均优于MODE算法. 图 12是NSGA-Ⅱ算法与MODE算法10个算例下某次Pareto解的分布对比图.其中空心圆点为NSGA-Ⅱ算法的求解结果, 星号点为MODE算法的求解结果.

表 5 实验结果对比表
图 12 Pareto解对比图

图 12可以看到, 大部分问题NSGA-Ⅱ算法求得的解优于MODE算法得到的解, 其解支配了通过MODE算法寻找得到的解, 只有在MK-F 05算例中, 两个算法求得的解相互支配.所以, 相比于MODE算法, NSGA-Ⅱ算法寻优能力更强, 求得的解的质量更好.

4 结论

在“研产混线”生产模式下, 产品种类多, 加工工艺复杂, 机器上的夹具不断更换, 生产过程中大量时间在进行非加工过程, 造成加工资源的浪费.在此背景下, 本文提出了考虑装卸的柔性作业车间双资源调度问题, 以最小化完工时间和准结时间为目标建立了FJSDRSP-LU的多目标数学优化模型.在NSGA-Ⅱ算法的框架下, 考虑问题特性设计降准解码算法对该问题进行求解.实验结果显示, 所提出的降准解码算法能够有效平衡完工时间和准结时间两个目标, NSGA-Ⅱ算法能够有效求解所提出的问题.

本文提出的问题在资源限制上只考虑了夹具和机器, 为了更贴近实际加工环境, 刀具、人力等资源限制可作为进一步的研究内容.

参考文献
[1]
田超, 李蕾.航空企业基于瓶颈管理的科研与批产混线生产管控研究[C]. 2012年中国航空学会管理科学分会学术交流会论文集.北京: 中国航空学会, 2012: 717-726.
(Tian C, Li L. Research on management and batch production control of aviation enterprises based on bottleneck management[C]. Proceedings of the Academic Exchange Meeting of the Management Science Branch of China Aviation Society in 2012. Beijing: Chinese Society of Aeronautics and Astronautics, 2012: 717-726.)
[2]
李峥峰.多时间因素作业车间调度问题的研究与工程应用[D].武汉: 华中科技大学机械科学与工程学院, 2010.
(Li Z F. Research on job shop scheduling problems with multi-time and its engineering application[D]. Wuhan: School of Mechanical Science and Engineering, Huazhong University of Science and Technology, 2010.)
[3]
Allahverdi A. The third comprehensive survey on scheduling problems with setup times/costs[J]. European Journal of Operational Research, 2015, 246(2): 345-378. DOI:10.1016/j.ejor.2015.04.004
[4]
Heger J, Jürgen B, Hildebrandt T, et al. Dynamic adjustment of dispatching rule parameters in flow shops with sequence-dependent set-up times[J]. International Journal of Production Research, 2016, 54(22): 6812-6824. DOI:10.1080/00207543.2016.1178406
[5]
Benkalai I, Rebaine D, Gagné C, et al. Improving the migrating birds optimization metaheuristic for the permutation flow shop with sequence-dependent set-up times[J]. International Journal of Production Research, 2017, 55(20): 6145-6157. DOI:10.1080/00207543.2017.1327732
[6]
Nourali S, Imanipour N. A particle swarm optimization-based algorithm for flexible assembly job shop scheduling problem with sequence dependent setup times[J]. Scientia Iranica, 2014, 21(3): 1021-1033.
[7]
Sahin M, Kellegöz T. Increasing production rate in U-type assembly lines with sequence-dependent set-up times[J]. Engineering Optimization, 2016, 49(8): 1401-1419.
[8]
Lee K, Lei L, Pinedo M. Production scheduling with history-dependent setup times[J]. Naval Research Logistics, 2012, 59(1): 58-68. DOI:10.1002/nav.21472
[9]
Aydilek A, Aydilek H, Allahverdi A. Minimising maximum tardiness in assembly flowshops with setup times[J]. International Journal of Production Research, 2017, 55(24): 7541-7565. DOI:10.1080/00207543.2017.1387300
[10]
陶莎, 胡志华, 盛昭瀚. 基于关键资源优先的三级装卸搬运分时协调策略[J]. 控制与决策, 2015, 30(8): 1441-1446.
(Tao S, Hu Z H, Sheng Z H. Time-dependent coordination strategies for key resource prioritized three-stage handling operations[J]. Control and Decision, 2015, 30(8): 1441-1446.)
[11]
Aldowaisan T, Allahverdi A. Total tardiness performance in M-machine no-wait flowshops with separate setup times[J]. Intelligent Control and Automation, 2015(6): 38-44.
[12]
罗志清, 王润孝, 雷建, 等. 机械制造辅助加工时间定额研究[J]. 机床与液压, 2004, 32(12): 62-64.
(Luo Z Q, Wang R X, Lei J, et al. A Study on the assistant mechanical time quota[J]. Machine Tool & Hydraulics, 2004, 32(12): 62-64.)
[13]
吴秀丽, 张志强, 李俊青. 求解离散调度问题的双机制头脑风暴优化算法[J]. 控制与决策, 2017, 32(9): 1583-1590.
(Wu X L, Zhang Z Q, LI J Q. A brain storm optimization algorithm integrating diversity and discussion mechanism for solving discrete production scheduling problem[J]. Control and Decision, 2017, 32(9): 1583-1590.)
[14]
李兢尧, 黄媛, 王军强, 等. 求解扩展双资源约束作业车间调度的分支种群遗传算法[J]. 西北工业大学学报, 2016, 34(4): 635-641.
(Li J Y, Huang Y, Wang J Q, et al. Branch population genetic algorithm for extension dual resource constrained job shop scheduling problem[J]. Journal of Northwestern Polytechnical University, 2016, 34(4): 635-641.)
[15]
关叶青, 朱颖, 谢乃明. 考虑多成本约束的柔性作业车间制造资源动态分配模型[J]. 控制与决策, 2018, 33(11): 2037-2044.
(Guan Y Q, Zhu Y, Xie N M. Dynamic allocation model of manufacturing resources in flexible job shop considering multi-cost constraints[J]. Control and Decision, 2018, 33(11): 2037-2044.)
[16]
李兢尧, 孙树栋, 黄媛, 等. 求解双资源约束车间调度问题的继承式双目标遗传算法[J]. 控制与决策, 2011, 26(12): 1761-1767.
(Li J Y, Sun S D, Huang Y, et al. Double-objective inherited genetic algorithm for dual resource constrained job shop[J]. Control and Decision, 2011, 26(12): 1761-1767.)
[17]
徐新黎, 应时彦, 王万良. 求解模糊柔性Job-shop调度问题的多智能体免疫算法[J]. 控制与决策, 2010, 25(2): 171-178.
(Xu X L, Ying S Y, Wang W L. Fuzzy flexible job-shop scheduling method based on multi-agent immune algorithm[J]. Control and Decision, 2010, 25(2): 171-178.)
[18]
Deb K, Agrawal S, Pratap A, et al. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-Ⅱ[C]. Proceedings for the International Conference on Parallel Problem Solving From Nature. Berlin, Heidelberg: Springer, 2000.
[19]
Wu X L, Sun Y J. A green scheduling algorithm for flexible job shop with energy-saving measures[J]. Journal of Cleaner Production, 2018, 172: 3249-3264. DOI:10.1016/j.jclepro.2017.10.342
[20]
Akay B, Yao X. Automated scheduling and planning[M]. Berlin: Springer, 2013: 191-224.
[21]
周严伟.基于快速非支配排序遗传算法的多目标流水车间调度研究[D].广州: 华南理工大学数学学院, 2015.
(Zhou Y W. Research of multi-objective flow shop scheduling based on fast non-dominated sorting genetic algorithm[D]. Guangzhou: School of Mathematics, South China University of Technology, 2015.)
[22]
吴秀丽, 崔琪. 考虑可再生能源的多目标柔性流水车间调度问题[J]. 计算机集成制造系统, 2018, 24(11): 2792-2807.
(Wu X L, Cui Q. Multi-objective flexible flow shop scheduling problem with renewable energy[J]. Computer Integrated Manufacturing Systems, 2018, 24(11): 2792-2807.)
[23]
Brandimarte P. Routing and scheduling in a flexible job shop by tabu search[J]. Annals of Operations Research, 1993, 41(3): 157-183. DOI:10.1007/BF02023073
[24]
丁青锋, 尹晓宇. 差分进化算法综述[J]. 智能系统学报, 2017, 12(4): 431-442.
(Ding Q F, Yin X Y. Research survey of differential evolution algorithms[J]. CAAI Transactions on Intelligent Systems, 2017, 12(4): 431-442.)
[25]
侍倩.基于差分进化算法的多目标优化问题的研究[D].上海: 东华大学信息科学与技术学院, 2016.
(Shi Q. Research on the multi-objective optimization problem based on differential evolution algorithm[D]. Shanghai: School of Information Science and Technology, Donghua University, 2016.)
[26]
韩玉艳, 李俊青, 桑红燕, 等. 离散NSGA-Ⅱ求解带有限缓冲区的多目标批量流水线调度问题[J]. 聊城大学学报:自然科学版, 2018, 31(1): 89-96.
(Han Y Y, Li J Q, Sang H Y, et al. Discrete NSGA-Ⅱ for multi-objective lot-streaming flow shop scheduling problem with limited buffers[J]. Journal of Liaocheng University: Natural Science Edition, 2018, 31(1): 89-96.)
[27]
贺利军, 李文锋, 张煜. 基于灰色综合关联分析的多目标优化方法[J]. 控制与决策, 2020, 35(5): 1134-1142.
(He L J, Li W F, Zhang Y. Multi-objective optimization method based on grey synthetic incidence analysis[J]. Control and Decision, 2020, 35(5): 1134-1142.)
[28]
Zitzler E, Thiele L. Multi-objective evolutionary algorithms: A comparative case study and the strength pareto approach[J]. IEEE Transactions on Evolutionary Computation, 1999, 3(4): 257-271. DOI:10.1109/4235.797969
[29]
Gong M, Jiao L, Du H, et al. Multi-objective immune algorithm with nondominated neighbor-based selection[J]. Evolutionary Computation, 2008, 16(2): 225-255. DOI:10.1162/evco.2008.16.2.225