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

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

冷热电联供微网优化调度通用建模方法

在分析典型冷热电联供(combined cooling,heat and power,CCHP)系统的基础上,提出描述其组成和结构的母线式结构,并围绕该系统结构设计了微网调度优化模型构架。在该结构中,选取电气、烟气、蒸汽、热水、空气作为基本母线,与源、负荷、储能和转换装置联接形成微网。使用该结构对各设备进行独立建模,有助于CCHP系统的灵活配置和通用建模。围绕该结构,建立联供型微网日前动态经济调度的0-1混合整数线性规划模型,最后通过测试算例证实了所提框架的合理性和有效性。

分析限界算法在企业动力系统优化中的应用

优化决策对于任何一个企业动力系统来说都是必要的。炼油厂蒸汽供应系统的优化问题是一个复杂的混合0-1整数线性规划问题:Z=CX,将Z转换为系列辅助约束关系(之和)后,可直接运用分支限界算法(结合反向搜索法)进行优化并分析,得到全局最优决策,这种方法对其他企业动力系统的优化同样适用。

考虑行人保护策略的交叉口信号配时优化模型

为促进平面交叉口的行人交通安全,本文基于美国国家电气制造商协会(NEMA)的双环相位标准,将行人专用相位(EPP)、行人同步保护相位(CYPP)以及行人前置相位(LPI)这3种行人保护策略整合到一起,以信号周期和行人-右转车的冲突点数量最小化为目标,构建交叉口信号配时优化模型。在假定交通参与者遵守信号规则的前提下,除LPI策略中远端行人与右转车冲突外,其余冲突点经模型优化后皆可消除,并且机动车的通行效率能够得到维持。该模型属于0-1混合整数线性规划问题(BMILP),可用分支定界法求解。选取南京市两个交叉口进行实例研究。结果表明:在交叉口几何尺寸及交通流量较小时,模型倾向于得到EPP方案,否则倾向于得到CYPP和LPI方案;在进口道设有直右共享车道或右转相位不易满足最大饱和度限制时,模型倾向于得到LPI方案。

一类单机排序问题的新伪多项式时间精确算法

本文以最小化所有工件的最大延误时间为目标,研究了带有工件释放时间和交付时间的单机排序问题。该问题是机器排序的经典基础性问题,是NP-hard问题。首先,从该问题的结构特征入手,通过揭示工件单机排序结构(各工件的排序位置)与工件最大延误时间(相比交付时间)之间的关联规律,从工件加工顺序链的视角考虑,建立了新的基于工件分配位置变量的0-1混合线性规划模型。该模型的结构特征具备更好的优化潜力。其次,结合Dantzig-Wolfe分解等整数优化理论和方法,对模型进行优化处理,进而开发出该单机排序问题的伪多项式时间精确算法。最后,通过仿真模拟测试验证算法的有效性。结果表明:该算法在计算该单机排序问题算例(特别是大型算例)的精确解方面具备显著的效率优势,例如,该算法能够在3000秒内计算出包含1200个工件规模的算例的最优解。

带时间窗约束的集装箱接驳运输问题模型研究

集装箱接驳运输是集装箱运输过程中的重要环节。针对带有时间窗约束的集装箱接驳运输问题,本文首先考虑四种集装箱接驳运输任务(进口重箱,出口重箱,进口空箱,出口空箱)的实际运输要求,确定其时间窗约束,其次,基于图论知识,采用一种确定的活动在顶点上的图的描述方法,将集装箱接驳运输问题转化为一个混合0-1线性规划模型,考虑其计算复杂度,设计了一种改进的遗传算法对该问题进行求解。最后给出算例,运用本文的求解方法进行计算,结果与其他方法相比较,本文所提出的算法比目前已知的最优解差了2.1%,但是计算速度提高了51.4%。总体上在目标函数值和计算时间上都较优。