博文
带有资源冲突的Seru在线并行调度算法
|
引用格式
江煜舟, 李冬妮, 靳洪博, 殷勇. 带有资源冲突的Seru在线并行调度算法. 自动化学报, 2022, 48(2): 444−459 DOI: 10.16383/j.aas.c190698 (Jiang Yu-Zhou, Li Dong-Ni, Jin Hong-Bo, Yin Yong. An online algorithm for parallel scheduling of serus with resource conflicts. Acta Automatica Sinica, 2022, 48(2): 444−459 DOI: 10.16383/j.aas.c190698) http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c190698?viewType=HTML 文章简介 关键词 赛如生产系统, 在线调度, 竞争比, 实例归约, 总加权完工时间 摘 要 随着大规模定制的市场需求日趋显著, 赛如生产系统(Seru production system, SPS)应运而生, 逐渐成为研究和应用领域的热点. 本文针对带有资源冲突的Seru在线并行调度问题进行研究, 即需要在有限的空间位置上安排随动态需求而构建的若干Seru, 以总加权完工时间最小为目标, 决策Seru的构建顺序及时间. 先基于平均延迟最短加权处理时间(Average delayed shortest weighted processing time, AD-SWPT)算法, 针对其竞争比不为常数的局限性, 引入调节参数, 得到竞争比为常数的无资源冲突的Seru在线并行调度算法. 接下来, 引入冲突处理机制, 得到有资源冲突的Seru在线并行调度算法, αAD-I (α-average delayed shortest weighted processing time-improved)算法, 特殊实例下可通过实例归约的方法证明其竞争比与无资源冲突的情况相同. 最后, 通过实验, 验证了在波动的市场环境下算法对于特殊实例与一般实例的优越性. 引 言 随着大规模定制发展的趋势, 传统的生产系统, 如流水线(Flow line)、丰田生产系统(Toyota production system, TPS)、作业车间(Job shop)、单元制造系统(Cellular manufacturing system, CMS)等, 难以适应对动态不确定市场的快速响应需求, 赛如生产系统(Seru production system, SPS)应运而生. Yin等的研究展示了传统生产系统转化为SPS的重要性, Liu等的研究也表明SPS具有传统生产系统难以企及的先进性和发展前景. 自二十世纪九十年代起, SPS已经逐渐被亚洲的众多电子企业采用, 如三星、佳能、LG、索尼、松下、富士通、NEC、富士康等. SeruSeru代指SPS下的最小生产单元, 脱胎自基于精益(Lean)思想的装配流水线, 一个SeruSeru通常是生产一种或多种产品的装配单元, 包含若干设备和工人. 一个SPS至少包含一个SeruSeru. SPS中的每一个SeruSeru都能够频繁地在短时间内被重构, 这给SPS带来了极大的灵活性. 可以快速频繁地建立、改变、拆除和转化, 以响应频繁波动的市场需求. SPS运作管理的基本原则为面向“组织”的准时生产原则(Just-in-time organisation system, JIT-OS), 是TPS传统的面向“物料”的准时生产原则(Just-in-time material system, JIT-MS)的延伸. JIT-MS指在合适的时间地点投入合适的物料, 强调的是物料. 而JIT-OS强调的是组织, 对应到SPS, 即在合适的时间地点构建合适的SeruSeru. 这让SPS可以通过调整生产组织结构快速获得相应的生产能力, 为重构的实施提供了有效的载体和途径. SPS的运作可以被划分为SeruSeru构建与SeruSeru调度两个部分, SeruSeru构建指如何依据订单任务对人员进行分配与组合, SeruSeru调度指如何在有限的空间下安排各个SeruSeru的构建顺序及时间, 目前相关研究大都侧重于SeruSeru构建. 如Liu等提出的解决工人分配问题的三段式启发模型、Yu等提出的以产品流通时间和总劳动时间为目标的一种非支配排序遗传算法、Yu等结合局部搜索算法提出的第二代非支配排序遗传算法、吴旭辉等联合SeruSeru构建与订单分配提出的一种协同进化算法、贾凌云等与田云娜等对跨单元调度问题的研究等. 目前对SeruSeru调度这一方面的研究相对较少, 难以充分体现SPS调整结构的动态性, 但要想充分发挥出SPS的灵活性, 快速响应“小批量, 多品种”市场的动态变化, 在提高SeruSeru构建效率之外, 还需要考虑结构上的变化, 即SeruSeru调度. 如何在有限的位置上安排SeruSeru的构建顺序及时间也是SPS运作管理基本原则JIT-OS的一项重要内容. 据此, 本文对SeruSeru在线并行调度问题展开了研究, 该问题具体是指, 将随时间动态构建的n个SeruSeru安排到有限的m个位置上, 以总加权完工时间最小为目标, 在线决策各SeruSeru的构建顺序及时间. 同时, 考虑到具体的生产环境, 为了增强算法的实用性, 本文还将对带有资源冲突的SeruSeru在线并行调度问题进行讨论. 三个算法的竞争比 作者简介 江煜舟 北京理工大学计算机学院博士研究生. 主要研究方向为赛如生产智能优化. E-mail: jiang_yuzhou@163.com 李冬妮 北京理工大学计算机学院教授. 主要研究方向为智能优化与仿真计算, 智慧工厂与数字孪生. 本文通信作者. E-mail: ldn@bit.edu.cn 靳洪博 北京理工大学计算机学院博士研究生. 主要研究方向为赛如生产智能优化. E-mail: hb@bit.edu.cn 殷 勇 同志社大学商学院教授. 主要研究方向为赛如生产与工业4.0. E-mail: yyin@mail.doshisha.ac.jp 相关文章
[1] 赵晓丽, 宫华, 车平. 批处理机上具有两类释放时间的工件集竞争调度问题[J]. 自动化学报, 2020, 46(1): 168-177. doi: 10.16383/j.aas.2018.c170536
http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2018.c170536?viewType=HTML
[2] 王永富, 马冰心, 柴天佑, 张晓宇. PEMFC空气供给系统的二型自适应模糊建模与过氧比控制[J]. 自动化学报, 2019, 45(5): 853-865. doi: 10.16383/j.aas.c180047
http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c180047?viewType=HTML
[3] 吴旭辉, 杜劭峰, 郝慧慧, 于洋, 殷勇, 李冬妮. 一种基于协同进化的流水线向Seru系统转化方法. 自动化学报, 2018, 44(6): 1015-1027
http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2018.c160642?viewType=HTML
[4] 田云娜, 李冬妮, 刘兆赫, 郑丹. 一种基于动态决策块的超启发式跨单元调度方法. 自动化学报, 2016, 42(4): 524-534
http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2016.c150402?viewType=HTML
[5] 俞胜平, 柴天佑. 开工时间延迟下的炼钢-连铸生产重调度方法[J]. 自动化学报, 2016, 42(3): 358-374. doi: 10.16383/j.aas.2016.c150197
http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2016.c150197?viewType=HTML
[6] 贾凌云, 李冬妮, 田云娜. 基于混合蛙跳和遗传规划的跨单元调度方法. 自动化学报, 2014, 40(5): 936-948
http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2015.c140455?viewType=HTML
[7] 王大志, 刘士新, 郭希旺. 求解总拖期时间最小化流水车间调度问题的多智能体进化算法[J]. 自动化学报, 2014, 40(3): 548-555. doi: 10.3724/SP.J.1004.2014.00548
http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2014.00548?viewType=HTML
[8] 汤步洲, 王晓龙, 王轩. 置信度加权在线序列标注算法[J]. 自动化学报, 2011, 37(2): 188-195. doi: 10.3724/SP.J.1004.2011.00188
http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2011.00188?viewType=HTML
[9] 刘亮, 段纳, 解学军. 具有奇整数比次方的随机高阶非线性系统的输出反馈镇定[J]. 自动化学报, 2010, 36(6): 858-864. doi: 10.3724/SP.J.1004.2010.00858
http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2010.00858?viewType=HTML
[10] 於春月, 王成恩, 曲蓉霞. 中厚板热轧生产调度优化方法[J]. 自动化学报, 2010, 36(2): 282-288. doi: 10.3724/SP.J.1004.2010.00282
http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2010.00282?viewType=HTML
[11] 赵君, 刘全利, 王伟. 冷轧生产调度模型及算法[J]. 自动化学报, 2008, 34(5): 565-573. doi: 10.3724/SP.J.1004.2008.00565
http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2008.00565?viewType=HTML
[12] 张居阳, 孙吉贵, 杨轻云. 半在线调度中约束求解算法研究[J]. 自动化学报, 2007, 33(7): 765-767. doi: 10.1360/aas-007-0765
http://www.aas.net.cn/cn/article/doi/10.1360/aas-007-0765?viewType=HTML
[13] 赵玉芳, 唐立新. 极小化最大完工时间的单机连续型批调度问题[J]. 自动化学报, 2006, 32(5): 730-737.
http://www.aas.net.cn/cn/article/id/13757?viewType=HTML
[14] 翟桥柱, 管晓宏, 郭燕, 孙岚, 范炜. 具有混合动态约束的生产系统优化调度新算法[J]. 自动化学报, 2004, 30(4): 539-546.
http://www.aas.net.cn/cn/article/id/16199?viewType=HTML
[15] 赵传立, 张庆灵, 唐恒永. 具有线性恶化加工时间的调度问题[J]. 自动化学报, 2003, 29(4): 531-535.
http://www.aas.net.cn/cn/article/id/13907?viewType=HTML
[16] 赵传立, 张庆灵, 唐恒永. 一类线性加工时间单机调度问题[J]. 自动化学报, 2003, 29(5): 703-708.
http://www.aas.net.cn/cn/article/id/13882?viewType=HTML
[17] 蔡圣义, 何勇. 工件从大到小到达的带处理器费用的半在线调度算法[J]. 自动化学报, 2003, 29(6): 917-921.
http://www.aas.net.cn/cn/article/id/16430?viewType=HTML
https://blog.sciencenet.cn/blog-3291369-1324627.html
上一篇：非线性预测控制终端约束集的优化
下一篇：机器人运动轨迹的模仿学习综述
