Research on flexible job-shop scheduling based on improved genetic algorithm
-
摘要: 针对柔性作业车间的多目标调度问题,文章建立以最大完工时间、能耗为目标的数学模型,提出一种多目标的改进遗传算法的求解方法。首先,在交叉算子中使用均匀交叉法,采用了基于邻域的变异算子。其次,针对交叉变异算子进行了非均匀改进,旨在增加算法搜索能力。通过动态调整非均匀交叉和非均匀变异的概率,提高搜索空间覆盖率,避免陷入局部最优解。最后,采用基准算例Kacem测试集进行测试。实验证明,该改进算法有效地解决了同时考虑最大完工时间和能耗的多目标调度问题,取得了显著的改善效果。Abstract: For the multi-objective scheduling problem in a flexible job shop, we have established a mathematical model with the objectives of maximizing the completion time and minimizing energy consumption. To address this problem, we propose an improved multi-objective genetic algorithm. Firstly, using the uniform crossover operator in the crossover process and introduce a neighborhood-based mutation operator. Secondly, improving the non-uniformity of the crossover and mutation operators to enhance the algorithm’s search capability. By dynamically adjusting the probabilities of non-uniform crossover and mutation, we increase the coverage of the search space and avoid getting trapped in local optima. Finally, testing the proposed algorithm using the Kacem benchmark test set. The experimental results demonstrate that our improved algorithm effectively solves the multi-objective scheduling problem considering both maximum completion time and energy consumption, achieving significant improvements.
-
表 1 相关参数定义
参数 定义 $ M $ 机器数量 $ N $ 工件数量 $ i $ 工序序号 $ j $ 工序序号 $ h $ 机器序号 $ {O}_{ij} $ 工件$ i $的第$ j $道工序 $ {t}_{ijh} $ 工件$ i $第$ j $道工序在机器$ h $的加工时间 $ {C}_{i} $ 工件$ i $的完工时间 $ {F}_{ijh} $ 工件$ i $第$ j $道工序在机器$ h $的完工时间 $ {S}_{ijh} $ 工件$ i $第$ j $道工序在机器$ h $的初始加工时间 $ {C}_{\mathrm{m}\mathrm{a}\mathrm{x}} $ 最大完工时间 $ E $ 机器加工的总能耗 $ \varphi $ 权重系数 $ {e}_{ijh} $ 工件$ i $的第$ j $道工序在机器$ h $上的加工能耗 $ {S}_{ijh} $ 工件$ i $的第$ j $道工序在机器$ h $上的开始加工时间 $ {a}_{ijh} $ 机器$ h $上能否加工工件$ i $的第$ j $道工序,
$ {a}_{ijh}=1 $表示可以加工,$ {a}_{ijh}=0 $表示不可以加工表 2 一个4×3的部分FJSP实例
工件 工序 $ {\mathit{M}}_{1} $ $ {\mathit{M}}_{2} $ $ {\mathit{M}}_{3} $ $ {\mathit{J}}_{1} $ $ {\mathit{O}}_{11} $ 4 — 10 $ {\mathit{O}}_{12} $ — 2 8 $ {\mathit{J}}_{2} $ $ {\mathit{O}}_{21} $ 4 6 — $ {\mathit{O}}_{22} $ 8 4 2 $ {\mathit{J}}_{3} $ $ {\mathit{O}}_{31} $ 4 6 — $ {\mathit{O}}_{32} $ 4 — 10 $ {\mathit{J}}_{4} $ $ {\mathit{O}}_{41} $ 8 — 4 $ {\mathit{O}}_{42} $ — 6 10 -
[1] Gao K,Yang F,Zhou M C,et al. Flexible job-shop rescheduling for new job insertion by using discrete jaya algorithm[J]. IEEE Transactions on Cybernetics,2018,49(5):1944-1955. [2] Brucker P,Schlie R. Job-shop scheduling with multi-purpose machines[J]. Computing,1990,45(4):369-375. doi: 10.1007/BF02238804 [3] 曲鹏举,唐向红. 改进粒子群算法在柔性车间调度问题的研究[J/OL]. 机械设计与制造[2023-09-05]. https://doi.org/10.19356/j.cnki.1001-3997.20230905.006. [4] 李长云,谷鹏飞,林多. 基于改进遗传算法的多目标柔性作业调度研究[J]. 制造技术与机床,2022(5):47-52. [5] Marzouki B ,Belkahla Driss O ,Ghédira K. Multi agent model based on chemical reaction optimization with greedy algorithm for flexible job shop scheduling problem[J]. Procedia Computer Science,2017,112:81-90. [6] 赵小惠,卫艳芳,王凯峰,等. 改进蚁群算法的柔性作业车间调度问题研究[J]. 组合机床与自动化加工技术,2022(2):165-168. [7] 钟小玉,韩玉艳,姚香娟,等. 不确定工时下多目标柔性作业车间调度问题的进化求解方法[J]. 中国科学:信息科学,2023,53(4):737-757. [8] 周鹏鹏,翟志波,戴玉森. 基于改进遗传算法的柔性作业车间调度问题研究[J]. 组合机床与自动化加工技术,2023(3):183-186,192. [9] 宋李俊,徐志鹏,李斐. 隐性扰动下柔性作业车间重调度决策[J]. 制造技术与机床,2023(1):160-167. [10] 梁晓磊,马千慧,李章洪,等. 考虑多时间约束和机器效率的柔性作业车间调度问题建模及优化[J]. 制造技术与机床,2021(10):114-122. [11] 王佳怡,潘瑞林,秦飞. 改进遗传算法求解柔性作业车间调度问题[J]. 制造业自动化,2022(12):91-94,106. [12] 姜一啸,吉卫喜,何鑫,等. 基于改进非支配排序遗传算法的多目标柔性作业车间低碳调度[J]. 中国机械工程,2022,33(21):2564-2577. [13] 唐艺军,李雪. 基于改进混合遗传算法的柔性车间调度问题研究[J]. 现代制造工程,2023(10):8-14. [14] 赵慧娟,范明霞,姜盼松,等. 时间-能耗-质量权衡优化的柔性作业车间多目标调度研究[J]. 计算机应用与软件,2023(5):67-75. [15] Chen R,Yang B,Li S,et al. A self-learning genetic algorithm based on reinforcement learning for flexible job-shop scheduling problem[J]. Computers & Industrial Engineering,2020,149:106778. [16] 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):1009117. doi: 10.1109/TSMCC.2002.1009117