GPRs条件下时间-费用权衡问题的初始最优解

求解时间-费用权衡问题时,特别是在确定项目的最优时间-费用曲线时,首先必须找出初始最优解,即费用最低的总工期,然后在该解的基础上,用最低的压缩费用将总工期逐步缩短。在工序之间只有严格优先关系下,各工序的费用最低的工期就是初始最优解。但是当工序之间存在一般优先关系(简称GPRs)时,各工序都选用费用最低的工期往往无法满足既定的优先关系,使得项目不可行,因此必须考虑其它费用较高的工期,并且在时间约束范围内使得总费用最低。所以求解GPRs条件下时间-费用权衡问题的初始最优解是一个项目调度问题。针对该问题,首先,通过分析GPRs及其表示方法的特点,建立了该问题的数学模型;其次,通过对该模型进行对偶变换,将其等效转化为产销平衡的运输模型。运用已有的相关算法能够简便有效地求得该模型的最优解,并跟据初始-对偶关系可求得原问题的最优解。     

炼钢连铸生产调度问题的两阶段遗传算法

将炼钢连铸生产过程抽象为混合流水车间,建立了0-1型混合整数线性规划调度模型。模型将严格连续浇注作为等式约束,并通过分段惩罚来平衡炉次的驻留时间。在对模型进行Benders分解的基础上,提出了将GA与LP结合的两阶段遗传算法。在算法设计中,提出了一种新的染色体编码来表示炉次设备指派与排序方案,给出了相应的遗传操作方法。算法的第一阶段通过最小化设备析取冲突来寻找高质量的种群,第二阶段通过求解线性规划模型来指导遗传算法的迭代过程。基于生产实际数据的仿真实验表明,该算法能够有效求解炼钢连铸生产调度问题。     

基于时差分析的资源均衡问题探究

本文在已有时差概念分析的基础上,提出了三个新时差概念,给出了同一工序不同时差关系,提出了标值算法,算出了不同工序时差传递量。对资源均衡优化问题的初始方案进行研究,给出了随机时标网络图的绘制方式,使网络技术的应用更具灵活性和实用性。在时差传递性的基础上,进一步对有资源限制的资源均衡优化方案进行研究,提出了基于赋值算法的优化调整方式,最后通过算例对该调整方式进行了验证。     

广义优先关系下工序机动时间的隐形消耗

在带有广义优先关系(generalized precedence relations,简称GPRs)的工序网络中,发现了新的奇异现象.传统观念中,如果某工序的机动时间被消耗,则必然发生在以下两种情况中:1)该工序主动消耗自身机动时间;2)由于该工序的前继工序消耗各自的机动时间,导致该工序被动地消耗自身机动时间.然而新发现的奇异现象是,即使脱离上述两种情况,某工序的机动时间也会被消耗.该现象称为工序机动时间的隐性消耗,出现在带有GPRs的工程项目中.在GPRs网络的基础上,研究了该奇异现象的特性,分别针对工序的经典时差和隐性时差,提出了相应的机动时间隐性消耗的量化方法.对于带有GPRs的项目调度问题,工序机动时间隐性消耗的现象会弱化现有的基于机动时间的模型和优化算法,因此,为了进一步提高项目调度的效率和准确性,对该奇异现象的理论研究是不可或缺的.     

资源受限下平行工序顺序对优化的0-1规划模型

资源受限是工程项目时刻都可能面对的挑战。由于资源限制，需要将原项目计划中相互之间无优先关系的平行工序调整为顺序工序。平行工序顺序化可导致项目工期延迟，因此需考虑如何使项目工期延迟最小。该平行工序顺序优化问题是项目调度问题，也是排列组合问题，通常难度很大，包括一些NP-hard问题。本文主要研究该问题的一类典型子问题——平行工序顺序对优化，即如何将项目中某2n个平行工序调整为n个顺序工序对，并且对项目工期的影响最小。该问题的总方案数可达到（2n）!/n!。本文借助工序网络（如CPM网络），运用简单的时间参数量化了平行工序顺序化对项目工期的影响，进而降低问题的求解难度，建立了纯0-1规划模型。实验验证了该模型的求解效率，求解100个平行工序规模的问题平均耗时0.2605秒，而求解500个平行工序规模的问题平均耗时10.66秒。     

广义优先关系下隐性时间、隐性时差和伪时差

在广义优先关系下的工序网络中，发现了奇异现象． 例如，某些工序的开始时间可早于最早开始时间，在不影响总工期的条件下，某些工序的工期延长量可超过总时差，而某些工序的结束时间可迟于最迟结束时间等． 这些现象无法用现有的时间参数值来解释． 通过研究奇异现象，揭示了工序的一些隐性特征，提出了隐性时间、隐性时差和伪时差的新概念，并给出了计算方法． 在很多情况下( 如调整工序的工期时) ，现有的时间参数值与实际不符，而上述隐性时间、隐性时差和伪时差能准确应用于实际． 另外，调整工序的工期是项目调度的重要措施，针对工序的工期在不影响总工期条件下的最大可延长量，发现常识性观点( 认为其等于现有总时差) 是错误的，并根据隐性时间参数值，给出了正确的算法．     

自由时差定理与k阶次关键路线的求法

针对项目进度计划管理中如何寻找CPM网络图中任意阶次关键路线等问题,在分析了自由时差概念和特性的基础上提出了k级标准工序、k级特征值和k级标准路线等新概念,推导出自由时差定理和特征值定理,进而利用这些概念和定理给出k阶次关键路线的求法--最小特征值法,分析了算法的正确性,并且得出该算法的计算复杂度为O(n2). 证明了该算法可以通过局部寻优实现全局寻优. 最后结合应用举例论述了该方法的应用范围及特点.     

“统筹法”网络中经典概念的拓广及应用

本文针对"统筹法"网络中总时差、节点时差、自由时差、安全时差、干扰时差、工序最早开始时间、工序最迟结束时间等经典概念,分析了这些概念存在的局限性,并对其进行了拓广,从单纯的时间领域拓广到长度领域,从不考虑方向性的时差概念拓广到考虑方向性的时差概念,等等;此外,简略表述了这些经典概念在拓广后的应用,例如,根据概念拓广后体现出来的性质,给出等效化简赶工网络的简单方法,以及计算工序排序结果的简单公式,等等。     

基于整数规划强对偶求解一类局域性资源受限项目调度问题

资源受限项目调度问题(简称RCPSP)是最具代表性的项目调度问题之一,调度过程可理解为,将受资源约束的平行工序调整为顺序工序。本文针对实际中广泛存在的资源局域、而非全局受限的情况,研究局域性RCPSP,并重点考虑一类问题：项目某环节的一系列平行工序,可用资源量只有一半,各资源可重复利用且具有相应多功能,但最多能承担2个工序,需将这些工序两两排列成对,实现项目工期最短。本文首先探索问题“局域性”特征,量化局域调度对项目工期的影响;基于此,构建只涵盖“局域调度工序”的0-1规划模型;再者,发展整数规划强对偶理论,结合Dangzig-Wolfe分解等方法,提出多项式时间的精确算法;最后通过算例测试,验证算法优势,例如,计算大规模算例的最优解,运用该算法比常规精确方法可快数万倍以上。