基于头脑风暴算法的多处理机组合生产批量调度问题

王全武; 徐震浩; 顾幸生

doi:10.14135/j.cnki.1006-3080.20210427005

基于头脑风暴算法的多处理机组合生产批量调度问题

doi: 10.14135/j.cnki.1006-3080.20210427005

华东理工大学化工过程和优化技术教育部重点实验室，上海 200237

基金项目: 国家自然科学基金（61573144，61673175，61603139）

详细信息

作者简介:
王全武（1996—），男，辽宁大连人，硕士生，主要研究方向为生产计划与调度。E-mail：Y30190752@mail.ecust.edu.cn

通讯作者:
徐震浩，E-mail：xuzhenhao@ecust.edu.cn

中图分类号: TP301
计量
- 文章访问数: 79
- HTML全文浏览量: 26
- PDF下载量: 7
- 被引次数: 0
出版历程
- 收稿日期: 2021-04-27
- 网络出版日期: 2021-07-28

Multi-Processor Combined Production Batch Scheduling Problem Based on Brain Storm Optimization Algorithm

Key Laboratory of Advanced Control and Optimization for Chemical Processes, Ministry of Education, East China University of Science and Technology, Shanghai 200237, China

摘要

摘要: 在生产调度领域中，受生产工艺等诸多因素的影响，往往每个生产过程都需要多台机器的同时参与加工。同时，待加工的工件数量较多，需要将每种类型的工件进行批量处理，以缩短生产周期。因此，本文在作业车间环境下，根据每个加工过程所参与机器的负荷，采用可变分批方案，提出了非混排多处理机组合生产批量调度模型，并结合头脑风暴算法，求解出最短加工时间。提出了一种改进的头脑风暴算法，引入贪婪思想与动态讨论机制，讨论次数随着算法的迭代而自适应变化，将全局搜索与局部搜索相结合，加强了算法的搜索能力。实验结果表明，改进的头脑风暴算法与基本的头脑风暴算法相比，求解效率更高，收敛速度更快。
- 多处理机组合生产 /
- 作业车间 /
- 批量调度 /
- 头脑风暴算法（BSO） /
- 讨论机制
Abstract: At present, in the field of production scheduling, affected by many factors such as production technology, each production process often requires multiple machines to participate in processing at the same time. At the same time, the number of workpieces to be processed is large, and each type of workpiece needs to be processed in batches to shorten the production cycle. Therefore, in a job shop environment, this paper adopts a variable batching scheme according to the load of the machines involved in each processing process, and proposes a non-mixed multi-processor combined production batch scheduling model, and combines the brainstorming algorithm to find the shortest Processing time. An improved brainstorming algorithm is proposed, which introduces greedy thinking and dynamic discussion mechanism. The number of discussions changes adaptively with the iteration of the algorithm. The global search and local search are combined to strengthen the search ability of the algorithm. The test results show that the improved brainstorming algorithm is more efficient and convergent than the basic brainstorming algorithm.
- multi-processor combined production /
- job shop /
- batch scheduling /
- brain storm optimization algorithm /
- discussion mechanism

HTML全文

图 1 引入贪婪思想的BSO算法流程图

Figure 1. Flow chart of BSOGT

下载: 全尺寸图片幻灯片

图 2 逆序交叉重组操作

Figure 2. Reverse precedence operation crossover

下载: 全尺寸图片幻灯片

图 3 环变异操作

Figure 3. Ring mutation operation

下载: 全尺寸图片幻灯片

图 4 多处理机组合生产的甘特图

Figure 4. Gantt chart of MCBSP

下载: 全尺寸图片幻灯片

图 5 残差正态概率分布图

Figure 5. Externally studentized residuals

下载: 全尺寸图片幻灯片

图 6 模型预测值和实际值

Figure 6. Predicted vs actual

下载: 全尺寸图片幻灯片

图 7 不同算法的收敛曲线

Figure 7. Convergences of different algorithms

下载: 全尺寸图片幻灯片

表 1 工件加工的信息

Table 1. Information of job processing

Job		$ {O}_{1} $			$ {O}_{2} $			$ {O}_{3} $			$ {O}_{4} $
Job	$ BH $	$PT_m$	$T_m$	$J_m$	$PT_m$	$T_m$	$J_m$	$PT_m$	$T_m$	$J_m$	$PT_m$	$T_m$	$J_m$
1	15	[7,5]	[20,24]	[4,5]	9	18	3	[6,8]	[14,8]	[1,2]	5	8	6
2	15	5	13	6	6	12	5	7	16	2	9	8	3
3	15	[5,7]	[19,25]	[2,1]	6	13	6	[8,6]	[15,14]	[4,5]	7	11	3
4	15	5	16	5	6	16	2	8	10	3	7	6	6
5	15	6	10	6	5	14	2	[6,5]	[7,13]	[5,4]	7	6	3
6	15	8	23	3	5	14	2	[6,3]	[9,12]	[5,4]	5	13	3

下载: 导出CSV

表 2 机器的最大负荷

Table 2. Maximum loads of the machines

Machine	P_max
M1	9
M2	9
M3	6
M4	9
M5	6
M6	13

下载: 导出CSV

表 3 不同规模算例工序总数统计表

Table 3. Statistical table of the total process for different scale calculation examples

$ n\times \mathrm{s}\mathrm{t}\mathrm{a}\mathrm{g}\mathrm{e} $	$ m $	$\mathrm{S}\mathrm{e}\mathrm{t}\mathrm{u}\mathrm{p}\;\mathrm{t}\mathrm{i}\mathrm{m}\mathrm{e}$	$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{c}\mathrm{e}\mathrm{s}\mathrm{s}\;\mathrm{t}\mathrm{i}\mathrm{m}\mathrm{e}$	$\mathrm{P}\mathrm{i}\mathrm{e}\mathrm{c}\mathrm{e}$	$\mathrm{T}\mathrm{o}\mathrm{t}\mathrm{a}\mathrm{l}\;\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{c}\mathrm{e}\mathrm{s}\mathrm{s}$
$ 6\times 4 $	6	（1，10）	（5，25）	15	$ 360 $
$ 6\times 7 $	11	（1，10）	（5，25）	15	$ 630 $
$ 6\times 10 $	17	（1，10）	（5，25）	15	$ 900 $
$ 6\times 15 $	27	（1，10）	（5，25）	15	$1\;350$
$ 10\times 4 $	6	（1，10）	（5，25）	15	$ 600 $
$ 10\times 7 $	11	（1，10）	（5，25）	15	$1\;050$
$ 10\times 10 $	17	（1，10）	（5，25）	15	$1\;500$
$ 10\times 15 $	27	（1，10）	（5，25）	15	$2\;250$
$ 15\times 4 $	6	（1，10）	（5，25）	15	$ 900 $
$ 15\times 7 $	11	（1，10）	（5，25）	15	$1\;575$
$ 15\times 10 $	17	（1，10）	（5，25）	15	$2\;250$
$ 15\times 15 $	27	（1，10）	（5，25）	15	$3\;375$
$ 20\times 4 $	6	（1，10）	（5，25）	15	$1\;200$
$ 20\times 7 $	11	（1，10）	（5，25）	15	$2\;100$
$ 20\times 10 $	17	（1，10）	（5，25）	15	$3\;000$
$ 20\times 15 $	27	（1，10）	（5，25）	15	$4\;500$
$ 35\times 4 $	6	（1，10）	（5，25）	15	$2\;100$
$ 35\times 7 $	11	（1，10）	（5，25）	15	$3\;675$
$ 35\times 10 $	17	（1，10）	（5，25）	15	$5\;250$
$ 35\times 15 $	27	（1，10）	（5，25）	15	$7\;875$
$ 50\times 15 $	29	（1，10）	（5，25）	15	$11\;250$

下载: 导出CSV

表 4 AVG的二次多项式模型的方差分析

Table 4. ANOVA of quadratic polynomial model for AVG

VS	MS	FD	SS	P
Model	50913.22	9	5.44	0.0180 (significant)
$ \mathrm{A} $-population size	882.00	1	0.85	0.3875
$ \mathrm{B} $-num of captain	2686.44	1	2.59	0.1519
$ \mathrm{C} $-Relativity mutation length	39846.65	1	38.35	0.0004
$ AB $	10.89	1	0.010	0.9213
$ AC $	65.61	1	0.063	0.8088
$ BC $	829.44	1	0.80	0.4013
$ {A}^{2} $	141.15	1	0.14	0.7233
$ {B}^{2} $	111.24	1	0.11	0.7531
$ {C}^{2} $	6092.81	1	5.86	0.0460
Residual	7273.12	7
Misfit term	3807.71	3	1.47	0.3505 (not significant)
Error	3465.41	4
Sum	58186.34	16

下载: 导出CSV

表 5 初始种群质量分析

Table 5. Quality of initial individual

$ n\times \mathrm{s}\mathrm{t}\mathrm{a}\mathrm{g}\mathrm{e} $	AVG
	$ \mathrm{R}\mathrm{G} $	$ \mathrm{O}\mathrm{B}\mathrm{L} $	$ \mathrm{I}\mathrm{E}\mathrm{G} $
$ 6\times 4 $	1908.91	1721.85	1704.77
$ 6\times 7 $	2430.7	2201.46	2105.11
$ 6\times 10 $	3185.91	2888.43	2716.01
$ 6\times 15 $	4901.84	4416.57	4110.76
$ 10\times 4 $	2718.27	2417.85	2305.98
$ 10\times 7 $	3594.04	3319.46	3015.6
$ 10\times 10 $	4416.3	4151.55	3270.18
$ 10\times 15 $	6559.62	6027.68	5344.48
$ 15\times 4 $	3526.84	3241.39	3064.36
$ 15\times 7 $	4798.78	4485.38	4038.49
$ 15\times 10 $	6178.45	5751.01	5074.35
$ 15\times 15 $	8299.25	7781.18	6744.10
$ 20\times 4 $	3672.6	4002.2	4182.2
$ 20\times 7 $	5119.8	5346.6	5437.8
$ 20\times 10 $	6591.2	6959.6	6896
$ 20\times 15 $	8936.4	9081.5	9198.8
$ 35\times 4 $	6621.8	6948.6	6713.6
$ 35\times 7 $	8613.4	8837	8681
$ 35\times 10 $	10874.6	11249.8	11047
$ 35\times 15 $	13597.6	13840.6	14017.6
$ 50\times 15 $	27477.52	26332.15	21065.63

下载: 导出CSV

表 6 不同分批方式的对比

Table 6. Comparison of different batch modes

$ n\times \mathrm{s}\mathrm{t}\mathrm{a}\mathrm{g}\mathrm{e} $	$ \mathrm{m}\mathrm{a}\mathrm{k}\mathrm{e}\mathrm{s}\mathrm{p}\mathrm{a}\mathrm{n} $		$ \mathrm{A}\mathrm{M}\mathrm{V}\mathrm{R} $
	$ \mathrm{V}\mathrm{M} $	$ \mathrm{C}\mathrm{M} $	$ \mathrm{V}\mathrm{M} $	$ \mathrm{C}\mathrm{M} $
$ 6\times 4 $	1511	1551	0.75	0.72
$ 6\times 7 $	1499	1445	0.79	0.83
$ 6\times 10 $	1938	2082	0.85	0.78
$ 6\times 15 $	2954	2541	0.81	0.73
$ 10\times 4 $	1502	1941	0.88	0.74
$ 10\times 7 $	2202	2341	0.89	0.81
$ 10\times 10 $	2704	2984	0.91	0.85
$ 10\times 15 $	3888	3799	0.79	0.72
$ 15\times 4 $	2321	2871	0.73	0.70
$ 15\times 7 $	3070	2577	0.84	0.80
$ 15\times 10 $	4062	4737	0.76	0.68
$ 15\times 15 $	5494	5439	0.78	0.71
$ 50\times 15 $	18962	21845	0.68	0.59

下载: 导出CSV

表 7 算法性能对比表

Table 7. Performance comparison of algorithms

$ n\times \mathrm{s}\mathrm{t}\mathrm{a}\mathrm{g}\mathrm{e} $	${\rm{RPD}}$				${\rm{ WRE }}$				${\rm{ BRE }}$
	$ \mathrm{B}\mathrm{S}\mathrm{O}\mathrm{G}\mathrm{T} $	$ \mathrm{I}\mathrm{C}\mathrm{A} $	$ \mathrm{M}\mathrm{A} $	$ \mathrm{B}\mathrm{S}\mathrm{O} $	$ \mathrm{B}\mathrm{S}\mathrm{O}\mathrm{G}\mathrm{T} $	$ \mathrm{I}\mathrm{C}\mathrm{A} $	$ \mathrm{M}\mathrm{A} $	$ \mathrm{B}\mathrm{S}\mathrm{O} $	$ \mathrm{B}\mathrm{S}\mathrm{O}\mathrm{G}\mathrm{T} $	$ \mathrm{I}\mathrm{C}\mathrm{A} $	$ \mathrm{M}\mathrm{A} $	$ \mathrm{B}\mathrm{S}\mathrm{O} $
$ 6\times 4 $	0	0	0	0	0	0	0	0	0	0	0	0
$ 6\times 7 $	0	0.19	0.27	0.32	0	0.35	0.25	0.71	0	0.18	0.53	0.85
$ 6\times 10 $	0	0	2.58	1.68	1.41	3.04	5.42	4.66	0.93	0.42	3.91	4.88
$ 6\times 15 $	0	4.63	6.05	10.35	1.93	2.81	3.51	5.62	2.51	3.25	3.82	3.45
$ 10\times 4 $	0	3.79	3.13	8.32	2.12	2.23	5.29	4.44	1.85	3.52	4.14	2.95
$ 10\times 7 $	0.77	0	1.28	6.13	1.95	2.82	3.50	2.73	2.46	3.70	6.89	3.55
$ 10\times 10 $	0	3.92	4.62	2.74	1.06	2.39	3.52	3.34	1.39	2.64	3.79	6.88
$ 10\times 15 $	0	6.53	5.92	9.88	3.14	12.48	6.63	3.40	4.61	5.52	5.42	3.30
$ 15\times 4 $	0	0.95	3.35	2.87	1.47	1.76	3.74	3.79	1.29	1.54	1.53	2.67
$ 15\times 7 $	0	4.66	4.65	4.82	1.40	3.28	3.51	6.15	1.43	2.53	2.70	2.68
$ 15\times 10 $	0.40	2.36	0	6.12	2.52	4.15	5.74	9.33	3.18	3.76	7.29	2.53
$ 15\times 15 $	0	2.47	3.72	4.75	1.16	4.34	5.33	3.85	1.04	3.47	3.50	2.97
$ 20\times 4 $	0	1.63	20.27	0.88	1.33	1.19	5.05	3.93	1.05	0.88	3.28	1.67
$ 20\times 7 $	0	0.32	20.26	2.33	1.21	1.53	3.60	1.72	1.28	1.92	2.68	2.62
$ 20\times 10 $	1.55	0	6.56	3.11	1.63	2.10	5.64	2.54	1.89	2.40	5.64	2.54
$ 20\times 15 $	8.22	0	3.74	4.21	1.64	1.55	3.46	7.52	1.34	2.05	3.48	3.44
$ 35\times 4 $	5.76	0	25.35	7.50	0.84	1.62	1.55	1.90	1.02	3.64	3.08	0.97
$ 35\times 7 $	5.06	0	10.41	5.69	1.66	1.75	7.34	2.84	2.75	2.46	5.18	1.61
$ 35\times 10 $	7.88	0	15.50	6.60	3.82	2.14	2.61	1.10	3.76	3.02	1.60	1.52
$ 35\times 15 $	7.55	0	6.41	0.86	1.56	3.18	2.25	5.60	3.34	1.68	2.40	4.36
$ 50\times 15 $	0	2.57	7.75	7.02	3.39	5.81	4.09	4.00	2.11	4.77	2.97	2.83

下载: 导出CSV

参考文献(18)

[1]	REITER S. A system for managing job-shop production[J]. The Journal of Business, 1966, 39(3): 371-393. doi: 10.1086/294867
[2]	REITER S, RICE D B. Discrete optimizing solution procedures for linear and nonlinear integer programming problems[J]. Management Science, 1966, 12(11): 829-850. doi: 10.1287/mnsc.12.11.829
[3]	HUANG R, YU T. An effective ant colony optimization algorithm for multi-objective jobshop scheduling with equal-size lot-splitting[J]. Applied Soft Computing, 2017, 57: 642- 656. doi: 10.1016/j.asoc.2017.04.062
[4]	ANDRZEJ B, FRANK W. Flexible job shop scheduling with lot streaming and sublot size optimization[J]. International Journal of Production Research 2018, 56(19): 6391-6411.
[5]	JUAN M N. Production scheduling and lot streaming at flexible job-shops environments using constraint programming[J]. Computer & Industrial Engineering, 2019, 136: 252-264.
[6]	DROZDOWSKI M. Scheduling multiprocessor tasks — An overview[J]. European Journal of Operational Research, 1996, 94(2): 215-230. doi: 10.1016/0377-2217(96)00123-3
[7]	JIANG E D, WANG L, WANG J J. Decomposition-based multi-objective optimization for energy-aware distributed hybrid flow shop scheduling with multiprocessor tasks[J]. Tsinghua Science and Technology, 2021, 26(5): 646-663. doi: 10.26599/TST.2021.9010007
[8]	CHEN J, LEE C Y. General multiprocessor task scheduling[J]. Naval Research Logistics, 1999, 46(1): 72-74.
[9]	吕媛媛, 樊坤, 瞿华, 等. 多目标粒子群算法求解混合多处理机任务作业车间调度问题研究[J]. 小型微型计算机系统, 2021: 1-8. doi: 10.3969/j.issn.1000-1220.2021.01.001
[10]	LIU X F, LI W D. Approximation algorithms for the multiprocessor scheduling with submodular penalties[J]. Optimization Letters, 2021: 1-16.
[11]	MOGHADDAM M E, BONYADI M R. An immune-based genetic algorithm with reduced search space coding for multiprocessor task scheduling problem[J]. International Journal of Parallel Programming, 2012, 40(2): 225-257. doi: 10.1007/s10766-011-0179-0
[12]	SHI Y. Brain storm optimization algorithm[C]// International Conference in Swarm Intelligence. Chongqing, China: DBLP, 2011: 303-309.
[13]	曹国刚, 朱信玉, 陈颖, 等. 基于改进头脑风暴优化算法的医学图像配准方法[J]. 数据采集与处理, 2020, 35(4): 730-738.
[14]	李怡敏, 王宝珠, 刘翠响, 等. DBBSO算法在低空航线规划中的应用[J]. 现代电子技术, 2019, 42(22): 108-112.
[15]	李捷, 张远春, 汪龙, 任佳, 等. 基于纵向变异头脑风暴算法的短期水火发电调度[J]. 电工材料, 2019(4): 28-32.
[16]	张超勇, 饶运清, 刘向军, 等. 基于POX交叉的遗传算法求解Job-Shop调度问题[J]. 中国机械工程, 2004(23): 83-87.
[17]	陈祥, 朱传军, 张超勇. 基于文化基因算法的开放车间调度问题研究[J]. 工业工程, 2018, 21(6): 16-22.
[18]	徐震浩, 王程, 顾幸生. 基于DICA的存储受限流水车间调度[J]. 华东理工大学学报(自然科学版), 2018, 44(4): 563-572.