求解差异机器平行批调度的双目标协同蚁群算法

贾兆红; 王燕; 张以文

doi:10.16383/j.aas.c180834

求解差异机器平行批调度的双目标协同蚁群算法

doi: 10.16383/j.aas.c180834

贾兆红^{1, 2,},
王燕^1,,
张以文^{1, 2,}

1.
安徽大学计算机科学与技术学院合肥 230601
2.
安徽大学计算智能与信号处理教育部重点实验室合肥 230601

基金项目: 国家自然科学基金(71601001, 71671168), 中国教育部人文社会科学青年基金会(15YJC630041), 安徽省科学基金(1608085MG154), 安徽省教育厅自然科学基金(KJ2015A062)资助

详细信息

作者简介:
贾兆红：安徽大学计算机科学与技术学院教授. 2008年获得中国科技大学博士学位. 主要研究方向为计算智能, 多目标优化, 决策支持. 本文通信作者. E-mail: jiazhaohong001@163.com

王燕：安徽大学硕士研究生. 主要研究方向为多目标优化, 进化计算. E-mail: yanwang0501@outlook.com

张以文：安徽大学计算机科学与技术学院教授. 主要研究方向为服务计算, 云计算, 电子商务. E-mail: zhangyiwen@ahu.edu.cn

计量
- 文章访问数: 1760
- HTML全文浏览量: 82
- PDF下载量: 185
- 被引次数: 0
出版历程
- 收稿日期: 2018-12-17
- 录用日期: 2019-08-08
- 网络出版日期: 2020-07-10
- 刊出日期: 2020-07-10

A Bi-objective Synergy Optimization Algorithm of Ant Colony for Scheduling on Non-identical Parallel Batch Machines

JIA Zhao-Hong^{1, 2
,},
WANG Yan^1
,,
ZHANG Yi-Wen^{1, 2
,}

1.
School of Computer Science and Technology, Anhui University, Hefei 230601
2.
Key Laboratory of Intelligent Computing and Signal Processing of Ministry of Education, Anhui University, Hefei 230601

Funds: Supported by National Natural Science Foundation of China (71601001, 71671168), Humanity and Social Science Youth Founda-tion of Ministry of Education of China (15YJC630041), Natural Science Foundation of Anhui Province (1608085MG154), and Natural Science Foundation of Anhui Provincial Department of Education (KJ2015A062)

摘要

摘要: 利用用户的偏好信息, 提出一种基于蚁群的双目标协同优化算法(Bi-objective synergy ant colony optimization algorithm based on Pareto domination, PDACO)并用于求解平行批处理机调度问题. 考虑在一组差异容量并带有不同加工功率的平行批处理机器上, 加工带有不同到达时间、尺寸和加工时间的一组工件, 以同时最小化最大完工时间和总能耗. 偏好向量的引入虽然可以提高算法的收敛性, 但会降低解的多样性. 为了弥补这一缺陷, 在本文所提算法中, 利用两个子蚁群分别沿着不同方向, 迭代地进行独立和联合搜索. 最后, 通过大量的仿真实验验证了本文提出算法的有效性.
- 协同优化 /
- 批处理机 /
- 用户偏好 /
- 最大完工时间 /
- 总能耗
Abstract: The paper proposed a bi-objective synergy optimization algorithm based on ant colony (PDACO) using preference vectors. It is used to solve the batch scheduling problem. These constraints, a set of jobs with different arrival times, sizes, and processing times on a group of parallel batch processing machines (BPMs) with different capacities and different processing powers, are taken into consideration. The objective is to minimize the maximum completion time and the total energy consumption, simultaneously. Although the preference vector is effective to improve the convergence of algorithm, it will deteriorate the diversity of solutions. In order to reduce the adverse effects of the preference vector, two colonies searching solutions in different directions iteratively use the independent and co-operation search approaches in the proposed algorithm. Finally, through extensive simulation experiments, the validity of the algorithm PDACO proposed in this paper is verified.
- Synergy optimization /
- batch processing machines (BPMs) /
- user preference /
- maximum completion time /
- total energy consumption

HTML全文

图 1 解 $ {\sigma _{{\rm{0}}}} $ 甘特图

Fig. 1 The Gantt chart of $ \sigma_{{\rm{0}}} $

下载: 全尺寸图片幻灯片

图 2 解 $ {\sigma _{{\rm{1}}}} $ 甘特图

Fig. 2 The Gantt chart of $ \sigma_{{\rm{1}}} $

下载: 全尺寸图片幻灯片

图 3 PDACO算法总流程图

Fig. 3 The flowchart of algorithm PDACO

下载: 全尺寸图片幻灯片

图 4 ($ N_1 $, $ N_2 $), $ K $, $ \rho $, $ Q $不同取值获得的$ H $值

Fig. 4 The values of $ H $ under different values of ($ N_1 $, $ N_2 $), $ K $, $ \rho $ and $ Q $

下载: 全尺寸图片幻灯片

图 5 $ ({\alpha _{{\rm{1}}}},{\beta _1}) $, $ ({\alpha _{{\rm{2}}}},{\beta _2}) $不同取值获得的$ H $值

Fig. 5 The values of $ H $ under different values of $ ({\alpha _{{\rm{1}}}},{\beta _1}) $, $ ({\alpha _{{\rm{2}}}},{\beta _2}) $

下载: 全尺寸图片幻灯片

图 6 采用不同策略时获得的$ H $值

Fig. 6 The values of $ H $ using different strategies

下载: 全尺寸图片幻灯片

图 7 4组不同工件数测试实例目标函数

Fig. 7 Solution distribution on four instances with different number of jobs

下载: 全尺寸图片幻灯片

图 8 90个工件实例调度甘特图

Fig. 8 The Gantt chart of the example with 90 jobs

下载: 全尺寸图片幻灯片

表 1 编码实例

Table 1 An example of a solution encoding

J_j	b	i
J₁	2	3
J₂	1	4
J₃	3	2
J₄	5	4
J₅	4	1
J₆	2	3
J₇	3	2
J₈	5	5
J₉	1	4

下载: 导出CSV

表 2 实例参数

Table 2 The example of the problem

B_bi	R_bi	PT_bi
B₁₁	3	7
B₂₁	12	5
B₁₂	5	4
B₂₂	2	5
B₃₂	3	4

下载: 导出CSV

表 3 实验参数设置

Table 3 Experimental parameter settings

参数	符号	取值
工件数	n	$n \in ${90, 108, 126, 144, 162, 180, 216, 252, 306, 360, 432}
工件尺寸	$s_j$	${s_j}\sim $P$({\lambda_i}),{\lambda _1} = 5,{\lambda _2} = 12.5, $ ${\lambda _3} = 32.5 $
工件到达时间	r_j	U [1, R]
工件加工时间	p_j	U [8, 48]
机器数	$m_i$	m₁ = 5, m₂ = 3, m₃ = 2
机器容量	$S^i$	S ¹ = 10, S ² = 25, S ³ = 65
机器功率	$l^i$	l ¹ = 10, l ² = 35, l ³ = 85

下载: 导出CSV

表 4 比较算法的参数设置

Table 4 The parameter settings of comparative algorithms

PDACO	PACO	NSGA-II	SPEA2	SMPSO
$N_1: 50$	$N:100$	$N:100$	$N:100$	$N: 100$
$N_2: 50$		$Q_a: 100$	$Q_a: 100$	$r_1 \in [0,1], r_2 \in[0,1]$
		交叉概率: 1.0	交叉概率: 1.0	交叉概率: 0.9
		变异概率: 0.01	变异概率: 0.01	变异概率: 1/L
$T_{\max}=200$	$T_{\max}=200$	$T_{\max}=200$	$T_{\max}=200$	$T_{\max}=200$

下载: 导出CSV

表 5 NPS指标值比较结果

Table 5 Comparison of the five algorithms using the NPS metric

工件数	PDACO			PACO			NSGA-II			SPEA2			SMPSO
工件数	MAX	MIN	AVG	MAX	MIN	AVG	MAX	MIN	AVG	MAX	MIN	AVG	MAX	MIN	AVG
90	11.10	3.20	6.80	10.40	2.65	6.30	7.75	1.00	2.74	4.25	1.00	1.22	8.4	1.2	4.26
108	11.45	3.00	7.00	10.05	2.75	6.36	7.85	1.00	2.92	5.65	1.00	1.51	7.95	1.4	4.07
126	11.40	3.80	7.24	10.50	2.75	6.28	7.75	1.05	2.84	6.95	1.00	1.73	8.2	1.3	3.99
144	12.85	3.65	7.62	19.15	7.40	13.04	8.80	1.00	3.02	8.05	1.00	1.92	7.9	1.35	4
162	11.50	3.60	7.39	10.50	3.30	6.63	9.70	1.00	3.05	6.95	1.00	1.73	7.35	1.25	3.93
180	12.35	3.45	7.40	11.40	2.55	6.64	8.95	1.00	2.95	7.70	1.00	2.11	8.35	1.25	4.15
216	12.40	3.90	7.75	11.40	3.20	7.04	8.55	1.00	2.71	8.20	1.00	2.11	7.95	1.2	4.03
252	12.45	3.75	7.87	11.35	3.55	7.16	9.25	1.00	2.71	8.60	1.00	2.01	7.6	1.4	4.02
306	12.35	3.60	7.72	11.30	3.20	7.00	8.45	1.00	2.55	8.50	1.00	2.00	8.1	1.3	4.11
360	12.75	3.60	7.79	11.85	3.35	7.40	7.75	1.00	2.42	9.05	1.00	2.06	8.15	1.3	4.21
432	13.15	4.00	8.10	12.15	3.25	7.61	8.05	1.00	2.39	7.65	1.00	1.76	8.2	1.25	4.04

下载: 导出CSV

表 6 覆盖率$(C) $比较结果

Table 6 Comparison of the five algorithms using the C metric

工件数	C (PDACO, PACO)	C (PACO, PDACO)	C (PDACO, NSGA-II)	C (NSGA-II, PDACO)	C (PDACO, SPEA2)	C (SPEA2, PDACO)	C (PDACO, SMPSO)	C (SMPSO, PDACO)
90	0.988	0.001	0.801	0.001	0.757	0	0.833	0.021
108	0.971	0.003	0.608	0.001	0.564	0.001	0.743	0.004
126	0.986	0.002	0.656	0	0.599	0	0.647	0
144	0.994	0	0.504	0	0.476	0	0.561	0
162	0.997	0	0.421	0	0.677	0	0.587	0
180	0.999	0	0.554	0	0.533	0	0.533	0
216	0.995	0	0.470	0	0.577	0	0.516	0
252	0.997	0	0.421	0	0.426	0	0.452	0
306	0.997	0	0.529	0	0.645	0	0.513	0
360	0.989	0	0.606	0	0.553	0	0.459	0
432	0.997	0	0.501	0	0.439	0	0.466	0

下载: 导出CSV

表 7 超体$(H) $指标比较结果

Table 7 Comparison of the five algorithms using the H metric

工件数	PDACO	PACO	NSGA-II	SPEA2	SMPSO
90	469 603	277 319	110 110	111 396	121 352
108	650 187	403 180	146 403	148 960	147 856
126	933 105	539 363	256 380	236 164	271 332
144	1 232 318	690 126	275 805	303 290	288 495
162	1 472 585	793 386	318 719	358 388	341 864
180	1 814 061	1 000 950	413 532	465 956	428 793
216	2 577 210	1 385 263	560 037	671 642	635 549
252	3 489 851	1 874 024	749 649	888 686	815 992
306	4 969 991	2 614 455	1 079 066	1 314 258	1 179 523
360	6 638 616	3 478 054	1 555 105	1 878 950	1 638 628
432	8 805 782	4 469 622	2 106 786	2 439 180	2 266 835

下载: 导出CSV

表 8 多样性(DVR)、Spacing(SPC)和时间(T)指标比较结果

Table 8 Comparison of the five algorithms using the DVR, SPC and T metrics

工件数	PDACO			PACO			NSGA-II			SPEA2			SMPSO
工件数	DVR	SPC	T	DVR	SPC	T	DVR	SPC	T	DVR	SPC	T	DVR	SPC	T
90	137 262	0.89	0.86	89 010	0.82	0.83	17 167	0.26	1.87	4 121	0.04	2.17	21 362	0.36	1.14
108	164 060	0.89	1.08	110 360	0.84	1.13	20 772	0.29	2.39	17 299	0.11	2.96	26 815	0.33	1.28
126	219 865	0.92	1.44	141 594	0.86	1.49	46 860	1.01	2.88	28 803	0.13	3.93	52 619	0.52	1.5
144	256 752	0.91	1.80	166 727	0.84	1.65	24 153	0.29	3.61	59 443	0.22	4.65	39 526	0.23	1.7
162	294 754	0.88	2.30	197 631	0.86	2.53	24 276	0.28	4.43	54 872	0.14	5.62	43 511	0.22	1.83
180	328 732	0.92	2.67	213 904	0.83	3.17	27 072	0.26	5.07	102 915	0.27	6.59	27 342	0.24	2.28
216	435 913	0.94	3.83	290 015	0.90	4.40	21 623	0.25	17.00	133 770	0.27	9.01	25 113	0.24	2.29
252	520 652	0.93	5.05	370 128	0.90	5.94	23 940	0.22	9.43	179 343	0.23	12.87	34 619	0.25	2.57
306	664 941	0.94	7.36	451 475	0.89	8.53	24 801	0.24	20.53	293 842	0.27	21.12	33 428	0.24	3.07
360	800 856	0.91	10.33	535 670	0.93	12.33	23 838	0.19	27.58	431 781	0.28	27.80	49 734	0.26	3.46
432	1 010 000	0.96	14.77	789 834	0.94	17.54	23 959	0.17	36.70	374 310	0.19	40.10	66 253	0.21	4.03

下载: 导出CSV

参考文献(27)

[1]	Ahmadi J H, Ahmadi R H, Dasu S, Tang C S. Batching and scheduling jobs on batch and discrete processors. Operations research, 1992, 40(4): 750−763 doi: 10.1287/opre.40.4.750
[2]	原豪男, 郭戈. 交通信息物理系统中的车辆协同运行优化调度. 自动化学报, 2019, 45(1): 143−152 Yuan Hao-Nan, Guo Ge. Vehicle cooperative optimization scheduilng intransportation cyber physical systems. Acta Automatica Sinica, 2019, 45(1): 143−152
[3]	Uzsoy R. Scheduling a single batch processing machine with non-identical job sizes. International Journal of Production Research, 1994, 32(7): 1615−1635 doi: 10.1080/00207549408957026
[4]	Ikura Y, Gimple M. Efficient scheduling algorithms for a single batch processing machine. Operations Research Letters, 1986, 5(2): 61−65 doi: 10.1016/0167-6377(86)90104-5
[5]	赵玉芳, 唐立新. 极小化最大完工时间的单机连续型批调度问题. 自动化学报, 2006, 32(5): 730−737 Zhao Yu-Fang, Tang Li-Xin. Scheduling a single continuous batch processing machine to minimize makespan. Acta Acta Automatica Sinica, 2006, 32(5): 730−737
[6]	Zhou H M, Pang J H, Chen P K, Chou F D. A modified particle swarm optimization algorithm for a batch-processing machine scheduling problem with arbitrary release times and non-identical job sizes. Computers and Industrial Engineering, 2018, 123: 67−81
[7]	Chang P Y, Damodaran P, Melouk S. Minimizing makespan on parallel batch processing machines. International Journal of Production Research, 2004, 42(19): 4211−4220 doi: 10.1080/00207540410001711863
[8]	Jia Z H, Wang Y, Wu C, Yang Y, Zhang X Y, Chen H P. Multi-objective energy-aware batch scheduling using ant colony optimization algorithm. Computer and Industrial Engineering, 2019, 131: 41−56
[9]	Shi Z S, Huang Z W, Shi L Y. Customer order scheduling on batch processing machines with incompatible job families. International Journal of Production Research, 2018, 56(1-2): 795−808 doi: 10.1080/00207543.2017.1401247
[10]	Zhou S C, Xie J H, Du N, Pang Y. A random-keys genetic algorithm for scheduling unrelated parallel batch processing machines with different capcities and arbitrary job sizes. Applied Mathematics and Computation, 2018, 334: 254−268 doi: 10.1016/j.amc.2018.04.024
[11]	Arroyo J E C, Leung J Y T. Scheduling unrelated parallel batch processing machines with non-identical job sizes and unequal ready times. Computers and Operations Research, 2017, 78: 117−128
[12]	陆志强, 刘欣仪. 考虑资源转移时间的资源受限项目调度问题的算法. 自动化学报, 2018, 44(6): 1028−1036 Lu Zhi-Qiang, Liu Xin-Yi. Algorithm for resource-constrained project scheduling problem with resource transfer time. Acta Automatica Sinica, 2018, 44(6): 1028−1036
[13]	Zhou S C, Li X L, Du N, Pang Y, Chen H P. A multi-objective differential evolution algorithm for parallel batch processing machine scheduling considering electricity consumption cost. Computers and Operations Research, 2018, 96: 55−68
[14]	Du B, Chen H P, Huang G Q, Yang H D. Preference vector ant colony system for minimising make-span and energy consumption in a hybrid flow shop. Multi-objective Evolutionary Optimisation for Product Design and Manufacturing. Springer-London, 2011. 279–304
[15]	Jia Z H, Zhang Y L, Leung J Y T, Li K. Bi-criteria ant colony optimization algorithm for minimizing makespan and energy consumption on parallel batch machines. Applied Soft Computing, 2017, 55: 226−237 doi: 10.1016/j.asoc.2017.01.044
[16]	汪恭书, 刘静宜, 唐立新. 连铸–轧制混流生产模式下轧批调度问题的分支–定价算法. 自动化学报, 2017, 43(7): 1178−1189 Wang Gong-Shu, Liu Jing-Yi, Tang Li-Xin. Branch-and-price algorithm for rolling batch scheduling problem in continuous-casting and rolling processes with hybrid production mode. Acta Automatica Sinica, 2017, 43(7): 1178−1189
[17]	郎劲, 唐立新. 考虑爬坡约束的油井间抽批调度问题. 自动化学报, 2019, 45(2): 388−397 Lang Jin, Tang Li-Xin. Batch scheduling problem of oil well considering ramping constraints in oilfield production. Acta Automatica Sinica, 2019, 45(2): 388−397
[18]	Zhao B X, Gao J M, Chen K, Guo K. Two-generation Pareto ant colony algorithm for multi-objective job shop scheduling problem with alternative process plans and unrelated parallel machines. Journal of Intelligent Manufacturing, 2018, 29(1): 93−108 doi: 10.1007/s10845-015-1091-z
[19]	Wu Y, Gong M G, Ma W P, Wang S F. High-order graph matching based on ant colony optimization. Neurocomputing, 2019, 328: 97−104 doi: 10.1016/j.neucom.2018.02.104
[20]	Eskandari L, Jafarian A, Rahimloo P, Baleanu D. A modified and enhanced ant colony optimization algorithm for traveling salesman problem. Mathematical Methods in Engineering. Springer-Cham, 2019. 257–265
[21]	Stützle T, Hoos H H. MAX-MIN ant system. Future Generation Computer Systems, 2000, 16(8): 889−914 doi: 10.1016/S0167-739X(00)00043-1
[22]	Jia Z H, Leung J Y T. A meta-heuristic to minimize makespan for parallel batch machines with arbitrary job sizes. European Journal of Operational Research, 2015, 240(3): 649−665 doi: 10.1016/j.ejor.2014.07.039
[23]	Deb K, Agrawal S, Pratap A, Meyarivan T. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II. In: Proceedings of the 2000 International Conference on Parallel Problem Solving from Nature. Berlin, Heidelberg: Springer, 2000. 849–858
[24]	Zitzler E, Laumanns M, Thiele L. SPEA2: Improving the strength Pareto evolutionary algorithm. TIK-Report, 2001, 103
[25]	Nebro A J, Durillo J J, Garcia-Nieto J, Coello C C A, Luna F, Alba E. SMPSO: A new PSO-based metaheuristic for multi-objective optimization. In: Proceedings of the 2009 IEEE Symposium on Computational Intelligence in Multi-Criteria Decision-Making. IEEE, 2009. 66–73
[26]	Wang J Q, Leung J Y T. Scheduling jobs with equal-processing-time on parallel machines with non-identical capacities to minimize makespan. International Journal of Production Economics, 2014, 156: 325−331 doi: 10.1016/j.ijpe.2014.06.019
[27]	Jia Z H, Li X H, Leung J Y T. Minimizing makespan for arbitrary size jobs with release times on P-batch machines with arbitrary capacities. Future Generation Computer Systems, 2017, 67: 22−34