考虑设备故障的鲁棒调度计划模板的建模优化

doi:10.16183/j.cnki.jsjtu.2019.146

摘要/Abstract

摘要：

为了解决不确定环境下的飞机移动装配线调度问题，提出了依赖感知器的果蝇优化算法(PDFOA)，生成具有较强鲁棒性的模板装配计划．PDFOA在借鉴果蝇优化算法的基础上设计了窄域嗅觉搜索操作与窄域视觉搜索操作，对邻域解进行高效的搜索与筛选．同时，为了加强算法的全局搜索能力，设置了果蝇“知识记忆库”记录寻优过程．最后，在各作业规模的算例下通过抽样仿真实验将PDFOA与禁忌搜索、遗传算法以及免疫粒子群优化算法进行对比，验证了PDFOA的有效性．

关键词: 设备故障与修复, 果蝇优化算法, 前摄型调度, 抽样仿真, 鲁棒性模板计划

Abstract:

In order to solve the scheduling problem of aircraft moving assembly line in uncertainty environment, this paper proposes a perceptron-dependent fruit fly optimization algorithm(PDFOA) to generate the assembly scheduling template with strong robustness. The proposed PDFOA, taking the fruit fly optimization algorithm as the basis, designs narrow-field osphresis-search operation and narrow-field vision-search operation which is helpful for searching and choosing neighborhood solutions. Simultaneously, the PDFOA sets up a memory library to enhance the global search ability. Finally, simulation experiments are conducted using different testing samples on different job scales. The proposed PDFOA is compared with tabu search, the genetic algorithm and the immune particle swarm optimization algorithm. The results demonstrate the effectiveness of the PDFOA.

Key words: failure and repair of equipments, fruit fly optimization algorithm, proactive scheduling, sampling simulation, robust baseline scheduling

中图分类号:

TP29

方佳, 陆志强. 考虑设备故障的鲁棒调度计划模板的建模优化[J]. 上海交通大学学报, 2020, 54(12): 1278-1290.

FANG Jia, LU Zhiqiang. Modeling and Optimization of Robust Scheduling Template Considering Equipment Failure[J]. Journal of Shanghai Jiao Tong University, 2020, 54(12): 1278-1290.

图/表 12

图1

图2

图3

图4

图5

图6

表1

表2

图7

表3

图8

表4

参考文献 17

[1]	KUMAR N, VIDYARTHI D P. A model for resource-constrained project scheduling using adaptive PSO[J]. Soft Computing, 2016, 20(4): 1565-1580.
[2]	ELSAYED S, SARKER R, RAY T, et al. Consolidated optimization algorithm for resource-constrained project scheduling problems[J]. Information Sciences, 2017, 418/419: 346-362.
[3]	LIU J, QIAO F, MA Y M, et al. Novel slack-based robust scheduling rule for a semiconductor manufacturing system with uncertain processing time[J]. Frontiers of Engineering Management, 2018, 5(4): 507-514.
[4]	ELLOUMI S, FORTEMPS P, LOUKIL T. Multi-objective algorithms to multi-mode resource-constrained projects under mode change disruption[J]. Computers & Industrial Engineering, 2017, 106: 161-173.
[5]	PAPROCKA I, SKOLUD B. A hybrid multi-objective immune algorithm for predictive and reactive scheduling[J]. Journal of Scheduling, 2017, 20(2): 165-182.
[6]	VAN DE VONDER S, DEMEULEMEESTER E, HERROELEN W. Proactive heuristic procedures for robust project scheduling: An experimental analysis[J]. European Journal of Operational Research, 2008, 189(3): 723-733.
[7]	VAN DE VONDER S, DEMEULEMEESTER E, HERROELEN W. A classification of predictive-reactive project scheduling procedures[J]. Journal of Scheduling, 2007, 10(3): 195-207.
[8]	VARAKANTHAM P, FU N, LAU H C. A proactive sampling approach to project scheduling under uncertainty[C]∥30th AAAI Conference on Artificial Intelligence. Phoenix, Arizona, USA: AAAI, 2016: 3195-3201.
[9]	张国辉，吴立辉，聂黎，等. 考虑机器故障的柔性作业车间鲁棒调度方法[J]. 系统仿真学报，2016, 28(4): 867-873.
	ZHANG Guohui, WU Lihui, NIE Li, et al. Robust flexible job shop scheduling method with machine breakdowns[J]. Journal of System Simulation, 2016, 28(4): 867-873.
[10]	WANG D J, LIU F, WANG Y Z, et al. A knowledge-based evolutionary proactive scheduling approach in the presence of machine breakdown and deterioration effect[J]. Knowledge-Based Systems, 2015, 90: 70-80.
[11]	赵婵媛，陆志强，崔维伟. 考虑随机故障的流水线调度问题前摄优化方法[J]. 浙江大学学报(工学版), 2016, 50(4): 641-649.
	ZHAO Chanyuan, LU Zhiqiang, CUI Weiwei. Proactive scheduling optimization on flow shops with random machine breakdowns[J]. Journal of Zhejiang University (Engineering Science), 2016, 50(4): 641-649.
[12]	陆志强，张思源，崔维伟. 集成预防性维护和流水线调度的鲁棒性优化研究[J]. 自动化学报，2015, 41(5): 906-913.
	LU Zhiqiang, ZHANG Siyuan, CUI Weiwei. Integrating production scheduling and maintenance policy for robustness in flow shop problems[J]. Acta Automatica Sinica, 2015, 41(5): 906-913.
[13]	PAN W T. A new Fruit Fly Optimization Algorithm: Taking the financial distress model as an example[J]. Knowledge-Based Systems, 2012, 26(26): 69-74.
[14]	LAMBRECHTS O, DEMEULEMEESTER E, HERROELEN W. A tabu search procedure for developing robust predictive project schedules[J]. International Journal of Production Economics, 2008, 111(2): 493-508.
[15]	RANJBAR M, KIANFAR F, SHADROKH S. Solving the resource availability cost problem in project scheduling by path relinking and genetic algorithm[J]. Applied Mathematics & Computation, 2008, 196(2): 879-888.
[16]	LAMBRECHTS O, DEMEULEMEESTER E, HERROELEN W. Time slack-based techniques for robust project scheduling subject to resource uncertainty[J]. Annals of Operations Research, 2011, 186(1): 443-464.
[17]	孙虎，周晶燕. 装配作业车间调度的免疫粒子群算法实现[J]. 武汉理工大学学报(信息与管理工程版), 2019, 41(3): 282-286.
	SUN Hu, ZHOU Jingyan. Implementation of immune particle swarm optimization algorithm for assembly job shop scheduling[J]. Journal of Wuhan University of Technology (Information & Management Engineering), 2019, 41(3): 282-286.

作业规模	实验组别	PDFOA		TS		GAP/%	R
作业规模	实验组别	Z	t^al/s	Z	t^al/s	GAP/%	R
30	1	3 257.742	21.05	3 153.854	19.30	－3.29	0.5
	2	2 971.501	23.16	3 231.603	19.40	8.75	0.6
	3	2 937.349	21.47	3 081.400	21.90	4.90	0.7
	4	3 039.011	23.45	3 098.801	30.10	1.97	0.7
	5	3 074.150	22.02	2 969.351	23.40	－3.53	0.5
Ave₃₀	—	3 055.951	22.23	3 107.002	22.82	1.67	—

作业规模	实验组别	PDFOA		TS		GAP/%	R
作业规模	实验组别	Z	t^al/s	Z	t^al/s	GAP/%	R
60	1	9 667.531	71.79	9 943.686	150.70	2.86	0.7
	2	9 551.523	67.62	9 831.644	137.70	2.93	0.6
	3	9 503.118	61.37	10 215.929	172.60	7.50	0.5
	4	9 724.105	66.95	10 082.333	175.20	3.68	0.6
	5	9 472.344	64.60	9 658.903	182.00	1.97	0.6
Ave₆₀	—	9 583.724	66.47	9 946.499	163.64	3.79	—
90	1	9 095.379	104.18	10 301.729	480.20	13.26	0.7
	2	9 589.933	94.70	9 793.311	457.90	2.12	0.7
	3	9 369.342	104.30	10 238.112	511.80	9.27	0.7
	4	9 777.214	96.57	10 317.234	474.10	5.52	0.7
	5	9 387.405	94.13	10 420.824	484.70	11.01	0.7
Ave₉₀	—	9 443.855	98.78	10 214.242	481.74	8.16	—
120	1	10 591.995	171.44	11 060.492	1 245.05	4.42	0.6
	2	9 508.043	179.99	10 999.779	1 305.17	15.69	0.8
	3	10 152.130	181.57	11 028.171	1 245.05	8.63	0.7
	4	10 056.386	174.82	10 823.794	1 542.50	7.63	0.6
	5	9 987.023	171.44	10 669.859	1 343.85	6.84	0.5
Ave₁₂₀	—	10 059.120	175.85	10 916.419	1 336.32	8.52	—

作业规模	IPSO		GA		PDFOA
作业规模	Z	t^al/s	Z	t^al/s	Z	t^al/s
30	4 185.22	16 723.950	3 642.85	17 010.340	3 232.68	21.483
60	18 313.33	57 523.320	18 186.85	65 243.440	12 090.34	99.285
90	13 853.76	97 861.270	12 472.02	109 085.600	9 693.10	128.982
120	14 272.08	115 713.200	11 923.75	124 381.700	9 718.58	211.281

作业规模	组别	PDFOA		GA		IPSO		GAP		R
作业规模	组别	Z	t^al/s	t^al/s	Z	t^al/s	GAP₁/%	GAP₂/%	R₁	R₂
30	1	3 059.399	28.015	4 069.015	4.603	4 138.863	3.945	33.00	35.28	1.0	1.0
	2	3 151.645	27.220	4 107.190	4.065	4 138.760	4.489	30.32	31.32	1.0	1.0
	3	3 167.558	26.129	3 985.915	4.342	4 139.131	4.508	25.84	30.67	1.0	1.0
	4	3 031.079	26.523	4 038.459	4.083	4 196.570	4.220	33.24	38.45	1.0	1.0
	5	2 986.407	26.062	4 122.606	3.976	4 142.255	4.389	38.05	38.70	1.0	1.0
Ave	—	3 079.218	26.790	4 064.637	4.214	4 151.116	4.310	32.00	34.81	—	—
60	1	9 604.442	72.216	12 558.948	9.042	12 512.393	8.810	30.76	30.28	1.0	1.0
	2	9 534.382	73.693	12 559.403	9.625	12 619.900	9.955	31.73	32.36	0.9	1.0
	3	9 912.964	74.979	12 586.081	9.256	12 299.707	10.983	26.97	24.08	1.0	1.0
	4	9 496.693	69.484	12 373.219	8.824	12 783.132	10.156	30.29	34.61	0.9	1.0
	5	9 187.852	66.451	12 348.720	8.190	12 726.143	10.094	34.40	38.51	1.0	1.0
Ave	—	9 547.267	71.364	12 485.274	8.987	12 588.255	9.999	30.77	31.85	—	—
90	1	9 378.256	124.456	12 854.942	12.674	13 055.721	13.711	37.07	39.21	1.0	1.0
	2	9 470.230	122.534	12 480.518	12.915	12 523.518	16.238	31.79	32.24	1.0	1.0
	3	9 279.456	99.309	12 680.626	12.744	13 515.244	16.766	36.65	45.65	1.0	1.0
	4	9 466.363	112.793	12 597.001	12.887	13 158.924	16.244	33.07	39.01	1.0	1.0
	5	9 592.995	96.299	12 657.266	12.112	12 967.308	16.212	31.94	35.17	1.0	1.0
Ave	—	9 437.460	111.078	12 654.071	12.667	13 044.143	15.834	34.08	38.22	—	—
120	1	10 689.500	196.357	14 936.332	20.671	14 488.041	22.008	39.73	35.54	1.0	1.0
	2	9 540.459	236.136	14 160.884	21.286	14 135.028	26.320	48.43	48.16	1.0	1.0
	3	10 724.056	184.227	14 244.757	20.777	14 742.373	26.744	32.83	37.47	1.0	0.9
	4	10 505.718	206.063	14 654.288	19.446	15 414.342	26.820	39.49	46.72	1.0	1.0
	5	9 984.351	189.940	14 123.134	18.927	14 777.539	26.614	41.45	48.01	1.0	1.0
Ave	—	10 288.817	202.544	14 423.879	20.222	14711.465	25.701	40.19	42.98	—	—