Heuristic Dynamic Scheduling Method for Re-Entrant Hybrid Flow Shops Considering Quality Sampling Inspection
-
摘要:
为了降低OLED玻璃基板阵列工艺中质量抽检及其判定结果对生产连续性以及最大完工时间的扰动，面向工件合格、返工与报废3类质量抽检结果，构建以最小化最大完工时间为优化目标的调度模型，并提出一种启发式动态调度方法. 首先，设计自适应离散麻雀搜索算法生成初始调度方案，采用工序与机器双层编码，利用经典NEH方法和混沌映射提高初始种群质量，并通过离散化位置更新、发现者与警戒者比例自适应调整、周期性对立学习、多引领者引导更新等策略增强搜索能力；其次，针对抽检事件及其不同结果，设计基于工序松弛时间的插空重调度策略来降低扰动带来的影响. 研究结果显示：在重调度策略对比实验中，本文提出的插空重调度策略可以将抽检引入的额外时间影响维持在约15%以内，显著缓解了抽检对完工时间的扰动；在算法整体对比实验中，该启发式动态调度方法在最大完工时间、收敛速度以及解的稳定性等关键指标上均表现更为突出，证明了其较强的综合求解性能与鲁棒性；该方法能够适配玻璃基板的可重入加工与抽检反馈机制，验证了其面向实际生产场景的有效性.
Abstract:To reduce the disruptive effects of quality sampling inspection and its outcomes on production continuity and makespan in OLED glass-substrate array manufacturing, a scheduling model was formulated to minimize makespan under three inspection outcomes (acceptance, rework, and scrapping), and a heuristic dynamic scheduling method was developed. First, an adaptive discrete sparrow search algorithm was designed to generate the initial schedule. An operation-machine two-layer encoding scheme was adopted, and the classical NEH heuristic and chaotic mapping were used to improve the quality of the initial population. Discrete position-update operators, adaptive adjustment of discoverer and scout proportions, periodic opposition-based learning, and multi-leader-guided updating were further introduced to enhance the search capability. Second, to mitigate the disturbances caused by inspection events and different inspection outcomes, a gap-insertion rescheduling strategy based on operation slack time was developed. The comparison of rescheduling strategies shows that the proposed gap-insertion strategy limits the additional time overhead caused by sampling inspection to approximately 15%, thus significantly mitigating its impact on makespan. In the overall algorithm comparison, the proposed heuristic dynamic scheduling method performs better in terms of makespan, convergence speed, and solution stability, demonstrating strong overall optimization performance and robustness. The method can accommodate the re-entrant processing characteristics and sampling-inspection feedback mechanism of glass-substrate manufacturing, demonstrating its effectiveness in practical production scenarios.
-
图 6 抽检结果为返工的重调度步骤甘特图
Figure 6. Gantt chart of rescheduling steps for rework inspection outcome
图 7 不同重调度方案下完工时间对比箱线图
Figure 7. Box plots comparing completion times across different rescheduling schemes
表 1 数学符号以及含义
Table 1. Notation and definitions
符号 含义 $ s $ 加工阶段数量 $ i $ 加工阶段序号，$ i=1,2,\cdots ,s $ $ n $ 工件数量 $ j $ 工件序号，$ j=1,2,\cdots ,j',\cdots ,n $ $ {m}_{i} $ 阶段$ i $的并行机数 $ k $ 并行机序号，$ k=1,2,\cdots ,{m}_{i} $ $ r $ 加工层次数量 $ l $ 加工层次序号，$ l=1,2,\cdots ,r $ $ {S}_{ijkl} $ 工件$ j $在第$ l $层的阶段$ i $的并行机$ k $上的开始加工时间 $ {p}_{ijk} $ 工件$ j $在阶段$ i $的并行机$ k $上的加工时间 $ {C}_{ijkl} $ 工件$ j $在第$ l $层的阶段$ i $的并行机$ k $上的完工时间 $ {O}_{ik} $ 0时刻阶段$ i $的并行机$ k $加工过的初始工件数量 $ {N}_{ik} $ 阶段$ i $的并行机$ k $加工过的工件数量 $ {M}_{ik} $ 对阶段$ i $的并行机$ k $加工的工件进行抽检的数量阈值 $ {Q}_{il} $ 在第$ l $层的阶段$ i $上被抽检的工件$ j $的质量得分 $ Q_{i}^{\text{A}},Q_{i}^{\text{B}} $ 质量指标 $ T_{i}^{\text{Q}} $ 阶段$ i $上被抽检的工件进行质量检测所需要的时间 $ {T}_{\mathrm{S}} $ 机器停机时间 $ W $ 一个足够大的正数 $ {C}_{\max } $ 最大完工时间 $ \varepsilon $ 一个常数为1，当工件不合格时为0 $ {X}_{ijkl} $ 若工件$ j $在第$ l $层的阶段$ i $的并行机$ k $上加工为1，否则为0 $ {Y}_{ij{{j}^{\prime}}l} $ 在第$ l $层的阶段$ i $上，若工件$ j $早于工件$ {j}^{\prime} $加工为1，否则为0 $ {Z}_{ijkl} $ 若工件$ j $在第$ l $层的阶段$ i $的并行机$ k $上加工后抽检为1，否则为0 $ {D}_{ijkl} $ 若工件$ j $在第$ l $层的阶段$ i $的并行机$ k $上抽检后合格为1，否则为0 $ {R}_{ijkl} $ 若工件$ j $在第$ l $层的阶段$ i $的并行机$ k $上抽检后需要返工为1，否则为0 $ {F}_{ijkl} $ 若工件$ j $在第$ l $层的阶段$ i $的并行机$ k $上抽检后不合格为1，否则为0 
下载: 导出CSV
表 2 算例集参数生成范围
Table 2. Parameter generation ranges for instance sets
参数 小规模 大规模 工件数 [5, 15] [15, 25] 阶段数 [3, 5] [5, 10] 层次数 [2, 3] [2, 5] 每阶段并行机器数 [2, 3] [3, 6] 各机器初始计件数 [0,10] 工序加工时间 [10, 30]
下载: 导出CSV
表 3 正交矩阵
Table 3. Orthogonal matrix
实验编号 参数 $ {C}_{max} $均值 $ {P}_{max} $ $ {S}_{min} $ $ {S}_{{\mathrm{T}}} $ $ \gamma $ 1 0.10 0.04 0.60 1.00 505.90 2 0.10 0.06 0.70 1.50 499.95 3 0.10 0.08 0.80 2.00 503.85 4 0.15 0.04 0.70 2.00 504.10 5 0.15 0.06 0.80 1.00 499.90 6 0.15 0.08 0.60 1.50 502.10 7 0.20 0.04 0.80 1.50 502.50 8 0.20 0.06 0.60 2.00 502.25 9 0.20 0.08 0.70 1.00 504.70 K1 503.23 504.17 503.42 503.50 K2 502.03 500.70 502.92 501.52 K3 503.15 503.55 502.08 503.40 R 1.20 3.47 1.33 1.98
下载: 导出CSV
表 4 5个重调度方案完工时间对比结果
Table 4. Comparison of completion times for five rescheduling schemes
算例 平均完工时间 DR_1 DR_2 DR_3 DR_4 DR_5 j18s6r2 861.45 746.40 825.10 783.65 667.15 j10s5r4 1065.85 900.80 991.00 947.30 785.75 j20s5r4 2058.35 1772.10 1901.20 1836.25 1550.70 j19s7r3 1697.00 1514.25 1654.20 1596.85 1337.45 j17s6r3 1129.15 990.50 1058.75 1044.30 815.65 j15s6r2 769.25 671.00 748.60 701.80 598.90 j11s8r2 833.00 692.35 787.90 715.45 538.85 j24s8r3 1821.75 1542.15 1756.30 1698.85 1190.30 j11s7r3 1049.80 903.25 980.65 928.25 643.25 j13s8r4 1927.55 1794.95 1855.65 1805.30 1382.50
下载: 导出CSV
表 5 6种算法对比实验结果
Table 5. Comparative experimental results of six algorithms
抽检情况 算法 算例 j18s6r2 j10s5r4 j20s5r4 j19s7r3 j17s6r3 j15s6r2 j11s8r2 j24s8r3 j11s7r3 j13s8r4 初始调度 CDABC 649.15 667.9 1313.8 984.1 829.9 575.8 571.8 967 699.3 1084.9 DWOA 770 799 1533 1206.6 991.8 719.1 661.9 1482 792 1276.2 HGTSA 684.9 732.5 1406.6 1075.4 925.25 599.3 608.2 1327 725.1 1183.4 IGWO 675.1 669 1342 1022.4 803 613 480 1464.2 753 916.6 DSSA 562 572 1129 804 706 501.3 511.8 988.9 599.15 887.2 ADSSA 536.6 559 1115 791.8 672.1 493 485 976.2 591.35 871.1 抽检后调度 CDABC 773.5 1036 1887.7 1252 1266.6 736.2 795.1 1223 1213 1355 DWOA 950 1313 1930 1286 1423 808 865 1436 1417 1467 HGATS 885 1541.3 1969 1421 1123 839 754 1470 1220 1304 IGWO 1090 1529 1992 1245 1295 876 1451 1508 1400 1713 DSSA 738.1 1238 1926.8 1175.2 1622 725.4 1037 1286 1293 1265 ADSSA 731.4 1000 1874.2 1153.2 940 665 662 1209.3 980 1226.5
下载: 导出CSV
表 6 六种算法稳定性对比
Table 6. Stability comparison of six algorithms
算例 j18s6r2 j10s5r4 j20s5r4 j19s7r3 j17s6r3 CDABC AVE 773.5 1036 1887.7 1252 1266.6 MIN 740 1005 1849 1204 1219 Std 18.31 18.95 29.86 23.44 32.67 DWOA AVE 950 1313 1930 1286 1423 MIN 903 1245 1877 1198 1342 Std 25.88 27.31 24.85 28.49 25.83 HGTSA AVE 885 1541.3 1969 1421 1123 MIN 847 1488 1815 1301 1085 Std 18.35 25.47 91.9 50.31 19.04 IGWO AVE 1090 1529 1992 1245 1295 MIN 1046 1477 1949 1178 1231 Std 24.14 19.06 37.73 20.31 21.45 DSSA AVE 738.1 1238 1926.8 1175.2 1622 MIN 728 1176 1873 1155 1327 Std 16.76 18.97 28.2 22.83 74.01 ADSSA AVE 731.4 1000 1874.2 1153.2 940 MIN 724 985 1843 1132 928 Std 12.01 14.29 19.42 15.63 8.67
下载: 导出CSV
-
[1] 罗亚波, 喻少龙, 张峰, 等. 改进候鸟算法求解可重入混流车间批量流调度[J]. 浙江大学学报(工学版), 2025, 59(8): 1598-1607. doi: 10.3785/j.issn.1008-973X.2025.08.006Luo Yabo, Yu Shaolong, Zhang Feng, et al. Improved migrating bird algorithm for re-entrant hybrid flowshop scheduling problem with lot streaming[J]. Journal of Zhejiang University (Engineering Science), 2025, 59(8): 1598-1607. doi: 10.3785/j.issn.1008-973X.2025.08.006 [2] Kumar P R. Re-entrant lines[J]. Queueing Systems, 1993, 13(1/2/3): 87-110. [3] 朱光宇, 贾海斌. 面向半导体车间多目标可重入调度研究[J]. 华中科技大学学报(自然科学版), 2023, 51(2): 122-130. doi: 10.13245/j.hust.230213Zhu Guangyu, Jia Haibin. Multi-objective reentrant scheduling problem for semiconductor workshop[J]. Journal of Huazhong University of Science and Technology (Nature Science Edition), 2023, 51(2): 122-130. doi: 10.13245/j.hust.230213 [4] 轩华, 李冰, 王薛苑, 等. 带运输考虑的多阶段动态可重入混合流水车间调度[J]. 控制理论与应用, 2018, 35(3): 357-366. doi: 10.7641/CTA.2017.70465Xuan Hua, Li Bing, Wang Xueyuan, et al. Multi-stage dynamic reentrant hybrid flowshop scheduling with transportation consideration[J]. Control Theory & Applications, 2018, 35(3): 357-366. doi: 10.7641/CTA.2017.70465 [5] 吴秀丽, 李雨馨, 匡源, 等. 改进迭代贪婪算法求解可重入流水车间调度问题[J]. 计算机集成制造系统, 2024, 30(7): 2364-2380. doi: 10.13196/j.cims.2022.1019Wu Xiuli, Li Yuxin, Kuang Yuan, et al. Improved iterated greedy algorithm for reentrant flow shop scheduling problem[J]. Computer Integrated Manufacturing Systems, 2024, 30(7): 2364-2380. doi: 10.13196/j.cims.2022.1019 [6] 余斌煌. 柔性流水车间调度问题综述[J]. 现代制造工程, 2022(9): 154-162, 71. doi: 10.16731/j.cnki.1671-3133.2022.09.022Yu Binhuang. Review on flexible flow shop scheduling[J]. Modern Manufacturing Engineering, 2022(9): 154-162,71. doi: 10.16731/j.cnki.1671-3133.2022.09.022 [7] Geng K F, Liu L, Wu Z Y. Energy-efficient distributed heterogeneous re-entrant hybrid flow shop scheduling problem with sequence dependent setup times considering factory eligibility constraints[J]. Scientific Reports, 2022, 12: 18741. doi: 10.1038/s41598-022-23144-6 [8] Tang H T, Zhou J H, Shao Y P, et al. Hybrid flow-shop scheduling problems with missing and re-entrant operations considering process scheduling and production of energy consumption[J]. Sustainability, 2023, 15(10): 7982. doi: 10.3390/su15107982 [9] Zheng Q Q, Zhang Y, Tian H W, et al. A cooperative adaptive genetic algorithm for reentrant hybrid flow shop scheduling with sequence-dependent setup time and limited buffers[J]. Complex & Intelligent Systems, 2024, 10(1): 781-809. doi: 10.1007/s40747-023-01147-8 [10] Moyne J, Samantaray J, Armacost M. Big data capabilities applied to semiconductor manufacturing advanced process control[J]. IEEE Transactions on Semiconductor Manufacturing, 2016, 29(4): 283-291. doi: 10.1109/TSM.2016.2574130 [11] Fuladi S K, Kim C S. Dynamic events in the flexible job-shop scheduling problem: rescheduling with a hybrid metaheuristic algorithm[J]. Algorithms, 2024, 17(4): 142. doi: 10.3390/a17040142 [12] 吴秀丽, 李雨馨. 带批处理机的可重入混合流水车间主动-反应式动态调度方法[J]. 计算机集成制造系统, 2025, 31(7): 2466-2481. doi: 10.13196/j.cims.2024.0317Wu Xiuli, Li Yuxin. Proactive-reactive dynamic scheduling method for reentrant hybrid flow shop with batch processing machines[J]. Computer Integrated Manufacturing Systems, 2025, 31(7): 2466-2481. doi: 10.13196/j.cims.2024.0317 [13] Ren F J, Liu H B. Dynamic scheduling for flexible job shop based on MachineRank algorithm and reinforcement learning[J]. Scientific Reports, 2024, 14: 29741. doi: 10.1038/s41598-024-79593-8 [14] Gui Y, Tang D B, Zhu H H, et al. Dynamic scheduling for flexible job shop using a deep reinforcement learning approach[J]. Computers & Industrial Engineering, 2023, 180: 109255. doi: 10.1016/j.cie.2023.109255 [15] 胡明珠, 张维维, 张剑, 等. 元模型驱动的柔性作业车间具身智能体及其调度系统构建[J/OL]. 西南交通大学学报, 2025-01-02. https: //link.cnki.net/urlid/51.1277.u.20241231.1624.018. [16] Xue J K, Shen B. A novel swarm intelligence optimization approach: sparrow search algorithm[J]. Systems Science & Control Engineering, 2020, 8(1): 22-34. doi: 10.1080/21642583.2019.1708830 [17] 李峥峰, 叶文枭, 梅亚航. 麻雀搜索算法及其应用研究综述[J]. 中原工学院学报, 2025, 36(4): 1-10, 45. doi: 10.3969/j.issn.1671-6906.2025.04.001Li Zhengfeng, Ye Wenxiao, Mei Yahang. A survey of sparrow search algorithm and its applications[J]. Journal of Zhongyuan University of Technology, 2025, 36(4): 1-10,45. doi: 10.3969/j.issn.1671-6906.2025.04.001 [18] Ashraf A, Pervaiz S, Haider Bangyal W, et al. Studying the impact of initialization for population-based algorithms with low-discrepancy sequences[J]. Applied Sciences, 2021, 11(17): 8190. doi: 10.3390/app11178190 [19] 周宁, 张嵩霖, 张晨. 融合粗糙数据推理的离散麻雀搜索算法求解HFSP问题[J]. 北京航空航天大学学报, 2024, 50(2): 398-408. doi: 10.13700/j.bh.1001-5965.2022.0424Zhou Ning, Zhang Songlin, Zhang Chen. Discrete sparrow search algorithm incorporating rough data-deduction for solving hybrid flow-shop scheduling problems[J]. Journal of Beijing University of Aeronautics and Astronautics, 2024, 50(2): 398-408. doi: 10.13700/j.bh.1001-5965.2022.0424 [20] 苏建涛, 董绍华, 朱诗敏. 多目标混合流水车间机器故障重调度问题研究[J]. 机械工程学报, 2024, 60(4): 438-448. doi: 10.3901/JME.2024.04.438Su Jiantao, Dong Shaohua, Zhu Shimin. Research on machine fault rescheduling problem of multi objective hybrid flow shop based on intelligent manufacturing[J]. Journal of Mechanical Engineering, 2024, 60(4): 438-448. doi: 10.3901/JME.2024.04.438 [21] Cho H M, Bae S J, Kim J, et al. Bi-objective scheduling for reentrant hybrid flow shop using Pareto genetic algorithm[J]. Computers & Industrial Engineering, 2011, 61(3): 529-541. doi: 10.1016/j.cie.2011.04.008 [22] Hu D Y, Wu Y L, Qiu L P, et al. Constructive-destructive neighbor search drives artificial bee colony algorithm for variable speed green hybrid flowshop scheduling problem[J]. Scientific Reports, 2025, 15: 9671. doi: 10.1038/s41598-025-93582-5 [23] Zhang S J, Gu X S. A discrete whale optimization algorithm for the no-wait flow shop scheduling problem[J]. Measurement and Control, 2023, 56(9/10): 1764-1779. [24] Xu W X, Hu Y W, Luo W, et al. A multi-objective scheduling method for distributed and flexible job shop based on hybrid genetic algorithm and tabu search considering operation outsourcing and carbon emission[J]. Computers & Industrial Engineering, 2021, 157: 107318. doi: 10.1016/j.cie.2021.107318 [25] Li X Y, Xie J, Ma Q J, et al. Improved gray wolf optimizer for distributed flexible job shop scheduling problem[J]. Science China Technological Sciences, 2022, 65(9): 2105-2115. doi: 10.1007/s11431-022-2096-6 -
下载:
点击查看大图
计量
- 文章访问数: 2
- HTML全文浏览量: 2
- PDF下载量: 3
- 被引次数: 0