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

doi:10.13229/j.cnki.jdxbgxb20210622

摘要/Abstract

摘要：

考虑工人操作熟练度对双资源约束柔性作业车间调度的影响，提出改进的Jaya算法对其进行求解。与经典柔性作业车间不同的是，双资源约束柔性作业车间调度问题（DRCFJSP）需要同时处理工件排序、设备分配和工人指派3个子问题。通过改进标准Jaya算法以使其适用于求解具有最小完工时间准则的DRCFJSP，具体改进包括设计三维向量编码方案，结合设备、工人和工件的集成特征进行种群初始化，围绕车间调度离散化特点扩展算法更新迭代机制，并设计了基于关键路径的局部邻域搜索策略和接受准则。对扩展后的柔性作业车间测试算例进行求解，并与现有算法进行比较，结果表明：本文算法具有一定的有效性和优越性，表明本文优化调度方法能在有限的资源下实现人员合理配置和工件快速排序。

关键词: 计算机应用, 双资源约束, 柔性作业车间调度, Jaya算法, 关键路径, 局部邻域搜索

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

中图分类号:

TP29

郭鹏,赵文超,雷坤. 基于改进Jaya算法的双资源约束柔性作业车间调度[J]. 吉林大学学报(工学版), 2023, 53(2): 480-487.

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.

图/表 6

表1

DRCFJSP问题实例"

工件	工序	$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	-

表1

图1

表2

工人-设备映射信息"

算例	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}$

表2

表3

算例计算结果"

算例	$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

表3

表4

3种算法的MRPD、ARPD和SRPD计算结果"

算例	$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

表4

图2

参考文献 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.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

[1]	祁贤雨,王巍,王琳,赵玉飞,董彦鹏. 基于物体语义栅格地图的语义拓扑地图构建方法[J]. 吉林大学学报(工学版), 2023, 53(2): 569-575.
[2]	时小虎,吴佳琦,吴春国,程石,翁小辉,常志勇. 基于残差网络的弯道增强车道线检测方法[J]. 吉林大学学报(工学版), 2023, 53(2): 584-592.
[3]	刘近贞,高国辉,熊慧. 用于脑组织分割的多尺度注意网络[J]. 吉林大学学报(工学版), 2023, 53(2): 576-583.
[4]	赵宏伟,张健荣,朱隽平,李海. 基于对比自监督学习的图像分类框架[J]. 吉林大学学报(工学版), 2022, 52(8): 1850-1856.
[5]	秦贵和,黄俊锋,孙铭会. 基于双手键盘的虚拟现实文本输入[J]. 吉林大学学报(工学版), 2022, 52(8): 1881-1888.
[6]	胡丹,孟新. 基于时变网格的对地观测卫星搜索海上船舶方法[J]. 吉林大学学报(工学版), 2022, 52(8): 1896-1903.
[7]	曲福恒,丁天雨,陆洋,杨勇,胡雅婷. 基于邻域相似性的图像码字快速搜索算法[J]. 吉林大学学报(工学版), 2022, 52(8): 1865-1871.
[8]	白天,徐明蔚,刘思铭,张佶安,王喆. 基于深度神经网络的诉辩文本争议焦点识别[J]. 吉林大学学报(工学版), 2022, 52(8): 1872-1880.
[9]	周丰丰,朱海洋. 基于三段式特征选择策略的脑电情感识别算法SEE[J]. 吉林大学学报(工学版), 2022, 52(8): 1834-1841.
[10]	周丰丰,张亦弛. 基于稀疏自编码器的无监督特征工程算法BioSAE[J]. 吉林大学学报(工学版), 2022, 52(7): 1645-1656.
[11]	王军,徐彦惠,李莉. 低能耗支持完整性验证的数据融合隐私保护方法[J]. 吉林大学学报(工学版), 2022, 52(7): 1657-1665.
[12]	康耀龙,冯丽露,张景安,陈富. 基于谱聚类的高维类别属性数据流离群点挖掘算法[J]. 吉林大学学报(工学版), 2022, 52(6): 1422-1427.
[13]	王文军,余银峰. 考虑数据稀疏的知识图谱缺失连接自动补全算法[J]. 吉林大学学报(工学版), 2022, 52(6): 1428-1433.
[14]	陈雪云,贝学宇,姚渠,金鑫. 基于G⁃UNet的多场景行人精确分割与检测[J]. 吉林大学学报(工学版), 2022, 52(4): 925-933.
[15]	方世敏. 基于频繁模式树的多来源数据选择性集成算法[J]. 吉林大学学报(工学版), 2022, 52(4): 885-890.