随机型双边混流装配线平衡问题的两阶段求解方法研究

摘要/Abstract

摘要：

为降低求解随机型双边混流装配线平衡问题的复杂性，提出了一种遗传算法与仿真分析相结合的两阶段求解方法。首先建立忽略装配线同一工作站组的两工作站之间作业先后顺序约束的随机型双边混流装配线平衡问题的简化数学模型，采用一种基于序列组合编码方式的遗传算法对简化模型进行求解，获取备选解；在此基础上，建立考虑所有约束条件的仿真模型，通过系统仿真分析与评价，从备选解中获得该问题的最优解（或次优解）。算例研究表明，所提出的两阶段求解方法，在获得满意解的同时，可以大幅度降低问题求解的复杂性。

关键词: 双边装配线平衡, 随机, 混流, 遗传算法, 仿真

Abstract:

To reduce the complexity of solving the stochastic two-sided mixed model assembly line balancing problem, a two-stage procedure of combining a genetic algorithm with simulation analysis is proposed. Firstly, a simplified mathematical programming model is formulated ignoring the constraint of precedence relation between the tasks assigned to the same mated-station, and a set of solutions is obtained by using a genetic algorithm based on a sequence combined encoding. Based on the set of solutions, a simulation model that takes all the constraints of the problem into account is developed. The optimal solution (or suboptimal solution) of the problem is obtained through simulation analysis and evaluation. The analysis of an illustrative example shows that the complexity of solving the problem can be greatly reduced and a satisfactory solution can be obtained with the proposed method.

Key words: two-sided assembly line balancing, stochastic, mixed-model, genetic algorithms, simulation

段移庭，苏平，郑晨鸣. 随机型双边混流装配线平衡问题的两阶段求解方法研究[J]. 工业工程.

DUAN Yiting, SU Ping, ZHENG Chenming. A Two-stage Method for Solving the Stochastic Two-sided Mixed-model Assembly Line Balancing Problem[J]. Industrial Engineering Journal .

参考文献

［1 ]SALVESON M. The assembly line balancing Problem［J］. Journal of Industrial Engineering, 1955, 6(3):18-25.
［2］陈心德，吴忠. 生产运营管理［M］. 北京：清华大学出版社，2005.
［3］ARMIN S, CHRISTIAN B. State-of-the-art exact and heuristic solution procedures for simple assembly line balancing［J］. European Journal of Operational Research, 2006, 168(6):666-693.
［4］BARTHOLDI J. Balancing twosided assembly lines: a case study［J］. International Journal of Production Research, 1993, 31(10):2447-2461.
［5］KIM Y. Two-sided assembly line balancing: a genetic algorithm approach［J］.Production Planning & Control, 2000, 11(1):44-45.
［6］LEE T O. Two-sided assembly line balancing to maximize work relatedness and slackness［J］. Computers & Industrial Engineering, 2001, 40(3):273-292.
［7］吴尔飞, 金烨,续爱民,等. 基于改进遗传算法的双边装配线平衡［J］.计算机集成制造系统,2007, 13(2):268-274.
WU Erfei, JING Ye, XU Aimin, et al. Two-sided assembly line balancing based on modified genetic algorithm［J］. Computer Integrated Manufacturing Systems, 2007, 13(2):268-274.
［8］ZCAN U.Multiple-criteria decision-making in two-sided assembly line balancing: a goal programming and a fuzzy goal programming models［J］. Computers & Operations Research, 2009, 36(6): 1955-1965.
［9］陈建行, 张其松. 蚁群算法在装配线平衡问题中的应用［J］. 计算机时代, 2008(12):20-22.
CHEN Jianhang, ZHANG Qisong. Ant colony algorithm in the application of the assembly line balancing problem［J］. Computer Era, 2008(12):20-22.
［10］杨涛, 鲁建厦, 孔令革. 具有并发操作的双边装配线平衡问题研究［J］. 浙江工业大学学报, 2011, 39(4): 440444.
YANG Tao, LU Jiansha, KONG Lingge. Study on balancing problem of two sided assembly line with concurrent operation［J］. Journal of Zhe Jiang University of Technology, 2011, 39(4): 440-444.
［11］宋林, 张则强, 程文明,等.随机型双边装配线平衡问题的一种启发式算法［J］. 工业工程, 2011, 14(4):129-134.
SONG Lin，ZHANG Zeqiang, CHEN Wenming, et al. Heuristic for twosided stochastic assembly line balancing［J］. Industrial Engineering Journal, 2011, 14(4):129-134.
［12］于兆勤. 混合型装配线平衡问题的不确定性仿真研究［J］. 中国机械工程, 2008, 19(11): 1297-1302.YU Zhaoqin. Simulation of uncertainty for mixedmodel assembly line balancing problem［J］.China Mechanical Engineering, 2008, 19(11): 1297-1302.
［13］张则强, 余庆良, 胡俊逸,等. 随机混流装配线平衡问题的一种混合粒子群算法［J］. 机械设计与研究, 2013, 29(2): 60-63.
ZHANG Zeqiang, YU Qingliang, HU Junyi, et al. Hybrid particle swarm optimization algorithm for balancing problem of stochastic mixed-model assembly line［J］.Machine Design and Research, 2013, 29(2): 60-63.
［14］黄卫平, 张健, 周支立. 随机型混合模式装配线平衡问题的集束搜索算法［J］. 运筹与管理, 2010, 19(6): 20-26.HUANG Weiping, ZHANG Jian, ZHOU Zhili. A beam search approach to stochastic mixedmodel assembly line balancing problem［J］. Operations Research and Management Science, 2010, 19(6): 20-26.
［15］吴尔飞. 双边装配线平衡技术的研究［D］. 上海：2009, 上海交通大学.WU Erfei. Research on balancing twosided assembly line［D］. shanghai: Shanghai Jiao Tong University,2009.
［16］施於人. eMPlant仿真技术教程［M］. 北京：科学出版社, 2009.
［17］肖田元，范文慧. 系统仿真导论［M］. 北京：清华大学出版社, 2010.

[1]	李广振, 徐志刚, 刘松凯, 任朝晖. 装配线仿真流程及其案例研究[J]. 工业工程, 2021, 24(5): 152-158.
[2]	张正敏, 管在林, 岳磊. 基于Lévy Flight的混合GA在柔性作业车间调度问题中的性能分析[J]. 工业工程, 2021, 24(4): 83-92.
[3]	廖志华, 刘建军, 陈庆新, 毛宁. 负荷型对偶单元授权卡片交叠循环系统性能仿真[J]. 工业工程, 2021, 24(4): 100-111.
[4]	王晓军, 王博, 晋民杰, 杨春霞, 白新利. 改进多种群遗传算法的AutoStore系统多AGV调度优化[J]. 工业工程, 2021, 24(4): 112-118,167.
[5]	樊博, 马筱栎, 雷小诗, 马新露. 基于支持向量机的高速公路事故实时风险预测[J]. 工业工程, 2021, 24(4): 143-149.
[6]	李思瀚, 莫超雄, 刘建军, 陈庆新, 毛宁. 物料齐套时间不确定的多地总装作业前摄性调度[J]. 工业工程, 2021, 24(3): 104-114.
[7]	彭辉, 赵宁, 孙阳君. 面向货到人拣货机器人系统的数字孪生系统[J]. 工业工程, 2021, 24(3): 121-129.
[8]	王莹莹, 吴立云. 基于改进NSGA-II的多项目多技能人力资源调度研究[J]. 工业工程, 2021, 24(3): 130-138.
[9]	刘珈琪, 刘继才, 雷晓莹. PPP项目政府激励与社会资本努力的演化博弈与仿真[J]. 工业工程, 2021, 24(2): 77-84.
[10]	曾创锋, 刘建军, 陈庆新, 毛宁. 求解一类无关并行机调度的遗传迭代贪心算法[J]. 工业工程, 2021, 24(2): 110-118.
[11]	黄露, 纪延光. 考虑顾客延误损失的配送中心选址双层规划问题研究[J]. 工业工程, 2021, 24(2): 141-147.
[12]	王冰怡, 张锦. 考虑网点共享与变更的多级快递网点选址问题[J]. 工业工程, 2021, 24(2): 155-165.
[13]	甄烨, 王文利. 竞争环境下新创企业的供应链管理模式选择——应急采购VS饥饿营销[J]. 工业工程, 2021, 24(1): 52-58.
[14]	马跃如, 文铮, 易丹. 考虑老年人满意度的多目标居家养老护理员路径优化[J]. 工业工程, 2021, 24(1): 74-81,103.
[15]	王玖河, 高辉, 刘欢. 基于遗传算法的共享助力车调度问题研究[J]. 工业工程, 2021, 24(1): 90-96.