可回退抢占的设备驱动综合调度算法

谢志强; 辛宇; 杨静

doi:10.3724/SP.J.1004.2011.01332

可回退抢占的设备驱动综合调度算法

doi: 10.3724/SP.J.1004.2011.01332

谢志强^1,2, ,,
辛宇¹,
杨静²

1.
哈尔滨理工大学计算机科学与技术学院哈尔滨 150080;
2.
哈尔滨工程大学计算机科学与技术学院哈尔滨 150001

详细信息

通讯作者:
谢志强哈尔滨工程大学博士后,哈尔滨理工大学教授. 主要研究方向为企业智能计算,数据库与知识工程. E-mail: xzq011@tom.com

计量
- 文章访问数: 2128
- HTML全文浏览量: 58
- PDF下载量: 971
- 被引次数: 0
出版历程
- 收稿日期: 2010-12-15
- 修回日期: 2011-05-28
- 刊出日期: 2011-11-20

Machine-driven Integrated Scheduling Algorithm with Rollback-preemptive

XIE Zhi-Qiang^{1,2
, ,},
XIN Yu¹,
YANG Jing²

1.
College of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080;
2.
College of Computer Science and Technology, Harbin Engineering University, Harbin 150001

摘要

摘要: 针对基于拟关键路径法的综合调度算法按路径长度确定工序的调度次序,形成工序组间的并行处理, 使设备产生较多空闲时间的问题,提出可回退抢占的设备驱动综合调度算法. 该算法以每次工序加工结束作为一次可调度工序的寻找事件,若此时新出现的可调度工序具备抢占能力,则产生回退事件进行重调度;若不产生回退事件,如果可调度工序唯一,则调度此工序;如果可调度工序不唯一, 选择父结点路径长的工序;如果父结点最长路径相同,选择用时长的工序. 由于该算法在调度工序时形成工序间的并行处理,缩小基于拟关键路径的综合调度算法形成的并行处理单位,进而减少加工过程中产生较多的设备空闲时间,提高设备利用率;同时,由于采用抢占式的回退调度策略,优先调度对调度结果有重要影响的长路径工序,达到对拟关键路径法的扬长避短,进一步提高设备利用率.
- 设备空闲事件 /
- 事件驱动 /
- 工序并行 /
- 综合调度 /
- 回退抢占 /
- 工序组
Abstract: Determining the scheduling sequence according to the length of path by the integrated scheduling algorithm based on allied critical path method will cause parallel processing among the sequence segment of procedures and machines with plenty of idle time. This paper presents a machine-driven integrated scheduling algorithm with rollback-preemptive. Each ending process of procedures is regarded as a searchable event of schedulable procedures in this algorithm. At this time, if a schedulable procedure which appears new has preemptive ability, it generates rollback event to reschedule. In case rollback event is not generated, we schedule this procedure if the schedulable procedure is sole; otherwise, we select the procedure which has the longest parents node path. If the longest parents node path is not sole, the procedure with the longest process time is select. As it will cause parallel processing among procedures when procedures are scheduled in this algorithm, it shortens the parallel processing unit generated by integrated scheduling algorithm based on allied critical path method and reduces excessive machine idle time caused in processing. So the machine utilization efficiency is heightened. Simultaneity, because it adopts rollback scheduling strategy with preemptive style and schedules the longest path procedure firstly which can influence scheduling result significantly, it makes best use of the advantage and bypasses the disadvantage of allied critical path method and advances the utilization efficiency further.
- Machines' idle event /
- event-driven /
- procedures parallel processing /
- integrated scheduling /
- rollback-preemptive /
- sequence segment of procedures

HTML全文

参考文献(1)

[1]

Zhang Chang-Sheng, Sun Ji-Gui, Yang Qing-Yun, Zheng Li-Hui. A hybrid algorithm for flowshop scheduling problem. Acta Automatica Sinica, 2009, 35(3): 332-336(张长胜, 孙吉贵, 杨轻云, 郑黎辉. 一种求解车间调度的混合算法. 自动化学报, 2009, 35(3): 332-336)[2] Zhang Hong-Yuan, Xi Yu-Geng, Gu Han-Yu. A decomposition and coordination scheduling method for flow-shop problem based on TOC. Acta Automatica Sinica, 2005, 31(2): 182-187(张宏远, 席裕庚, 谷寒雨. 基于约束理论的Flow-shop分解协调算法. 自动化学报, 2005, 31(2): 182-187)[3] Xu Zhen-Hao, Gu Xing-Sheng. Immune scheduling algorithm for flow shop under uncertainty with zero wait. Computer Integrated Manufacturing Systems, 2004, 10(10): 1247-1251(徐震浩, 顾幸生. 不确定条件下具有零等待的流水车间免疫调度算法. 计算机集成制造系统, 2004, 10(10): 1247-1251)[4] Yan Li-Jun, Li Zong-Bin, Wei Jun-Hu, Du Xuan. A new hybrid optimization algorithm and its application in job shop scheduling. Acta Automatica Sinica, 2008, 34(5): 604-608(闫利军, 李宗斌, 卫军胡, 杜轩. 一种新的混合优化算法及其在车间调度中的应用. 自动化学报, 2008, 34(5): 604-608)[5] Xiong He-Gen, Li Jian-Jun, Kong Jian-Yi, Yang Jin-Tang, Jiang Guo-Zhang. Heuristic method for dynamic job shop scheduling problem with operation relativity. Chinese Journal of Mechanical Engineering, 2006, 42(8): 50-55(熊禾根, 李建军, 孔建益, 杨金堂, 蒋国璋. 考虑工序相关性的动态Job shop调度问题启发式算法. 机械工程学报, 2006, 42(8): 50-55)[6] Wei Ying-Zi, Zhao Ming-Yang. A reinforcement learning-based approach to dynamic job shop scheduling. Acta Automatica Sinica, 2005, 31(5): 765-771(魏英姿, 赵明扬. 一种基于强化学习的作业车间动态调度方法. 自动化学报, 2005, 31(5): 765-771)[7] Xie Zhi-Qiang. Study on Operation Scheduling of Complex Product with Constraint among Jobs [Ph.D. dissertation], Harbin University of Science and Technology, China, 2009(谢志强. 工件间有约束的复杂产品工序调度研究 [博士学位论文], 哈尔滨理工大学, 中国, 2009)[8] Xie Zhi-Qiang, Liu Sheng-Hui, Qiao Pei-Li. Dynamic job-shop scheduling algorithm based on ACPM and BFSM. Journal of Computer Research and Development, 2003, 40(7): 977-983(谢志强, 刘胜辉, 乔佩利. 基于ACPM和BFSM的动态Job-Shop调度算法. 计算研究与发展, 2003, 40(7): 977-983)[9] Xie Z Q, Ye G J, Zhang D L, Tan G Y. New nonstandard job shop scheduling algorithm. Chinese Journal of Mechanical Engineering, 2008, 21(4): 97-100[10] Xie Zhi-Qiang, Mo Tao, Tan Guang-Yu. Dynamic job-shop scheduling algorithm of the non-close-joining operations. Chinese Journal of Mechanical Engineering, 2008, 44(1): 155-160(谢志强, 莫涛, 谭光宇. 非紧密衔接工序动态车间调度算法. 机械工程学报, 2008, 44(1): 155-160)[11] Xie Zhi-Qiang, Shao Xia, Yang Jing. Algorithm for integrated flexible scheduling with device-independence deferred constraint. Journal of Mechanical Engineering, 2011, 47(4): 177-185(谢志强, 邵侠, 杨静. 存在设备无关延迟约束的综合柔性调度算法. 机械工程学报, 2011, 47(4): 177-185)[12] Xie Zhi-Qiang, Li Zhi-Min, Hao Shu-Zhen, Tan Guang-Yu. Study on complex product scheduling problem with no-wait constraint between operations. Acta Automatica Sinica, 2009, 35(7): 983-989(谢志强, 李志敏, 郝淑珍, 谭光宇. 工序间存在零等待约束的复杂产品调度研究. 自动化学报, 2009, 35(7): 983-989)[13] Xie Zhi-Qiang, Teng Yu-Zheng, Yang Jing. Integrated scheduling algorithm with no-wait constraint operation group. Acta Automatica Sinica, 2011, 37(3): 371-379(谢志强, 滕宇峥, 杨静. 紧密衔接工序组联动的综合调度算法. 自动化学报, 2011, 37(3): 371-379)[14] Xie Z Q, Hao S Z, Ye G J, Tan G Y. A new algorithm for complex product flexible scheduling with constraint between jobs. Computers and Industrial Engineering, 2009, 57(3): 766-772[15] Xie Zhi-Qiang, Yang Jing, Yang Guang, Tan Guang-Yu. Dynamic job-shop scheduling algorithm with dynamic set of operation having priority. Chinese Journal of Computers, 2008, 31(3): 502-508(谢志强, 杨静, 杨光, 谭光宇. 可动态生成具有优先级工序集的动态Job-Shop调度算法. 计算机学报, 2008, 31(3): 502-508)[16] Xie Zhi-Qiang, Yang Jing, Zhou Yong, Zhang Da-Li, Tan Guang-Yu. Dynamic critical paths multi-product manufacturing scheduling algorithm based on operation set. Chinese Journal of Computers, 2011, 34(2): 406-412(谢志强, 杨静, 周勇, 张大力, 谭光宇. 基于工序集的动态关键路径多产品制造调度算法. 计算机学报, 2011, 34(2): 406-412)[17] Yang Zhi-Yi, Yang Gang, Zhang Hai-Hui. An approach for implementing service-oriented and event-driven information integration platform. Journal of Computer Research and Development, 2008, 45(10): 1799-1806(杨志义, 杨刚, 张海辉. 一种面向服务的事件驱动架构信息集成平台构造方法. 计算机研究与发展, 2008, 45(10): 1799-1806)[18] Liu Jia-Hong, Wu Quan-Yuan. An event-driven service-oriented computing platform. Chinese Journal of Computers, 2008, 31(4): 588-598(刘家红, 吴泉源. 一个基于事件驱动的面向服务计算平台. 计算机学报, 2008, 31(4): 588-598)

施引文献

资源附件(0)

访问统计