高级检索
    谢志强, 辛 宇, 杨 静. 基于逆序信号驱动的紧密衔接综合调度算法[J]. 计算机研究与发展, 2013, 50(8): 1710-1721.
    引用本文: 谢志强, 辛 宇, 杨 静. 基于逆序信号驱动的紧密衔接综合调度算法[J]. 计算机研究与发展, 2013, 50(8): 1710-1721.
    Xie Zhiqiang, Xin Yu, Yang Jing. No-Wait Integrated Scheduling Algorithm Based on Reversed Order Signal-Driven[J]. Journal of Computer Research and Development, 2013, 50(8): 1710-1721.
    Citation: Xie Zhiqiang, Xin Yu, Yang Jing. No-Wait Integrated Scheduling Algorithm Based on Reversed Order Signal-Driven[J]. Journal of Computer Research and Development, 2013, 50(8): 1710-1721.

    基于逆序信号驱动的紧密衔接综合调度算法

    No-Wait Integrated Scheduling Algorithm Based on Reversed Order Signal-Driven

    • 摘要: 针对以往综合调度中紧密衔接调度算法只能处理单一紧前工序的情况,使算法具有局限性问题,提出基于逆序信号驱动的紧密衔接综合调度算法.该算法先建立设备和调度2个子系统,并通过相互间传递的信号驱动逆序调度;对于紧密衔接工序组包含非单一紧前工序的情况,将紧密衔接工序组定义为一棵特殊的紧密衔接子树,采用逆序调度的方式自顶向下对紧密衔接问题求解;当信号驱动时刻存在多个可调度工序(组)时,按最大可并行性选择策略选择子节点关键路径长的工序(组)调度;对于可调度工序直接锁定该工序的加工时间段;对于可调度工序组,则按锁定紧密衔接工序组的前沿贪心策略锁定工序组的加工时间段.由于采用逆序调度和锁定紧密衔接工序组的前沿贪心策略,可使各紧密衔接工序组独立调度,实现紧密衔接紧前工序数无限制的综合调度.

       

      Abstract: 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.

       

    /

    返回文章
    返回