关键词: 图的广度搜索, 项目调度, 进度生成机制, 优先规则

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

Key words: breadth search of graph, project scheduling, schedule generation scheme, priority rules