基于图的广度搜索的进度生成机制

启发式算法是解决资源受限的项目调度问题的经典方法之一，通常用来生成元启发算法初始解，传统的串行（SSGS）和并行（PSGS）是生成项目调度方案的经典机制，本文基于图的广度优先搜索算法，提出了一种考虑任务节点位置因素的广度生成机制（BSSGS），并验证了算法的效果。借鉴广度搜索算法定义进度生成机制中的当前任务集合C、候选任务集合D以及阶段变量g等，对各任务节点进行层次划分并定义任务调度秩序；结合优先规则选择候选任务j^*并进行资源R_k（t）调度更新，进而生成完整的调度方案；案例分析表明新机制在满足优先规则和资源约束的同时兼顾了任务节点在网络中位置因素，拥有对于局部复杂网络不回避，对关键节点及时调度等明显优势；选择PSPLIB中算例，在不同优先规则下对新机制进行了测试，测试结果表明新的进度生成机制在LPT、SPT、MTS和MIS等优先规则下，在平均最短工期、平均资源利用率及最优调度方案率等方面优于串行和并行进度生成机制，且算法时间复杂度与传统机制相比并未增加，仍为O（J²，K）。

A Schedule Generation Scheme Based on Breadth Search of Graph

Heuristic algorithms are one of the most classical methods to solve resource-constrained project scheduling problems and usually used to generate initial solutions to meta-heuristic algorithms. The traditional serial (SSGS) and parallel (PSGS) are classical mechanisms for generating project scheduling schemes. In this paper, a breadth-based progress generation mechanism (BSSGS) that takes into account the location of task nodes based on graph-based breadth-first search algorithm is proposed and the effectiveness of the algorithm is verified. Firstly, the breadth search algorithm is used to define the current task set C, the candidate task set D and the stage variable g in the progress generation mechanism, and hierarchically defined each task node and the task scheduling order. Secondly, combining with the priority rules, the candidate tasks are selected and the resources are updated to generate a complete scheduling scheme. In addition, the new mechanism takes into account the position factor of the task node in the network while meeting priority rules and resource constraint, which haves significant advantages of processing to local complex network and timely scheduling key node and so on. Finally, the examples in PSPLIB are seleeted and tested the new mechanism is tested under different priority rules. The test results show that the shortest duration, the average resource utilization and the optimal scheduling scheme rate is superior to the serial and parallel progress generation mechanism under the priority rules of LPT, SPT, MTS and MIS, and the algorithm time complexity does not increase compared with the traditional mechanism, still O (J², K).