国内大多数纺织企业的生产车间仍在采用传统的人工物流调度方式,由人力将加工好的产品运送至检验区。传统人工调度方式效率较低,劳动强度较大,工人工作内容较为繁琐。因此,采用自动化设备代替人工完成车间物流调度有重要的现实意义。自上世纪50年代以来,欧美等发达国家运用AGV已有60余年,采用AGV代替人工完成车间物流调度的技术相对成熟。AGV在生产车间的任务是将成品料箱运送至检验区。采用AGV进行运输可以减少工人劳动强度,降低企业人力成本,提升车间生产效率。如何对AGV进行路径寻优,使其既能根据车间的实际生产情况提供及时有效的调度,又能减少因调度不及时而造成的能耗浪费,在保证调度高效的同时,积极响应国家节能减排“十二五”规划。
目前,在多载AGV路径优化问题的任务分配策略上,绍雪松等[2]提出了一种基于车辆行驶距离、任务等待时间与搬运任务优先级的AGV多目标负荷任务调度模型。朱云飞等[3]采用增强学习方式对作业车间的任务分配过程进行强化学习,以此为评价机制来确定调度任务的分配方案。
在路径优化问题的模型建立上,Knust S等[4]研究了一种新型流水作业模型和开放作业模型来解决柔性车间调度问题。Maryam Mousavi等[5]围绕提高AGV运行效率这一问题,研究了AGV的任务调度、最小车辆数以及时间成本的多目标优化。徐云琴等[6]建立了使用AGV搬运的柔性车间调度模型,研究了AGV最优调度方案和最佳AGV数量。韩曙光等[7]采用考虑时间窗的多周期混合收送货物流调度模型,研究循环供料与周期的关系。Ghasemzadeh等[8]基于网状拓扑提出了无冲突调度路径模型,该模型可以在产生路径冲突时选择另一条最短路径。
在路径优化问题的求解方法上,Zheng等[9]提出了一种基于禁忌搜索算法的混合整数线性最优化模型来解决加工机床和AGV的同时调度问题。罗辞勇等[10]提出组合粒子群优化和分布估计的多目标优化算法,将粒子群优化算法的全局搜索能力与分布估计算法良好的学习和局部搜索能力相结合,使组合算法在基准函数ZDT1~ZDT3, ZDT6和ZDT6-1上获得的Pareto解集具有较好的收敛性与多样性。曾强等[11]提出了一种基于"需求时间窗"的作业车间调度问题优化方法,针对模型提出并设计了一种基于多阶段混合变异的禁忌搜索算法,利用"逆序变异"和"基因段交换变异"搜索最优解。Nouriri等[12]以最大完成时间最小化为目标,采用改进粒子群算法求解该问题。
在车间物流调度的绿色要素上,朱光宇等[13]建立考虑完工时间、空闲时间、加工质量及机器能耗的多目标柔性作业车间调度模型,提出一种基于直觉模糊集相似度的遗传算法,通过直觉模糊集相似度值选出最满意解。Wang等[14]提出了作业的综合模型用来揭示其动态特征,实现节能调度优化。王雷等[15]建立以最大完工时间,机器功耗,员工舒适度为目标的多目标函数,使用加权方法初始化种群,通过快速解码获取适应度值。
在大量的文献中,很少考虑AGV物流调度中的绿色能耗问题。但在车间实际生产过程中AGV长时间运转能耗较大。因此,考虑AGV能耗因素的绿色物流调度具有实际意义。文中主要研究车间AGV的路径寻优,力求减少任务发生后AGV的响应时间与行驶时间,并引入AGV调度能耗指标作为绿色要素。将AGV响应时间、行驶时间、能耗指标进行加权统一,提出多目标的多载AGV路径寻优模型。并采用包含任务排序约束的改进GA-PSO(genetic particle swarm optimization)[16]来求解该路径寻优模型,对多载AGV在针织车间的实际投入运行有重要意义。
1 AGV物流调度描述与建模 1.1 问题描述AGV小车初始停靠在A处(卸货点),当AGV接收到调度任务时便驶向需要运送成品料箱的任务节点,在任务节点处进行料箱的装载,当AGV装载满k个料箱后便驶回A处进行卸载任务,卸载完成后再开始执行新的装载任务。而在实际生产过程中AGV可能因为之前的任务未完成导致新的任务发生时不能及时前往任务点装载料箱,导致AGV待响应时间较长,所以如何以较少的AGV待响应时间、较短的AGV行驶路径来完成料箱的运载任务是研究的关键。
建模时参照如下规定:
1) AGV搬运时间固定,不超时。
2) AGV工作内容是:将满载袜子的成品料箱装载上AGV,再将其运送至全检车间卸货点卸载。
3) 在零时刻开始时,所有的织机设备与AGV均处于可运行状态。
4) 保证所有织机的原材料充足,不会出现缺乏原材料的情况。
5) 织机旁的空料箱充足,不考虑料箱的供应情况。
6) 织机在加工袜子时不中断,不会出现任何故障情况。
7) AGV保持匀速前进,其运载时间只与物流路径的长短有关。
8) AGV的容量有限制,其满载容量不能超过k个成品料箱。
9) 当AGV收到装载任务后,在其相应的任务点只执行一次装载任务。
10) 在零时刻所有AGV的装载任务已知,且每个任务的发生时间均不一样。
参数设置如表 1所示,有目标任务的集合为X=(1, 2, 3, 4...n),j为i的下一项任务(j=i+1),i∈X,j∈X。
在针织车间的物流调度中,影响AGV调度时间的主要因素是AGV在任务点间的行驶时间和AGV收到装载任务后的待响应时间。文中假设AGV保持匀速行驶,AGV在任务点中的行驶时间只与其行驶路径的长短有关。AGV在整个调度流程中并不是时时刻刻都处于运行状态,倘若没有新的任务安排AGV可能会在A处或者上一项任务的任务点处等待。AGV运行时的功率比等待时的功率要大很多。所以,如何找到一条较优的路径使AGV的运行时间、响应时间、能耗都较少是问题的关键。
因此,综合考虑AGV运行时间、响应时间和能耗等主要因素,建立绿色物流调度模型如下:
$ T E=T_{z}+q_{3} * E, $ | (1) |
$ T_{z}=q_{1} * \sum\limits_{j=2}^{n} D_{j}+q_{2} * \sum\limits_{i=1}^{n-1} \sum\limits_{j=2}^{n} t_{i j}, $ | (2) |
$ E=\sum\limits_{i=1}^{n-1} \sum\limits_{j=2}^{n}\left(t_{i j} * p+\left|t_{i}-T_{j}\right|\right)-\sum\limits_{j=2}^{n} D_{j}, $ | (3) |
$ {\rm s.t }\\ ~~~~t_{i j}=S_{i j} / V, $ | (4) |
$ 当i=k a, a=(1, 2, 3, 4 ...)时S_{i j}=d_{i+} d_{j}, $ | (5) |
$ t_{j}=T_{j}+D_{j}+t_{i j}+Z, $ | (6) |
$ D_{j}=t_{i}-T_{j}, $ | (7) |
$ D j=0, 当 ti<T j 时, $ | (8) |
式中:q1,q2,q3为权重系数;p为AGV小车的运行功率与等待功率的比值。
式(2)为AGV调度时间目标函数。式(3)为AGV调度能耗目标函数。式(4)表示任务i处到任务j处的AGV行驶时间。式(5)表示AGV装载满k个成品料箱后回到起始点A卸货,再去执行下一项任务。式(6)表示任务j完成的时刻。式(7)表示完成任务i时,任务j已经发生了的时间即AGV的响应时间。式(8)表示之前所有任务均已完成,后续任务仍未发生,AGV在任务i处原地待命。
式(1)为总目标函数,将车间物流调度的多目标模型转换成单目标模型。为了对AGV运行时间、响应时间、能耗这3种因素的权重系数进行定量,采用层次分析法(AHP)[17]进行赋值。采用矩阵判断标度,对矩阵中各要素的重要性进行定量显示。构造判断矩阵,运用线性变换计算各部分权重,经过一致性检验后,得到合适的权重系数如表 2所示。
传统GA-PSO方法在解决复杂的搜索问题时,容易产生早熟收敛,出现局部寻优能力较差,算法收敛速度过慢等情况。为了解决这一问题,笔者在任务排序规则引入算法的交叉变异操作中,提出了一种改进GA-PSO方法,在算法的交叉变异中引入任务排序来约束粒子的进化方向,使粒子的进化方向更加明确,有效避免了算法早熟收敛和收敛速度过慢的情况。
2.1 算法编码根据建立的车间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点卸载。
2.2 以任务排序为约束的遗传交叉操作文中采用十字交叉法来进行交叉操作,并以任务序列作为其中一组。所需要交叉的位置片段是任务发生的先后顺序(任务编号)与任务序列的差值决定的。选择差值最大和最小的两个任务的位置来作为交叉片段的两端。将任务序列的片段与群体极值相应的片段进行交叉更新。更新后得到的任务序列中如果有任务重复,即用未包含的任务来代替重复的任务。
例如:任务编号(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)
2.3 以任务排序为约束的遗传变异操作文中采用位置互换的方式来进行遗传变异操作,并以任务序列作为其中一组。选择任务序列中与任务发生的先后顺序(任务编号)的差值最大的和最小的两个任务作为一组变异任务,再选择任务序列中与任务编号的差值第二大的和第二小的两个任务作为一组变异任务。将每组两个任务的位置互换来进行变异操作的更新。
例如:初始任务序列(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)
2.4 算法流程图初始粒子在经过改进算法任务排序约束的交叉变异操作之后,会得到一个新的粒子。为了寻找最优解并减少不必要的运算,只有在新粒子的适应度更优的情况下才对粒子进行更新。
文中以某智能针织车间作为研究对象,采用MATLAB软件平台[18],在4.00 GB RAM/3.20 GHz的计算机上计算验证所提出的模型和算法的有效性与准确性。以该车间在某时间段内总共接收到12个成品料箱运载任务为例,对任务顺序进行优化排序以获得更优的调度方案。算法采用的粒子个体数目为200个,迭代次数为100次。
图 2为智能针织车间任务点分布图。车间内54台织袜机两两相对布置,每两台机器共用一个料箱装载点,总共27个任务点。为方便计算将任务点位置与AGV行驶路径标准化,任务点与路径均处于图 2网格上,图 2中每格长宽均为0.8 m。图 2中黑色的线条表示AGV的行驶路径,黑色的圆圈表示每个任务装载点,黑色的菱形A表示全检区AGV卸货点亦是AGV的初始停靠点。
AGV小车从A点出发,经可行的路径前往发出装载任务的织袜机所对应的任务点处,将装满成品袜子的料箱装载上AGV,再前往下一个目标任务点,直至AGV装满4个成品料箱,AGV达到满载,遂驶往A点处进行卸载。卸载完成后再返回针织车间运载新的任务料箱,如此往复循环直到完成所有装载任务。
AGV的运行功率与等待功率通过咨询相关AGV供应商获得,拟采用AGV小车的运行功率为144 W,等待功率为36 W。
将选取的智能针织车间的目标时间段的起始时刻定为模型的零时刻,12个目标装载任务的发生时刻Ti,及所对应的任务点如表 3所示。
通过目标函数确定适应度函数,再利用文中的改进算法进行求解。得到AGV小车的行驶路径与其相应的适应度值,从时间优先、能耗优先、综合优先三方面对调度方案进行考量。时间优先采用式(2)作为适应度函数,能耗优先采用式(3)作为适应度函数,综合优先采用式(1)作为适应度函数。3种调度策略的最优解如表 4所示。
从调度时间、调度能耗两方面对比上述3种调度方案,结果如表 5所示。
由表 5可知,着力于时间优先的路径规划其调度能耗较高,着力于能耗优先的路径规划调度时间又很长。文中所提出的综合目标路径规划在保持调度时间较优的情况下,有效降低了调度能耗,既拥有趋于最优的调度时间又拥有趋于最优的调度能耗。
3.3 算法对比文中所采用的改进GA-PSO方法与常规GA-PSO方法的调度平均解对比结果,如表 6所示。
文中所采用的改进GA-PSO方法与常规GA-PSO方法的算法收敛对比结果如图 3、图 4、图 5所示(适应度采用综合适应度函数)。图中黑色实线条为文中改进算法的迭代过程,黑色虚线条为常规遗传粒子群算法的迭代过程。图 3、图 4为处理12个目标任务的算法迭代过程。图 5为处理24个目标任务的算法迭代过程。
图 3和图 4分别为执行12项任务时运行3次和运行10次的算法迭代过程,对比两图可看出文中的改进GA-PSO方法在每次运行时相较于常规GA-PSO方法具有更快的收敛速度,寻优能力更强。图 4和图 5分别为执行12项任务和24项任务的算法迭代过程,对比两图可看出在任务项较多时文中的GA-PSO方法的收敛速度和寻优能力优势依旧明显。
4 结束语针对作业车间的AGV绿色物流调度问题,综合考虑了AGV的调度时间和调度能耗,根据调度时AGV的实际运作情况,建立了车间物流调度的时间与能耗指标优化模型。由于多载AGV的调度问题属于NP-hard[19]问题,因此,提出了一种寻优能力更强的改进GA-PSO方法,该算法在常规GA-PSO方法的基础上引入同时考虑调度时间与调度能耗的任务排序策略,以此来约束粒子的进化方向,从而使算法的收敛速度更快,并通过实际案例验证了文中所提出的改进GA-PSO方法具有更好的寻优能力,对解决作业车间的绿色物流调度问题有较大的实际意义。对于更加细化的问题,如AGV充电对调度时间和调度能耗的影响,可增加目标函数的约束函数进行研讨, 后续可深入研究。随着工业4.0[20]的不断推进,企业的智能化水平越来越高,AGV的智能调度将迈向更高的台阶,多AGV协同调度将成为未来研究的主流。
[1] |
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. |
[2] |
邵雪松, 高雨翔, 宋瑞鹏, 等. 多目标复合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) |
[3] |
朱云飞, 楼佩煌, 钱晓明, 等. 基于改进合同网协议的作业车间调度方法研究[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) DOI:10.3969/j.issn.2095-509X.2018.03.019 |
[4] |
Knust S, Shakhlevich N V, Waldherr S, et al. Shop scheduling problems with pliable jobs[J]. Journal of Scheduling, 2019, 22(6): 635-661. DOI:10.1007/s10951-019-00607-9 |
[5] |
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. |
[6] |
徐云琴, 叶春明, 曹磊. 含有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) DOI:10.3969/j.issn.1001-3695.2018.11.017 |
[7] |
韩曙光, 季园园. 车间内多周期混合收送货物流调度优化研究[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) |
[8] |
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. |
[9] |
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. DOI:10.1080/00207543.2014.910628 |
[10] |
罗辞勇, 卢斌, 陈民铀, 等. 组合粒子群优化和分布估计的多目标优化算法[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) |
[11] |
曾强, 杨育, 王小磊, 等. 应用需求时间窗的柔性作业车间调度优化模型[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) |
[12] |
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. DOI:10.1007/s10845-015-1039-3 |
[13] |
朱光宇, 徐文婕. 考虑能耗与质量的机床构件生产线多目标柔性作业车间调度方法[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) |
[14] |
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. DOI:10.1016/j.jclepro.2018.03.254 |
[15] |
王雷, 蔡劲草, 石鑫. 基于改进遗传算法的多目标柔性作业车间节能调度问题[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) |
[16] |
Huo T Q, Zhang J X, Wu X J. Cluster analysis based on GAPSO evolutionary algorithm[M]. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011: 207-213.
|
[17] |
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. DOI:10.1007/s11518-006-0151-5 |
[18] |
Trefethen L N. Spectral methods in MATLAB[M]. Society for Industrial and Applied Mathematics, 2000.
|
[19] |
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. DOI:10.4028/www.scientific.net/AMR.645.290 |
[20] |
Schlechtendahl J, Keinert M, Kretschmer F, et al. Making existing production systems Industry 4.0-ready[J]. Production Engineering, 2015, 9(1): 143-148. |