定制化生产模式下智能制造单元建模与布局优化求解

doi:10.16381/j.cnki.issn1003-207x.2024.0252

摘要/Abstract

摘要：

本文针对具有资源协同约束的智能制造单元生产系统，以最大化系统平均产出率为目标，探讨设施布局的二次分配优化问题，并提出基于排队网的元启发式优化算法进行求解。由于定制生产模式下生产系统存在诸多不确定性因素，因此，建立具有阻塞影响、一般分布服务时间的开排队网模型，并提出近似求解方法计算系统平均产出率。进而，建立单元设施布局优化问题的非线性随机规划模型，提出基于排队网的改进变邻域搜索算法优化求解。在变邻域搜索算法中，根据工艺路径改进初始解生成方法，并通过有向图同构判定方法缩减邻域搜索的解空间规模，提高算法效率。实验算例对比证明，所提出的算法在优化解的质量和求解效率上均具有明显的优越性。

关键词: 设施布局, 二次分配问题, 排队网络, 变邻域搜索

Abstract:

Intelligence and servitization are important trends in the development of industrial modernization. Smart factory is the carrier to realize smart manufacturing， factory planning is the first step to build a smart factory， and the layout of production facilities is an important part of smart factory planning. The layout of production facilities has an important impact on the productivity， material handling efficiency， and production cycle of manufacturing systems. For the smart manufacturing cell system with resource coordination constraints， a quadratic assignment problem of facility layout to maximize the average throughput of the system is studied， and a queuing network-based meta-heuristic optimization algorithm is proposed. Due to the stochastic property of the system under the customized production mode， an open queuing network model with blocking and generally distributed service time is established， and an approximate solution method is proposed to evaluate the system throughput. Then， a non-linear stochastic programming model for the facility layout problem is developed， and an improved variable neighborhood search algorithm based on queuing network is proposed to solve the solutions. In the variable neighborhood search algorithm， the initial solution generation method based on the processing route is improved， and the scale of the solution space of the neighborhood search is reduced by the isomorphism determination of directed graphs， to improve the efficiency of the algorithm. The comparison of experiments proves that our proposed algorithm has obvious advantages in both the quality of the optimal solution and the efficiency of the solution. Experiments show that the improved R-VNS* and D-VNS* algorithms have similar solution results due to the improved initial solution generation method， which avoids getting trapped in local optimum， and both of them outperform the improved R-VNS and D-VNS algorithms before the improvement. Due to the improvement of the initial solution generation method and the strategy of eliminating the homomorphic coding to reduce the solution space， both the improved R-VNS* and D-VNS* algorithms have improved the algorithm time complexity compared with the pre-improved algorithms， and the proposed R-VNS* algorithm based on the reduced-neighborhood search strategy operates more efficiently.

Key words: facility layout, quadratic assignment problem （QAP）, queueing network, variable neighborhood search （VNS）

中图分类号:

TH181

张惠煜,廖勇,陈庆新, 等. 定制化生产模式下智能制造单元建模与布局优化求解[J]. 中国管理科学, 2026, 34(8): 182-194.

Huiyu Zhang,Yong Liao,Qingxin Chen, et al. Modeling and Layout Optimization Solution of a Smart Manufacturing Cell under Customized Production[J]. Chinese Journal of Management Science, 2026, 34(8): 182-194.

图/表 14

图1

图2

图3

图4

图5

表1

表2

实验算例参数"

编号		工艺路径	导轨结构	系统参数
1	SMC6-A1	串行	环形双向	λ₀=2.0，μ_i =2.5，N_i =3， $C S i 2$ =1.0，i∊[1, 4]
2	SMC6-A2		环形单向
3	SMC6-A3		线形双向
4	SMC6-B1	并行	环形双向	λ₀=2.0，μ_i =1.5，N_i =3， $C S i 2$ =1.0，i∊[1, 4]
5	SMC6-B2		环形单向
6	SMC6-B3		线形双向
7	SMC8-A1	串行	环形双向	λ₀=2，μ_i =2.5，N_i =3， $C S i 2$ =1.0，i∊[1, 6]
8	SMC8-A2		环形单向
9	SMC8-A3		线形双向
10	SMC8-B1	并行	环形双向	λ₀=2，μ_i =1.5，N_i =3， $C S i 2$ =1.0，i∊[1, 6]
11	SMC8-B2		环形单向
12	SMC8-B3		线形双向
13	SMC10-A1	串行	环形双向	λ₀=2，μ_i =2.5，N_i =3， $C S i 2$ =1.0，i∊[1, 8]
14	SMC10-A2		环形单向
15	SMC10-A3		线形双向
16	SMC10-B1	并行	环形双向	λ₀=2，μ_i =1.5，N_i =3， $C S i 2$ =1.0，i∊[1, 8]
17	SMC10-B2		环形单向
18	SMC10-B3		线形双向
19	SMC11-C1	混合	环形双向	λ₀=1.8， $C A 0 2$ =1.1， μ =[1.2, 1.2, 0.7, 0.5, 1.1, 1.2, 1.8, 2.1, 2.2]， N =[4, 4, 3, 3, 4, 4, 5, 6, 6]， $C S i 2$ =0.9，i∊[1, 9]

表2

表3

表4

图6

表5

表6

表7

图7

参考文献 19

[1]	孙凯，刘祥. 基于蚁群-遗传混合算法的设备布局优化方法［J］. 系统工程理论与实践， 2019， 39（10）： 2581-2589.
	Sun K， Liu X. A method of workshop equipment layout based on ant colony-genetic hybrid algorithm［J］. Systems Engineering-Theory Practice， 2019， 39（10）： 2581-2589.
[2]	Pérez-Gosende P， Mula J， Díaz-Madroñero M. Facility layout planning. An extended literature review［J］. International Journal of Production Research， 2021， 59（12）： 3777-3816.
[3]	Al-Zubaidi S Q D， Fantoni G， Failli F. Analysis of drivers for solving facility layout problems： A Literature review［J］. Journal of Industrial Information Integration， 2021， 21： 100187.
[4]	Hosseini-Nasab H， Fereidouni S， Fatemi Ghomi S M T， et al. Classification of facility layout problems： A review study［J］. The International Journal of Advanced Manufacturing Technology， 2018， 94（1-4）： 957-977.
[5]	Papadopoulos C T， Li J， O’Kelly M E J. A classification and review of timed Markov models of manufacturing systems［J］. Computers Industrial Engineering， 2019， 128： 219-244.
[6]	肖丽萍，李加莲，邵雪焱，等. 分级诊疗下基于排队网络的医联体系统优化［J］. 中国管理科学， 2023， 31（9）： 186-195.
	Xiao L P， Li J L， Shao X Y， et al. Medical alliance system optimization based on queuing network under hierarchical diagnosis and treatment［J］. Chinese Journal of Management Science， 2023， 31（9）： 186-195.
[7]	杨静蕾，丁以中. 一种基于闭排队网络的集装箱码头设备配置优化模型［J］. 中国管理科学， 2006， 14（6）： 56-60.
	Yang J L， Ding Y Z. Research on optimal equipment allocation in container terminals by using closed queueing networks［J］. Chinese Journal of Management Science， 2006， 14（6）： 56-60.
[8]	Chen C， Tiong L K. Using queuing theory and simulated annealing to design the facility layout in an AGV-based modular manufacturing system［J］. International Journal of Production Research， 2019， 57（17）： 5538-5555.
[9]	Raman D， Nagalingam S V， Gurd B W. A genetic algorithm and queuing theory based methodology for facilities layout problem［J］. International Journal of Production Research， 2009， 47（20）： 5611-5635.
[10]	Tu Y M， Lu C W， Lee A H I. AMHS capacity determination model for wafer fabrication based on production performance optimization［J］. International Journal of Production Research， 2013， 51（18）： 5520-5535.
[11]	Pourvaziri H， Pierreval H. Dynamic facility layout problem based on open queuing network theory［J］. European Journal of Operational Research， 2017， 259（2）： 538-553.
[12]	Mohammadi M， Dauzère-pérès S， Yugma C， et al. A queue-based aggregation approach for performance evaluation of a production system with an AMHS［J］. Computers Operations Research， 2020， 115： 104838.
[13]	Zhang H Y， Chen Q X， Smith J M， et al. Queueing network models for intelligent manufacturing units with dual-resource constraints［J］. Computers Operations Research， 2021， 129： 105213.
[14]	Gross D， Shortle J F， Thompson J M， et al. Fundamentals of queueing theory［M］. New York： Wiley， 2008.
[15]	Labetoulle J， Pujolle G. Isolation method in a network of queues［J］. IEEE Transactions on Software Engineering， 1980， SE-6（4）： 373-381.
[16]	Friedrich C， Klausnitzer A， Lasch R. Integrated slicing tree approach for solving the facility layout problem with input and output locations based on contour distance［J］. European Journal of Operational Research， 2018， 270（3）： 837-851.
[17]	Hore S， Chatterjee A， Dewanji A. Improving variable neighborhood search to solve the traveling salesman problem［J］. Applied Soft Computing， 2018， 68： 83-91.
[18]	杨育. 设施规划［M］. 北京：科学出版社， 2010.
	Yang Y. Facility planning［M］. Beijing： Science Press， 2010.
[19]	Bangjensen J， Gutin G. Digraphs—theory， algorithms and applications［M］. New York： Springer， 2010.

机器人导轨结构	理论解空间	剔除同构编码的解空间
机器人导轨结构	理论解空间	n为偶数	n为奇数
环形双向	n!	(n-2)!	(n-1)!
环形单向		n(n-2)!	n(n-2)!
线形双向		(n-2)!/2	(n-2)!/2

编号	R-NVS^*				R-NVS
编号	X_opt	Θ_max	Θ_mean	cpu.	X_opt	Θ_max	Θ_mean	cpu.
1	[0,2,1,3,4,5]	1.58	1.58	19.9	[0,2,1,3,4,5]	1.58	1.58	49.7
2	[1,0,2,3,4,5]	1.51	1.48	22.3	[0,2,3,4,5,1]	1.51	1.45	67.6
3	[2,1,3,4,5,0]	1.61	1.61	25.7	[4,5,0,2,1,3]	1.61	1.61	41.5
4	[3,2,1,0,4,5]	1.81	1.81	2.1	[3,2,1,0,4,5]	1.81	1.81	2.6
5	[3,1,0,4,5,2]	1.75	1.75	1.6	[3,1,0,4,5,2]	1.75	1.75	3.0
6	[0,4,5,1,3,2]	1.84	1.84	2.1	[2,0,4,5,1,3]	1.84	1.84	2.8
7	[0,2,1,3,4,5,6,7]	1.79	1.78	97.3	[7,6,5,4,3,1,2,0]	1.78	1.77	196.7
8	[1,0,2,3,4,5,6,7]	1.78	1.77	86.2	[4,5,6,7,1,0,2,3]	1.77	1.77	137.2
9	[6,5,4,3,1,2,0,7]	1.79	1.78	86.8	[7,0,2,1,3,4,5,6]	1.78	1.78	146.7
10	[7,6,5,0,1,2,3,4]	1.88	1.88	4.0	[7,6,5,0,1,2,3,4]	1.88	1.88	11.2
11	[7,3,4,1,0,5,2,6]	1.88	1.88	6.0	[1,0,5,2,6,7,3,4]	1.88	1.88	12.0
12	[7,6,5,0,1,2,3,4]	1.88	1.88	5.9	[3,4,7,6,5,0,1,2]	1.88	1.88	8.0
13	[0,2,1,3,4,5,6,7,8,9]	1.60	1.60	227.9	[9,8,0,2,1,3,4,5,6,7]	1.39	1.33	650.0
14	[1,0,2,3,4,5,6,7,8,9]	1.61	1.61	239.3	[9,3,4,5,6,1,0,2,7,8]	1.30	1.20	668.0
15	[8,7,6,5,4,3,1,2,0,9]	1.70	1.70	369.4	[7,3,9,0,6,2,5,8,4,1]	1.43	1.43	589.9
16	[9,8,7,6,0,1,2,3,4,5]	1.83	1.82	19.8	[8,2,0,7,6,1,5,4,3,9]	1.72	1.69	43.2
17	[5,7,8,9,1,0,6,2,3,4]	1.79	1.79	32.0	[9,3,1,0,6,2,4,5,7,8]	1.62	1.62	45.6
18	[5,1,6,7,8,9,0,2,3,4]	1.82	1.82	23.4	[5,1,9,8,7,6,0,2,3,4]	1.72	1.72	34.3
19	[0,1,6,7,8,9,10,5,4,3,2]	1.74	1.74	83.2	[6,1,0,2,3,4,5,10,9,8,7]	1.66	1.65	129.6

编号	D-NVS^*				D-NVS
编号	X_opt	Θ_max	Θ_mean	cpu.	X_opt	Θ_max	Θ_mean	cpu.
1	[0,2,1,3,4,5]	1.58	1.58	36.4	[0,2,1,3,4,5]	1.58	1.58	125.0
2	[1,0,2,3,4,5]	1.51	1.49	30.1	[1,0,2,3,4,5]	1.51	1.48	92.3
3	[0,2,1,3,4,5]	1.61	1.61	25.9	[2,1,3,4,5,0]	1.61	1.61	118.6
4	[5,4,0,1,2,3]	1.81	1.81	4.2	[3,2,1,0,4,5]	1.81	1.81	5.2
5	[3,1,0,4,5,2]	1.75	1.75	3.9	[3,1,0,4,5,2]	1.75	1.75	7.4
6	[4,5,1,3,2,0]	1.84	1.84	2.0	[0,4,5,1,3,2]	1.84	1.83	5.3
7	[0,2,1,3,4,5,6,7]	1.79	1.79	79.6	[0,2,1,3,4,5,6,7]	1.78	1.78	468.5
8	[1,0,2,3,4,5,6,7]	1.78	1.78	207.2	[1,0,2,3,4,5,6,7]	1.78	1.77	464.6
9	[1,2,0,7,6,5,4,3]	1.79	1.78	153.2	[6,5,4,3,1,2,0,7]	1.78	1.78	374.8
10	[7,6,5,0,1,2,3,4]	1.88	1.88	8.7	[7,6,5,0,1,2,3,4]	1.88	1.88	29.0
11	[0,5,2,6,7,3,4,1]	1.88	1.88	11.6	[7,3,4,1,0,5,2,6]	1.88	1.88	31.7
12	[7,6,5,0,1,2,3,4]	1.88	1.88	10.8	[7,6,5,0,1,2,3,4]	1.88	1.88	27.8
13	[0,2,1,3,4,5,6,7,8,9]	1.60	1.60	565.3	[9,8,0,2,1,3,4,5,6,7]	1.39	1.34	2019.7
14	[1,0,2,3,4,5,6,7,8,9]	1.61	1.61	893.6	[5,1,0,2,6,7,8,9,3,4]	1.30	1.22	2062.1
15	[0,2,1,3,4,5,6,7,8,9]	1.70	1.70	585.2	[2,5,8,4,1,6,7,3,9,0]	1.43	1.43	1838.4
16	[9,8,7,6,0,1,2,3,4,5]	1.83	1.83	57.9	[5,4,3,9,8,2,0,7,6,1]	1.72	1.72	104.3
17	[4,5,7,8,9,1,0,2,6,3]	1.79	1.79	58.0	[9,3,1,0,6,2,4,5,7,8]	1.62	1.60	226.9
18	[4,5,9,8,7,6,0,1,2,3]	1.83	1.83	70.0	[9,8,7,6,0,5,4,3,2,1]	1.72	1.72	34.3
19	[7,8,9,10,5,4,3,2,0,1,6]	1.74	1.74	201.4	[7,5,4,3,2,0,1,6,10,9,8]	1.66	1.65	129.6

算法	X_opt	距离矩阵 [d_i_,_j ]
算法	X_opt		B₀	W₁	W₂	W₃	W₄	W₅	W₆	W₇	W₈	B₉
R-NVS^* D-NVS^*	[9,8,7,6,0,1,2,3,4,5]	B₀	0	1	2	3	4	5	1	2	3	4
		W₁	1	0	1	2	3	4	2	3	4	5
		W₂	2	1	0	1	2	3	3	4	5	4
		W₃	3	2	1	0	1	2	4	5	4	3
		W₄	4	3	2	1	0	1	5	4	3	2
		W₅	5	4	3	2	1	0	4	3	2	1
		W₆	1	2	3	4	5	4	0	1	2	3
		W₇	2	3	4	5	4	3	1	0	1	2
		W₈	3	4	5	4	3	2	2	1	0	1
		B₉	4	5	4	3	2	1	3	2	1	0
R-NVS	[8,2,0,7,6,1,5,4,3,9]	B₀	0	3	1	4	5	4	2	1	2	3
		W₁	3	0	4	3	2	1	1	2	5	4
		W₂	1	4	0	3	4	5	3	2	1	2
		W₃	4	3	3	0	1	2	4	5	2	1
		W₄	5	2	4	1	0	1	3	4	3	2
		W₅	4	1	5	2	1	0	2	3	4	3
		W₆	2	1	3	4	3	2	0	1	4	5
		W₇	1	2	2	5	4	3	1	0	3	4
		W₈	2	5	1	2	3	4	4	3	0	1
		B₉	3	4	2	1	2	3	5	4	1	0
D-NVS	[5,4,3,9,8,2,0,7,6,1]	B₀	0	3	1	4	5	4	2	1	2	3
		W₁	3	0	4	3	2	1	1	2	5	4
		W₂	1	4	0	3	4	5	3	2	1	2
		W₃	4	3	3	0	1	2	4	5	2	1
		W₄	5	2	4	1	0	1	3	4	3	2
		W₅	4	1	5	2	1	0	2	3	4	3
		W₆	2	1	3	4	3	2	0	1	4	5
		W₇	1	2	2	5	4	3	1	0	3	4
		W₈	2	5	1	2	3	4	4	3	0	1
		B₉	3	4	2	1	2	3	5	4	1	0

编号	R-NVS^*			GA			SA
编号	Θ_max	Θ_mean	cpu.	Θ_max	Θ_mean	cpu.	Θ_max	Θ_mean	cpu.
1	1.58	1.58	19.9	1.58	1.55	50.5	1.58	1.56	161.8
2	1.51	1.48	22.3	1.51	1.45	51.2	1.51	1.49	114.6
3	1.61	1.61	25.7	1.61	1.60	34.2	1.61	1.61	66.1
4	1.81	1.81	2.1	1.81	1.81	3.4	1.81	1.81	10.2
5	1.75	1.75	1.6	1.75	1.75	3.0	1.75	1.75	6.7
6	1.84	1.84	2.1	1.84	1.84	2.0	1.84	1.84	4.0
7	1.79	1.78	97.3	1.78	1.78	77.6	1.78	1.78	342.2
8	1.78	1.77	86.2	1.77	1.77	89.0	1.78	1.77	346.6
9	1.79	1.78	86.8	1.78	1.78	99.2	1.78	1.78	293.9
10	1.88	1.88	4.0	1.88	1.88	5.2	1.88	1.88	19.3
11	1.88	1.88	6.0	1.88	1.88	6.2	1.88	1.88	20.2
12	1.88	1.88	5.9	1.88	1.88	4.7	1.88	1.88	20.3
13	1.60	1.60	227.9	1.29	1.24	344.2	1.28	1.22	837.4
14	1.61	1.61	239.3	1.17	1.06	237.8	1.22	1.07	813.6
15	1.70	1.70	369.4	1.39	1.34	277.5	1.39	1.35	911.8
16	1.83	1.82	19.8	1.69	1.64	15.9	1.67	1.65	51.8
17	1.79	1.79	32.0	1.58	1.52	13.9	1.61	1.54	45.1
18	1.82	1.82	23.4	1.71	1.70	18.7	1.71	1.70	49.9
19	1.74	1.74	83.2	1.65	1.63	47.3	1.73	1.72	125.9