资源受限的项目调度问题(Resource-Constrained Project Scheduling Problem,RCPSP)广泛地存在于各行各业,不仅是项目管理实践的核心内容,也是运筹学的一个重要分支。合理的调度计划能够节约资源、缩短工期、获得较大的经济效益。在理论研究上,资源受限项目调度问题模型丰富,大部分属于NP-hard问题,求解困难,因此研究RCPSP具有重要的现实意义和理论价值。本论文围绕这个问题,分为两大部分：一个是受到水利工程建设项目的启发,提出了一种新的具有硬性时间约束的资源受限项目调度扩展模型,称之为具有禁止时间窗口的资源受限项目调度问题(Resource-Constrained Project Scheduling Problem with Forbidden Time Windows,RCPSP-FTW);二是在资源受限项目调度中引入数据包络分析技术,解决调度方案的选择问题。本论文的主要工作和创新点如下：
1、建立了具有禁止时间窗口的资源受限项目调度问题的模型,详细说明了其特点。调整了经典的调度方案生成机制和基于多优先规则的启发式算法,使之适合于求解具有禁止时间窗口的资源受限项目调度问题。同时基于PSPLIB实例库数据,构建了具有禁止时间窗口约束的仿真实例,并使用它验证了基于多优先规则启发式算法的有效性。
2、设计了两种求解具有禁止时间窗口的资源受限项目调度问题的元启发式算法。一种是遗传算法,根据问题特点提出了禁止时间窗口的交叉算子,并使用双对齐技术和精英保留机制改善解的质量。另一种是改进的类电磁算法,使用随机键和拓扑排序相结合的编码方式,改进了粒子电荷、合力以及粒子移动的方式并使用变邻域搜索作为局部搜索方法。仿真实验分别用一个简化的水利工程项目和大量仿真数据验证了两个算法的求解效果。实验表明这两种算法能够大大提高解的质量。根据实验结果也说明了禁止时间窗口和受到禁止时间窗口影响的活动分布是导致具有禁止时间窗口的资源受限项目调度问题工期波动的主要原因。
3、使用了数据包络分析技术解决管理者面对众多候选的资源受限项目调度方案陷入选择困境的难题。项目调度问题本身具有三个相互矛盾的目标,分别是工期、成本和质量。实际中管理者对这三个目标的偏好并不统一,导致调度方案难以抉择。因此在资源受限项目调度中引入数据包络分析技术。利用一个多模式资源受限项目调度问题作为例子,说明两者如何结合。这为资源受限项目调度应用的扩展和实际的项目决策提供了一个新的思路。
柔性流水车间有限缓冲区排产优化问题是柔性流水车间排产优化问题的延伸,是柔性流水车间与现实生产制造结合的产物,广泛存在于车辆制造、烟草、半导体生产以及大型装备制造等重要国民经济领域。柔性流水车间有限缓冲区排产优化问题的主要特征为工序之间存在缓冲区且缓冲区容量有限,工件在当前机器加工完毕后,若下一道工序被占用,则工件进入缓冲区等待,由于技术水平的低下以及存储设备和生产工艺方面的限制,工件在流水车间相邻工序间的缓冲数量受到严格的限制,若缓冲区已满,则工件在当前机器上等待,直到缓冲区空闲。缓冲区容量有限会导致阻塞问题,所以柔性流水车间有限缓冲区排产优化问题是一个比FSP更为复杂的NP-hard问题。工件在缓冲区中的顺序,关系到企业的生产效率,另外,随着当今各类产品的市场需求的多样化和个性化,车间不仅生产任务量大,而且生产任务类型繁多,这必然导致生产线的生产节奏难以控制,生产过程不确定性增大,对中间缓冲区的需求增加。本文的研究内容具有重要的理论意义和实际应用价值。柔性流水车间有限缓冲区排产优化问题(LBFFSP),是在柔性流水车间排产优化问题上加上有限缓冲区的约束,使问题更加复杂。本文针对柔性流水车间有限缓冲区排产优化问题进行深入的研究,首先建立柔性流水车间有限缓冲区数学规划模型,依据先入先出(first in first out,FIFO)原则和最先空闲机器优先选择(first available machine,FAM)原则,在解码过程中考虑工位阻塞情况的发生,为了便于表述,采用混合启发式解码方法(Hybrid heuristic decode methods,HDM)建立数学规划模型。随后对柔性流水车间有限缓冲区的排产优化过程进行分析,最后本文对柔性流水车间有限缓冲区排产优化方法进行了深入研究。本文采用结构简单,全局优化能力强的类电磁算法(Electromagnetism-like Mechanism,EM)作为柔性流水车间有限缓冲区排产优化问题的全局优化算法。EM算法的主要步骤包括,初始化、局部搜索、电荷量及合力的计算和粒子的移动,同时EM算法也能够比较容易的与其他算法结合,形成新的结合算法,提升算法性能。优化目标方面,选择经典的最小化最大完工时间作为优化目标,采用标准EM算法求解柔性流水车间有限缓冲区排产优化问题,并验证它的有效性。然而EM算法也存在很多不足,在局部搜索策略中,采用随机线性搜索,EM算法的搜索范围小,容易陷入局部极值,导致算法无法找到全局最优点,算法的种群多样性也会随着迭代过程逐渐减小,算法容易陷入局部极值,导致算法精度不高。所以需要对EM算法进行改进,使得算法在求解各种类型的复杂问题都具有高效性、鲁棒性和稳定性。针对上述缺点,本文引入模拟退火的思想,在EM算法局部搜索步骤中,结合模拟退火算法的退火操作,以一定的概率接受使目标适应度更差的解,这样就可以扩大模拟退火算法的搜索范围,增加种群粒子的多样性,提高算法的灵活度,并且可以有效避免算法在迭代搜索过程中陷入局部最优解,进而增加算法搜寻最优解的能力与精度。这种改进方法恰好弥补了标准EM算法的缺陷。另外,由于EM算法的初始种群为随机生成,且生成质量不高。本文针对这个问题提出一种基于概率模型的初始种群建立方法,提高了种群的丰富度,并且有利于提高整体的进化收敛速度。基于概率模型的方法可以增加每个个体的随机性,并且以最小化最大完工时间为优化目标建立概率模型,使生成的个体更接近最优解,进化效果更好,从而达到提高全局优化效果的目的。本文的主要工作内容是对EM算法本身性能的改进以及将改进算法应用于现实复杂生产调度的问题,改进后的EM算法在寻优精度、收敛速度方面优于标准类电磁算法,并且有效避免算法陷入局部极值。
暂无评论