博文
串行生产线中机器维修工人的任务分配问题研究
|
引用本文
鄢超波, 张雷. 串行生产线中机器维修工人的任务分配问题研究. 自动化学报, 2021, 47(11): 2578-2584 doi: 10.16383/j.aas.c180781 Yan Chao-Bo, Zhang Lei. Formulation and solution methodology for repairman allocation problem in serial production lines. Acta Automatica Sinica, 2021, 47(11): 2578-2584 doi: 10.16383/j.aas.c180781 http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c180781?viewType=HTML 文章简介 关键词 生产系统, 机器维修, 任务分配, LPT算法, 回溯策略 摘 要 在串行生产线中, 机器会发生故障而且故障间隔时间随机, 因此需要维修工人及时维修, 使得故障的机器恢复加工能力, 否则就可能导致系统吞吐率降低. 如何在满足系统吞吐率的前提下, 使用尽可能少的维修工人来完成机器的维修任务, 本文称这样一个全新的问题为串行生产线中机器维修工人的任务分配问题. 针对该问题, 本文首先建立了问题的优化模型, 并将该优化问题转换为多个判定问题进行求解; 然后, 通过合理地定义机器的维修工作量, 使得判定问题可以类比为并行机调度问题; 最后, 采用了一种基于最长处理时间优先算法(Longest processing time, LPT)和回溯策略的启发式算法, 搜索最优的维修工人任务分配方式. 实验结果表明, 该方法能有效求解维修工人的任务分配问题. 引 言 对于制造业来说, 其产品主要来自于庞大的生产线系统, 生产线的效率(吞吐率)越高, 企业效益往往也就越好. 然而生产线中的机器会发生随机故障, 当生产线中某一台机器发生故障时, 如果该机器没有得到及时的维修, 就有可能使得系统吞吐率下降, 进而导致企业利润减少. 本文假设一台机器故障时, 只能由已分配的某一名维修工人进行维修, 显然如果为每台机器都配备一名维修工人, 那么所有的机器故障都会得到立即维修, 企业的损失也就最小. 然而, 这样会导致维修工人在大多数时间都处于空闲状态, 极大地增加了企业的用人成本. 如何在保证串行生产线系统吞吐率的情况下, 使用尽可能少的维修工人来完成机器的维修任务, 本文称这样一个问题为串行生产线中机器维修工人的任务分配问题. 在生产线领域, 已经存在有大量的资料, 文献中主要通过排队论、分解、仿真和近似等方法来对生产线进行研究. 当前生产线领域的研究方向主要是生产线的性能分析和优化, 例如生产线平衡问题和生产线中缓冲区大小分配问题等. 然而, 尽管在生产线这一领域已经有了很多研究工作, 但是根据文献调研, 目前还没有相关文献在研究串行生产线中机器维修工人的任务分配问题. 这也就是说, 本文所研究的问题是一个全新的问题. 对于这样一个新问题, 有三类问题与之具有一定相似性. 第一类问题是任务分配问题, 该问题要求定义每一个任务分配给任意一个人的"成本", 然而在本文所研究的问题中吞吐率是一个整体的性能指标, 难以定义每一个机器的维修任务分配给任意一个工人的"成本", 所以不能应用分配问题的算法来求解本文的问题.第二类问题是装箱问题, 该问题要求将一定数量的物品放入容量相同的一些箱子中, 使得所用的箱子数目最少, 然而由于无法定义维修工人的"容量" (单个工人可以负责维修的机器数量), 所以也不能直接应用装箱问题的算法来求解本文的问题. 第三类问题是并行机调度问题和文献[12]中提出的线边缓冲区分配问题(Line-side buffer assignment problem, LBAP), 其中并行机调度问题要求使用一定数量的机器完成一些相互独立的任务, 使得完成时间最短, 而LBAP问题则是要求在保证总装线吞吐率的条件下, 使用给定数量的司机完成物料传送任务. 由于第三类问题中的LBAP问题与本文所研究的新问题非常类似, 因此可以借鉴文献[12]中提出的带回溯的序贯分配算法(Sequential assignment with backtracking, SAB), 来求解本文所研究的问题. 该算法基于并行机调度问题中的最长处理时间优先(Longest processing time, LPT)算法和回溯策略, 是一种启发式算法. 本文的贡献在于: 1) 本文提出了一个全新的问题—串行生产线中机器维修工人的任务分配问题, 并对其进行了建模; 2)合理地定义了机器的维修工作量, 使得本文所研究的问题可以类比为并行机调度问题; 3)通过仿真实验, 验证了文献[12]中提出的SAB算法, 对本文所研究的问题同样适用, 该方法在保证系统吞吐率的前提下, 能够有效减少企业的用人成本. 本文的结构安排如下: 第1节介绍串行生产线, 建立问题模型和仿真模型; 第2节定义和量化机器以及工人的维修工作量, 并对维修工人数量的下界进行估计; 第3节描述带回溯的维修工人任务分配算法; 第4节进行仿真实验, 验证本文方法的有效性; 最后对本文的内容和贡献进行总结. 图 2 串行生产线中维修工人任务分配 作者简介 鄢超波 博士, 西安交通大学电信学部自动化学院教授. 主要研究方向为生产系统的建模、分析和优化, 以及信息物理融合系统理论及其在制造、物流和仓储系统中的应用. 本文通信作者. E-mail: chaoboyan@mail.xjtu.edu.cn 张 雷 西安交通大学系统工程研究所硕士研究生. 主要研究方向为生产系统性能分析和优化. E-mail: zhanglei6549@163.com 相关文章 [1] 李孙寸, 施心陵, 张松海, 董易, 高莲. 基于多元优化算法的三维装箱问题的研究. 自动化学报, 2018, 44(1): 106-115. doi: 10.16383/j.aas.2018.c160381 http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2018.c160381?viewType=HTML [2] 贾之阳, 陈京川, 戴亚平. 基于几何可靠性机器模型的装配系统实时性能分析. 自动化学报, 2020, 46(12): 2583-2592. doi: 10.16383/j.aas.c180180 http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c180180?viewType=HTML [3] 刘畅, 贾之阳. 有限小批量定制生产伯努利三机器装配系统实时性能分析. 自动化学报, 2019, 45(3): 471-479. doi: 10.16383/j.aas.c170685 http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c170685?viewType=HTML [4] 王彩璐, 陶跃钢, 杨鹏, 刘作军, 周颖. 云控制系统并行任务分配优化算法与并联控制. 自动化学报, 2017, 43(11): 1973-1983. doi: 10.16383/j.aas.2017.c160504 http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2017.c160504?viewType=HTML [5] 贾丙西, 刘山, 张凯祥, 陈剑. 机器人视觉伺服研究进展:视觉系统与控制策略. 自动化学报, 2015, 41(5): 861-873. doi: 10.16383/j.aas.2015.c140724 http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2015.c140724?viewType=HTML [6] 高文科, 张志胜, 周一帆, 刘飏, 刘祺. 存在故障相关及不完备检测的主辅并联系统可靠性建模与维修策略. 自动化学报, 2015, 41(12): 2100-2114. doi: 10.16383/j.aas.2015.c140735 http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2015.c140735?viewType=HTML [7] 王小乐, 黄宏斌, 邓苏. 处理顺序约束的信息物理融合系统静态任务表调度算法. 自动化学报, 2012, 38(11): 1870-1879. doi: 10.3724/SP.J.1004.2012.01870 http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2012.01870?viewType=HTML [8] 杨海蓉, 方红, 张成, 韦穗. 基于回溯的迭代硬阈值算法. 自动化学报, 2011, 37(3): 276-282. doi: 10.3724/SP.J.1004.2011.00276 http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2011.00276?viewType=HTML [9] 杨超林, 沈厚才, 高春燕. 按单装配系统中组件生产和库存分配控制策略研究. 自动化学报, 2011, 37(2): 234-240. doi: 10.3724/SP.J.1004.2011.00234 http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2011.00234?viewType=HTML [10] 苏兆品, 蒋建国, 梁昌勇, 张国富. 一种基于P学习的分布式并行多任务分配算法. 自动化学报, 2011, 37(7): 865-872. doi: 10.3724/SP.J.1004.2011.00865 http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2011.00865?viewType=HTML [11] 刘军, 芮执元, 韦尧兵, 陈积明. 具有不确定需求的混杂系统的生产与维修控制. 自动化学报, 2007, 33(12): 1331-1336. doi: 10.1360/aas-007-1331 http://www.aas.net.cn/cn/article/doi/10.1360/aas-007-1331?viewType=HTML [12] 龙涛, 沈林成, 朱华勇, 牛轶峰. 面向协同任务的多UCAV分布式任务分配与协调技术. 自动化学报, 2007, 33(7): 731-737. doi: 10.1360/aas-007-0731 http://www.aas.net.cn/cn/article/doi/10.1360/aas-007-0731?viewType=HTML [13] 翟桥柱, 管晓宏, 郭燕, 孙岚, 范炜. 具有混合动态约束的生产系统优化调度新算法. 自动化学报, 2004, 30(4): 539-546. http://www.aas.net.cn/cn/article/id/16199?viewType=HTML [14] 范英俐, 谭民. 结合遗传算法和设禁搜索求解可重构制造系统的生产计划问题. 自动化学报, 2002, 28(3): 461-465. http://www.aas.net.cn/cn/article/id/15545?viewType=HTML [15] 范英俐, 谭民. 结合遗传算法和设禁搜索求解可重构制造系统的生产计划问题. 自动化学报, 2002, 28(3): 461-465. http://www.aas.net.cn/cn/article/id/16158?viewType=HTML [16] 刘民, 吴澄, 尹文君. 带特殊工艺约束的并行机器生产线调度问题的一种遗传算法. 自动化学报, 2001, 27(3): 381-386. http://www.aas.net.cn/cn/article/id/16137?viewType=HTML [17] 熊刚, 许晓鸣, 孙优贤. 润滑油生产溶剂回收系统的混合优化策略. 自动化学报, 1999, 25(1): 52-59. http://www.aas.net.cn/cn/article/id/16731?viewType=HTML [18] 李明树, 洪炳鎔. 一个基于规则的空间站GaAs自动生产线实时故障诊断维修系统. 自动化学报, 1993, 19(5): 615-620. http://www.aas.net.cn/cn/article/id/14193?viewType=HTML [19] 廖炯生. n中取相邻k系统可靠性及街灯照明系统维修策略. 自动化学报, 1992, 18(3): 343-347. http://www.aas.net.cn/cn/article/id/14474?viewType=HTML [20] 伍乃骐, 庄颂新, 薛劲松. 考虑机器故障和有限缓冲器的级联生产线系统的建模和分析. 自动化学报, 1991, 17(4): 481-486. http://www.aas.net.cn/cn/article/id/14570?viewType=HTML [21] 吴芳美. 在机器人的控制中自动绕过机械干涉区的策略和算法. 自动化学报, 1988, 14(3): 178-183. http://www.aas.net.cn/cn/article/id/14981?viewType=HTML 
https://blog.sciencenet.cn/blog-3291369-1341285.html
上一篇：基于改进YOLOv3算法的公路车道线检测方法
下一篇：参考点自适应调整下评价指标驱动的高维多目标进化算法
