Multi-Processor Combined Production Batch Scheduling Problem Based on Brain Storm Optimization Algorithm
-
摘要: 在生产调度领域中，受生产工艺等诸多因素的影响，往往每个生产过程都需要多台机器的同时参与加工。同时，待加工的工件数量较多，需要将每种类型的工件进行批量处理，以缩短生产周期。因此，本文在作业车间环境下，根据每个加工过程所参与机器的负荷，采用可变分批方案，提出了非混排多处理机组合生产批量调度模型，并结合头脑风暴优化算法，求解出最短加工时间。提出了一种改进的头脑风暴优化算法，引入贪婪思想与动态讨论机制，讨论次数随着算法的迭代而自适应变化，将全局搜索与局部搜索相结合，加强了算法的搜索能力。实验结果表明，改进的头脑风暴优化算法与基本的头脑风暴优化算法相比，求解效率更高，收敛速度更快。
-
关键词:
- 多处理机组合生产 /
- 作业车间 /
- 批量调度 /
- 头脑风暴优化算法（BSO） /
- 讨论机制
Abstract: In the field of production scheduling, due to the inffluence of many factors such as production technology, each production process usually requires multiple machines to simultaneously participate in processing. Meanwhile, the number of workpieces to be processed is large, and each type of workpiece needs to be processed in batches for shortening the production cycle. Aiming at the above problems, 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 integrate the brainstorming algorithm to search the shortest Processing time. Moreover, an improved brainstorming algorithm is proposed by introducing greedy thinking and dynamic discussion mechanism. The number of discussions is changed adaptively with the iteration and the global search and local search are utilized to strengthen the search ability of the proposed algorithm. Finally, it is shown via the test results that the improved brainstorming algorithm is more efficient and convergent than the basic brainstorming algorithm. -
表 1 工件加工的信息
Table 1. Information of job processing
Job $ {O}_{1} $ $ {O}_{2} $ $ {O}_{3} $ $ {O}_{4} $ $ 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
表 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
-
[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. -
点击查看大图
图(7) / 表(7)
计量
- 文章访问数: 289
- HTML全文浏览量: 121
- PDF下载量: 24
- 被引次数: 0
