• CN:11-2187/TH
  • ISSN:0577-6686

机械工程学报 ›› 2018, Vol. 54 ›› Issue (6): 191-202.doi: 10.3901/JME.2018.06.191

• 交叉与前沿 • 上一篇    下一篇

考虑串行工序紧密度的择时综合调度算法

谢志强, 张晓欢, 高一龙, 辛宇   

  1. 哈尔滨理工大学计算机科学与技术学院 哈尔滨 150080
  • 收稿日期:2016-09-03 修回日期:2017-05-06 出版日期:2018-03-20 发布日期:2018-03-20
  • 通讯作者: 谢志强(通信作者),男,1962年出生,博士后,教授,博士研究生导师。主要研究方向为企业智能计算与调度优化。E-mail:xiezhiqiang@hrbust.edu.cn;张晓欢(通信作者),女,1983年出生,博士。主要研究方向为企业智能计算。E-mail:huanhuan291@126.com
  • 作者简介:高一龙,男,1991年出生。主要研究方向为企业智能计算。E-mail:1033634051@qq.com;辛宇,男,1987年出生,博士后。主要研究方向为企业智能计算、云计算。E-mail:xin_yu_xy@yahoo.cn
  • 基金资助:
    国家自然科学基金(61370086,61602133,61772160)、黑龙江省教育厅科技(12531105)、黑龙江省博士后科研启动(LBH-Q13092)、中国博士后(2016M591541)、黑龙江省博士后(LBH-Z15096)和全国高等学校计算机教育研究会(研究生创新)(ER2014018)资助项目。

Time-selective Integrated Scheduling Algorithm Considering The Compactness of Serial Processes

XIE Zhiqiang, ZHANG Xiaohuan, GAO Yilong, XIN Yu   

  1. College of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080
  • Received:2016-09-03 Revised:2017-05-06 Online:2018-03-20 Published:2018-03-20

摘要: 针对目前综合调度算法在处理一般综合调度问题时为了兼顾加工工艺树中工序的并行处理,忽略串行工序之间紧密度,影响调度结果的问题,提出考虑串行工序紧密度的择时综合调度算法。该算法提出工序序列排序策略,从工艺树的整体结构出发,将其划分成内部工序只具有串行关系的工序序列,根据工序序列的长短确定其调度顺序;提出择时调度策略,结合工艺树自身特点,为调度工序选择若干合法加工时间点,分别在每个时间点调度工序,得到该工序的试调度方案集合,从其中选择加工总用时最小的方案作为工序调度方案,若不唯一,则选择工序加工时间最早的方案。实例表明,该算法既保证并行工序的并行处理,又有效提高串行工序的紧密度,优化了综合调度的结果。

关键词: 串行工序, 工序序列排序, 紧密度, 择时, 综合调度算法

Abstract: Aiming at the problem of ignoring the compactness of serial processes when being compatible with parallel processing of processes that leads to the imprecision result,an time-selective integrated scheduling algorithm considering the compactness of serial processes is presented.The strategy of process sequence sorting is proposed, and it divide the processes into several process sequences based on the integral structure of the processing tree, and the processes in these sequences only has serial relation.Determine the scheduling order according to the length of the process sequence; the time-selective strategy is proposed, and some legal processing time points are selected for the scheduling process according to the characteristics of the process tree. trial scheduling process at each time point respectively,a set of trial scheduling scheme for the process is obtained, The scheme which's total scheduling time is least in the set is chosen as the process scheduling scheme. If not unique, the scheme in which the start time of the process is earliest should be selected. Example shows that the proposed algorithm can raise the compactness of serial processes when being compatible with parallel processing of processes, and make the scheduling result more accurate.

Key words: compactness, integrated scheduling algorithm, process sequence sorting, serial process, time-selective

中图分类号: