高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

存在设备时间限制的两个企业协同的综合调度算法

谢志强 裴莉榕

谢志强, 裴莉榕. 存在设备时间限制的两个企业协同的综合调度算法[J]. 电子与信息学报, 2022, 44(5): 1653-1663. doi: 10.11999/JEIT211394
引用本文: 谢志强, 裴莉榕. 存在设备时间限制的两个企业协同的综合调度算法[J]. 电子与信息学报, 2022, 44(5): 1653-1663. doi: 10.11999/JEIT211394
XIE Zhiqiang, PEI Lirong. Integrated Scheduling Algorithm for Two Corporate Synergies with Equipment Time Constraints[J]. Journal of Electronics & Information Technology, 2022, 44(5): 1653-1663. doi: 10.11999/JEIT211394
Citation: XIE Zhiqiang, PEI Lirong. Integrated Scheduling Algorithm for Two Corporate Synergies with Equipment Time Constraints[J]. Journal of Electronics & Information Technology, 2022, 44(5): 1653-1663. doi: 10.11999/JEIT211394

存在设备时间限制的两个企业协同的综合调度算法

doi: 10.11999/JEIT211394
基金项目: 国家自然科学基金(61772160)
详细信息
    作者简介:

    谢志强:男,1962年出生,博士后,教授,博士生导师,主要研究方向为智能计算和调度系统

    裴莉榕:女,1994年出生,博士生,研究方向为智能计算和调度系统

    通讯作者:

    谢志强 xiezhiqiang@hrbust.edu.cn

  • 中图分类号: TP278

Integrated Scheduling Algorithm for Two Corporate Synergies with Equipment Time Constraints

Funds: The National Natural Science Foundation of China (61772160)
  • 摘要: 针对自有加工企业设备使用时间存在限制无法满足产品交货期的综合调度问题,该文提出存在设备时间限制的两个企业协同的综合调度算法。为了保证自有加工企业能够获得更多的收益,需要将加工任务尽可能多地分配给自有加工企业进行加工。因此,需要将加工任务进行有效分解,首先逆向遍历加工树,将自有加工企业设备使用时间上限作为阈值,设计加工任务分配策略对加工树进行拆分并生成自有加工企业加工的拆分加工树,其余部分为协同加工企业加工的协同加工树。然后设计协同选择策略,在考虑到运输问题并满足交货期的前提下,选取使自有加工企业收益最大的企业为协同加工企业。最后实例分析,该算法可以更好地解决加工企业设备使用时间存在限制并带有交货期和收益的企业车间协同综合调度问题。
  • 图  1  加工树例1

    图  2  标记加工树

    图  3  初始拆分树

    图  4  协同选择策略流程

    图  5  协同加工树调度甘特图

    图  6  增加设备后对比甘特图

    图  7  加工树实例

    图  8  标记加工树

    图  9  初始拆分树

    图  10  标记初始拆分树

    图  11  初始拆分树调度发生超时甘特图

    图  12  纯叶子节点插入后对比甘特图

    图  13  文献[17]调度甘特图

    图  14  协同加工树调度甘特图

    表  1  各参数含义

    RoRsFoFsFvFmToTsTvTmTQ
    含义自有加工
    企业收益
    协同加工
    企业收益
    自有加工
    企业成本
    协同加工
    企业成本
    企业间运
    输成本
    管理中
    心费用
    自有加工企业
    总加工时间
    协同加工企业
    总加工时间
    企业间总
    运输时间
    管理中心
    停留时间
    交货期
    下载: 导出CSV

    表  2  企业内部设备迁移信息 (h)

    D1D2D3$D'_2 $$D'_3 $D4
    D10.10.20.40.30.4
    D20.10.10.30.40.4
    D30.20.10.40.50.3
    $D'_2 $0.40.30.40.20.1
    $D'_3 $0.30.40.50.20.2
    D40.40.40.30.10.2
    下载: 导出CSV

    表  3  协同加工企业相关信息

    协同加工企业Ts
    TvTmFvFm
    P121.68.25.516.411.0
    P223.07.66.314.010.75
    P325.36.17.010.9812.6
    下载: 导出CSV
  • [1] 宫华, 许可, 孙文娟. 带尺寸约束的二机流水车间生产运输协调博弈调度问题[J]. 控制与决策, 2022, 5(5):1–9.

    GONG Hua, XU Ke, and SUN Wenjuan. Coordinated two-machine flow-shop and transportation scheduling under size constraint and game theory consideration[J]. Control and Decision, 2022, 5(5):1–9.
    [2] 吕海利, 朱家涛, 王正国, 等. 装配作业车间的JIT调度研究[J]. 机械工程学报, 2021, 57(5): 157–165. doi: 10.3901/JME.2021.05.157

    LÜ Haili, ZHU Jiatao, WANG Zhengguo, et al. Research of just-in-time scheduling for assembly job shop[J]. Journal of Mechanical Engineering, 2021, 57(5): 157–165. doi: 10.3901/JME.2021.05.157
    [3] 代乙君, 张志英, 王维泽. 运输能力有限的分段两阶段多车间调度问题[J]. 计算机工程与应用, 2016, 52(7): 222–228,235. doi: 10.3778/j.issn.1002-8331.1404-0201

    DAI Yijun, ZHANG Zhiying, and WANG Weize. Block two-stage and multi-workshop scheduling with transportation consideration[J]. Computer Engineering and Applications, 2016, 52(7): 222–228,235. doi: 10.3778/j.issn.1002-8331.1404-0201
    [4] 苑明海, 张理志, 周开俊, 等. 基于混合遗传算法的柔性车间调度问题研究[J]. 工业工程与管理, 2021, 26(6): 95–103. doi: 10.19495/j.cnki.1007-5429.2021.06.011

    YUAN Minghai, ZHANG Lizhi, ZHOU Kaijun, et al. Research on flexible shop scheduling based on improved hybrid genetic algorithm[J]. Industrial Engineering and Management, 2021, 26(6): 95–103. doi: 10.19495/j.cnki.1007-5429.2021.06.011
    [5] 胡瑞淇, 程辉, 张执南. 基于表达式树的顺序柔性车间调度问题求解[J/OL]. 计算机集成制造系统. http://kns.cnki.net/kcms/detail/11.5946.tp.20220317.1506.002.html, 2022.

    HU Ruiqi, CHENG Hui, and ZHANG Zhinan. Solving job shop scheduling problem with flexible process sequence based on expression tree model[J/OL]. Computer Integrated Manufacturing Systems, http://kns.cnki.net/kcms/detail/11.5946.tp.20220317.1506.002.html, 2022.
    [6] 刘晓冰, 焦璇, 黄明, 等. 用混合量子算法求解模糊柔性作业车间调度问题[J]. 工业工程与管理, 2015, 20(3): 8–13. doi: 10.19495/j.cnki.1007-5429.2015.03.002

    LIU Xiaobing, JIAO Xuan, HUANG Ming, et al. Solving the fuzzy flexible job shop scheduling problem with hybrid quantun algorithm[J]. Industrial Engineering and Management, 2015, 20(3): 8–13. doi: 10.19495/j.cnki.1007-5429.2015.03.002
    [7] 张立果, 黎向锋, 左敦稳, 等. 求解多目标柔性作业车间调度问题的两层遗传算法[J]. 计算机应用, 2020, 40(S1): 14–22. doi: 10.11772/j.issn.1001-9081.2019061073

    ZHANG Liguo, LI Xiangfeng, ZUO Dunwen, et al. Two-phase genetic algorithm for multi-objective flexible job-shop scheduling problem[J]. Journal of Computer Applications, 2020, 40(S1): 14–22. doi: 10.11772/j.issn.1001-9081.2019061073
    [8] 马千慧, 梁晓磊, 刘星雨, 等. 多AGV和机器集成的多目标柔性作业车间调度研究[J/OL]. 计算机工程与应用, http://kns.cnki.net/kcms/detail/11.2127.TP.20211026.1706.016.html, 2022.

    MA Qianhui, LIANG Xiaolei, LIU Xingyu, et al. Research on multi-objective flexible job shop scheduling with multiple AGVs and machines integration[J/OL]. Computer Engineering and Applications, http://kns.cnki.net/kcms/detail/11.2127.TP.20211026.1706.016.html, 2022.
    [9] 董海, 徐晓鹏, 谢谢. 多目标优化算法求解多柔性作业车间调度问题[J]. 计算机科学, 2020, 47(12): 239–244. doi: 10.11896/jsjkx.191100042

    DONG Hai, XU Xiaopeng, and XIE Xie. Solving multi-flexible job-shop scheduling by multi-objective algorithm[J]. Computer Science, 2020, 47(12): 239–244. doi: 10.11896/jsjkx.191100042
    [10] MATI Y and XIE Xiaolan. Multiresource shop scheduling with resource flexibility and blocking[J]. IEEE Transactions on Automation Science and Engineering, 2011, 8(1): 175–189. doi: 10.1109/TASE.2010.2052356
    [11] 王凌, 邓瑾, 王圣尧. 分布式车间调度优化算法研究综述[J]. 控制与决策, 2016, 31(1): 1–11. doi: 10.13195/j.kzyjc.2014.1949

    WANG Ling, DENG Jin, and WANG Shengyao. Survey on optimization algorithms for distributed shop scheduling[J]. Control and Decision, 2016, 31(1): 1–11. doi: 10.13195/j.kzyjc.2014.1949
    [12] ENJALBERT S, ARCHIMÈDE B, and CHARBONNAUD P. Distributed simulation of virtual workshops for the multi-site scheduling feasibility evaluation[J]. International Journal of Production Research, 2011, 49(22): 6663–6676. doi: 10.1080/00207543.2010.520911
    [13] VALILAI O F and HOUSHMAND M. A collaborative and integrated platform to support distributed manufacturing system using a service-oriented approach based on cloud computing paradigm[J]. Robotics and Computer-Integrated Manufacturing, 2013, 29(1): 110–127. doi: 10.1016/j.rcim.2012.07.009
    [14] XIA Yingchun, XIE Zhiqiang, XIN Yu, et al. A multi-shop integrated scheduling algorithm with fixed output constraint[J]. Journal of Intelligent & Fuzzy Systems, 2021, 41(3): 4609–4617. doi: 10.3233/JIFS-189721
    [15] 裴小兵, 孙志卫. 改进区块遗传算法解决分布式车间调度问题[J]. 智能系统学报, 2021, 16(2): 303–312. doi: 10.11992/tis.201906035

    PEI Xiaobing and SUN Zhiwei. Solving distributed-shop scheduling problems based on modified genetic algorithm[J]. CAAI Transactions on Intelligent Systems, 2021, 16(2): 303–312. doi: 10.11992/tis.201906035
    [16] 谢志强, 辛宇, 杨静. 基于设备空闲事件驱动的综合调度算法[J]. 机械工程学报, 2011, 47(11): 139–147. doi: 10.3901/JME.2011.11.139

    XIE Zhiqiang, XIN Yu, and YANG Jing. Integrated scheduling algorithm based on event-driven by machines' idle[J]. Journal of Mechanical Engineering, 2011, 47(11): 139–147. doi: 10.3901/JME.2011.11.139
    [17] 谢志强, 常宁宁, 杨静. 基于交货期紧迫度的综合调度算法[J]. 机械工程学报, 2011, 47(22): 181–190. doi: 10.3901/JME.2011.22.181

    XIE Zhiqiang, CHANG Ningning, and YANG Jing. Integrated scheduling algorithm based on delivery dates urgency degree[J]. Journal of Mechanical Engineering, 2011, 47(22): 181–190. doi: 10.3901/JME.2011.22.181
    [18] 谢志强, 周伟, 余泽睿. 动态调整设备维护开始时间的综合调度算法[J]. 机械工程学报, 2021, 57(4): 240–246. doi: 10.3901/JME.2021.04.240

    XIE Zhiqiang, ZHOU Wei, and YU Zerui. Integrated scheduling algorithm for dynamic adjustment of equipment maintenance start time[J]. Journal of Mechanical Engineering, 2021, 57(4): 240–246. doi: 10.3901/JME.2021.04.240
    [19] 谢志强, 于洁, 陈德运, 等. 基于邻域渲染的二车间综合调度算法[J]. 机械工程学报, 2016, 52(1): 149–159. doi: 10.3901/JME.2016.01.149

    XIE Zhiqiang, YU Jie, CHEN Deyun, et al. Integrated scheduling algorithm of two workshops based on the principle of the neighborhood rendering[J]. Journal of Mechanical Engineering, 2016, 52(1): 149–159. doi: 10.3901/JME.2016.01.149
    [20] 廖不凡, 雷琦, 吴文烈, 等. 基于混合教学优化算法的多车间协作综合调度[J]. 中国机械工程, 2020, 31(16): 1940–1949.

    LIAO Bufan, LEI Qi, WU Wenlie, et al. Hybrid teaching-learning-based optimization algorithms for integrated scheduling of multi-workshop collaborations[J]. China Mechanical Engineering, 2020, 31(16): 1940–1949.
  • 加载中
图(14) / 表(3)
计量
  • 文章访问数:  249
  • HTML全文浏览量:  129
  • PDF下载量:  26
  • 被引次数: 0
出版历程
  • 收稿日期:  2021-12-01
  • 修回日期:  2022-04-11
  • 录用日期:  2022-04-11
  • 网络出版日期:  2022-04-15
  • 刊出日期:  2022-05-25

目录

    /

    返回文章
    返回