摘要
针对以往综合调度中紧密衔接调度算法只能处理单一紧前工序的情况,使算法具有局限性问题,提出基于逆序信号驱动的紧密衔接综合调度算法.该算法先建立设备和调度2个子系统,并通过相互间传递的信号驱动逆序调度;对于紧密衔接工序组包含非单一紧前工序的情况,将紧密衔接工序组定义为一棵特殊的紧密衔接子树,采用逆序调度的方式自顶向下对紧密衔接问题求解;当信号驱动时刻存在多个可调度工序(组)时,按最大可并行性选择策略选择子节点关键路径长的工序(组)调度;对于可调度工序直接锁定该工序的加工时间段;对于可调度工序组,则按锁定紧密衔接工序组的前沿贪心策略锁定工序组的加工时间段.由于采用逆序调度和锁定紧密衔接工序组的前沿贪心策略,可使各紧密衔接工序组独立调度,实现紧密衔接紧前工序数无限制的综合调度.
Aiming at the problem that the existing no-wait algorithm could only schedule the process with SIPP （sole immediate predecessor process） which limits the application of integrated scheduling algorithm, we have proposed the no-wait integrated scheduling algorithm based on reversed order signal-driven. This algorithm establishes device and scheduling subsystem, both subsystems are driven by the signals transmitted between them; For the NWPG （no-wait process group） with NSIPP （non-sole immediate predecessor process）, we define the NWPG as a no-wait subtree and adopt the reversed order method to solve the no-wait problem top to down. In the case that there are several schedulable processes or schedulable process groups, we choose the process or process group by the BPCP （biggest parallelism chosen policy）, which looks for the process or process group with longest child-node critical path; If the chosen one is a process, we lock the timespan of the process immediately; If the chosen one is a process group, we determine the locked timespans by the FGP （frontier greedy policy）. Because we have adopted the reversed order method and the FGP, the NWPG could be scheduled independently, achieving the no-wait integrated scheduling with unlimited number of SIPP.
出处
《计算机研究与发展》
EI
CSCD
北大核心
2013年第8期1710-1721,共12页
Journal of Computer Research and Development
基金
国家自然科学基金项目(60873019
61073043)
黑龙江省自然科学基金项目(F200901
F201101)
中国博士后科学基金项目(20090460880)
哈尔滨市优秀学科带头人基金项目(2010RFXXG054
2011RFXXG015)
关键词
紧密衔接
多紧前工序
逆序调度
信号驱动
综合调度
no-wait
non-sole immediate predecessor process
reversed order
signal-driven
integrated scheduling
