论文部分内容阅读
资源约束多项目调度问题(RCMPSP)广泛存在于企业的项目管理中,与项目成本和生产效率密切相关。由于企业项目管理的复杂性和多样性,使得RCMPSP的问题模型各具特点,目前还没有统一的处理模型。针对某企业项目管理的实际需求,本文在传统的RCMPSP的基础上加入了一些新的概念,如工件、工位、时间窗等,同时考虑了工件约束、工位约束、时间窗约束等复杂的约束关系,设定最大完工时间最小化为目标,提出了一个带资源时间窗的资源约束多项目调度问题模型(RCMPSPTWC),用以解决该企业项目管理中的实际问题。首先,基于传统的串行多项目进度生成机制(SMPSGS)的思想,设计了适用于本课题的串行多项目进度生成机制(ISMPSGS),并结合七类用以决策的优先规则来求解RCMPSPTWC问题。实验表明ISMPSGS是合理有效的且优于SMPSGS,且基于ISMPSGS提出的启发式算法可快速生成合理可行的初始解。然后,研究了优化初始解的元启发式算法。通过分析RCMPSPTWC的特点,本文发现工件转移顺序是制约调度结果的关键因素,因此设计了工件转移顺序随机抽样算法进行验证,结果表明随机确定工件转移顺序可得到更优的结果。在此基础上,将最大最小蚂蚁系统(MMAS)应用到工件转移顺序的选择上,提出了基于ISMPSGS和MMAS的优化算法。实验表明使用MMAS优化工件转移顺序的选择是合理有效的,并且ISMPSGS在元启发式算法中同样优于SMPSGS。最后,为了进一步处理资源时间窗约束,提出了基于蚁群和禁忌搜索的两阶段算法,其中蚁群算法用以确定工件的初始工位,禁忌搜索算法用以确定后续工位。实验表明该算法求解RCMPSPTWC是切实有效的,并且当迭代次数相同时,该算法可在牺牲一定的CPU时间的前提下找到比基于ISMPSGS和MMAS的优化算法更优的解。以本文研究成果为基础的核心算法已经实际应用。