论文部分内容阅读
随着现代制造技术、信息技术和自动化技术的迅猛发展,当今管理越来越显现出项目的特质,按照项目方式管理(management by project)已经逐渐成为一种经济社会活动的主流管理方法。无论是理论研究还是管理实务,项目调度都是项目管理实践的核心内容,资源受限项目调度问题(resource-constrained project scheduling problem,RCPSP)不仅在实践中广泛存在,理论研究上,该问题模型丰富,且多属于NP-hard问题,求解困难,一直吸引着国内外众多学者的关注和研究。目前RCPSP问题主要针对确定的资源约束进行研究,即资源供给是已知的确定常量,但在实际的项目调度中,工程项目的资源供给经常都是不确定的,这往往也是导致项目失败的重要因素。各种意料之外的不确定因素都会导致项目资源供给的不确定性,极大增加了项目调度的复杂度。近几年来,相关研究已经开始围绕不确定资源约束条件下项目调度问题展开。针对上述问题,在借鉴前人研究成果的基础上,本论文对RCPSP司题进行拓展研究,围绕不确定性资源约束下项目调度(uncertain resource-constrained project scheduling problem,URCPSP)这一基本问题,创新性地从资源约束切入,首先重点针对弹性工时约束(flexible resource-constrained project scheduling problem, FRCPSP)与时变资源约束(time-varying resource-constrained project scheduling problem, TRCPSP)这两类最常见的不确定资源约束项目调度问题展开深入研究,并针对这两类问题特征进行深入分析,引入群体智能与拟生态智能算法思想,给出了适合各自特点的算法设计。在此基础上,文章继续深入剖析,将资源受限的项目调度问题扩展到不确定资源约束环境下,提出了针对不确定资源约束下项目调度问题求解的共性模型,并给出了优化策略。最后在单项目不确定资源约束调度问题的基础上,对多项目环境下的不确定资源约束调度问题(uncertain resource-constrained multi-project scheduling problem,URCMPSP)进行了研究。具体而言,本文工作的主要贡献与创新总结如下：(1)详细分析了弹性资源约束下的项目调度问题的特征,并给出了一个完整的数学模型。借鉴蚁群优化理论与分支定界查找机制的设计思想,本文提出了一种新型的弹性资源约束下的混合蚁群项目调度算法MACO_FRCPSP,可以快速地找到资源总量上限及其相应最优调度计划的项目工期变化情况,为项目管理者在考虑加班的情况下如何合理调配人力资源使得项目在最短工期内完工提供了决策依据。计算机实验结果证明本文提出的项目调度算法在性能与准确度等各方面都能很好地满足实际应用需求。(2)详细分析了时变资源约束下的项目调度问题,并给出了一个精确的形式化模型。该问题研究资源到达时间和到达数量按已知函数随时间变化的项目调度问题,在实际工程项目中应用极为广泛,可对应于如原材料采购、设备租赁、资源外包以及项目团队的扩建等一系列情况。本文参考遗传算法的设计理念,提出了一种基于任务优先列表编码的时变资源约束下项目调度问题求解算法TPLC_TRCPSP,该方法采用了带有任务优先值和任务链表的编码方案,可快速得到时变资源约束下的最优项目工期。计算机实验结果验证了该算法的高性能与有效性。(3)在FRCPSP与TRCPSP问题基础上,分析资源上限和资源到达时间均不确定情况下的项目调度问题,并给出了一个共性的形式化模型。针对这一问题的复杂性特征,在遗传算法基础上,进一步提出了一种基于鲁棒优化模型的双不确定环境下项目调度算法ROGA URCPSP,可获得能够使项目在各种不确定性环境下获得平均最优项目工期的任务执行序列。实验结果证明了本文提出的算法有效解决了多种不确定性环境对项目调度带来的挑战。(4)在单项目调度问题的基础上,本文创新性地研究不确定性资源约束下的多项目调度问题,提出一种改进的遗传算法,采用基于随机键的多项目进度计划的编码方案,可获得能够使项目在各种不确定性环境下获得平均最优加权项目工期的多项目任务执行序列。实验结果证明了本文提出的算法相较于传统算法有效解决了由于多项目调度带来的高复杂性问题。