基于拟关键路径的二车间综合调度算法

计算机科学 ›› 2013, Vol. 40 ›› Issue (4): 193-198.

基于拟关键路径的二车间综合调度算法

谢志强,周含笑,桂忠艳,郑付萍

哈尔滨理工大学计算机科学与技术学院,哈尔滨150080;哈尔滨理工大学计算机科学与技术学院,哈尔滨150080;哈尔滨理工大学计算机科学与技术学院,哈尔滨150080;哈尔滨理工大学计算机科学与技术学院,哈尔滨150080

出版日期:2018-11-16 发布日期:2018-11-16
基金资助:
本文受国家自然科学基金(60873019),黑龙江省自然科学基金(F201101),哈尔滨市优秀学科带头人(2010RFXXG054),黑龙江省2011年研究生创新科研资金项目(YJSCX2011-035HLJ)资助

Integrated Scheduling Algorithm of Two Workshops Based on ACPM

XIE Zhi-qiang,ZHOU Han-xiao,GUI Zhong-yan and ZHENG Fu-ping

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

摘要： 针对如何将复杂产品工序有效地分配到具有相同设备资源的二车间加工的问题,提出了基于拟关键路径法的二车间综合调度算法。为了让二车间负载平衡并进行充分的并行处理, 尽早结束产品加工,该算法按拟关键路径法(ACPM)对工序排序,再采取二车间加工结束时间接近的预调度策略进行调度。为了减少二车间工序的迁移次数,该算法将入度不小于2的工序放入其紧前工序分配较多的车间；将入度小于2且其紧后工序的入度不小于2的工序分配到能让其尽早结束的车间；对于其他唯一紧前紧后工序与其叶子节点所形成的工序串按预调度策略进行整串调度。实例表明,该算法可以在二次复杂度内较优地实现具有相同设备资源的二车间分布式综合调度。

关键词: 拟关键路径法,二车间,分布式,综合调度

Abstract: Aiming at the problem that how processes of complex products are effectively allocated to two workshops with the same equipment resources,this paper proposed integrated scheduling algorithm of two workshops based on ACPM．In order to let the two workshops load balancing and fully parallel processed,and complete products processing as soon as possible,the algorithm according to the ACPM,takes the pre-scheduled strategy for scheduling for the end of the two workshops in which processed time is close．In order to reduce the number of relocation of two workshops,the algorithm assigns fork point process for in-degree no less than two into the workshop in which predecessor assigned is more；assigns the processes of their in-degree less than 2, at the same time having the successor with the in-degree no less than 2into the workshop which makes them early finished,to take pre-scheduled strategy for the other processes which have the only predecessor and successor formed by their leaf nodes to finishing a whole string．Examples show that the algorithm has better achieved the two workshop distributed scheduling with the same equipment resources in which in the two time complexity.

Key words: ACPM,Two workshops,Distributed,Integrated scheduling

谢志强,周含笑,桂忠艳,郑付萍. 基于拟关键路径的二车间综合调度算法[J]. 计算机科学, 2013, 40(4): 193-198. https://doi.org/

XIE Zhi-qiang,ZHOU Han-xiao,GUI Zhong-yan and ZHENG Fu-ping. Integrated Scheduling Algorithm of Two Workshops Based on ACPM[J]. Computer Science, 2013, 40(4): 193-198. https://doi.org/

参考文献

[1] 曾立平,黄文奇．求解JobShop调度问题的一种新的邻域搜索算法[J]．计算机研究与发展,2005,32(5):48-53
[2] 张维存,郑丕谔,吴晓丹．蚁群遗传算法求解能力约束的柔性作业车间调度问题[J]．计算机集成制造系统,2007,13(2):127-131,156
[3] 何彦,刘飞,曹华军,等.面向绿色制造的机械加工系统任务优化调度模型[J]．机械工程学报,2007,43(4):27-31
[4] Yamamotoa H,Sunb J,Matsuic M．A study on limited-cyclescheduling problem with multiple periods[J]．Computers & Industrial Engineering,2010,9:675-681
[5] 羌磊,肖田元．应用扩展贝叶斯进化算法求解混流装配调度问题[J]．计算机集成制造系统,2007,13(2):111-116
[6] 李原,张开富,王挺,等．基于遗传算法的飞机装配序列规划优化方法[J]．计算机集成制造系统,2006,12(2):30-33
[7] Wu S,David,Richard A W．An Application of Dscrete-eventSimulation to On-line Control and Scheduling in Flexible Manufacturing [J]．Prod.Res,1989,27(9):1603-1623
[8] 谢志强．工件间有约束的复杂产品工序调度研究[D]．哈尔滨:哈尔滨理工大学,2009
[9] 谢志强,张磊,杨静．基于调度长路径的复杂产品综合调度算法[J]．计算机科学,2010,37(2):156-159
[10] 谢志强,杨静,周勇,等．基于工序集的动态关键路径多产品制造调度算法[J]．计算机学报,2011,34(2):216-222
[11] 谢志强,滕宇峥,杨静．紧密衔接工序组联动的综合调度算法[J]．自动化学报,2011,37(3):117-125
[12] 谢志强,邵侠,杨静．存在设备无关延迟约束的综合柔性调度算法[J]．机械工程学报,2011,47(4):181-189
[13] 刘世平,张洁,饶运清,等．分布式车间管理控制系统研究[J]．中国机械工程,2001,12(12):1432-435
[14] 包振强,李长仪,周鑫．分布式混合优化调度方法研究[J]．中国机械工程,2006,7(18):1908-1912
[15] Chung S H,Chan Felix T S,Chan H K．A modified genetic algorithm approach for scheduling of perfect maintenance in distri-buted production scheduling[J]．Engineering Applications of Artificial Intelligence,2009,2(7):1005-1014
[16] Oike S,Tanaka T．Robust production scheduling using autonomous distributed systems[J]．Key Engineering Materials,2012,6:166-169
[17] 谢志强,刘胜辉,乔佩利．基于ACPM和BFSM的动态Job-Shop调度算法[J]．计算机研究与发展,2003,40(7):79-85

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed