带有广义优先关系的平行工序顺序优化研究

在带有广义优先关系(GPRs)的工程项目中,把2n个平行工序调整为n个顺序工序对是一类典型的带有GPRs的资源限制项目排序问题。为了给该类问题的解决提供理论和方法,研究了在GPRs下,如何将8个平行工序调整为对总时差影响最小的4个顺序工序对。通过运用重心定理、行偶亏值定理和最佳行偶定理等现有相关结论,将带有严格优先关系的同类问题算法进行拓展,提出了求解该带有GPRs的平行工序顺序优化问题的简单算法,并进行理论上的证明。最后,通过算例演示了该算法的效用。

高中到大学过渡中的困扰及对策研究——基于班主任视角

大一新生挂科呈现人数多,比例大的特点。原因很多,主观原因包括目标、学习方法、适应性、人际关系等四个方面;客观原因包括学生基础、学校管理、学生社团等三个方面。而班主任作为大一新生接触最多的老师,其言行对学生的影响深远,所以班主任可以通过开好三次重要的班会、构建良好的沟通渠道以及得力的班委来引导学生合理安排好大学生的学习生活,帮助学生顺利完成大学学业,并为未来的发展打好基础。

求解无回路有向连通图中的k阶最短路问题

针对如何在无回路有向连通图中求解k阶最短路问题,提出了新的思路,即先求出某路径与最短路的长度之差,再利用该差值求得该路径。在该思路的指引下,提出了新的参数概念,如点参数N、弧参数A以及终点的特征参数θ,并给出了这些参数的计算方法;揭示了这些参数与图中相应路径之间的关系,推导出点参数N定理和弧参数A定理;利用这些参数和定理,设计出在无回路有向连通图中求解k阶最短路问题的多项式算法,证明了算法的正确性,并且经过分析,该算法的复杂度为O(km),m表示弧数;最后,通过应用举例对该算法进行了演示。

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

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

广义优先关系下工序共用时差的计算与应用

工序共用时差和干扰时差能够体现项目中工序间相互影响的规律,是决定实际项目调度难易程度的重要因素。针对在带有广义优先关系(简称GPRs)的项目中尚缺乏对这两类时差的分析计算,从多视角研究GPRs下工序共用时差的量化及特性。首先,分析GPRs下工序共用时差的分布和效用特征,将其细分为工序前、后共用时差和总体共用时差,提出相应计算方法。其次,根据上述各子类型时差的特征、功能和规律,提出"半岛工序"和"孤岛工序"新概念。最后,将工序共用时差应用于GPRs下的资源均衡问题,实现了问题简化,提出提高求解效率的新思路。

大学生对当前教学的感知及科研成果引入课堂的期待调查研究

根据学生对当前教学的感知及科研成果引入课堂的期待调查发现,教学科研必须齐头并进,但是受限于当前的政策制度,老师们更关注科研,教学投入相对较少。本文在现有调查数据的基础上,提出由教学团队完成教学科研共同发展的重任,完成大学培养合格接班人的目标。

计及风险的供电公司最优购电决策模型研究

鉴于我国电力市场必将由目前的发电侧竞争模式发展并过渡到输配分离模式:输电网向电力市场各方参与者提供无歧视的电能输送服务,提出了不确定的电力市场环境中供电公司的风险决策方法。该方法准确计及决策者行为的改变能影响供电公司风险的大小;使用预期收益和实际收益的比值作为风险测量的指标,用机会约束规划建立输配电分离后供电公司报价购电组合最优风险策略模型,采用Monte-Carlo模拟结合基因算法求解,并给出了直接优化方法对模型进行求解。

基于Lagrange松弛求解带有广义优先关系的离散型时间—费用权衡问题解的下界

时间-费用权衡问题(TCTP)是项目调度领域最重要的、用途最广的问题之一。然而,对于各工序具有多个模式,且工序间存在广义优先关系(GPRs)的情况,相应的TCTP目前却没有受到很多重视,该问题称为带有GPRs的离散型TCTP(DTCTP)。DTCTP是NP-hard问题,且工序调度在GPRs下会存在很多奇异现象,有悖于常规理论和方法。因此,启发式方法有必要被用于求解该类型的大规模问题。而为了评估启发式方法的效果,需要得到原问题的解的尽量紧的下界。该文基于Lagrange松弛、分解和对偶,计算出带有GPRs的DTCTP的一个较紧的下界。

求解含负权弧的网络最小截问题

对于经典网络最小截问题,所有弧权数非负,可运用最大流算法求解。但是对于广义最小截问题,若某些弧权数为负,则运用算法难以求解。针对含负权弧网络最小截问题,通过与经典最小截问题的对比,提出简单截集和复合截集概念,并给出广义网络最小截概念——截量最小的简单截集;引入负容量和负流量,给出求解含负权弧网络最小截问题的原理,并设计求解含负权网络最小截问题的网络流算法;最后,通过应用举例对算法进行演示。

一类局域性资源受限项目调度问题的新0-1混合线性优化模型

资源受限项目调度问题(简称RCPSP)是最具代表性且难解的项目调度问题之一,其经典问题以“资源全局受限”为特征。本文从新的视角考虑资源受限的特征,针对实际中广泛存在的“稀缺资源受限导致项目局域性调度”的情况,研究局域性RCPSP,并重点探索一类问题:项目局部的某系列平行工序,可配备的资源数量极少,甚至为1,该资源可重复使用,且具有多技能,故需安排该资源顺序完成该系列工序,使项目工期最短。虽是局域性调度,但项目的系统性使其“牵一发而动全身”,难度可能不亚于全局性调度。本文探索问题的“局域性”特征,量化“局域调度”对“项目全局”的影响;基于此,构建只涵盖“局部调度工序”,实现项目全局最优化的0-1混合线性规划模型,且模型结构简单,简化了项目的复杂结构;最后,通过算例测试,验证该模型在计算较大型、大型案例的最优解方面具有的优势,如针对将包含9000个工序的项目中,安排1个可重复使用的资源完成某300个平行工序的案例,借助该模型平均耗时236.16秒可算出最优解。

CPM机动时间可使用量和使用效率分析

主要解决项目进度计划管理中,CPM机动时间实际可使用量和使用效率问题,以及如何将对机动时间的研究从单个工序扩展到整个网络。首先,根据CPM网络计划已有的知识体系和机动时间已有的概念和性质,提出CPM机动时间可使用量的概念;其次,分析CPM机动时间可使用量与合理分配机动时间的关系,给出求解CPM机动时间可使用量的算法,并相应给出求解其最大值和最小值的算法,证明了算法的正确性;再次,通过对算法的分析,得出任意CPM网络计划的机动时间可使用量会随机动时间分配情况的不同而不同,并非常数;最后,依据CPM机动时间可使用量及其最大值和最小值,定义CPM机动时间的使用效率参数,并给出参数的计算公式和取值范围,分析如何提高CPM网络计划中机动时间使用效率的问题。

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

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

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

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

一类局域性多技能资源受限项目调度的新算法

多技能资源受限项目调度问题(简称MS-RCPSP)是项目管理中颇具代表性的调度问题,一般性问题以“资源全局受限”为特征.本文从新视角,针对实际中广泛存在的资源局域受限情况,以及反应性和应急性等情况,研究局域性MS-RCPSP;并重点考虑一类典型问题:项目某部分的平行活动,可用的资源量极少,甚至为1,但具备各活动所需技能,且可重复使用,需安排该资源顺序完成这一众活动,使项目工期最小化.虽是局域性调度,但项目系统性使其“牵一发而动全身”,难度可能不亚于全局性调度.本文从探索问题“局域性”特征入手,量化局域调度导致的项目工期延迟,并发展整数线性优化强对偶理论,结合Dantzig-Wolfe分解法,开发出伪多项式时间精确算法求解该问题;通过仿真模拟测试,验证该算法计算大规模问题案例精确解的优势.

规范化工程网络图的理论和方法

工序网络图在工程项目计划和流程分析方面有重要的用途。若用现有方法将复杂的工序系统绘制成Activity-on-Arc(简称AoA)网络图,则图容易出现错综复杂的结构。特别是,用最少的虚弧绘制AoA网络图是NPhard问题,意味着在多数情况下,对同一工序系统无法绘制出统一的最简网络图,不同的人员绘制出的网络可能差别迥异,不利于分析、交流和应用。因此,如果简化图的结构,将网络图绘制的具有层次分明的多个点阶段和弧阶段--规范网络图,将有助于上述问题的解决。本文运用网络计划技术中时差与路线长的关系,设计出通过增加较少的虚弧将工序网络图等效绘制成规范网络图的方法。