考虑多技能水平工人分配的复杂产品装配调度问题

doi:10.3901/JME.2025.04.389

摘要/Abstract

摘要： 在卫星、导弹等航天复杂产品总装车间，许多装配工作由一组工人手工协作完成，且每个产品都需要经过相同的装配工序才能完成装配。由于不同工人的技能水平和装配效率不同，每道工序又有多个可选的工位，因此复杂产品装配车间调度问题可以被视为混合流水车间调度和工人分配的组合问题。为此，针对复杂产品总装生产调度问题，以最小化最大完工时间和最小化平均延迟时间作为优化目标，构建一个考虑多技能水平工人分配的多目标混合流水车间调度模型，提出一种改进的优化突变进化算法。首先，利用纳瓦兹-恩斯科-汉姆启发式算法产生初始种群以提高解的质量；其次，将非支配排序的种群增加一个突变生成的种群，以提高种群多样性。最后，基于某航天复杂产品装配车间实例，将所提算法与6种多目标优化算法(Multi-objective evolutionary algorithm，MOEA)进行了对比。结果表明，所提算法在逼近最优解的质量和算法稳定性上均优于其他6个MOEA算法。

关键词: 混合流水车间调度, 工人分配, 复杂产品, 装配车间, 多目标优化算法

Abstract: In the assembly production line of complex aerospace products such as satellites and missiles, many assembly jobs are manually completed by a group of workers collaborating together, and each product requires the same assembly process for completion. Due to variations in the skill levels and assembly efficiency among different workers, as well as multiple optional workstations for each process, the scheduling problem in the complex product assembly workshop can be regarded as a combination of hybrid flow shop scheduling and worker allocation. To address this issue, a multi-objective hybrid flow shop scheduling model considering the allocation of workers with multiple skill levels is constructed in this paper. An improved optimization algorithm called optimizing mutation evolution algorithms is proposed. Firstly, the Nawaz-Enscore-Ham heuristic algorithm is utilized to generate an initial population and enhance the quality of solutions. Secondly, a mutated population is added to the non-dominated sorted population to increase population diversity. Finally, the proposed algorithm is compared with six other multi-objective evolutionary algorithms(MOEAs) based on a case study of a complex aerospace product assembly workshop. The results demonstrate that the proposed algorithm outperforms the other six MOEAs algorithms in terms of approaching the quality of the optimal solution and algorithm stability.

Key words: hybrid flow-shop scheduling, worker assignment, complex product, assembly workshop, multi-objective optimization algorithm

中图分类号:

TH165

王培旭, 裴凤雀, 刘检华, 郭昊鑫, 庄存波. 考虑多技能水平工人分配的复杂产品装配调度问题[J]. 机械工程学报, 2025, 61(4): 389-402.

WANG Peixu, PEI Fengque, LIU Jianhua, GUO Haoxin, ZHUANG Cunbo. Complex Product Assembly Scheduling Problem Considering Allocation of Workers with Multiple Skilled Level[J]. Journal of Mechanical Engineering, 2025, 61(4): 389-402.

参考文献

[1] 李伯虎，柴旭东. 复杂产品虚拟样机工程[J]. 计算机集成制造系统，2002，8(9):678-683. LI Bohu，CHAI Xudong. Virtual prototype engineering for complex products[J]. Computer Integrated Manufacturing Systems，2002，8(9):678-683.
[2] FANG Pengcheng，YANG Jianjun，LIAO Qingmiao，et al. Flexible worker allocation in aircraft final assembly line using multiobjective evolutionary algorithms[J]. IEEE Transactions on Industrial Informatics，2021，17(11):7468-7478.
[3] 余斌煌. 柔性流水车间调度问题综述[J]. 现代制造工程，2022，504(9):154-162. YU Binhuang. A review of flexible flow shop scheduling problems[J]. Modern Manufacturing Engineering，2022，504(9):154-162.
[4] XIN Bo，LI Yuan，YU Jianfeng，et al. An adaptive bpso algorithm for multi-skilled workers assignment problem in aircraft assembly lines[J]. Assembly Automation，2015，35(4):317-328.
[5] LENSTRA J K，RINNOOY KAN A H G，BRUCKER P. Complexity of machine scheduling problems[J]. Annals of Discrete Mathematics，1977，1:343-362.
[6] JOHNSON S M. Optimal two-stage and three-stage production schedules with setup times included[J]. Naval Research Logistics，1954，1(1):61-68.
[7] SALVADOR，MICHAEL S. A solution to a special class of flow shop scheduling problems[J]. Symposinm on the Theory of Soheduling and Its Applications 1973，86:83-91.
[8] ZHENG Qianqian，ZHANG Yu，TIAN Hongwei，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，2023，8:260747020.
[9] HAN Dayong，TANG Qiuhua，ZHANG Zikai，et al. An improved migrating birds optimization algorithm for a hybrid flow shop scheduling within steel plants[J]. Mathematics，2020，8(10):1661-1689．
[10] 张源，陶翼飞，王加冕. 改进差分进化算法求解混合流水车间调度问题[J]. 中国机械工程，2021，32(6): 714-720. ZHANG Yuan，TAO Yifei，WANG Jiamian. An improved DE algorithm for solving hybrid flow-shop scheduling problems[J]．China Mechanical Engineering，2021，32(6):714-720．
[11] SHI W G，SONG C L．Improved grey wolf optimization to solve the hybrid flow shop scheduling problem[J]. Computer Integrated Manufacturing Systems，2021(9):1-16．
[12] MENG Leilei，ZHANG Chaoyang，SHAO Xinyu，et al. Mathematical modelling and optimisation of energy-conscious hybrid flow shop scheduling problem with unrelated parallel machines[J]. International Journal of Production Research，2018，57:1119-1145.
[13] AZADEH A，GOODARZI A H，KOLAEE M H，et al. An efficient simulation-neural network-genetic algorithm for flexible flow shops with sequence-dependent setup times，job deterioration and learning effects[J]. Neural Computing and Applications，2019，31(9):5327-5341．
[14] CHENG Qiang，LIU Chenfei，CHU Hongyan，et al. A new multi-objective hybrid flow shop scheduling method to fully utilize the residual forging heat[J]. IEEE Access，2020，8:151180-151194．
[15] ZHOU Rui，LEI Deming，ZHOU Xinmin. Multi-objective energy-efficient interval scheduling in hybrid flow shop using imperialist competitive algorithm[J]. IEEE Access，2019，7:85029-85041.
[16] SONG Cunli. A hybrid multi-objective teaching-learning based optimization for scheduling problem of hybrid flow shop with unrelated parallel machine[J]. IEEE Access，2021，9:56822-56835.
[17] GONG Guiliang，CHIONG R，DENG Qianwang，et al. Energy-efficient flexible flow shop scheduling with worker flexibility[J]. Expert Systems with Applications，2020，141:112902-112919.
[18] 周炳海，刘文龙. 考虑能耗和准时的混合流水线多目标调度[J]. 上海交通大学学报，2019，53(7):773-779. ZHOU Binghai，LIU Wenlong. Multi-objective hybrid flow-shop scheduling problem considering energy consumption and on time delivery[J]. Journal of Shanghai Jiaotong University，2019，53(7):773-779.
[19] 黎展滔. 具有前成组约束的两阶段柔性流水车间的启发式算法[J]. 机械工程学报，2012，(22):189-198. LI Zhantao. A heuristic algorithm for two-phase flexible flow shop with preformed group constraints[J]. Journal of Mechanical Engineering，2012，(22):189-198.
[20] 顾涛，李苏建，林莹璐，等. 周期式退火炉作批处理机的可重入批离散机流水车间调度[J]. 机械工程学报，2020，56(2):220-232. GU Tao，LI Sujian，LIN Yinglu，et al. Re-entrant batch discrete machine flow shop scheduling for periodic annealing furnaces as batch processors[J]. Journal of Mechanical Engineering，2020，56(2):220-232.
[21] 田志强，姜兴宇，杨国哲，等. 一种面向航天复杂构件的柔性作业车间能耗优化调度问题研究[J]. 机械工程学报，2023，59(8):273-287. TIAN Zhiqiang，JIANG Xingyu，YANG Guozhe，et al. Energy efficient scheduling of flexible job shop with aerospace complex components[J]. Journal of Mechanical Engineering，2023，59(8):273-287.
[22] LIU Rongfan，LIU Ming，CHU Feng，et al. Eco-friendly multi-skilled worker assignment and assembly line balancing problem[J]. Computers & Industrial Engineering，2021，151:106944-106956.
[23] 肖世昌，吴自高，孙树栋，等. 双资源约束的鲁棒Job Shop调度问题研究[J]. 机械工程学报，2021，57(4):227-239. XIAO Shichang，WU Zigao，SUN Shudong，et al. Research on the dual-resource constrained robust job shop scheduling problems[J]. Journal of Mechanical Engineering，2021，57(4):227-239.
[24] FOROUTAN R A，REZAEIAN J，SHAFIPOUR M. Bi-objective unrelated parallel machines scheduling problem with worker allocation and sequence dependent setup times considering machine eligibility and precedence constraints[J]. Journal of Industrial and Management Optimization，2023，19(1):402-436.
[25] KHORRAM M，EGHTESADIFARD M，NIROOMAND S. Hybrid meta-heuristic algorithms for U-shaped assembly line balancing problem with equipment and worker allocations[J]. Soft Computing，2022，26(5):2241-2258.
[26] 李颖俐，李新宇，高亮. 混合流水车间调度问题研究综述[J]. 中国机械工程，2020，31(23):2798-2813，2828. LI Yingli，LI Xinyu，GAO Liang. A review of research on hybrid flow shop scheduling problems[J]. China Mechanical Engineering，2020，31(23):2798-2813，2828.
[27] NEUFELD J S，SCHULZ S，BUSCHER U，et al. A systematic review of multi-objective hybrid flow shop scheduling[J]. European Journal of Operational Research，2023，309(1):1-23.
[28] ALI H，SEYED M H H. A bi-objective flexible flow shop scheduling problem with machine-dependent processing stages:Trade-off between production costs and energy consumption[J]. Applied Mathematics and Computation，2020，386:125533-125545.
[29] CHAMNANLOR C，SETHANAN K，GEN M. et al. Embedding ant system in genetic algorithm for re-entrant hybrid flow shop scheduling problems with time window constraints[J]. Journal of Intelligent Manufacturing，2017，28(8):1915-1931.
[30] MOUSAVI S M，MAHDAVI I，REZACIAN J. et al. An efficient bi-objective algorithm to solve re-entrant hybrid flow shop scheduling with learning effect and setup times[J]. International Journal of Operational Research，2018，18:123-158.
[31] GUAN Yuxiang，CHEN Yuning，GAN Zhongxue. et al. Hybrid flow-shop scheduling in collaborative manufacturing with a multi-crossover-operator genetic algorithm[J]. Journal of Industrial Information Integration，2023，36:100514.
[32] TANG Hongtao，ZHOU Jiahao，SHAO Yiping，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:7982.
[33] XIE Jin，LI Xinyu，GAO Liang，et al. A hybrid genetic tabu search algorithm for distributed flexible job shop scheduling problems[J]. Journal of Manufacturing Systems，2023，71:82-94.
[34] CUI Hanghao，LI Xinyu，GAO Liang. An improved multi-population genetic algorithm with a greedy job insertion inter-factory neighborhood structure for distributed heterogeneous hybrid flow shop scheduling problem[J]. Expert Systems with Applications，2023，222:119805.
[35] DU Wei，TANG Yang，LEUNG S Y S，et al. Robust order scheduling in the discrete manufacturing industry:A multi objective optimization approach[J]. IEEE Transactions on Industrial Informatics，2017，14(1):253-264.