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

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

雪灾救援物资车辆-直升机联合运送的调度问题研究

文章研究了雪灾救援中车辆与直升飞机联合运输应急物资的调度问题。在道路疏通能力与整体救援时间有限的情况下,首先决策需要疏通的道路,及其疏通顺序,对疏通后的需求点采用汽车运输补给,该阶段决策目标为汽车运输量最大化;然后调度直升飞机对各点疏通前的物资短缺以及未疏通的需求点进行物资运输,设计每架直升机的飞行路线与各点投放量,使得两个阶段运输完成后,最大化所有需求点中最小物资可维持时间。文章对两个阶段分别建立混合整数规划模型,并设计启发式算法,最后以西北某区域的路网结构为例,设计了数值算例。     

大型供应链设计的基本数学模型与算法研究

随着信息技术与全球经济一体化的发展,供应链管理成为全球管理科学的研究热点。本文在分析国内外各种关于供应链设计的数学模型与算法的基础上,提出了具有普遍性意义且简单易行的MIP供应链设计的数学模型以及求解供应链问题的有界变量广义上界算法。实例计算表明,提出的模型和方法是可靠实用的。     

旅行售货员问题的整数规划建模研究

本文分别基于无向图和有向图,建立了旅行售货员问题（Traveling Salesman Problem）的显式整数规划模型,应用整数规划软件包求解之可以方便地确定出售货员的最优售货旅行路线。进一步,本文还讨论了随机旅行售货员问题,建立了相应的确定型等价模型。通过举例说明了各种模型的有效性。最后,本文还讨论了旅行售货员问题的可能推广及其建模问题。     

一类可分解的0—1规划算法

本文提出了一类可分解的０－１规划算法，与常用的０－１规划相比，此算法有很多优越性，这些优越性通过仿真得以验证。最后，用此算法解决一种资源分配问题。     

一类应急物资调度的双层规划模型及其算法

应急物资的调度是应急管理中的一个重要分支,衡量其运作效果的两个最常用的指标是应急时间和应急成本,目前的建模大多都以多目标规划为主.但现实告诉我们,面对应急事件,应该在最短的允许时间奔赴现场,而成本与此目标相比要次之.为此,建立了单资源应急物资调度的双层规划模型,上层为时间目标,下层为成本目标,并将此模型的求解转化为若干个有限制的运输问题的求解,利于计算机实现.算例证明了算法的有效性.     

基于风险的考虑成本和允许等待的车辆运输调度问题研究

本文同时考虑了成本约束和允许等待情形,研究了最小化风险的车辆运输调度问题,其中运输风险是随时间不同而变化的,即研究在时间依赖网络中基于风险的有约束的运输路径选择问题,以及在选定路径的顶点上决定的出发和等待时间的综合问题。建立了相应的混合整数规划模型,设计了相应的算法,并分析了算法复杂性,最后通过算例验证了该算法的有效性和可行性。     

基于实物期权的项目组合投资决策研究

基于项目投资决策的可延迟性特征,将实物期权的决策灵活性思想引入到企业的投资组合决策中,建立了基于实物期权的0-1整数规划模型.模型以项目的期权价值最大化作为投资组合项目选择的标准,通过项目组合投资时机的灵活安排,实现了项目组合的总投资价值最大化.     

中国铁矿石期货市场的定价影响力研究——基于VEC-SVAR模型的实证分析

为探究中国铁矿石期货这一新兴市场的定价影响力状况以评价其对于中国铁矿石国际定价权的提升所起到的作用,本文从期货市场功能的视角,采用以VEC-SVAR模型为核心的研究方法,选取2013年10月至2016年3月的相关日度历史数据,对中国铁矿石期货价格与国内外现货价格间的动态联动及引导关系进行实证分析。结果表明：中国铁矿石期货价格与国内外现货价格之间存在高度关联性和长期均衡关系,已具备风险规避功能,可用于套期保值转移市场风险,但尚不具备有效的价格发现功能,无法对国内外现货价格的形成起决定和引导作用,定价影响力较弱,并未实质性地促进中国铁矿石国际定价权的提升;以TSI为代表的国际铁矿石现货价格指数占据绝对的定价权主导地位,但其高度的价格独立性和不透明的编制过程隐藏有价格操纵的可能性。     

面向新零售的生鲜连锁企业城市配送网络优化研究

城市配送网络优化是生鲜连锁经营企业实施新零售的关键环节,本文研究新零售背景下生鲜企业城市配送网络面临的多业态门店选址及末端需求点分配问题。本文系统考虑多业态零售门店选址布局及覆盖范围、冷链设施配置、冷藏品类选择等生鲜新零售特征构建非线性混合整数规划模型,并设计混合拉格朗日松弛算法求解模型,通过与CPLEX对比验证本文算法的有效性。根据典型生鲜连锁企业重庆果琳的实际数据,运用本文模型及算法得到重庆果琳多业态零售门店布局、门店线上订单覆盖范围、门店冷藏最优品类和门店冷链设施配置方案,并探讨需求规模变动、消费者自提意愿、线上订单规模和气温变化等因素对城市配送系统的影响。结果发现相比重庆果琳现有配送网络,优化方案平均成本降低2.52%;生鲜连锁企业损耗成本占总成本超过70%,配置冷链设施总成本仅降低0.32%;需求规模变动对城市配送网络及单位配送成本的影响较小;消费者自提意愿、线上订单规模和气温变化不影响城市配送网络结构且对总成本影响较小。     

基于极大团模型的多星多站测控资源调度方法研究

针对实际应用中大量卫星测控需求不能得到满足这一瓶颈问题,为缓解地面站测控资源有限与不断增长的测控需求数量之间的矛盾,研究多星多站测控调度问题。考虑卫星-地面站可见测控弧段间的冲突及地面测控设备转换时间约束,同时考虑同一测控设备上可能存在多个满足需求的测控弧段,以测控需求是否分配到某一测控弧段为决策变量,建立了多星多站测控调度0-1整数规划模型。针对传统0-1整数规划模型约束众多、规模庞大、难以求解的不足,本文提出了测控弧段区间图描述,基于区间图描述构建了测控调度极大团模型,大幅减少了约束数量,有效提高问题求解效率。为了获取区间图的所有极大团,设计了一个多项式时间(O(nlogn))的极大团获取算法,并从理论上证明了算法的复杂度和最优性。此外,针对存在升降轨特定类型测控数量要求的调度问题,本文对极大团模型进行了拓展,建立了相应的线性整数规划模型。实验结果表明,对于满足实际应用需求的周计划调度问题(测控需求数量≥9000),极大团模型能够在数分钟内得到单次测控需求调度问题最优解。对于多次测控需求调度问题,拓展的极大团模型也能高效求解,得到问题最优解或近似最优解,满足实际应用需求。相对于目前...     

考虑分时电价的多目标批调度问题蚁群算法求解

对同时优化电力成本和制造跨度的多目标批处理机调度问题进行了研究,设计了两种多目标蚁群算法,基于工件序的多目标蚁群算法(J-PACO,Job-based Pareto Ant Colony Optimization)和基于成批的多目标蚁群算法(B-PACO,Batch-based Pareto Ant Colony Optimization)对问题进行求解分析。由于分时电价中电价是时间的函数,因而在传统批调度进行批排序的基础上,需要进一步确定批加工时间点以测定电力成本。提出的两种蚁群算法分别将工件和批与时间线相结合进行调度对此类问题进行求解。通过仿真实验将两种算法对问题的求解进行了比较,仿真实验表明B-PACO算法通过结合FFLPT(First Fit Longest Processing Time)启发式算法先将工件成批再生成最终方案,提高了算法搜索效率,并且在衡量算法搜索非支配解数量的Q指标和衡量非支配集与Pareto边界接近程度的HV指标上,均优于J-PACO算法。     

救援物资跨区域调度双层规划模型——考虑幸存者感知满意度和风险可接受度

为减少幸存者的痛苦、提高灾害响应效率和降低各种损失,聚焦于跨区域救援物资反应性调度主从优化问题.综合考虑救援物资调度与分配网络中不确定供应-需求-行程时间、公平性分配原则、幸存者多层次异质性与风险可接受度限制、利益相关者的层级或纵向"府际"关系、需求可拆分、多灾点、多供应点和多运输模式等特征;构建了上层最小化加权行程时间总和,下层最大化加权感知满意度的双层整数规划模型.通过分析模型的特征,设计了以互补松弛条件为基础的原始-对偶算法对其进行求解.最后,以汶川地震为算例,验证了所提出模型与求解策略的可行性与有效性.     

模糊信息动态车辆调度优化问题研究

针对车辆调度中的模糊信息问题,以车辆模糊行驶时间以及顾客模糊预约时间为模糊信息参量,采用细分顾客类别以吸收配送者知识系统的方法,分别以物流企业效用最大化和顾客效用最大化两种决策目标构建了2类模糊信息动态车辆调度优化模型,并给出了求解该类问题的蚁群算法.仿真试验分析了决策参数的变化对2类模型计算结果的影响,并给出了相关参数制定的依据.     

基于协同效应的知识创新团队伙伴选择方法

在知识创新团队的伙伴选择问题中着重考虑了伙伴间的协同效应信息。首先,分析了伙伴之间的协同关系与协同效应,描述了考虑多个协同效应评价指标的知识创新团队伙伴选择问题;然后,建立了团队伙伴选择的数学模型,该模型是一个0-1二次整数规划问题,为了求解该问题,开发了一种GRASP启发式算法;最后,通过一个实例分析说明了所提出方法的可行性和实际应用价值。     

考虑订单类型的两台平行批处理机在线调度模型研究

探讨了两台平行批处理机的调度决策问题,着重考虑了订单具有不同加工类型、同一批次只能加工相同类型的订单以及机器批容量有限的调度情形。针对订单实时到达且需要立即决策是否接受的实际情景,运用在线理论构建了平行机批调度在线模型。证明了该问题的竞争比下界为2Bw/（1+√Bw）,其中B和w分别表示批容量和单个订单的最大完工收益。进而设计给出了收益阈值算法PT并证明其对于订单具有紧交货期限的情形竞争比为2（1+Bw）/（1+√Bw）;对于非紧交货期限的情形,证明了修正的PT算法具有竞争比为1+2（1+Bw）/（1+√Bw）。     

基于银行授信额度的Max-NPV项目调度问题研究

本文对基于银行授信额度的Max-NPV项目调度问题进行研究.首先界定研究的假设条件并对文中所用到的符号进行定义;随后采用基于事件的研究方法构建了问题的整数规划优化模型;鉴于问题的NP-hard属性,设计了双层模拟退火搜索循环嵌套的启发式求解算法;最后对一个算例进行了求解分析,并讨论了银行授信额度及客户支付比例对项目收益的影响.结果表明:随着银行授信额度的提高,承包商安排项目进度自由度的增加使得其净现值得到改善,在支付比例较低的条件下项目完成时间也随之提前;当客户支付比例提高时,项目净现值单调上升,而项目完成时间呈先提前后延迟的变化趋势.     

灾后模糊需求情境下考虑救援公平性的应急物资调度问题模型与算法研究

在重大灾害发生初期,由于受灾地区对应急物资的需求激增,合理的应急物资分配有助于提高救援效率。本文考虑受灾点应急物资需求具有模糊属性,将需求物资用三角模糊数表示,以受灾群众损失最小、体现救援公平性的受灾点应急物资满意度方差最小及应急救援成本最小为目标,构建了灾后初期应急物资调度的多目标模糊优化模型,并采用改进的粒子群算法对模型进行求解。该算法在粒子群算法的基础上采取天牛寻找食物的策略,将单一粒子分为左、中、右三个粒子,并结合单纯形算子和模拟退火策略,使算法不易陷入局部收敛。本文通过算例进行模拟实验表明,所提出的模型和算法可以有效解决重大灾害事件下应急物资的合理分配问题,且改进算法的性能更优。     

电子商务下基于改进两阶段算法的有时间窗车辆调度优化

为满足电子商务下的物流配送需求,将传统车辆调度模型进行修改,将目标函数改为基于费用最小,在约束条件中增加时间约束、货物容积约束、车辆最大工作时间、多种车型、载重量限制和最大行驶距离等,以提高模型的适用性和通用性。由于有时间窗的车辆调度问题是NP难问题,采用改进两阶段算法进行求解。即第一阶段用模糊分层聚类法将客户群分成若干区域,在每个区域又用扫描算法分解成若干符合约束条件的小规模子集;第二个阶段对各个分组内客户点,就是一个个单独TSPTW模型的线路优化问题,因此,采用改进混合遗传算法进行优化求解,最后的算例仿真表明了算法的有效性和可行性。     

基于粒子群算法的短期汽车租赁服务的调度优化问题研究

汽车租赁服务是一个服务分布网络化、客户需求不确定与汽车租赁服务短期供给不确定的行业,这就使得汽车租赁服务商会面临复杂的日常运营决策问题。混合了车辆升级的统一调度方法是降低供给与需求不确定的有效解决方案,可以提高汽车出租率和车辆利用率,满足客户需求,增加服务提供商的收入。本文正是基于此,提出了使用类子群算法求解的车辆分配、升级和调度优化的方案,算例表明这种方法可以有效提高汽车租赁服务的收入。