吉林大学学报(工学版) ›› 2018, Vol. 48 ›› Issue (2): 578-587.doi: 10.13229/j.cnki.jdxbgxb20160985

• • 上一篇    下一篇

存在多工序同时结束的多车间逆序综合调度算法

谢志强1, 郭禾1, 苏文秀1, 辛宇1, 杨静2   

  1. 1.哈尔滨理工大学 计算机科学与技术学院,哈尔滨 150080;
    2.哈尔滨工程大学 计算机科学与技术学院,哈尔滨 150001
  • 收稿日期:2016-09-01 出版日期:2018-03-01 发布日期:2018-03-01
  • 作者简介:谢志强(1962-),男,教授,博士生导师. 研究方向:企业智能计算与调度优化.E-mail:xiezhiqiang@hrbust.edu.cn
  • 基金资助:
    国家自然科学基金项目(61370086,61370083,61772160,61602133,61672179); 高等学校博士学科点专项科研基金项目(20122304110012); 黑龙江省教育厅科技项目(12531105); 黑龙江省博士后科研启动项目(LBH-Q13092); 中国博士后科学基金项目(2016M591541); 黑龙江省博士后项目(LBH-Z15096); 全国高等学校计算机教育研究会(研究生创新)项目(ER2014018)

Reversal sequence integrated scheduling algorithm of multiple workshop with multi-procedures ended together

XIE Zhi-qiang1, GUO He1, SU Wen-xiu1, XIN Yu1, YANG Jing2   

  1. 1. College of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080,China;
    2. College of Computer Science and Technology, Harbin Engineering University, Harbin 150001,China
  • Received:2016-09-01 Online:2018-03-01 Published:2018-03-01

RICH HTML

0   

PDF (PC)

377

摘要： 针对存在多工序同时结束的单件复杂产品的多车间制造问题,提出了存在多工序同时结束的多车间逆序综合调度算法。首先,为解决正序调度需迁移虚拟工序导致的设备资源空闲和操作复杂的问题,设计了逆序分批次调度策略;然后,为减少工序迁移和车间负载尽量均衡,设计了逆序车间确定策略确定所有工序的加工车间;最后,为满足多工序同时结束的特殊约束,设计了逆序同时开始策略确定每组虚拟工序组的逆序开始加工时间。实例验证表明,所提出算法满足特殊约束,完工时间较短且工序迁移次数少。

关键词: 计算机应用, 单件复杂产品, 多车间, 逆序分批次调度策略, 逆序车间确定策略, 逆序同时开始策略

Abstract: To solve the problem in multiple workshop manufacturing that there are single complex products with multi-procedures ended at the same time, a reversal sequence integrated scheduling algorithm is proposed. First, a reverse batch scheduling strategy is designed to solve the problem that migrate virtual processes for positive sequence scheduling can lead to equipment resource idle operating complex. Then, in order to reduce the process migration and keep the balance of load among the workshops, the workshop identified strategy is proposed to assign all the processes to the workshops. Finally, in order to satisfy the special constraints of multi-procedures ended at the same time, a strategy of reversal sequence starting together is designed to determine the reverse starting processing time of each virtual procedure group. A case study verifies that the proposed algorithm meets the special constraints, and the completion time is shortened with less process migrations.

Key words: computer application, single complex products, multiple workshop, reverse batch scheduling strategy, reverse workshop identified strategy, reversal sequence start together strategy

中图分类号: 

  • TP278
[1] 李京生,王爱民,唐承统,等. 基于动态资源能力服务的分布式协同调度技术[J]. 计算机集成制造系统,2012,18(7): 1563-1574.
Li Jing-sheng, Wang Ai-min, Tang Cheng-tong, et al. Distributed coordination scheduling technology based on dynamic manufacturing ability service[J]. Computer Integrated Manufacturing Systems, 2012, 18(7): 1563-1574.
[2] 周鑫,马跃,胡毅. 求解车间作业调度问题的混合遗传模拟退火算法[J]. 小型微型计算机系统, 2015, 36(2): 370-374.
Zhou Xin, Ma Yue, Hu Yi. Mixed genetic algorithm and simulated annealing algorithm for solving job shop scheduling problem[J]. Journal of Chinese Computer Systems, 2015, 36(2): 370-374.
[3] 叶寒锋,李占山,陈超. 基于具有自适应与自学习能力的粒子群优化算法的车间调度算法[J].吉林大学学报:理学版,2014,52(1): 93-97.
Ye Han-feng, Li Zhan-shan, Chen Chao. Adaptive and self-learning pso-based algorithm for job shop scheduling problem[J]. Journal of Jilin University(Science Edition), 2014,52(1): 93-97.
[4] 赵诗奎,方水良. 基于工序编码和邻域搜索策略的遗传算法优化作业车间调度[J]. 机械工程学报,2013,49(16): 160-169.
Zhao Shi-kui,Fang Shui-liang. Operation-based encoding and neighborhood search genetic algorithm for job shop scheduling optimization[J]. Journal of Mechanical Engineering,2013,49(16): 160-169.
[5] 谢志强,杨静,周勇,等. 基于工序集的动态关键路径多产品制造调度算法[J]. 计算机学报,2011,34(2): 406-412.
Xie Zhi-qiang, Yang Jing, Zhou Yong, et al. Dynamic critical paths multi-product manufacturing scheduling algorithm based on operation set[J]. Chinese Journal of Computers, 2011, 34(2): 406-412.
[6] 曾强,杨育,王小磊,等.基于多规则设备分配及工序排序的FJSP多目标集成优化方[J].计算机集成制造系统,2011,17(5): 980-989.
Zeng Qiang, Yang Yu, Wang Xiao-lei, et al. Integrated multi-objective optimization method for FJSP based on multiple rule machine assignment and job sequencing[J]. Computer Integrated Manufacturing Systems, 2011,17(5): 980-989.
[7] 谢志强,桂忠艳,杨静. 基于设备驱动和实质路径的动态并行综合柔性调度算法[J]. 机械工程学报,2014,50(18): 204-211.
Xie Zhi-qiang, Gui Zhong-yan, Yang Jing. Dynamic parallel integrated flexible scheduling algorithm based on device driver and essential path[J].Journal of Mechanical Engineering, 2014, 50(18): 204-211.
[8] 谢志强,周含笑,于洁,等. 基于设备驱动的综合柔性调度冲突调解算法[J]. 北京理工大学学报,2014,34(11): 1151-1156.
Xie Zhi-qiang, Zhou Han-xiao, Yu Jie, et al. Conflict mediation algorithm of the integrated flexible scheduling based on the device driver[J]. Transactions of Beijing Institute of Technology, 2014, 34(11): 1151-1156.
[9] Palmieri F,Buonanno L, Venticinque S, et al. A distributed scheduling framework based on selfish autonomous agents for federated cloud environments[J]. Future Generation Computer Systems, 2013, 29(6): 1461-1472.
[10] Oike S, Tanaka T, Zhu J, et al. Robust production scheduling using autonomous distributed systems[J]. Key Engineering Materials, 2012, 516:166-169.
[11] Valilai O F, Houshmand M, et al. 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.
[12] 陶辛阳,夏唐斌,奚立峰. 基于健康指数的预防性维护与多目标生产调度联合优化建模[J]. 上海交通大学学报,2014,48(8): 1170-1174.
Tao Xin-yang, Xia Tang-bin, Xi Li-feng. Health-index-based joint optimization of preventive maintenance and multi-attribute production scheduling[J]. Journal of Shanghai Jiaotong University, 2014, 48(8): 1170-1174.
[13] Dalfard V M, Mohammadi G. Two meta-heuristic algorithms for solving multi-objective flexible job-shop scheduling with parallel machine and maintenance constraints [J]. Computers & Mathematics with Applications, 2012, 64(6): 2111-2117.
[14] Marichelvam M K, Prabaharan T, Yang X S. A discrete firefly algorithm for the multi-objective hybrid flowshop scheduling problems[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(2): 301-305.
[15] 谢志强,周含笑,桂忠艳,等. 基于拟关键路径的二车间综合调度算法[J]. 计算机科学,2013,40(4): 193-198.
Xie Zhi-qiang, Zhou Han-xiao, Gui Zhong-yan, et al. Integrated scheduling algorithm of two workshops based on ACPM[J]. Computer Science,2013, 40(4): 193-198.
[16] 谢志强,郑付萍,朱天浩. 两车间可调度工序均衡处理的综合调度算法[J]. 计算机工程,2014,40(1): 295-304.
Xie Zhi-qiang, Zheng Fu-ping, Zhu Tian-hao. Integrated scheduling algorithm with equalization processing of schedulable processes in two workshops[J]. Computer Engineering, 2014, 40(1): 295-304.
[17] 谢志强,于洁,陈德运,等. 基于邻域渲染的二车间综合调度算法[J]. 机械工程学报,2016,52(1): 149-159.
Xie Zhi-qiang, Yu Jie, Chen De-yun, 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.
[18] 朱天浩,谢志强,郑付萍. 存在多工序同时结束的综合调度算法[J]. 计算机应用研究, 2013, 30(10): 2907-2911,2919.
Zhu Tian-hao, Xie Zhi-qiang, Zheng Fu-ping. Integrated scheduling algorithm of multi-procedures ended together[J]. Application Research of Computers, 2013, 30(10): 2907-2911,2919.
[1] 刘富,宗宇轩,康冰,张益萌,林彩霞,赵宏伟. 基于优化纹理特征的手背静脉识别系统[J]. 吉林大学学报(工学版), 2018, 48(6): 1844-1850.
[2] 王利民,刘洋,孙铭会,李美慧. 基于Markov blanket的无约束型K阶贝叶斯集成分类模型[J]. 吉林大学学报(工学版), 2018, 48(6): 1851-1858.
[3] 金顺福,王宝帅,郝闪闪,贾晓光,霍占强. 基于备用虚拟机同步休眠的云数据中心节能策略及性能[J]. 吉林大学学报(工学版), 2018, 48(6): 1859-1866.
[4] 赵东,孙明玉,朱金龙,于繁华,刘光洁,陈慧灵. 结合粒子群和单纯形的改进飞蛾优化算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1867-1872.
[5] 刘恩泽,吴文福. 基于机器视觉的农作物表面多特征决策融合病变判断算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1873-1878.
[6] 欧阳丹彤, 范琪. 子句级别语境感知的开放信息抽取方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1563-1570.
[7] 刘富, 兰旭腾, 侯涛, 康冰, 刘云, 林彩霞. 基于优化k-mer频率的宏基因组聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1593-1599.
[8] 桂春, 黄旺星. 基于改进的标签传播算法的网络聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1600-1605.
[9] 刘元宁, 刘帅, 朱晓冬, 陈一浩, 郑少阁, 沈椿壮. 基于高斯拉普拉斯算子与自适应优化伽柏滤波的虹膜识别[J]. 吉林大学学报(工学版), 2018, 48(5): 1606-1613.
[10] 车翔玖, 王利, 郭晓新. 基于多尺度特征融合的边界检测算法[J]. 吉林大学学报(工学版), 2018, 48(5): 1621-1628.
[11] 赵宏伟, 刘宇琦, 董立岩, 王玉, 刘陪. 智能交通混合动态路径优化算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1214-1223.
[12] 黄辉, 冯西安, 魏燕, 许驰, 陈慧灵. 基于增强核极限学习机的专业选择智能系统[J]. 吉林大学学报(工学版), 2018, 48(4): 1224-1230.
[13] 傅文博, 张杰, 陈永乐. 物联网环境下抵抗路由欺骗攻击的网络拓扑发现算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1231-1236.
[14] 曹洁, 苏哲, 李晓旭. 基于Corr-LDA模型的图像标注方法[J]. 吉林大学学报(工学版), 2018, 48(4): 1237-1243.
[15] 侯永宏, 王利伟, 邢家明. 基于HTTP的动态自适应流媒体传输算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1244-1253.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 焦玉玲, 徐良成, 王占中, 张鹏. 基于有向网络的双U型装配线平衡实验与分析[J]. 吉林大学学报(工学版), 2018, 48(2): 454 -459 .
[2] 刘雪娟, 袁家斌, 许娟, 段博佳. 量子k-means算法[J]. 吉林大学学报(工学版), 2018, 48(2): 539 -544 .
版权所有 © 《吉林大学学报(工学版)》编辑部
地址：长春市人民大街5988号　电话：+86-431-85095297　传真：+86-431-85094074　E-mail: xbgxb@jlu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发