论文部分内容阅读
资源受限项目调度问题(RCPSP)是从资源受限角度出发,兼顾优先关系约束和资源约束,合理配置各任务的开始和结束时间,从而达到项目总工期最小或其他目标。该问题本身属于NP-hard难题,加之项目实施过程中的干扰事件使原计划出现扰动甚至不再可行,因此如何有效处理干扰事件使新方案与原调度计划的扰动偏差最小,更成为项目调度问题的难点。干扰管理思想正可用于解决该类问题,根据扰动状态对原方案进行局部优化调整、扰动恢复,要同时考虑初始目标、新的恢复约束,使系统扰动最小,并兼顾扰动成本,进而及时产生最优调整方案。本文对多模式资源受限项目调度问题(MRCPSP)进行研究,并选择任务类干扰事件对调度的影响为研究重点,以期为该类问题的解决提供新的途径。本文的主要研究内容包括: (1)MRCPSP问题的遗传算法设计和求解。通过一种改进的遗传算法,即采用双任务链表结构的编码方式,而后进行交叉、变异、适值计算、选择等操作。(2)在分析MRCPSP扰动问题的基础上,运用干扰管理思想提出了扰动辨识和度量方法,建立了基于客户、项目总工期偏差、扰动成本偏差等因素的度量函数,构建干扰管理模型。并在此基础上,提出了多种扰动恢复策略及其调整方案选择的策略。(3)针对PSPLIB中的基准问题进行了遗传算法的设计,并对其具体的任务扰动的干扰管理予以解决,及时生成具体的干扰管理调整方案。通过算例研究验证了GA和干扰管理模型求解MRCPSP的可行性和有效性。本文分别从客户满意程度、项目总工期以及扰动成本三方面对MRCPSP扰动问题进行扰动辨识和度量,突破了以往的研究局限。干扰管理模型的建立和求解,能有效降低扰动对系统的影响,及时生成最优调整方案,对实际项目具有较强的指导意义,也为MRCPSP干扰管理提供了新的解决思路。