王真(1976—), 女, 教授, 博士, 主要从事系统建模仿真与优化研究, (E-mail)
随着现代制造业的飞速发展,企业在生产效率和生产能耗方面有越来越高的要求,智能生产车间的自动化程度逐渐提高。主要研究作业车间自动导引车(automated guided vehicle,AGV)的智能绿色物流调度问题。首先,建立以降低AGV能耗和最优AGV路径为目标的AGV物流调度优化模型;然后,提出一种以任务排序为约束的改进遗传粒子群算法;最后,以某针织车间的实际物流调度为例对文中方法进行验证。计算结果表明,文中提出的AGV物流调度模型能够较好地模拟AGV绿色调度耗能问题,提出的改进遗传粒子群算法具有较快的收敛速度和较好的寻优能力。
With the rapid development of modern manufacturing industry, enterprises are required to have higher production efficiency and lower production energy consumption, resulting in more improvement of the automation degree of intelligent production workshop. This paper mainly studied green intelligent logistics scheduling of automated guided vehicle(AGV) in job shop. AGV logistics scheduling optimization model was establised to reduce the energy consumption of AGV and optimize AGV path. A genetic particle swarm optimization (PSO) algorithm was proposed with task sequencing as the constraint condition. Finally, the actual logistics scheduling of a knitting shop was taken as example to verify the method proposed in this paper. The calculation results show that the AGV logistics scheduling model proposed can well simulate the AGV green scheduling energy consumption, and the improved genetic particle swarm optimization algorithm presents a faster convergence speed and a better optimization ability.
国内大多数纺织企业的生产车间仍在采用传统的人工物流调度方式,由人力将加工好的产品运送至检验区。传统人工调度方式效率较低,劳动强度较大,工人工作内容较为繁琐。因此,采用自动化设备代替人工完成车间物流调度有重要的现实意义。自上世纪50年代以来,欧美等发达国家运用AGV已有60余年,采用AGV代替人工完成车间物流调度的技术相对成熟。AGV在生产车间的任务是将成品料箱运送至检验区。采用AGV进行运输可以减少工人劳动强度,降低企业人力成本,提升车间生产效率。如何对AGV进行路径寻优,使其既能根据车间的实际生产情况提供及时有效的调度,又能减少因调度不及时而造成的能耗浪费,在保证调度高效的同时,积极响应国家节能减排“十二五”规划。
目前,在多载AGV路径优化问题的任务分配策略上,绍雪松等[
在路径优化问题的模型建立上,Knust S等[
在路径优化问题的求解方法上,Zheng等[
在车间物流调度的绿色要素上,朱光宇等[
在大量的文献中,很少考虑AGV物流调度中的绿色能耗问题。但在车间实际生产过程中AGV长时间运转能耗较大。因此,考虑AGV能耗因素的绿色物流调度具有实际意义。文中主要研究车间AGV的路径寻优,力求减少任务发生后AGV的响应时间与行驶时间,并引入AGV调度能耗指标作为绿色要素。将AGV响应时间、行驶时间、能耗指标进行加权统一,提出多目标的多载AGV路径寻优模型。并采用包含任务排序约束的改进GA-PSO(genetic particle swarm optimization)[
AGV小车初始停靠在A处(卸货点),当AGV接收到调度任务时便驶向需要运送成品料箱的任务节点,在任务节点处进行料箱的装载,当AGV装载满
建模时参照如下规定:
1) AGV搬运时间固定,不超时。
2) AGV工作内容是:将满载袜子的成品料箱装载上AGV,再将其运送至全检车间卸货点卸载。
3) 在零时刻开始时,所有的织机设备与AGV均处于可运行状态。
4) 保证所有织机的原材料充足,不会出现缺乏原材料的情况。
5) 织机旁的空料箱充足,不考虑料箱的供应情况。
6) 织机在加工袜子时不中断,不会出现任何故障情况。
7) AGV保持匀速前进,其运载时间只与物流路径的长短有关。
8) AGV的容量有限制,其满载容量不能超过
9) 当AGV收到装载任务后,在其相应的任务点只执行一次装载任务。
10) 在零时刻所有AGV的装载任务已知,且每个任务的发生时间均不一样。
参数设置如
符号含义表
Symbol meaning
符号 | 含义 |
任务 |
|
AGV小车在任务点装载料箱的时间 | |
任务 |
|
AGV的行驶速度 | |
暂存区卸货点A到任务 |
|
暂存区卸货点A到任务 |
|
任务 |
|
任务 |
|
任务 |
|
完成任务 |
在针织车间的物流调度中,影响AGV调度时间的主要因素是AGV在任务点间的行驶时间和AGV收到装载任务后的待响应时间。文中假设AGV保持匀速行驶,AGV在任务点中的行驶时间只与其行驶路径的长短有关。AGV在整个调度流程中并不是时时刻刻都处于运行状态,倘若没有新的任务安排AGV可能会在A处或者上一项任务的任务点处等待。AGV运行时的功率比等待时的功率要大很多。所以,如何找到一条较优的路径使AGV的运行时间、响应时间、能耗都较少是问题的关键。
因此,综合考虑AGV运行时间、响应时间和能耗等主要因素,建立绿色物流调度模型如下:
式中:
式(2)为AGV调度时间目标函数。式(3)为AGV调度能耗目标函数。式(4)表示任务
式(1)为总目标函数,将车间物流调度的多目标模型转换成单目标模型。为了对AGV运行时间、响应时间、能耗这3种因素的权重系数进行定量,采用层次分析法(AHP)[
权重评定表
Weight evaluation table
矩阵判断标度 | ||||||
0.295 | 0.649 | 0.056 | ||||
1 | 1/3 | 7 | ||||
3 | 1 | 9 | 29.5% | 4.7% | 5.6% | |
1/7 | 1/9 | 1 |
传统GA-PSO方法在解决复杂的搜索问题时,容易产生早熟收敛,出现局部寻优能力较差,算法收敛速度过慢等情况。为了解决这一问题,笔者在任务排序规则引入算法的交叉变异操作中,提出了一种改进GA-PSO方法,在算法的交叉变异中引入任务排序来约束粒子的进化方向,使粒子的进化方向更加明确,有效避免了算法早熟收敛和收敛速度过慢的情况。
根据建立的车间AGV绿色物流调度模型,采用任务排序作为粒子的编码方式,每个粒子均表示AGV的一个目标装载任务,粒子的编号即为任务发生的时间顺序,例如,编号为3的粒子表示第3个发生的任务。粒子的先后顺序即为AGV装载成品料箱的先后顺序,例如,个体的编码为(3, 6, 4, 7, 1, 2, 8, 5),即任务的执行顺序为先执行第3个发生的任务再执行第6个发生的任务以此类推直至所有任务完成。
假设AGV满载为4个成品料箱,在完成4个装载任务后小车需要回到A点进行卸载,卸载完成后再继续完成任务。所以,AGV的实际行驶路线需要考虑在满载后驶向卸货点卸货的情况。例如,个体的编码为(3, 6, 4, 7, 1, 2, 8, 5),则AGV的实际行驶路线为(3, 6, 4, 7, A, 1, 2, 8, 5, A),AGV先后完成3, 6, 4, 7号任务的装载后回到A点卸载,再依次完成1, 2, 8, 5号任务的装载后回到A点卸载。
文中采用十字交叉法来进行交叉操作,并以任务序列作为其中一组。所需要交叉的位置片段是任务发生的先后顺序(任务编号)与任务序列的差值决定的。选择差值最大和最小的两个任务的位置来作为交叉片段的两端。将任务序列的片段与群体极值相应的片段进行交叉更新。更新后得到的任务序列中如果有任务重复,即用未包含的任务来代替重复的任务。
例如:任务编号(1, 2, 3, 4, 5, 6, 7, 8)
初始任务序列(3, 6, 4, 7, 1, 2, 8, 5)
↓
差值(-2, -4, -1, -3, 4, 4, -1, 3)
↓
交叉片段(*, 6, 4, 7, 1, *, *, *)
↓
极值(5, 1, 8, 4, 3, 2, 6, 7)
极值片段(*, 1, 8, 4, 3, *, *, *)
↓
更新后的任务序列(3, 1, 8, 4, 3, 2, 8, 5, )
↓
新任务序列(3, 1, 8, 4, 6, 2, 7, 5)
文中采用位置互换的方式来进行遗传变异操作,并以任务序列作为其中一组。选择任务序列中与任务发生的先后顺序(任务编号)的差值最大的和最小的两个任务作为一组变异任务,再选择任务序列中与任务编号的差值第二大的和第二小的两个任务作为一组变异任务。将每组两个任务的位置互换来进行变异操作的更新。
例如:初始任务序列(3, 6, 4, 7, 1, 2, 8, 5)
任务编号(1, 2, 3, 4, 5, 6, 7, 8)
↓
差值(2, 4, 1, 3, -4, -4, 1, -3)
↓
变异的位置(*, 6, *, *, 1, *, *, *)(*, *, *, 7, *, 2, *, *)
↓
新任务序列(3, 1, 4, 2, 6, 7, 8, 5)
初始粒子在经过改进算法任务排序约束的交叉变异操作之后,会得到一个新的粒子。为了寻找最优解并减少不必要的运算,只有在新粒子的适应度更优的情况下才对粒子进行更新。
改进GA-PSO算法流程图
The flow chart of improved GA-PSO algorithm
文中以某智能针织车间作为研究对象,采用MATLAB软件平台[
车间任务点分布图
Task point distribution of workshop
AGV小车从A点出发,经可行的路径前往发出装载任务的织袜机所对应的任务点处,将装满成品袜子的料箱装载上AGV,再前往下一个目标任务点,直至AGV装满4个成品料箱,AGV达到满载,遂驶往A点处进行卸载。卸载完成后再返回针织车间运载新的任务料箱,如此往复循环直到完成所有装载任务。
AGV的运行功率与等待功率通过咨询相关AGV供应商获得,拟采用AGV小车的运行功率为144 W,等待功率为36 W。
将选取的智能针织车间的目标时间段的起始时刻定为模型的零时刻,12个目标装载任务的发生时刻
运载任务数据表
Launch mission data sheet
编号 | 织袜机号 | 任务点 | |
1 | 9 | 5 | 9 |
2 | 36 | 18 | 16 |
3 | 49 | 25 | 21 |
4 | 42 | 21 | 120 |
5 | 38 | 19 | 137 |
6 | 8 | 4 | 180 |
7 | 15 | 8 | 343 |
8 | 28 | 14 | 369 |
9 | 32 | 16 | 514 |
10 | 33 | 17 | 677 |
11 | 43 | 22 | 720 |
12 | 13 | 7 | 789 |
通过目标函数确定适应度函数,再利用文中的改进算法进行求解。得到AGV小车的行驶路径与其相应的适应度值,从时间优先、能耗优先、综合优先三方面对调度方案进行考量。时间优先采用式(2)作为适应度函数,能耗优先采用式(3)作为适应度函数,综合优先采用式(1)作为适应度函数。3种调度策略的最优解如
计算结果表
Table of results
调度方案 | 最佳任务先后顺序 | 最佳路径任务点顺序 | 最优适应度值 |
时间优先 |
1 2 3 4 5 6 7 |
0 5 18 25 21 0 19 4 |
141.95 |
能耗优先 |
3 1 4 2 6 5 7 8 |
0 25 5 21 18 0 4 19 |
1 931.8 |
综合目标 |
1 2 3 4 5 6 7 |
0 5 18 25 21 0 19 4 |
268.17 |
从调度时间、调度能耗两方面对比上述3种调度方案,结果如
结果评价表
Result evaluation
路径规划 | 调度时间 | 调度能耗 |
时间优先路径规划 | 141.95 | 2 025.0 |
能耗优先路径规划 | 160.19 | 1 931.8 |
综合目标路径规划 | 142.04 | 1 955.8 |
由
文中所采用的改进GA-PSO方法与常规GA-PSO方法的调度平均解对比结果,如
算法对比表
Algorithm comparison
参数 | 文中改进遗传粒子群算法 | 常规遗传粒子群算法 |
运行次数 | 20 | 20 |
调度时间平均解 | 142.43 | 146.12 |
调度能耗平均解 | 1 944.55 | 1 980.71 |
综合调度平均解 | 268.97 | 276.04 |
文中所采用的改进GA-PSO方法与常规GA-PSO方法的算法收敛对比结果如
运行三次的算法迭代对比图
Comparison diagram of algorithm iteration running three times
运行十次的算法迭代对比图
Comparison diagram of algorithm iteration running ten times
任务较多时的算法迭代对比图
Comparison diagram of algorithm iteration with more tasks
针对作业车间的AGV绿色物流调度问题,综合考虑了AGV的调度时间和调度能耗,根据调度时AGV的实际运作情况,建立了车间物流调度的时间与能耗指标优化模型。由于多载AGV的调度问题属于NP-hard[
Wang J B, Hou L Y, Li W, et al. Simulating an AGV scheduling in job workshop for optimal configuration[J]. Advanced Materials Research, 2014, 926: 1562-1565.
邵雪松, 高雨翔, 宋瑞鹏, 等.多目标复合AGV调度系统建模及在电力计量检定中的应用[J].江苏电机工程, 2016, 35(5): 24-27.
SHAO Xuesong, GAO Yuxiang, SONG Ruipeng, et al. Multi-target compounded AGV scheduling system modeling and application in electric power metering calibration[J]. Jiangsu Electrical Engineering, 2016, 35(5): 24-27.(in Chinese)
朱云飞, 楼佩煌, 钱晓明, 等.基于改进合同网协议的作业车间调度方法研究[J].机械设计与制造工程, 2018, 47(3): 97-102.
ZHU Yunfei, LOU Peihuang, QIAN Xiaoming, et al. Research on shop scheduling problem based on the improved contract net protocol[J]. Machine Design and Manufacturing Engineering, 2018, 47(3): 97-102.(in Chinese)
Knust S, Shakhlevich N V, Waldherr S, et al. Shop scheduling problems with pliable jobs[J]. Journal of Scheduling, 2019, 22(6): 635-661.
Mousavi M, Yap H J, Musa S N, et al. Multi-objective AGV scheduling in an FMS using a hybrid of genetic algorithm and particle swarm optimization[J]. PLoS One, 2017, 12(3): 0169817.
徐云琴, 叶春明, 曹磊.含有AGV的柔性车间调度优化研究[J].计算机应用研究, 2018, 35(11): 3271-3275.
XU Yunqin, YE Chunming, CAO Lei. Research on flexible Job-Shop scheduling problem with AGV constraints[J]. Application Research of Computers, 2018, 35(11): 3271-3275.(in Chinese)
韩曙光, 季园园.车间内多周期混合收送货物流调度优化研究[J].浙江理工大学学报(社会科学版), 2017(6): 497-504.
HAN Shuguang, JI Yuanyuan. Research on optimization of multicycle logistics scheduling problem with pickup and delivery in assembly plant[J]. Journal of Zhejiang Sci-Tech University(Social Sciences Edition), 2017(6): 497-504.(in Chinese)
Ghasemzadeh H, Behrangi E, Abdollahi Azgomi M. Conflict-free scheduling and routing of automated guided vehicles in mesh topologies[J]. Robotics and Autonomous Systems, 2009, 57(6/7): 738-748.
Zheng Y, Xiao Y J, Seo Y. A tabu search algorithm for simultaneous machine/AGV scheduling problem[J]. International Journal of Production Research, 2014, 52(19): 5748-5763.
罗辞勇, 卢斌, 陈民铀, 等.组合粒子群优化和分布估计的多目标优化算法[J].重庆大学学报, 2010, 33(4): 31-36.
LUO Ciyong, LU Bin, CHEN Minyou, et al. Hybrid multiobjective particle swarm optimization and estimation of distribution algorithm[J]. Journal of Chongqing University, 2010, 33(4): 31-36.(in Chinese)
曾强, 杨育, 王小磊, 等.应用需求时间窗的柔性作业车间调度优化模型[J].重庆大学学报, 2011, 34(2): 86-94.
ZENG Qiang, YANG Yu, WANG Xiaolei, et al. Optimal model and algorithm for flexible job-shop scheduling problem based on demand time window[J]. Journal of Chongqing University, 2011, 34(2): 86-94.(in Chinese)
Nouiri M, Bekrar A, Jemai A, et al. An effective and distributed particle swarm optimization algorithm for flexible job-shop scheduling problem[J]. Journal of Intelligent Manufacturing, 2018, 29(3): 603-615.
朱光宇, 徐文婕.考虑能耗与质量的机床构件生产线多目标柔性作业车间调度方法[J].控制与决策, 2019, 34(2): 252-260.
ZHU Guangyu, XU Wenjie. Multi-objective flexible job shop scheduling method for machine tool component production line considering energy consumption and quality[J]. Control and Decision, 2019, 34(2): 252-260.(in Chinese)
Wang H, Jiang Z G, Wang Y, et al. A two-stage optimization method for energy-saving flexible job-shop scheduling based on energy dynamic characterization[J]. Journal of Cleaner Production, 2018, 188: 575-588.
王雷, 蔡劲草, 石鑫.基于改进遗传算法的多目标柔性作业车间节能调度问题[J].南京理工大学学报, 2017, 41(4): 494-502.
WANG Lei, CAI Jincao, SHI Xin. Multi-objective flexible job shop energy-saving scheduling problem based on improved genetic algorithm[J]. Journal of Nanjing University of Science and Technology, 2017, 41(4): 494-502.(in Chinese)
Huo T Q, Zhang J X, Wu X J. Cluster analysis based on GAPSO evolutionary algorithm[M]//Communications in Computer and Information Science. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011: 207-213.
Saaty T L. Decision making: the analytic hierarchy and network processes (AHP/ANP)[J]. Journal of Systems Science and Systems Engineering, 2004, 13(1): 1-35.
Trefethen L N. Spectral methods in MATLAB[M]. Society for Industrial and Applied Mathematics, 2000.
Wu H P, Huang M, Wang X W. A mixed integer mathematical programming optimization model for the NP-hard industrial processes scheduling problem[J]. Advanced Materials Research, 2013, 645: 290-294.
Schlechtendahl J, Keinert M, Kretschmer F, et al. Making existing production systems Industry 4.0-ready[J]. Production Engineering, 2015, 9(1): 143-148.