基于改进Jaya算法的双资源约束柔性作业车间调度

doi:10.13229/j.cnki.jdxbgxb20210622

Abstract

Abstract:

To consider worker's operational proficiency in the dual-resource constrained flexible job shop scheduling problem（DRCFJSP）， an improved Jaya algorithm is proposed to solve the DRCFJSP in this paper. Unlike the flexible job shop scheduling problem， the DRCFJSP deals with the three sub-problems machine allocation， job sequence and worker assignment. The standard Jaya algorithm is improved for solving the DRCFJSP problem with the minimization of makespan. The main improvements include introducing a three-dimensional vector representation coding scheme， using the properties of jobs， machines and workers to implement the population initialization， adopting the discretization characteristics of shop scheduling to update the iterative mechanism， and designing the neighborhood search operators and acceptance criteria based on the critical path， are presented. The test instances were generated based on the flexible job shop scheduling benchmark and were used to test the performance of the proposed algorithm. The computational results demonstrate that the improved Jaya algorithm is efficient and effective. Moreover， the improved Jaya algorithm can realize the reasonable allocation of personnel and rapid sequencing of jobs under the limited resources.

Key words: computer application, dual resource constraints, flexible job shop scheduling, Jaya algorithm, critical path, local neighborhood search

CLC Number:

TP29

Peng GUO,Wen-chao ZHAO,Kun LEI. Dual⁃resource constrained flexible job shop optimal scheduling based on an improved Jaya algorithm[J].Journal of Jilin University(Engineering and Technology Edition), 2023, 53(2): 480-487.

Figures/Tables 6

Table 1

Examples of DRCFJSP problem"

工件	工序	$M 1$		$M 2$		$M 3$
工件	工序	$W 1$	$W 2$	$W 1$	$W 2$	$W 1$	$W 2$
$J 1$	$O 11$	3	4	7	6	-	-
$J 1$	$O 12$	3	2	3	7	-	2
$J 2$	$O 21$	-	-	3	5	-	4
$J 2$	$O 22$	3	5	2	4	-	3
$J 3$	$O 31$	-	-	2	2	3	4
	$O 32$	3	2	3	6	5	-
	$O 33$	3	5	-	-	7	-
$J 4$	$O 41$	3	5	-	-	4	-

Table 1

Fig.1

Table 2

Worker-equipment mapping information"

算例	w	每个工人能够操作的机器集合
DMK1~2	4	$W 1 = {M 1, M 3, M 5}, W 2 = {M 2, M 4, M 5}, W 3 = {M 1, M 4, M 6}, W 4 = {M 2, M 3, M 4}$
DMK3~4	6	$W 1 = {M 1, M 5}, W 2 = {M 2, M 4}, W 3 = {M 1, M 4, M 6}, W 4 = {M 2, M 3, M 6, M 7}, W 5 = {M 6, M 7, M 8}, W 6 = {M 5, M 8}$
DMK5	3	$W 1 = {M 1, M 3, M 4}, W 2 = {M 2, M 4}, W 3 = {M 1, M 2, M 3}$
DMK6，DMK10	8	$W 1 = {M 1, M 8, M 10}, W 2 = {M 2, M 7, M 11}, W 3 = {M 3, M 4, M 6, M 11}, W 4 = {M 2, M 9, M 12, M 13}, W 5 = {M 6, M 7, M 8, M 15}, W 6 = {M 5, M 8, M 10}, W 7 = {M 4, M 9, M 14, M 15}, W 8 = {M 1, M 3, M 10, M 14}$
DMK7	4	$W 1 = {M 1, M 3, M 5}, W 2 = {M 2, M 4}, W 3 = {M 3, M 4}, W 4 = {M 1, M 2, M 5}$
DMK8，DMK9	6	$W 1 = {M 1, M 3, M 5}, W 2 = {M 2, M 4, M 9}, W 3 = {M 3, M 4, M 8, M 10}, W 4 = {M 1, M 7, M 9}, W 5 = {M 5, M 6, M 7}, W 6 = {M 2, M 4, M 8, M 10}$

Table 2

Table 3

Computational results of the instances"

算例	$C m a x l o w$	Jaya		VNS		KGFOA
算例	$C m a x l o w$	$C m a x$	CPU/s	$C m a x$	CPU/s	$C m a x$	CPU/s
DMK1	63	63	4.83	68	4.28	66	3.14
DMK2	51	54	4.06	55	4.38	56	3.23
DMK3	190	235	114.94	272	31.00	279	13.44
DMK4	69	89	6.89	86	5.39	81	5.28
DMK5	287	293	30.24	323	34.80	310	15.11
DMK6	89	109	88.65	129	22.20	115	11.23
DMK7	184	228	62.85	216	21.9	204	10.47
DMK8	536	623	194.26	651	114	649	59.22
DMK9	437	536	148.52	571	117	515	52.86
DMK10	328	360	108.43	454	89.5	427	49.43

Table 3

Table 4

MRPD、ARPDandSRPDof the three algorithms"

算例	$C m a x l o w$	$M R P D$			$A R P D$			$S R P D$
算例	$C m a x l o w$	Jaya	VNS	KGFOA	Jaya	VNS	KGFOA	Jaya	VNS	KGFOA
DMK1	63	0	7.93	4.76	6.10	17.32	8.20	2.68	3.58	0
DMK2	51	5.88	7.84	9.80	11.27	22.55	7.69	2.76	7.65	0
DMK3	190	25.79	43.15	46.84	28.86	48.78	48.94	1.42	4.46	3.12
DMK4	69	28.98	24.63	17.39	32.75	32.46	26.28	2.17	5.84	6.28
DMK5	287	2.10	10.97	8.01	6.45	12.67	9.21	1.60	1.08	1.43
DMK6	89	22.47	44.94	29.21	29.60	49.66	32.28	2.64	2.83	3.54
DMK7	184	23.91	17.39	10.98	27.50	24.67	13.38	1.73	3.90	3.45
DMK8	536	20.14	21.46	21.08	21.40	22.91	22.36	1.49	1.69	1.33
DMK9	437	22.65	30.66	17.85	26.06	35.08	19.36	1.40	2.54	1.88
DMK10	328	9.76	38.41	30.18	14.02	42.16	31.67	1.26	3.19	2.25

Table 4

Fig.2

References 25

1	肖世昌,吴自高,孙树栋, 等. 双资源约束的鲁棒Job Shop调度问题研究[J]. 机械工程学报, 2021, 57(4): 227-239.
	Xiao Shi-chang, Wu Zi-gao, Sun Shu-dong, et al. Research on the dual-resource constrained robust job shop scheduling problems[J]. Journal of Mechanical Engineering, 2021, 57(4): 227-239.
2	谢志强,郭禾,苏文秀, 等. 存在多工序同时结束的多车间逆序综合调度算法[J]. 吉林大学学报(工学版), 2018, 48(2): 578-587.
	Xie Zhi-qiang, Guo He, Su Wen-xiu, et al. Reversal sequence integrated scheduling algorithm of multiple workshop with multi-procedures ended together[J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(2): 578-587.
3	Xie J, Gao L, Peng K K, et al. Review on flexible job shop scheduling[J]. IET Collaborative Intelligent Manufacturing, 2019, 1(3): 67-77.
4	Li X Y, Gao L. An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem[J]. International Journal of Production Economics, 2016, 174: 93-110.
5	Ding H J, Gu X S. Improved particle swarm optimization algorithm based novel encoding and decoding schemes for flexible job shop scheduling problem[J]. Computers & Operations Research, 2020, 121: 104951.
6	李俊青,杜宇,田杰, 等. 带运输资源约束柔性作业车间调度问题的人工蜂群算法[J]. 电子学报, 2021, 49(2): 324-330.
	Li Jun-qing, Du Yu, Tian Jie, et al. An artificial bee colony algorithm for flexible job shop scheduling with transportation resource constraints[J]. Acta Electronica Sinica, 2021, 49(2): 324-330.
7	孙宝凤,任欣欣,郑再思, 等. 考虑工人负荷的多目标流水车间优化调度[J]. 吉林大学学报(工学版), 2021, 51(3): 900-909.
	Sun Bao-feng, Ren Xin-xin, Zheng Zai-si, et al. Multi-objective flow shop optimal scheduling considering worker′s load[J]. Journal of Jilin University (Engineering and Technology Edition), 2021, 51(3): 900-909.
8	吴锐,郭顺生,李益兵, 等. 改进人工蜂群算法求解分布式柔性作业车间调度问题[J]. 控制与决策, 2019, 34(12): 2527-2536.
	Wu Rui, Guo Shun-sheng, Li Yi-bing, et al. Improved artificial bee colony algorithm for distributed and flexible job-shop scheduling problem[J]. Control and Decision, 2019, 34(12): 2527-2536.
9	Cao X Z, Yang Z H. An improved genetic algorithm for dual-resource constrained flexible job shop scheduling[C]∥Fourth International Conference on Intelligent Computation Technology and Automation, Shenzhen,China, 2011: 42-45.
10	Lei D M, Guo X P. Variable neighborhood search for dual-resource constrained flexible job shop scheduling[J]. International Journal of Production Research, 2014, 52(9): 2519-2529.
11	Zheng X L, Wang L. A knowledge-guided fruit fly optimization algorithm for dual resource constrained flexible job-shop scheduling problem[J]. International Journal of Production Research, 2016, 54(18): 5554-5566.
12	Gao L, Pan Q K. A shuffled multi-swarm micro-migrating birds optimizer for a multi-resource-constrained flexible job shop scheduling problem[J]. Information Sciences, 2016, 372: 655-676.
13	Rao R. Jaya: a simple and new optimization algorithm for solving constrained and unconstrained optimization problems[J]. International Journal of Industrial Engineering Computations, 2016, 7(1): 19-34.
14	Zhang Y D, Yang X J. Tea category identification using a novel fractional fourier entropy and Jaya algorithm[J]. Entropy, 2016, 18(3): 1-17.
15	Rao R, Waghmare G. A new optimization algorithm for solving complex constrained design optimization problems[J]. Engineering Optimization, 2017, 49(1): 60-83.
16	Degertekin S O, Lamberti L, Ugur I B. Sizing, layout and topology design optimization of truss structures using the Jaya algorithm[J]. Applied Soft Computing, 2018, 70: 903-928.
17	Mishra A, Shrivastava D, Shiv N U. A TLBO and a Jaya heuristics for permutation flow shop scheduling to minimize the sum of inventory holding and batch delay costs[J]. Computers & Industrial Engineering, 2018, 124: 509-522.
18	Buddala R, Mahapatra S. Improved teaching-learning-based and JAYA optimization algorithms for solving flexible flow shop scheduling problems[J]. Journal of Industrial Engineering International, 2018, 14(3): 555-570.
19	Gao K Z, Yang F J, Zhou M C, et al. Flexible job-shop rescheduling for new job insertion by using discrete Jaya algorithm[J]. IEEE Transactions on Cybernetics, 2019, 49(5): 1944-1955.
20	Li J Q, Deng J W, Li C Y. An improved Jaya algorithm for solving the flexible job shop scheduling problem with transportation and setup times[J]. Knowledge-Based Systems, 2020, 200: 106032.
21	Caldeira R H, Gnanavelbabu A. A pareto based discrete Jaya algorithm for multi-objective flexible job shop scheduling problem[J]. Expert Systems with Applications, 2021, 170: 114567.
22	Kacem I, Hammadi S, Borne P. Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part C(Applications and Reviews),2002,32(1): 1-13.
23	Guo J, Gao K Z, Wang C, et al. Discrete Jaya algorithm for solving flexible job shop rescheduling problem[C]∥29th Chinese Control And Decision Conference, Chongqing, China, 2017, 6010-6015.
24	Li J Q, Pan Q K, Suganthan P N, et al. A hybrid tabu search algorithm with an efficient neighborhood structure for the flexible job shop scheduling problem[J]. International Journal of Advanced Manufacturing Technology, 2011, 52(5): 683-697.
25	Brandimarte P. Routing and scheduling in a flexible job shop by tabu search[J]. Annals of Operations Research, 1993, 41(3): 157-183.

Related Articles 15

[1]	Xian-yu QI,Wei WANG,Lin WANG,Yu-fei ZHAO,Yan-peng DONG. Semantic topological map building with object semantic grid map [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(2): 569-575.
[2]	Xiao-hu SHI,Jia-qi WU,Chun-guo WU,Shi CHENG,Xiao-hui WENG,Zhi-yong CHANG. Residual network based curve enhanced lane detection method [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(2): 584-592.
[3]	Jin-Zhen Liu,Guo-Hui Gao,Hui Xiong. Multi⁃scale attention network for brain tissue segmentation [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(2): 576-583.
[4]	Gui-he QIN,Jun-feng HUANG,Ming-hui SUN. Text input based on two⁃handed keyboard in virtual environment [J]. Journal of Jilin University(Engineering and Technology Edition), 2022, 52(8): 1881-1888.
[5]	Fu-heng QU,Tian-yu DING,Yang LU,Yong YANG,Ya-ting HU. Fast image codeword search algorithm based on neighborhood similarity [J]. Journal of Jilin University(Engineering and Technology Edition), 2022, 52(8): 1865-1871.
[6]	Tian BAI,Ming-wei XU,Si-ming LIU,Ji-an ZHANG,Zhe WANG. Dispute focus identification of pleading text based on deep neural network [J]. Journal of Jilin University(Engineering and Technology Edition), 2022, 52(8): 1872-1880.
[7]	Feng-feng ZHOU,Hai-yang ZHU. SEE： sense EEG⁃based emotion algorithm via three⁃step feature selection strategy [J]. Journal of Jilin University(Engineering and Technology Edition), 2022, 52(8): 1834-1841.
[8]	Feng-feng ZHOU,Yi-chi ZHANG. Unsupervised feature engineering algorithm BioSAE based on sparse autoencoder [J]. Journal of Jilin University(Engineering and Technology Edition), 2022, 52(7): 1645-1656.
[9]	Jun WANG,Yan-hui XU,Li LI. Data fusion privacy protection method with low energy consumption and integrity verification [J]. Journal of Jilin University(Engineering and Technology Edition), 2022, 52(7): 1657-1665.
[10]	Yao-long KANG,Li-lu FENG,Jing-an ZHANG,Fu CHEN. Outlier mining algorithm for high dimensional categorical data streams based on spectral clustering [J]. Journal of Jilin University(Engineering and Technology Edition), 2022, 52(6): 1422-1427.
[11]	Wen-jun WANG,Yin-feng YU. Automatic completion algorithm for missing links in nowledge graph considering data sparsity [J]. Journal of Jilin University(Engineering and Technology Edition), 2022, 52(6): 1428-1433.
[12]	Xue-yun CHEN,Xue-yu BEI,Qu YAO,Xin JIN. Pedestrian segmentation and detection in multi-scene based on G-UNet [J]. Journal of Jilin University(Engineering and Technology Edition), 2022, 52(4): 925-933.
[13]	Shi-min FANG. Multiple source data selective integration algorithm based on frequent pattern tree [J]. Journal of Jilin University(Engineering and Technology Edition), 2022, 52(4): 885-890.
[14]	Da-xiang LI,Meng-si CHEN,Ying LIU. Spontaneous micro-expression recognition based on STA-LSTM [J]. Journal of Jilin University(Engineering and Technology Edition), 2022, 52(4): 897-909.
[15]	Xiao-hui WEI,Yan-wei MIAO,Xing-wang WANG. Rhombus sketch： adaptive and more accurate sketch for streaming data [J]. Journal of Jilin University(Engineering and Technology Edition), 2022, 52(4): 874-884.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Comments

Recommended 10

[1]	LI Shoutao, LI Yuanchun. Autonomous Mobile Robot Control Algorithm Based on Hierarchical Fuzzy Behaviors in Unknown Environments[J]. 吉林大学学报(工学版), 2005, 35(04): 391 -397 .
[2]	Liu Qing-min，Wang Long-shan，Chen Xiang-wei，Li Guo-fa. Ball nut detection by machine vision[J]. 吉林大学学报(工学版), 2006, 36(04): 534 -538 .
[3]	Li Hong-ying; Shi Wei-guang;Gan Shu-cai. Electromagnetic properties and microwave absorbing property of Z type hexaferrite Ba_3-xLa_xCo₂Fe₂₄O₄₁[J]. 吉林大学学报(工学版), 2006, 36(06): 856 -0860 .
[4]	Li Yue-ying，Liu Yong-bing，Chen Hua . Surface hardening and tribological properties of a cam materials[J]. 吉林大学学报(工学版), 2007, 37(05): 1064 -1068 .
[5]	Che Xiang-jiu，Liu Da-you，Wang Zheng-xuan . Construction of joining surface with G¹ continuity for two NURBS surfaces[J]. 吉林大学学报(工学版), 2007, 37(04): 838 -841 .
[6]	Liu Han-bing, Jiao Yu-ling, Liang Chun-yu,Qin Wei-jun . Effect of shape function on computing precision in meshless methods[J]. 吉林大学学报(工学版), 2007, 37(03): 715 -0720 .
[7]	Yang Qing-fang, Chen Lin . Division approach of traffic control work zone[J]. 吉林大学学报(工学版), 2006, 36(增刊2): 139 -142 .
[8]	Yu Hua-nan， Kang Jian . An improved blind multiuser detection scheme based on Kalman filter[J]. 吉林大学学报(工学版), 2006, 36(增刊2): 122 -125 .
[9]	Zhang He-sheng, Zhang Yi, Wen Hui-min, Hu Dong-cheng . Estimation approaches of average link travel time using GPS data[J]. 吉林大学学报(工学版), 2007, 37(03): 533 -0537 .
[10]	Qu Zhao-wei，Chen Hong-yan，Li Zhi-hui，Hu Hong-yu，Wei Wei . 2D view reconstruction method based on single calibration pattern [J]. 吉林大学学报(工学版), 2007, 37(05): 1159 -1163 .

Dual⁃resource constrained flexible job shop optimal scheduling based on an improved Jaya algorithm

RICH HTML

PDF (PC)