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

Previous Articles     Next Articles

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

CLC Number: 

  • 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] LIU Fu,ZONG Yu-xuan,KANG Bing,ZHANG Yi-meng,LIN Cai-xia,ZHAO Hong-wei. Dorsal hand vein recognition system based on optimized texture features [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1844-1850.
[2] WANG Li-min,LIU Yang,SUN Ming-hui,LI Mei-hui. Ensemble of unrestricted K-dependence Bayesian classifiers based on Markov blanket [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1851-1858.
[3] JIN Shun-fu,WANG Bao-shuai,HAO Shan-shan,JIA Xiao-guang,HUO Zhan-qiang. Synchronous sleeping based energy saving strategy of reservation virtual machines in cloud data centers and its performance research [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1859-1866.
[4] ZHAO Dong,SUN Ming-yu,ZHU Jin-long,YU Fan-hua,LIU Guang-jie,CHEN Hui-ling. Improved moth-flame optimization method based on combination of particle swarm optimization and simplex method [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1867-1872.
[5] LIU En-ze,WU Wen-fu. Agricultural surface multiple feature decision fusion disease judgment algorithm based on machine vision [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1873-1878.
[6] OUYANG Dan-tong, FAN Qi. Clause-level context-aware open information extraction [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1563-1570.
[7] LIU Fu, LAN Xu-teng, HOU Tao, KANG Bing, LIU Yun, LIN Cai-xia. Metagenomic clustering method based on k-mer frequency optimization [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1593-1599.
[8] GUI Chun, HUANG Wang-xing. Network clustering method based on improved label propagation algorithm [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1600-1605.
[9] LIU Yuan-ning, LIU Shuai, ZHU Xiao-dong, CHEN Yi-hao, ZHENG Shao-ge, SHEN Chun-zhuang. LOG operator and adaptive optimization Gabor filtering for iris recognition [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1606-1613.
[10] CHE Xiang-jiu, WANG Li, GUO Xiao-xin. Improved boundary detection based on multi-scale cues fusion [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1621-1628.
[11] ZHAO Hong-wei, LIU Yu-qi, DONG Li-yan, WANG Yu, LIU Pei. Dynamic route optimization algorithm based on hybrid in ITS [J]. 吉林大学学报(工学版), 2018, 48(4): 1214-1223.
[12] HUANG Hui, FENG Xi-an, WEI Yan, XU Chi, CHEN Hui-ling. An intelligent system based on enhanced kernel extreme learning machine for choosing the second major [J]. 吉林大学学报(工学版), 2018, 48(4): 1224-1230.
[13] FU Wen-bo, ZHANG Jie, CHEN Yong-le. Network topology discovery algorithm against routing spoofing attack in Internet of things [J]. 吉林大学学报(工学版), 2018, 48(4): 1231-1236.
[14] CAO Jie, SU Zhe, LI Xiao-xu. Image annotation method based on Corr-LDA model [J]. 吉林大学学报(工学版), 2018, 48(4): 1237-1243.
[15] HOU Yong-hong, WANG Li-wei, XING Jia-ming. HTTP-based dynamic adaptive streaming video transmission algorithm [J]. 吉林大学学报(工学版), 2018, 48(4): 1244-1253.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] JIAO Yu-ling, XU Liang-cheng, WANG Zhan-zhong, ZHANG Peng. Balance experiment and analysis of double U-shaped assembly line based on directed network[J]. 吉林大学学报(工学版), 2018, 48(2): 454 -459 .
[2] LIU Xue-juan, YUAN Jia-bin, XU Juan, DUAN Bo-jia. Quantum k-means algorithm[J]. 吉林大学学报(工学版), 2018, 48(2): 539 -544 .
Copyright © Journal of Jilin University(Engineering and Technology Edition), All Rights Reserved.
Tel: +86-431-85095297　Fax: +86-431-85094074　E-mail: xbgxb@jlu.edu.cn
Powered by Beijing Magtech Co. Ltd