超启发式三维分布估计算法求解分布式流水线和车辆运输集成调度问题

doi:10.12263/DZXB.20201057

电子学报 ›› 2021, Vol. 49 ›› Issue (12): 2419-2427.DOI: 10.12263/DZXB.20201057

超启发式三维分布估计算法求解分布式流水线和车辆运输集成调度问题

周丰顺¹^,², 胡蓉¹^,², 钱斌¹^,², 张长胜¹, 向凤红¹

^1.昆明理工大学信息工程与自动化学院, 云南昆明 650500
^2.昆明理工大学云南省人工智能重点实验室, 云南昆明 650500

收稿日期:2020-09-24 修回日期:2021-03-03 出版日期:2021-12-25
- 通讯作者:
- 胡蓉
- 作者简介:
- 周丰顺男,1998年出生,湖南永州人.硕士研究生,研究方向为优化调度与智能算法.E-mail：1445155907@qq.com
  胡蓉(通讯作者) 女,1974年出生,云南曲靖人.副教授,硕士生导师,研究方向为优化方法与决策支持系统.E-mail：ronghu@vip.163.com
  钱斌男,1976年出生,云南曲靖人.教授,博士生导师,研究方向为智能调度理论与方法.E-mail：bin.qian@vip.163.com
  张长胜男,1970年出生,云南昆明人.副教授,硕士生导师,研究方向为光纤传感器技术与应用.E-mail：1368037752@qq.com
  向凤红男,1964年出生,四川省盐亭人.教授,硕士生导师,研究方向为智能优化方法.E-mail：xiangfh5447@sina.com
- 基金资助:
- 国家自然科学基金 (62173169)

Hyper-Heuristic Three-Dimensional Estimation of Distribution Algorithm for Solving Distributed Permutation Flow-Shop and Vehicle Transportation Integrated Scheduling Problem

ZHOU Feng-shun¹^,², HU Rong¹^,², QIAN Bin¹^,², ZHANG Chang-sheng¹, XIANG Feng-hong¹

^1.School of Information Engineering and Automation, Kunming University of Science and Technology, Kunming, Yunnan 650500, China
^2.Yunnan Key Laboratory of Artificial Intelligence, Kunming University of Science and Technology, Kunming, Yunnan 650500, China

Received:2020-09-24 Revised:2021-03-03 Online:2021-12-25 Published:2021-12-25
- Corresponding author:
- HU Rong
- Supported by:
- National Natural Science Foundation of China (62173169)

摘要/Abstract

摘要：

针对一类广泛存在的分布式流水线和车辆运输集成调度问题(Distributed Permutation Flow-shop and Vehicle Transportation Integrated Scheduling Problem, DPFVTISP), 本文建立问题模型,并提出一种超启发式三维分布估计算法(Hyper-Heuristic three-Dimensional Estimation of Distribution Algorithm, HH3DEDA) 进行求解. 首先, 根据DPFVTISP的问题特性, 采用贪婪策略设计一种新颖的编解码规则. 其次, 为实现对DPFVTISP问题解空间中不同区域的深入搜索, 设计10种低层启发式操作 (即10种有效的邻域操作), 并将其所构成的排列作为高层个体; 同时在高层采用三维分布估计算法 (three-Dimensional Estimation of Distribution Algorithm, 3DEDA) 学习和积累优质高层个体中块结构及其位置信息, 再通过采样3DEDA中的概率模型生成新的高层个体或排列; 进而在低层将高层所生成的每个新个体所表征的一系列有序的启发式操作作为一种新的启发式算法, 对问题解空间执行较深入的邻域搜索. 最后, 通过仿真实验与算法对比验证HH3DEDA可有效求解DPFVTISP.

关键词: 分布式流水线, 车辆运输, 集成调度, 超启发式算法, 三维分布估计算法, 块结构

Abstract:

Aiming at a kind of widely existing distributed permutation flow-shop and vehicle transportation integrated scheduling problem(DPFVTISP), this paper establishes the problem model and proposes a hyper-heuristic three-dimensional estimation of distribution algorithm(HH3DEDA) to solve it. Firstly, a novel coding and decoding rules adopting the greedy strategy is designed via analyzing the characteristics of DPFVTISP. Secondly, in order to search different regions in the solution space of DPFVTISP, ten kinds of low-layer heuristic operations, i.e., ten kinds of effective neighborhood operations, are designed, and their permutations are regarded as high-layer individuals. At the same time, the three-dimensional estimation of distribution algorithm (3DEDA) is used in the high layer to learn and accumulate the information of block structures and their positions in the high-quality high-layer individuals, and then new low-layer individuals or permutations are generated by sampling the probability model in 3DEDA. Furthermore, in the low layer, an ordered series of heuristic operations presenting by each new individual generated in the high layer is regarded as a new heuristic algorithm to execute further neighborhood search in the problem’s solution space. Finally, simulations and comparisons demonstrate that HH3DEDA can effectively solve the DPFVTISP.

Key words: distributed permutation flow-shop, vehicle transportation, integrated scheduling, hyper-heuristic algorithm, three-dimensional estimation of distribution algorithm, block structure

中图分类号:

TP273

周丰顺, 胡蓉, 钱斌, 等. 超启发式三维分布估计算法求解分布式流水线和车辆运输集成调度问题[J]. 电子学报, 2021, 49(12): 2419-2427.

Feng-shun ZHOU, Rong HU, Bin QIAN, et al. Hyper-Heuristic Three-Dimensional Estimation of Distribution Algorithm for Solving Distributed Permutation Flow-Shop and Vehicle Transportation Integrated Scheduling Problem[J]. Acta Electronica Sinica, 2021, 49(12): 2419-2427.

图/表 7

表1 符号表

符号	说明
$j$	工件编号. $j = {1, 2, . . ., N j}$ .
$i$	机器编号. $i = {1, 2, . . .,, M}$ .
$p j, i$	工件j在机器i上的加工时间.
$W (j)$	工件j的重量.
$k, f$	工厂和集合点编号 $k, f = {0, 1, 2, . . ., F}$ ，集合点编号为0.
$π k$	工厂k中工件加工序列. $π k = {π k (l) \| l = 1, 2, . . ., N k}$ .
$C j, i$	工件j在机器i上的完工时间.
$h$	车辆编号. $h = {1,2, . . ., H}$ .
$Q$	车辆的最大载重.
$D k, f$	从工厂或集合点k到工厂或集合点f之间的距离.
$V$	车辆行驶的速度.
$S h, k$	车辆h从工厂或集合点k出发时间.
$A h, k$	车辆h到达工厂或集合点k的时间.
$π w h$	车辆h所运载的工件序列. $π w h = {π w h (a) \| a = 1, 2, . . ., N w h}$ .
$π r h$	车辆h行驶路径点序列. $π r h = {π r h (b) \| b = 1, 2, . . ., N r h}$ .
$C s t 1 (j)$	工件j在加工阶段的完工时间.
$C s t 2 (j)$	工件j运输至集合点的时间.

表1 符号表

符号	说明
$j$	工件编号. $j = {1, 2, . . ., N j}$ .
$i$	机器编号. $i = {1, 2, . . .,, M}$ .
$p j, i$	工件j在机器i上的加工时间.
$W (j)$	工件j的重量.
$k, f$	工厂和集合点编号 $k, f = {0, 1, 2, . . ., F}$ ，集合点编号为0.
$π k$	工厂k中工件加工序列. $π k = {π k (l) \| l = 1, 2, . . ., N k}$ .
$C j, i$	工件j在机器i上的完工时间.
$h$	车辆编号. $h = {1,2, . . ., H}$ .
$Q$	车辆的最大载重.
$D k, f$	从工厂或集合点k到工厂或集合点f之间的距离.
$V$	车辆行驶的速度.
$S h, k$	车辆h从工厂或集合点k出发时间.
$A h, k$	车辆h到达工厂或集合点k的时间.
$π w h$	车辆h所运载的工件序列. $π w h = {π w h (a) \| a = 1, 2, . . ., N w h}$ .
$π r h$	车辆h行驶路径点序列. $π r h = {π r h (b) \| b = 1, 2, . . ., N r h}$ .
$C s t 1 (j)$	工件j在加工阶段的完工时间.
$C s t 2 (j)$	工件j运输至集合点的时间.

图1 DPFVTISP示意图

图2 运输阶段车辆路径示意图

图3 高层策略域个体示意图

图4 解码后低层问题域个体示意图

表2 验证HH3DEDA高层策略的有效性

问题规模	HHGA	HHEDA		HH3DEDA
问题规模	AVG	AVG	IMP	AVG	IMP
$20 × 5 × 2$	1324.8	1326.6	-0.14%	1322.7	0.15%
$20 × 10 × 2$	1742.0	1745.5	-0.20%	1738.9	0.18%
$20 × 20 × 2$	2406.4	2406.2	0.01%	2403.6	0.12%
$50 × 5 × 2$	2612.4	2544.4	2.60%	2475.0	5.26%
$50 × 10 × 2$	3227.7	3202.9	0.77%	3181.1	1.44%
$50 × 20 × 2$	4135.3	4056.4	1.91%	4039.5	2.32%
$100 × 5 × 2$	4714.7	4633.1	1.73%	4581.9	2.82%
$100 × 10 × 2$	6405.4	6301.0	1.63%	6257.4	2.31%
$100 × 20 × 2$	7229.9	6982.1	3.43%	6913.8	4.37%
$20 × 5 × 4$	1122.7	1083.4	3.50%	1065.0	5.14%
$20 × 10 × 4$	1486.0	1450.7	2.37%	1450.3	2.40%
$20 × 20 × 4$	2035.7	1999.6	1.77%	1999.5	1.78%
$50 × 5 × 4$	2429.5	2355.2	3.06%	2301.1	5.28%
$50 × 10 × 4$	2472.2	2275.7	7.95%	2265.1	8.38%
$50 × 20 × 4$	3603.4	3496.1	2.98%	3390.5	5.91%
$100 × 5 × 4$	4563.9	4393.1	3.74%	4359.2	4.49%
$100 × 10 × 4$	5192.3	4896.4	5.70%	4847.4	6.64%
$100 × 20 × 4$	6218.5	6056.2	2.61%	6009.9	3.35%
$20 × 5 × 6$	1207.1	1183.7	1.94%	1176.2	2.56%
$20 × 10 × 6$	1468.0	1462.8	0.35%	1461.3	0.46%
$20 × 20 × 6$	2066.1	2062.1	0.19%	2063.6	0.12%
$50 × 5 × 6$	2117.5	2084.2	1.57%	2033.7	3.96%
$50 × 10 × 6$	2711.7	2612.7	3.65%	2574.3	5.07%
$50 × 20 × 6$	3384.2	3200.8	5.42%	3123.5	7.70%
$100 × 5 × 6$	4628.5	4426.3	4.37%	4406.5	4.80%
$100 × 10 × 6$	5065.1	4801.5	5.20%	4845.1	4.34%
$100 × 20 × 6$	5643.9	5298.7	6.12%	5423.3	3.91%
Average	3378.3	3271.8	3.15%	3248.5	3.84%
NB	0	3	3	24	24

表2 验证HH3DEDA高层策略的有效性

问题规模	HHGA	HHEDA		HH3DEDA
问题规模	AVG	AVG	IMP	AVG	IMP
$20 × 5 × 2$	1324.8	1326.6	-0.14%	1322.7	0.15%
$20 × 10 × 2$	1742.0	1745.5	-0.20%	1738.9	0.18%
$20 × 20 × 2$	2406.4	2406.2	0.01%	2403.6	0.12%
$50 × 5 × 2$	2612.4	2544.4	2.60%	2475.0	5.26%
$50 × 10 × 2$	3227.7	3202.9	0.77%	3181.1	1.44%
$50 × 20 × 2$	4135.3	4056.4	1.91%	4039.5	2.32%
$100 × 5 × 2$	4714.7	4633.1	1.73%	4581.9	2.82%
$100 × 10 × 2$	6405.4	6301.0	1.63%	6257.4	2.31%
$100 × 20 × 2$	7229.9	6982.1	3.43%	6913.8	4.37%
$20 × 5 × 4$	1122.7	1083.4	3.50%	1065.0	5.14%
$20 × 10 × 4$	1486.0	1450.7	2.37%	1450.3	2.40%
$20 × 20 × 4$	2035.7	1999.6	1.77%	1999.5	1.78%
$50 × 5 × 4$	2429.5	2355.2	3.06%	2301.1	5.28%
$50 × 10 × 4$	2472.2	2275.7	7.95%	2265.1	8.38%
$50 × 20 × 4$	3603.4	3496.1	2.98%	3390.5	5.91%
$100 × 5 × 4$	4563.9	4393.1	3.74%	4359.2	4.49%
$100 × 10 × 4$	5192.3	4896.4	5.70%	4847.4	6.64%
$100 × 20 × 4$	6218.5	6056.2	2.61%	6009.9	3.35%
$20 × 5 × 6$	1207.1	1183.7	1.94%	1176.2	2.56%
$20 × 10 × 6$	1468.0	1462.8	0.35%	1461.3	0.46%
$20 × 20 × 6$	2066.1	2062.1	0.19%	2063.6	0.12%
$50 × 5 × 6$	2117.5	2084.2	1.57%	2033.7	3.96%
$50 × 10 × 6$	2711.7	2612.7	3.65%	2574.3	5.07%
$50 × 20 × 6$	3384.2	3200.8	5.42%	3123.5	7.70%
$100 × 5 × 6$	4628.5	4426.3	4.37%	4406.5	4.80%
$100 × 10 × 6$	5065.1	4801.5	5.20%	4845.1	4.34%
$100 × 20 × 6$	5643.9	5298.7	6.12%	5423.3	3.91%
Average	3378.3	3271.8	3.15%	3248.5	3.84%
NB	0	3	3	24	24

表3 HH3DEDA与3种算法的对比结果

问题规模	IWOA	IICA	DGA	HH3DEDA
问题规模	AVG	AVG	AVG	AVG
$20 × 5 × 2$	1345.8	1332.0	1340.6	1322.7
$20 × 10 × 2$	1805.1	1758.4	1784.7	1738.9
$20 × 20 × 2$	2452.3	2423.1	2432.3	2403.6
$50 × 5 × 2$	2555.2	2509.8	2528.1	2475.0
$50 × 10 × 2$	3279.7	3230.0	3220.1	3181.1
$50 × 20 × 2$	4176.2	4107.8	4066.5	4039.5
$100 × 5 × 2$	4785.4	4651.5	4552.2	4581.9
$100 × 10 × 2$	6564.6	6381.9	6220.0	6257.4
$100 × 20 × 2$	7288.7	7123.7	6882.9	6913.8
$20 × 5 × 4$	1120.8	1090.3	1109.3	1065.0
$20 × 10 × 4$	1508.3	1471.8	1489.9	1450.3
$20 × 20 × 4$	2046.5	2020.9	2028.6	1999.5
$50 × 5 × 4$	2468.1	2391.9	2380.6	2301.1
$50 × 10 × 4$	2393.2	2305.9	2279.8	2265.1
$50 × 20 × 4$	3589.5	3513.2	3501.6	3390.5
$100 × 5 × 4$	4705.5	4501.0	4366.4	4359.2
$100 × 10 × 4$	5408.1	5076.9	4909.3	4847.4
$100 × 20 × 4$	6463.1	6184.9	5965.0	6009.9
$20 × 5 × 6$	1218.6	1207.0	1231.6	1176.2
$20 × 10 × 6$	1524.4	1492.2	1505.2	1461.3
$20 × 20 × 6$	2115.7	2084.8	2100.1	2063.6
$50 × 5 × 6$	2210.1	2111.3	2095.7	2033.7
$50 × 10 × 6$	2721.8	2695.8	2659.7	2574.3
$50 × 20 × 6$	3297.1	3263.5	3260.8	3123.5
$100 × 5 × 6$	4866.9	4622.1	4465.5	4406.5
$100 × 10 × 6$	5275.3	5038.7	4904.1	4845.1
$100 × 20 × 6$	5935.6	5661.7	5549.1	5423.3
Average	3449.0	3342.7	3290.0	3248.5
NB	0	0	4	23

表3 HH3DEDA与3种算法的对比结果

问题规模	IWOA	IICA	DGA	HH3DEDA
问题规模	AVG	AVG	AVG	AVG
$20 × 5 × 2$	1345.8	1332.0	1340.6	1322.7
$20 × 10 × 2$	1805.1	1758.4	1784.7	1738.9
$20 × 20 × 2$	2452.3	2423.1	2432.3	2403.6
$50 × 5 × 2$	2555.2	2509.8	2528.1	2475.0
$50 × 10 × 2$	3279.7	3230.0	3220.1	3181.1
$50 × 20 × 2$	4176.2	4107.8	4066.5	4039.5
$100 × 5 × 2$	4785.4	4651.5	4552.2	4581.9
$100 × 10 × 2$	6564.6	6381.9	6220.0	6257.4
$100 × 20 × 2$	7288.7	7123.7	6882.9	6913.8
$20 × 5 × 4$	1120.8	1090.3	1109.3	1065.0
$20 × 10 × 4$	1508.3	1471.8	1489.9	1450.3
$20 × 20 × 4$	2046.5	2020.9	2028.6	1999.5
$50 × 5 × 4$	2468.1	2391.9	2380.6	2301.1
$50 × 10 × 4$	2393.2	2305.9	2279.8	2265.1
$50 × 20 × 4$	3589.5	3513.2	3501.6	3390.5
$100 × 5 × 4$	4705.5	4501.0	4366.4	4359.2
$100 × 10 × 4$	5408.1	5076.9	4909.3	4847.4
$100 × 20 × 4$	6463.1	6184.9	5965.0	6009.9
$20 × 5 × 6$	1218.6	1207.0	1231.6	1176.2
$20 × 10 × 6$	1524.4	1492.2	1505.2	1461.3
$20 × 20 × 6$	2115.7	2084.8	2100.1	2063.6
$50 × 5 × 6$	2210.1	2111.3	2095.7	2033.7
$50 × 10 × 6$	2721.8	2695.8	2659.7	2574.3
$50 × 20 × 6$	3297.1	3263.5	3260.8	3123.5
$100 × 5 × 6$	4866.9	4622.1	4465.5	4406.5
$100 × 10 × 6$	5275.3	5038.7	4904.1	4845.1
$100 × 20 × 6$	5935.6	5661.7	5549.1	5423.3
Average	3449.0	3342.7	3290.0	3248.5
NB	0	0	4	23

参考文献 19

1	戚远航, 蔡延光, 蔡颢, 等.带容量约束的供应链物流运输调度问题的双层变邻域蝙蝠算法[J]. 电子学报, 2019, 47(7): 1434 - 1442.
	QiY H, CaiY G, CaiH, et al. Two-level bat algorithm with variable neighborhood search for capacitated vehicle routing problem in supply chain[J]. Acta Electronica Sinica, 2019, 47(7): 1434 - 1442. (in Chinese)
2	MoonsS, RamaekersK, CarisA, et al. Integrating production scheduling and vehicle routing decisions at the operational decision level: A review and discussion[J]. Computers & Industrial Engineering, 2017, 104: 224 - 245.
3	MohammadiS, Al-E-hashemS M J M, RekikY. An integrated production scheduling and delivery route planning with multi-purpose machines: A case study from a furniture manufacturing company[J]. International Journal of Production Economics, 2020, 219: 347 - 359.
4	FengX, XuZ Y. Integrated production and transportation scheduling on parallel batch-processing machines [J]. IEEE Access, 2019, 7: 148393 - 148400.
5	GharaeiA, JolaiF. A branch and price approach to the two-agent integrated production and distribution scheduling [J]. Computers & Industrial Engineering, 2019, 136: 504 - 515.
6	GharaeiA, JolaiF. Two heuristic methods based on decomposition to the integrated multi-agent supply chain scheduling and distribution problem[J]. Optimization Methods and Software, 2020. DOI:10.1080/10556788.202.1714615.
7	AbdollahzadehV, NakhaikamalabadiI, HajimolanaS M, et al. A multifactory integrated production and distribution scheduling problem with parallel machines and immediate shipments solved by improved whale optimization algorithm [J]. Complexity, 2018, 2018: 1 - 21.
8	KarimiN, DavoudpourH. A branch and bound method for solving multi-factory supply chain scheduling with batch delivery [J]. Expert Systems with Applications, 2015, 42 (1) : 238 - 245.
9	MarandiF, Fatemi GhomiS M T. Integrated multi-factory production and distribution scheduling applying vehicle routing approach [J]. International Journal of Production Research, 2019, 57(3): 722 - 748.
10	李尚函, 胡蓉, 钱斌, 等. 超启发式遗传算法求解模糊柔性作业车间调度 [J]. 控制理论与应用, 2020, 37(2): 316 - 330.
	LiS H, HuR, QianB, et al. Hyper-heuristic genetic algorithm for solving fuzzy flexible job shop scheduling problem[J]. Control Theory & Applications, 2020, 37(2): 316 - 330.(in Chinese)
11	ParkJ, MeiY, NguyenS, et al. An investigation of ensemble combination schemes for genetic programming based hyper-heuristic approaches to dynamic job shop scheduling[J]. Applied Soft Computing, 2018, 63: 72 - 86.
12	田云娜, 李冬妮, 刘兆赫, 等. 一种基于动态决策块的超启发式跨单元调度方法[J]. 自动化学报, 2016, 42(4): 524 - 534.
	TianY N, LiD N, LiuZ H, et al. A hyper-heuristic approach with dynamic decision blocks for inter-cell scheduling[J]. Acta Automatica Sinica, 2016, 42(4): 524 - 534.(in Chinese)
13	周雅兰, 王甲海, 黄聪. 求解排列问题的分布估计离散粒子群优化算法[J]. 电子学报, 2014, 42(3): 561 - 571.
	ZhouY L, WangJ H, HuangC. Estimation of distribution-discrete particle swarm optimization algorithm for permutation-based problems[J]. Acta Electronica Sinica, 2014, 42(3): 561 - 571.(in Chinese)
14	程玉虎, 王雪松, 郝名林. 一种多样性保持的分布估计算法[J]. 电子学报, 2010, 38(3): 591 - 597.
	ChengY H, WangX S, HaoM L. An estimation of distribution algorithm with diversity preservation[J]. Acta Electronica Sinica, 2010, 38(3): 591 - 597.(in Chinese)
15	Faraji AmiriM, BehnamianJ. Multi-objective green flowshop scheduling problem under uncertainty: Estimation of distribution algorithm[J]. Journal of Cleaner Production, 2020, 251: 119734.
16	曹政才, 林诚然, 黄冉. 带等待时间约束并行机调度问题的Copula分布估计算法 [J]. 电子学报, 2017, 45(12): 2949 - 2956.
	CaoZ C, LinC R, HuangR. An estimation of distribution algorithm based on copula for parallel machine scheduling with constrained waiting time[J]. Acta Electronica Sinica, 2017, 45(12): 2949 - 2956. (in Chinese)
17	WangS Y, WangL. An estimation of distribution algorithm-based memetic algorithm for the distributed assembly permutation flow-shop scheduling problem[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2016, 46(1): 139 - 149.
18	ShaoW S, PiD C, ShaoZ S. A Pareto-based estimation of distribution algorithm for solving multiobjective distributed no-wait flow-shop scheduling problem with sequence-dependent setup time[J]. IEEE Transactions on Automation Science and Engineering, 2019, 16(3): 1344 - 1360.
19	MontgomeryD C. Design and Analysis of Experiments [M]. Hoboken: John Wiley and Sons, 2005.

[1]	唐捷凯, 胡蓉, 钱斌, 金怀平, 向凤红. 混合帝国竞争算法求解带多行程批量配送的多工厂集成调度问题[J]. 电子学报, 2022, 50(7): 1621-1630.
[2]	李志丹, 和红杰, 尹忠科, 陈帆, 仁青诺布. 基于块结构稀疏度的自适应图像修复算法[J]. 电子学报, 2013, 41(3): 549-554.
[3]	王欣;魏急波;李颖. 具有子块编码结构和优化编码增益的非相干全分集空频码设计[J]. 电子学报, 2008, 36(4): 655-660.

超启发式三维分布估计算法求解分布式流水线和车辆运输集成调度问题

Hyper-Heuristic Three-Dimensional Estimation of Distribution Algorithm for Solving Distributed Permutation Flow-Shop and Vehicle Transportation Integrated Scheduling Problem

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 19

相关文章 3

编辑推荐

Metrics