论文部分内容阅读
资源受限项目调度问题(Resource-constrained Project Scheduling Problem, RCPSP)包含一组在调度过程中必须满足优先关系和资源约束的任务,常见调度目标是最小化最大完工时间(Makespan)。在生产系统或服务组织中,存在这么一类问题,相对于RCPSP,额外拥有一定数量不同类型的工位,任务需要在特定的工位上执行,每个资源只能服务有限的工位,工件或可移动的资源在工位之间移动需要一定的时间,调度目标也是最小化最大完工时间。在以前RCPSP研究中,缺少对工件和资源位置的考虑,因此上述问题不能直接使用RCPSP模型进行求解。本文将对基于工位约束的资源受限项目调度问题(Site-based and Resource-constrained Project Scheduling Problem, SRCPSP)做以下详细描述与分析。首先,本文在介绍RCPSP及其各种扩展约束后,分析了工位的基本约束,并对工位与资源、工位与工件和工位与任务之间的约束进行了详细的分析与公式化描述。结合任务优先关系与工位的约束,证明了任务的同工位特性,定义了同工位任务。基于同工位任务提出了任务子网(Sub-net, SN)和联合子网(Combined Sub-nets,CSN)的概念,并设计了SN和CSN的求解流程,将工位约束与RCPSP模型结合,给出了SRCPSP的模型。其次,为了在可接受时间内获得SRCPSP的可行解,本文提出两个基于优先规则的启发式调度算法,分别是基于任务子网的搜索算法(Sub-net Based Search algorithm, SNBS)和基于联合子网的搜索算法(Combined Sub-nets Based Search algorithm, CSNBS)。此外,为更好的解释上述算法,文中给出了SNBS算法和CSNBS算法的流程图。最后,本文使用项目调度仿真平台获得了可用于验证算法正确新的两组测试实例。实验结果表明SNBS在时间效率上优于CSNBS,但CSNBS较SNBS获得了更小的项目完工时间。并且基于测试实例,验证两个算法都优于人工调度算法。