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

摘要：

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

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

所属期刊栏目：26

分类号：TU722(建筑施工)

资助基金：国家自然科学基金资助项目71671065;中央高校基本科研业务费专项资金项目2017XS100

在线出版日期：2018-11-07（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：119-128