求解零空闲流水车间调度问题的离散正弦优化算法

doi:10.16183/j.cnki.jsjtu.2019.321

摘要/Abstract

摘要：

针对以最小化最大完工时间(makespan)为目标的零空闲流水车间调度问题(NIFSP)，提出一种离散正弦优化算法(DSOA)进行求解．受正弦波形的启发，原始的正弦优化算法(SOA)是一种利用正弦函数对个体位置进行更新的全局优化算法．首先，重新定义了适应组合优化问题的位置更新策略，采用一种去除工件数大小可变的迭代贪婪算法来对个体位置进行更新，以提高算法的探索能力．其次，采用了交叉操作和保留精英解的选择策略，避免算法陷入局部最优．最后，为了提高局部搜索的开发能力和算法精度，引入了一种基于插入的局部搜索方法，以便于在当前最优解的周围寻找更好的解．此外，基于Taillard基准，给出了算法性能比较的仿真结果，实验结果验证了所提出的DSOA算法求解NIFSP的有效性．

关键词: 生产调度, 正弦优化算法, 零空闲流水车间调度问题, 迭代贪婪算法, 最大完工时间, 智能优化算法, 局部搜索

Abstract:

Aimed at the no-idle flow-shop scheduling problem (NIFSP) with minimized makespan, a discrete sine optimization algorithm (DSOA) is proposed. Inspired by sine waveforms, the original sine optimization algorithm (SOA) is a global optimization algorithm, which uses the sine function to update the position of search agents. First, the update position strategy to adapt to the combinatorial optimization problem is redefined. An iterated greedy algorithm with a variable removing size is employed to update the position to enhance the exploration ability. Then, a crossover strategy and a selection strategy are applied to avoid the algorithm falling into local optimum. Next, to improve the exploitation ability of local search and the accuracy of the algorithm, an insertion-based local search scheme is applied in DSOA to search for a better solution around the current optimal solution. Finally, based on the Taillard benchmark, the simulation results of performance comparisons are presented. The experimental results demonstrate the effectiveness of the proposed DSOA algorithm for solving NIFSP.

Key words: production scheduling, sine optimization algorithm, no-idle flow-shop scheduling problem (NIFSP), iterated greedy algorithm, makespan, intelligent optimization algorithm, local search

中图分类号:

TP278

赵芮, 顾幸生. 求解零空闲流水车间调度问题的离散正弦优化算法[J]. 上海交通大学学报, 2020, 54(12): 1291-1299.

ZHAO Rui, GU Xingsheng. A Discrete Sine Optimization Algorithm for No-Idle Flow-Shop Scheduling Problem[J]. Journal of Shanghai Jiao Tong University, 2020, 54(12): 1291-1299.

图/表 9

图1

图2

图3

表1

图4

表2

图5

表3

图6

参考文献 22

[1]	LIN J, ZHANG S. An effective hybrid biogeography-based optimization algorithm for the distributed assembly permutation flow-shop scheduling problem[J]. Computers & Industrial Engineering, 2016, 97: 128-136.
[2]	JOHNSON S M. Optimal two- and three-stage production schedules with setup times included[J]. Naval Research Logistics Quarterly, 1954, 1(1): 61-68.
[3]	GONCHAROV Y, SEVASTYANOV S. The flow shop problem with no-idle constraints: A review and approximation[J]. European Journal of Operational Research, 2009, 196(2): 450-456.
[4]	MAKUCHOWSKI M. Permutation, no-wait, no-idle flow shop problems[J]. Archives of Control Sciences, 2015, 25(2): 189-199.
[5]	BAPTISTE P, HGUNY L K. A branch and bound algorithm for the F/no-idle/C_max[C]∥Proceedings of the International Conference on Industrial Engineering and Production Management. Lyon, France: IEEE, 1997: 429-438.
[6]	PAN Q K, WANG L. No-idle permutation flow shop scheduling based on a hybrid discrete particle swarm optimization algorithm[J]. The International Journal of Advanced Manufacturing Technology, 2008, 39(7/8): 796-807.
[7]	DENG G L, GU X S. A hybrid discrete differential evolution algorithm for the no-idle permutation flow shop scheduling problem with makespan criterion[J]. Computers & Operations Research, 2012, 39(9): 2152-2160.
[8]	FATIH TASGETIREN M, PAN Q K, SUGANTHAN P N, et al. A variable iterated greedy algorithm with differential evolution for the no-idle permutation flowshop scheduling problem[J]. Computers & Operations Research, 2013, 40(7): 1729-1743.
[9]	TASGETIREN M F, PAN Q K, SUGANTHAN P N, et al. A discrete artificial bee colony algorithm for the no-idle permutation flowshop scheduling problem with the total tardiness criterion[J]. Applied Mathematical Modelling, 2013, 37(10/11): 6758-6779.
[10]	ZHOU Y Q, CHEN H, ZHOU G. Invasive weed optimization algorithm for optimization no-idle flow shop scheduling problem[J]. Neurocomputing, 2014, 137: 285-292.
[11]	SHEN J N, WANG L, WANG S Y. A bi-population EDA for solving the no-idle permutation flow-shop scheduling problem with the total tardiness criterion[J]. Knowledge-Based Systems, 2015, 74: 167-175.
[12]	刘翱，冯骁毅，邓旭东，等. 求解零空闲置换流水车间调度问题的离散烟花算法[J]. 系统工程理论与实践，2018, 38(11): 2874-2884.
	LIU Ao, FENG Xiaoyi, DENG Xudong, et al. A discrete fireworks algorithm for solving no-idle permutation flow shop problem[J]. Systems Engineering-Theory & Practice, 2018, 38(11): 2874-2884.
[13]	SHAO W S, PI D C, SHAO Z S. Memetic algorithm with node and edge histogram for no-idle flow shop scheduling problem to minimize the makespan crite-rion[J]. Applied Soft Computing, 2017, 54: 164-182.
[14]	SHAO W S, PI D C, SHAO Z S. A hybrid discrete teaching-learning based meta-heuristic for solving no-idle flow shop scheduling problem with total tardiness criterion[J]. Computers & Operations Research, 2018, 94: 89-105.
[15]	MIRJALILI S. SCA: A Sine Cosine Algorithm for solving optimization problems[J]. Knowledge-Based Systems, 2016, 96: 120-133.
[16]	MESHKAT M, PARHIZGAR M. Sine Optimization Algorithm (SOA): A novel optimization algorithm by change update position strategy of search agent in Sine Cosine Algorithm[C]∥2017 3rd Iranian Conference on Intelligent Systems and Signal Processing (ICSPIS). Piscataway, NJ, USA: IEEE, 2017: 11-16.
[17]	LI S, FANG H J, LIU X Y. Parameter optimization of support vector regression based on sine cosine algorithm[J]. Expert Systems With Applications, 2018, 91: 63-77.
[18]	WANG J Z, YANG W D, DU P, et al. A novel hybrid forecasting system of wind speed based on a newly developed multi-objective sine cosine algorithm[J]. Energy Conversion and Management, 2018, 163: 134-150.
[19]	ATTIA A F, EL SEHIEMY R A, HASANIEN H M. Optimal power flow solution in power systems using a novel Sine-Cosine algorithm[J]. International Journal of Electrical Power & Energy Systems, 2018, 99: 331-343.
[20]	LIU W B, JIN Y, PRICE M. A new Nawaz-Enscore-Ham-based heuristic for permutation flow-shop problems with bicriteria of makespan and machine idle time[J]. Engineering Optimization, 2016, 48(10): 1808-1822.
[21]	ZHAO F Q, LIU H, ZHANG Y, et al. A discrete Water Wave Optimization algorithm for no-wait flow shop scheduling problem[J]. Expert Systems With Applications, 2018, 91: 347-363.
[22]	TAILLARD E. Benchmarks for basic scheduling problems[J]. European Journal of Operational Research, 1993, 64(2): 278-285.

算例	α=0.1			α=0.3			α=0.5
算例	avg	min	ARPD	avg	min	ARPD	avg	min	ARPD
Ta051	5442.1	5398	1.14	5401.6	5381^*	0.38	5399.3	5386	0.34
Ta061	5834.1	5833^*	0.02	5833.0	5833^*	0.00	5833.0	5833^*	0.00
Ta071	6751.5	6736	0.35	6742.8	6728^*	0.22	6740.1	6728^*	0.18
Ta081	9337.6	9327	0.21	9327.8	9318^*	0.11	9324.2	9319	0.07

算例	规模		SOA	DSOA¹		DSOA²		DSOA³		DSOA
算例	n	m	C_max	C_max	PIP	C_max	PIP	C_max	PIP	C_max	PIP
Ta001	20	5	1 439.2	1 384.5	3.801%	1 383.5	3.870%	1 381.4	4.016%	1 380.6	4.072%
Ta011	20	10	2 331.0	2 198.7	5.676%	2 196.6	5.766%	2 198.6	5.680%	2 196.4	5.774%
Ta021	20	20	3 621.5	3 222.9	11.006%	3 215.0	11.225%	3213.1	11.277%	3 212.2	11.302%
Ta031	50	5	3 082.6	3 014.0	2.225%	3 014.0	2.225%	3 014.0	2.225%	3 014.0	2.225%
Ta041	50	10	3 935.8	3 435.7	12.706%	3 438.1	12.645%	3427.2	12.922%	3 423.0	13.029%
Ta051	50	20	6 383.3	5 430.2	14.931%	5 450.0	14.621%	5 411.1	15.230%	5 399.3	15.415%
Ta061	100	5	6 092.9	5 833.4	4.259%	5 833.1	4.264%	5 833.0	4.266%	5 833.0	4.266%
Ta071	100	10	7 403.3	6 756.7	8.734%	6 764.6	8.627%	6 750.0	8.824%	6 740.1	8.958%
Ta081	100	20	10 735.4	9 355.5	12.854%	9 353.2	12.875%	9 327.7	13.113%	9 324.2	13.145%
Ta091	200	10	12 826.8	11 683.4	8.914%	11 691.2	8.853%	11 651.6	9.162%	11 645.4	9.210%
Ta101	200	20	17 351.8	14 918.5	14.023%	14 982.0	13.657%	14 857.5	14.375%	14 841.8	14.465%
均值					9.012%		8.966%		9.190%		9.260%

规模		DSOA		DFWA-LS		IWO
n	m	ARPD	SD	ARPD	SD	ARPD	SD
20	5	0.05	0.008	0.15	0.013	0.92	0.083
	10	0.21	0.034	0.62	0.060	2.37	0.156
	20	0.21	0.057	0.51	0.093	2.33	0.272
50	5	0.00	0.000	0.01	0.004	0.49	0.103
	10	0.29	0.048	0.52	0.085	2.76	0.311
	20	0.37	0.113	0.64	0.174	4.04	0.497
100	5	0.00	0.002	0.03	0.011	0.61	0.141
	10	0.05	0.016	0.13	0.056	1.39	0.361
	20	0.22	0.091	0.35	0.154	3.66	0.651
200	10	0.05	0.041	0.13	0.098	1.85	0.397
	20	0.20	0.146	0.27	0.244	3.93	0.891
均值		0.15	0.050	0.31	0.090	2.21	0.351