一种规模化混杂生产线缓冲区容量优化分配技术

刘军; 任建华; 冯硕

doi:10.16383/j.aas.c200578

一种规模化混杂生产线缓冲区容量优化分配技术

doi: 10.16383/j.aas.c200578

刘军^1,,
任建华^1,,
冯硕^1,

1. 兰州理工大学机电工程学院兰州 730050

基金项目: 国家自然科学基金(71861025), 科技部国家重点研发计划(2018 YFB1703105), 兰州理工大学红柳一流学科建设项目资助

详细信息

作者简介:
刘军：兰州理工大学机电工程学院教授. 2005年获得浙江大学控制科学与工程博士学位. 主要研究方向为复杂制造系统, 生产调度与控制和智能机械. 本文通信作者. E-mail: lzhjliu@126.com

任建华：兰州理工大学机电工程学院硕士研究生. 主要研究方向为复杂制造系统.E-mail: renjianhua0318@163.com

冯硕：兰州理工大学机电工程学院硕士研究生. 主要研究方向为复杂制造系统. E-mail: fengshuo1003@163.com

计量
- 文章访问数: 861
- HTML全文浏览量: 278
- PDF下载量: 166
- 被引次数: 0
出版历程
- 收稿日期: 2020-07-23
- 录用日期: 2020-12-14
- 网络出版日期: 2021-01-06
- 刊出日期: 2023-05-20

Optimal Allocation Technology for Buffer Capacity of Large-scale Hybrid Production Lines

1. School of Mechanical and Electrical Engineering, Lanzhou University of Technology, Lanzhou 730050

Funds: Supported by National Natural Science Foundation of China (71861025), National Key Research and Development Project (2018YFB1703105), and Hongliu First-class Disciplines Development Program of Lanzhou University of Technology

More Information

Author Bio:
LIU Jun　Professor at the School of Mechanical and Electrical Engineering, Lanzhou University of Technology. He received his Ph.D. degree in control science and engineering from Zhejiang University in 2005. His research interest covers complex manufacturing system, production scheduling and control, and intelligent mechanism. Corresponding author of this paper

REN Jian-Hua　Master student at the School of Mechanical and Electrical Engineering, Lanzhou Univ-ersity of Technology. His main research interest is complex manufacturing system

FENG Shuo　Master student at the School of Mechanical and Electrical Engineering, Lanzhou Univ-ersity of Technology. Her main research interest is complex manufacturing system

摘要

摘要: 针对传统技术难以解决规模化混杂生产线缓冲区容量分配问题(Buffer allocation problem, BAP), 提出了一种规模化生产线递阶分解建模并行寻优技术(Hierarchical decomposition modeling parallel optimizing technique of large-scale production lines, HDMPOT). 该技术结合混杂生产线系统综合方法与分解方法的技术思想, 兼顾生产线平衡性与系统规模, 将原系统递阶分解为包含虚拟生产线在内的n + 1个子生产线系统, 通过求解子系统的最优解构造原系统的渐近最优解, 并在系统递阶建模阶段, 提出了一种设备模糊聚类的辅助方式; 同时, 基于混杂生产线系统综合方法, 提出了一种系统渐次综合的初解改进确定方法; 并提出了一种通过构造动态步长来设计领域结构的改进型禁忌搜索算法(Simple tabu search, STS), 对子系统进行并行寻优. 最后, 对技术算法的收敛性进行了证明. 提出的生产线递阶分解建模并行寻优技术具有一般性, 对受设备随机故障等随机事件影响的生产线, 尤其是规模化生产线系统其他优化、控制问题也具有借鉴和参考价值.
- 缓冲区容量分配问题 /
- 规模化 /
- 最优化 /
- 递阶分析模型 /
- 生产线平衡
Abstract: For large-scale production lines, hierarchical decomposition modeling parallel optimizing technique of large-scale production lines (HDMPOT) is proposed here to deal with the buffer allocation problem (BAP), which is intractable for traditional techniques. The technique, which combines the technique philosophy of the aggregation method and that of the decomposition method of hybrid production lines and takes into account both production line balance and system scale, decomposes the original production system into $n + 1$ pseudo-production subsystems to set up a hierarchical analysis model and obtains the near-optimal solution of original production system by the optimal solutions of pseudo-production subsystems. A fuzzy clustering method is adopted for machines in the system to help the technique setting up the hierarchical analysis model. Meanwhile, the initial solution is obtained by a new method utilizing the aggregation method of hybrid production lines. In addition, an improved simple tuba searching (STS) algorithm, in which a dynamical searching step length is used to build the neighboring structure of solutions, is proposed to search the optimal solutions of subsystems synchronously. At last, the convergence of the algorithm about the technique is proved. The technique to some extent is of generality and can be utilized to deal with other system optimizing problems of large-scale production lines disturbed by breakdowns of machines or other stochastic events.
- Buffer allocation problem (BAP) /
- large-scale /
- optimization /
- hierarchical analysis model /
- production line balance

HTML全文

图 1 生产线示例

Fig. 1 Example of production lines

下载: 全尺寸图片幻灯片

图 2 规模化生产线递阶分解建模过程

Fig. 2 Hierarchical decomposition modeling process of large scale production lines

下载: 全尺寸图片幻灯片

图 3 设备模糊聚类示例

Fig. 3 Example of fuzzy clustering

下载: 全尺寸图片幻灯片

图 4 生产线综合示意图

Fig. 4 Aggregation process of production lines

下载: 全尺寸图片幻灯片

图 5 HDMPOT技术流程图

Fig. 5 Flow chart of HDMPOT

下载: 全尺寸图片幻灯片

图 6 分解方法示意图

Fig. 6 Schematic diagram of decomposition method

下载: 全尺寸图片幻灯片

图 7 生产线寻优过程

Fig. 7 Optimizing process of production lines

下载: 全尺寸图片幻灯片

表 1 生产线${L_1}$设备参数

Table 1 Machine parameters of production line ${L_1}$

参数类型	设备参数
${p_i}\left( { { {10}^{ {\rm{ - } }3} } } \right)$	1-2-1-1.5-3-4-1-1-2-3-2-2-1-2.5-3-2-1-3-10-15-1-2-1-1.5-3-4-1-1-2-3-2-2-1-2.5-3-2-1-3-10-15-15-3-4-12-20-20-5-10-6-10
${r_i}\left( { { {10}^{ {\rm{ - } }3} } } \right)$	5-6-10-4-6-8-8-4-6-1-10-4-6-8-4-6-1-10-20-3-5-6-10-4-6-8-8-4-6-1-10-4-6-8-4-6-1-10-20-3-2-4-6-2-8-7-5-4-6-8
${S_i}$	8-6-7-10-5-12-14-12-10-6-8-7-11-10-10-9-4-12-11-9-8-6-7-10-5-12-14-12-10-6-8-7-11-10-10-9-4-12-11-9-7-12-12-9-12-10-15-12-13-6

下载: 导出CSV

表 2 生产线${L_2}$设备参数

Table 2 Machine parameters of production line ${L_2}$

参数类型	设备参数
${p_i}\left( { { {10}^{ {\rm{ - } }3} } } \right)$	1.5-2.5-1-3-2-1-2-3-2-2-1-2-1-1-2-1-2-2-2-1-1-2-1-1.5-3-4-1-1-2-3-2-2-1-2. 5-3-2-1-3-10-15-50-20-10-14-16-2- 3-20-3-5-15-3-4-12-20-20-5-10-6-10-2-1-4-3-4-3-2-2-3-1-5-3-5-6-4-3-2-5-3-4
${r_i}\left( { { {10}^{ {\rm{ - } }3} } } \right)$	2-2-1-2.5-3-2-1-3-10-15-1-2-1-1.5-3-4-1-1-2-3-5-6-10-4-6-8-8-4-6-1-10-4-6-8-4-6-1-10-20-3-4-6-1-10-15-3-4- 12-20-8-2-4-6-2-8-7-5-4-6-8-5-6-10-4-6-8-7-7-5-4-5-4-20-6-7-8-5-15-6-2
${S_i}$	8-7-11-10-10-9-4-12-11-9-8-6-7-10-5-12-14-12-10-6-8-6-7-10-5-12-14-12-10-6-8-7-11-10-10-9-4-12-11-9-15-11- 10-3-13-9-8-11-8-7-7-12-12-9-12-10-15-12-13-6-8-12-12-13-14-10-10-14-12-11-9-14-11-8-10-7-8-10-9-7

下载: 导出CSV

表 3 生产线${L_3}$设备参数

Table 3 Machine parameters of production line ${L_3}$

参数类型	设备参数
${p_i}\left( { { {10}^{ {\rm{ - } }3} } } \right)$	2-1-4-3-4-3-2-2-3-1-5-3-5-6-4-3-2-5-3-4-50-20-10-14-16-2-3-20-3-5-15-3-4-12-20-20-5-10-6-10-1-2-1- 1.5-3-4-1-1-2-3-2-2-1-2.5-3-2-1-3-10-15-1.5-2.5-1-3-2-1-2-3-2-2-1-2-1-1-2-1-2-2-2-1-2-1-4-3-4- 3-2-2-3-1-5-3-5-6-4-3-2-5-3-4-1-2-1-1-2-1-2-2-2-1-1-2-1-1.5-3-4-1-1-2-3
${r_i}\left( { { {10}^{ {\rm{ - } }3} } } \right)$	5-6-10-4-6-8-7-7-5-4-5-4-20-6-7-8-5-15-6-2-4-6-1-10-15-3-4-15-20-8-2-4-6-2-8-7-5-4-6-8-5-6-10-4-6-8- 8-4-6-1-10-4-6-8-4-6-1-10-20-3-2-2-1-2.5-3-2-1-3-10-15-1-2-1-1.5-3-4-1-1-2-3-4-6-1-10-15-3-4- 12-20-8-2-4-6-2-8-7-5-4-6-8-1-2-1-1.5-3-4-1-1-2-3-4-6-1-10-15-3-4-12-20-8
${S_i}$	8-12-12-13-14-10-10-14-12-11-9-14-11-8-10-7-8-10-9-7-15-11-10-3-13-9-8-11-8-7-7-12-12-9-12-10-15-12-13-6-8- 6-7-10-5-12-14-12-10-6-8-7-11-10-10-9-4-12-11-8-7-11-10-10-9-4-12-11-9-8-6-7-10-5-12-14-12-10-6-7-12-12-9- 12-10-15-12-13-6-15-11-10-3-13-9-8-11-8-7-7-12-12-9-12-10-15-12-13-6-8-7-11-10-10-9-4-12-11-9

下载: 导出CSV

表 4 生产线${L_1}$缓冲区分配结果

Table 4 Buffer allocation for production line ${L_1}$

算法	缓冲区容量分配结果
${\rm{STS}}$	7-1-10-13-6-10-10-7-4-2-10-2-5-1-13-7-8-1-2-6-3-1-5-2-10-9-5-1-2-4-4-1-2-2-2-2-7-6-1-2-1-2-4-4-5-1-7-8
${\rm{ATS}}$	2-1-2-11-15-11-11-4-4-1-1-7-1-10-2-4-3-3-3-1-6-1-3-1-1-3-11-1-7-2-1-2-13-7-3-4-8-1-1-1-6-3-4-5-2-1-5-1-2
${\rm{HDMPOT}}$	5-1-2-11-14-8-10-8-6-3-1-8-1-7-1-8-5-5-2-1-6-2-2-1-1-7-10-4-4-1-1-2-5-4-2-3-5-4-2-2-4-2-3-4-4-1-2-1-7

下载: 导出CSV

表 5 生产线${L_2}$缓冲区分配结果

Table 5 Buffer allocation for production line ${L_2}$

算法	缓冲区容量分配结果
${\rm{STS}}$	1-1-1-7-3-6-12-2-6-1-3-4-1-2-6-3-1-1-6-1-1-4-1-1-1-1-1-3-2-1-1-4-1-1-1-1-1-1-1-4-4-2-6-9-3-2-4-1-3-4-6- 1-1-1-6-1-6-1-2-1-1-1-1-1-1-1-1-2-1-2-2-1-1-2-1-1-2-1-6
${\rm{ATS}}$	1-1-2-3-7-13-10-4-4-6-1-7-1-1-5-1-2-8-2-3-2-3-1-2-5-5-1-5-4-1-2-4-1-5-1-1-3-3-2-2-6-3-4-2-2-14-5-2-7-1- 1-2-6-4-3-2-1-3-3-2-1-4-10-1-6-6-5-3-1-2-5-1-2-2-1-1-1-1-1
${\rm{HDMPOT}}$	1-1-1-13-4-13-10-4-4-6-1-9-1-1-6-2-2-1-3-3-2-2-1-2-6-4-6-4-4-2-2-4-1-4-1-2-3-3-2-6-3-3-2-3-13-5-2-7-1-2- 2-1-8-1-1-3-3-3-1-4-10-1-6-6-5-4-3-1-2-4-2-2-1-2-1-1-1

下载: 导出CSV

表 6 生产线${L_3}$缓冲区分配结果

Table 6 Buffer allocation for production line ${L_3}$

算法	缓冲区容量分配结果
${\rm{STS}}$	12-4-5-7-13-12-11-2-7-1-1-4-5-5-1-1-11-7-2-5-2-2-2-1-1-2-2-3-8-10-3-2-3-5-3-1-1-1-2-5-5-11-2-4-2-6-4-4-2- 11-4-3-8-4-1-8-5-2-2-1-2-1-10-2-1-1-2-4-11-4-7-4-2-1-1-2-3-10-3-1-1-2-11-2-1-1-2-2-2-3-3-4-4-2-12-2- 1-12-1-1-2-2-1-7-2-2-1-2-2-2-1-1-5-1-1-1-1-4-5 (达到迭代截止次数1000代)
${\rm{ATS}}$	12-2-2-15-17-12-31-26-17-11-2-4-22-1-1-6-2-2-1-7-10-24-16-2-3-12-2-28-10-13-1-5-12-13-1-1-1-4-12-3-2-11- 1-8-18-1-8-2-17-24-13-10-4-4-15-12-3-1-1-4-11-11-1-1-2-3-2-1-2-1-1-1-5-8-7-4-4-4-7-6-1-1-2-5-5-1-2- 4-2-6-4-4-2-1-4-3-8-4-1-8-1-3-10-10-1-3-6-6-2-1-1-7-1-1-1-6-9-3-8-2 (达到迭代截止次数1000代)
${\rm{HDMPOT}}$	17-8-9-10-13-13-23-10-1-7-3-3-2-3-1-12-2-9-1-1-4-1-5-1-1-5-2-12-1-4-1-7-10-10-1-1-3-18-1-3-10-10-1-3-6-6- 2-1-1-7-1-1-1-6-9-3-8-2-2-6-2-3-1-4-2-9-1-2-2-6-5-3-2-1-6-2-13-1-7-1-2-2-2-21-9-1-10-5-1-3-3-1- 1-10-3-11-1-3-3-2-1-3-1-3-1-2-2-1-11-10-3-6-22-16-1-8-3-1-5

下载: 导出CSV

表 7 仿真时间及系统生产力

Table 7 Simulation time and system productivity

设备数 (台)	总缓冲区容量	寻优方法	运行时间 (s)	生产力
50	250	HDMPOT	428.21	0.1299
		ATS	699.17	0.1235
		STS	769.91	0.1228
80	400	HDMPOT	561.22	0.1295
		ATS	1303.38	0.1209
		STS	1427.61	0.1169
120	1150	HDMPOT	1022.41	0.1250
		ATS	6810.72	0.1091
		STS	9742.51	0.1026

下载: 导出CSV

参考文献(27)

[1]	Koenigsberg, Ernest. Production Lines and Internal Storage-A Review. Management Science, 1959, 5(4): 410-433. doi: 10.1287/mnsc.5.4.410
[2]	Li J, Blumenfeld, D E, Huang, N, & Alden, J M. Throughput analysis of production systems: recent advances and future topics. International Journal of Production Research, 2009, 47(14): 3823-3851. doi: 10.1080/00207540701829752
[3]	Demir, Leyla, Tunali, Semra, Eliiyi, Deniz. The state of the art on buffer allocation problem: a comprehensive survey. Journal of Intelligent Manufacturing, 2014, 25(3): 371-392. doi: 10.1007/s10845-012-0687-9
[4]	Kraemer S A and Love R F. A model for optimizing the buffer inventory storage size in a sequential production system. AIIE Transactions, 1970, 2(1), 64-69. doi: 10.1080/05695557008974732
[5]	Krogh B H. Recent advances in discrete analysis and control of hybrid systems. In: Proceedings of the 6th International Workshop on Discrete Event Systems. Zaragoza, Spain: 2002.
[6]	Li J S, Meerkov S M. Mathematical modeling of production systems. Production Systems Engineering, 2009: 1−59
[7]	Chow W M. Buffer capacity analysis for sequential production lines with variable process times. International Journal of Production Research, 1987, 25(8): 1183-1196.
[8]	Gershwin S B. An efficient decomposition method for the approximate evaluation of tandem queues with finite storage space and blocking. Operations Research, 1987, 35(2): 291-305. doi: 10.1287/opre.35.2.291
[9]	Liu J, Wang Y N, Li J H, Chen R S. An Extended System Aggregation Method for Hybrid Production Lines with Multiple Failure Rate and Unreliable Limited Buffers. Advanced Materials Research, 2012, 459: 432-436. doi: 10.4028/www.scientific.net/AMR.459.432
[10]	Nabil N, Nourelfath M. Buffer allocation and preventive maintenance optimization in unreliable production lines. Journal of Intelligent Manufacturing, 2017, 128(1), 85-93.
[11]	Dolgui A, Eremeev A V, Sigaev V S. HBBA: hybrid algorithm for buffer allocation in tandem production lines. Journal of Intelligent Manufacturing, 2007, 18(3): 411-420. doi: 10.1007/s10845-007-0030-z
[12]	Weiss S, Stolletz R. Buffer allocation in stochastic flow lines via sample-based optimization with initial bounds. OR Spectrum, 2015, 37(4): 869-902. doi: 10.1007/s00291-015-0393-z
[13]	Demir L, Tunalı S, Eliiyi D T. An adaptive tabu search approach for buffer allocation problem in unreliable non-homogenous production lines[J]. Computers & Operations Research, 2012, 39(7): 1477-1486.
[14]	Moradi N, Shadrokh S. A simulated annealing optimization algorithm for equal and unequal area construction site layout problem. International journal of research in industrial engineering, 2019 8(2), 89-104.
[15]	Amiri M, Mohtashami A. Buffer allocation in unreliable production lines based on design of experiments, simulation, and genetic algorithm. The International Journal of Advanced Manufacturing Technology, 2012, 62(1): 371-383.
[16]	Motlagh M M, Azimi P, Amiri M, Madraki G. An Efficient Simulation Optimization Methodology to Solve a Multi-Objective Problem in Unreliable Unbalanced Production Lines. Expert Systems with Applications, 2019, 138: 112836. doi: 10.1016/j.eswa.2019.112836
[17]	Demir L, Diamantidis A C, Deniz T E, O'Kelly M E J, Tunali S. Optimal buffer allocation for serial production lines using heuristic search algorithms: a comparative study. International Journal of Industrial and Systems Engineering, 2019, 33(2): 252-270. doi: 10.1504/IJISE.2019.102473
[18]	黄君政, 李爱平, 刘雪梅, 谢楠. 考虑缓冲区配置的生产线布局优化设计. 同济大学学报(自然科学版), 2015, 43(07): 115-121. Huang Jun-Zheng, Li Ai-Ping, Liu Xue-Mei, Xie Nan. Optimal Design of Production Line Layout Considering Buffer Allocation. Journal of Tongji University(Natural Science), 2015, 43(07): 1075-1081(in Chinese).
[19]	Zandieh M, Joreir-Ahmadi M N, Fadaei-Rafsanjani A. Buffer allocation problem and preventive maintenance planning in non-homogeneous unreliable production lines. The International Journal of Advanced Manufacturing Technology, 2017, 91(5): 2581-2593.
[20]	Chuan Shi and Stanley B, Gershwin. A segmentation approach for solving buffer allocation problems in large production system. International Journal of Production Research, 2016, 54(20): 6121-6141. doi: 10.1080/00207543.2014.991842
[21]	Xi S, Chen Q, Smith M G, Mao N, Zhang H. A new method for solving buffer allocation problem in large unbalanced production lines. International Journal of Production Research, 2019(2): 1-22.
[22]	Lei Li, Yan Ling Qian, Yong Min Yang, Kai Du. A fast algorithm for buffer allocation problem. International Journal of Production Research, 2015, 54(11): 3243-3255.
[23]	Alfieri A, Matta A. Mathematical programming formulations for approximate simulation of multistage production systems. European Journal of Operational Research, 2012, 219(3): 773-783. doi: 10.1016/j.ejor.2011.12.044
[24]	Alfieri A, Matta A, Pastore E. A column generation algorithm for the Buffer Allocation Problem approximated by the Time Buffer concept. IFAC PapersOnLine, 2016, 49(12): 739-744. doi: 10.1016/j.ifacol.2016.07.862
[25]	Li J. Overlapping decomposition: a system-theoretic method for modeling and analysis of complex manufacturing systems. IEEE Transactions on Automation ence & Engineering, 2005, 2(1): 40-53.
[26]	孔军平. 非相似型混杂平行生产线系统性能分析研究 [硕士论文], 兰州理工大学, 中国, 2015 Kong Jun-Ping. Performance Analysis of Non-homogeneous Hybrid Parallel-line System [Master thesis], Lanzhou University of Technology, China, 2015
[27]	Liu J, Kong J P. Performance analysis of non-homogeneous hybrid production lines based on decomposition method. International Journal of Industrial & Systems Engineering, 2016, 4(4):463-467.