长江上游集装箱码头泊位——锚地系统配置策略

针对内河集装箱运输增长与内河航道制约所导致的集装箱运输系统运作效率与航运安全问题,讨论长江上游集装箱码头泊位-锚地系统最优配置策略.通过构建码头泊位-锚地系统的船舶候泊排队服务模型,推导出队长水平状态的稳态概率分布,计算出平均等待队长,并建立泊位-锚地系统配置模型,采用数值算例考察相应的最优配置策略和锚泊溢出概率.     

集装箱码头泊位计划的鲁棒优化模型

针对集装箱码头作业中的不确定性因素,构建泊位计划的鲁棒优化模型与算法,目的是降低不确定性因素对集装箱码头作业系统的影响。首先,提出泊位计划鲁棒性度量指标,利用算例对各指标的效果进行分析。在此基础上,设计泊位计划鲁棒优化的两阶段优化算法。算法的第一阶段不考虑泊位计划的鲁棒性,以船舶总延误时间最小为目标;算法的第二阶段以所选择的鲁棒性指标最大为目标,以第一阶段获得的船舶总延误时间为约束条件,获得鲁棒调度方案。最后,研究作业资源(装卸桥数量)的变化对泊位计划鲁棒性的影响。算例分析表明,权重松弛量是有效的度量泊位计划鲁棒性的指标,两阶段算法可以有效解决泊位计划鲁棒优化问题。     

预知信息下集装箱码头资源联合调度在线策略研究

探讨了有限预知信息下的集装箱码头泊位与岸桥联合调度over-list在线模型,当分配每个船舶服务请求时预知后续k≥2个请求,要求完成所有请求的最大完工时间最小。着重考虑了由3个离散泊位组成的混合型泊位、6个岸桥以及只有两种请求的联合调度模型,证明了任意k≥2个请求预知能力下确定性在线策略的竞争比下界为9/7;同时,设计了k=2时的在线联合调度策略并证明其具有最优竞争比9/7,表明有限的预知能力即可实现在线策略最优调度效果,这也为集装箱码头资源调度实践中的策略设计提供理论依据。     

考虑码头内外堆场竞争的集装箱堆存定价模型

针对由于集装箱吞吐量增加造成翻箱成本增加与码头堆场拥堵,考虑内外堆场竞争,构建集装箱堆存定价模型,研究内外堆场竞争下的堆存定价决策和货主移箱决策,分析码头堆场操作成本、场外堆场运输成本、货主需求参数和码头堆场收益的内在关系。算例结果表明:一旦过了免费期立即移箱到场外堆场,货主成本最小。随着场外堆场运输成本的增加,码头堆场的堆存定价和箱量增加,提高码头堆场收益。随着码头堆场操作成本降低,码头堆场堆存价格随之下降,但码头堆存箱量增加,提高码头堆场收益。此外降低堆场定价对货主需求的影响参数以及提高运输成本对货主需求的影响系数,有利于提高码头堆场收益。     

兼顾成本与时间保证率的泊位及岸桥协同调度优化

针对集装箱班轮根据船期表按计划到离港的运行规律以及港口企业追求低运营成本的需求,本文以集装箱班轮按计划离港保证率最大和码头作业成本最低为目标,构建了泊位及岸桥协同调度多目标优化模型;设计了叠加式局部搜索算法,将其嵌入到带精英策略的非支配排序遗传算法中,经过相互交叉反馈运算,得到Pareto非劣解;采用“性价比”的概念和量化方法,选择出对港口和船公司的利益偏向最小的实施方案,解决了在Pareto解集中寻优的问题。最后,以大连港集装箱码头的生产实际为例,验证了上述优化模型及算法的合理性和有效性。     

提前预知信息的在线分批排序问题

研究工件可提前预知信息的在线分批排序问题, 工件的预知信息时间依时间到达, 目标为极小化最大完工时间. 已知从工件的信息可预知到该工件可加工需要时间~$a$, 所有工件的最大加工时间为~$p_{{rm max}}$, 多个工件可以作为一批被机器同时加工, 批的加工时间为该批工件中最长加工时间. 对于批容量无限的单机问题给出一个在线算法~$gamma H^infty$, 并证明其竞争比和问题的下界都为~$1+gamma$, 其中~$gamma=left(-1+sqrt{1+frac{4p_{{rm max}}}{p_{{rm max}}+a}}right)/2$, 进而算法是最优的.     

考虑泊位疏浚的连续型泊位和动态岸桥联合调度

针对集装箱码头泊位需要定期维护的实际特征,研究了泊位疏浚情况下连续型泊位和动态岸桥联合调度问题。首先,建立了一个以船舶周转时间最小为目标的整数线性规划模型;其次,针对问题特性设计了三种启发式算法。为了分析泊位疏浚对码头工作的影响并验证模型正确性和算法有效性,分别对未考虑泊位疏浚和考虑泊位疏浚两种调度情形,进行了小规模与大规模问题输入的多组测试。三种算法在小规模输入上均取得了相同于CPLEX的精确解,从而验证了算法的有效性;进一步通过对比分析这些算法在大规模输入中的运行结果,验证其有效性能。     

基于泊位偏好与岸桥干扰的泊位和岸桥分配

泊位和岸桥是集装箱港口资源中最紧缺的资源,合理的泊位分配和岸桥调度可以提高集装箱港口的资源利用率和港口的运作效率和效益。针对泊位偏离和岸桥工作损失两个因素,文章建立了集装箱港口泊位和岸桥的混合整数线性规划模型;运用采集自宁波某典型集装箱港口的数据,用Gurobi优化软件和两阶段启发式算法对模型进行了求解;对计算结果进行了经济性分析。计算结果表明:该港口的岸线资源利用率为46%时,1000m~1600m基本没被利用;18台岸桥要比16台岸桥的目标值更优,求解时间更短,而且18台岸桥的平均利用率为80%,为此,建议该港口再增加两台岸桥。同时发现:随着船舶规模的增加,Gurobi优化求解的时间增长较快,而两阶段启发式算法仍能在很短时间内求得准优解。     

一种解决集装箱港口拖车调度的混合策略

集装箱码头作为集装箱船舶与其它运输节点之间的枢纽,在不断增长的全球贸易中起着极其重要的作用.由于多种因素影响着集装箱码头的服务效率,从而使其成为了商界和学术界研究的热点.本文针对集装箱码头中的拖车调度问题,对于当某辆拖车完成一项作业任务后,如何去寻找下一个装卸任务的问题,提出了一个多因素的在线调度策略,该策略在针对我国大多数港口的现有布局和信息现状的基础上,综合考虑了拖车空驶和距离平衡多种因素,建立了综合评价函数,并应用评价搜索和离散事件仿真方法对评价函数进行了优化计算.在相关理论分析基础上,通过比较本文的调度策略和港口传统调度策略,我们认为本文的调度策略在缩短船舶停留时间和减少拖车空驶上具有十分明显的效果.     

基于改进模拟植物生长算法的集装箱码头插船调度优化

为解决临时接受计划外船舶到港作业的插船调度问题,建立了综合考虑港口安排插船作业的成本最小优化模型,将模拟植物生长算法(PGSA)改进后进行求解。经过对实际案例进行计算分析后表明,所建模型和算法可以有效解决上述问题并取得了较好结果。为验证算法的有效性,同时引入遗传算法进行计算对比,结果显示经改进的PGSA在求解过程中具有较好的收敛速度与精确度。采用本文建立的模型和算法能够快速解决临时插船的调度调整问题,为集装箱码头在特殊情况下泊位调度优化提供了解决问题的思路和方法。     

单机上带有可变前瞻区间的分批在线排序问题

本文研究单台无界平行批处理机上带有可变前瞻区间的在线排序问题。工件按时在线到达,目标是最小化时间表长。在时刻$t$,在线算法能够预见到$（t,t+Delta（t）]$内到达工件的信息,这里前瞻区间的长度$Delta（t）=beta p_{max}（t）$并非定长,其中$p_{max}（t）$表示在$t$时刻及之前到达工件的最大加工时长,$betain（0,1）$是常数。本文对于工件加工时长的一般情形,给出了当 0<β≤1/6 时最好可能的在线算法;对于工件加工时长被限制在一个区间的情形,给出了当 0<β<1 时最好可能的在线算法。     

单机上带有可变前瞻区间的分批在线排序问题

本文研究单台无界平行批处理机上带有可变前瞻区间的在线排序问题。工件按时在线到达,目标是最小化时间表长。在时刻$t$,在线算法能够预见到$（t,t+Delta（t）]$内到达工件的信息,这里前瞻区间的长度$Delta（t）=beta p_{max}（t）$并非定长,其中$p_{max}（t）$表示在$t$时刻及之前到达工件的最大加工时长,$betain（0,1）$是常数。本文对于工件加工时长的一般情形,给出了当 0<β≤1/6 时最好可能的在线算法;对于工件加工时长被限制在一个区间的情形,给出了当 0<β<1 时最好可能的在线算法。     

两台恒速机上的MapReduce排序算法研究

研究源自于MapReduce系统的一类排序问题。给定两台恒速机和一组按列表到达的工件,每个工件包含两类任务：Map Task和Reduce Task。假设Map任务和Reduce任务都是不可中断的,Map任务可以并行处理,即可以任意分割成若干小的任务并在两台机器上同时处理,而Reduce任务只可以在单台机器上处理。一旦工件到达,必须为其指派机器和开工时间,目标是使得最后完工时间最小。对LSc算法的竞争比进行了分析,得到其一般情形下的竞争比当$sgeq（1+sqrt{5}）/2$时为$1+1/s$,否则为$1+s/（s+1）$。而当每个工件$J_j$都满足其Map任务总长大于等于Reduce任务总长时,其竞争比当$sgeq（1+sqrt{3}）/2$时不超过$1+1/（2s）$,否则为不超过$1+s/（2s+1）$。     

两台恒速机上的MapReduce排序算法研究

研究源自于MapReduce系统的一类排序问题。给定两台恒速机和一组按列表到达的工件,每个工件包含两类任务：Map Task和Reduce Task。假设Map任务和Reduce任务都是不可中断的,Map任务可以并行处理,即可以任意分割成若干小的任务并在两台机器上同时处理,而Reduce任务只可以在单台机器上处理。一旦工件到达,必须为其指派机器和开工时间,目标是使得最后完工时间最小。对LSc算法的竞争比进行了分析,得到其一般情形下的竞争比当$sgeq（1+sqrt{5}）/2$时为$1+1/s$,否则为$1+s/（s+1）$。而当每个工件$J_j$都满足其Map任务总长大于等于Reduce任务总长时,其竞争比当$sgeq（1+sqrt{3}）/2$时不超过$1+1/（2s）$,否则为不超过$1+s/（2s+1）$。     

具有等级约束的三台机排序问题的可中断在线算法

研究具有等级约束的三台机在线排序问题．机器和工件的等级数均为1或2,工件只能在等级数不超过自身等级的机器上加工,且加工允许中断,目标是极小化最大工件完工时间．如果有两台机器等级为1,给出竞争比为3／2的在线算法,并证明算法是最好可能的;如果只有一台等级为1的机器,也给出竞争比为3／2的在线算法．     

工件满足一致性的同类机在线分批排序问题

研究了工件满足一致性,批容量无界的两台同类机在线分批排序问题,目标为极小化工件的最大完工时间和极小化工件的最大流程时间,三元素法分别表示为Q_2|r_ir_j?p_i≤p_j,B=∞, on-line|C_(max),Q_2|r_ir_j?p_i≥p_j,B=∞, on-line|F_(max).不失一般性,假设第一台机器速度为1,第二台机器速度为s,s≥1.对于上述两类问题设计了一个在线算法,并分析了算法竞争比的上界.对第一类问题该在线算法的竞争比不超过s+α,这里α为α~2+sα-1=0的正根,特别地,当s=1时,该算法的竞争比不超过1.618.对第二类排序问题,该在线算法的竞争比不超过1+1/α.     

带两个服务等级的三台机最优在线算法

研究了带服务等级约束的三台平行机在线排序问题.每台机器和每个工件的服务等级为1或者2,工件只能在等级不高于它的机器上加工,即等级为1的工件只能在等级为1的机器上加工,等级为2的工件可在所有机器上加工.每个工件的加工时间为一个单位,目标是极小化所有工件的总完工时间.考虑两种情形:当一台机器等级为1,两台机器等级为2时,给出了竞争比为17/14的最优在线算法;当两台机器等级为1,一台机器等级为2时,给出了竞争比为43/36的最优在线算法.     

工件可拒绝排序问题综述

可拒绝排序问题是兴起于2000年前后的有代表性、应用背景极强的的排序问题,是经典排序问题的衍生和推广.经典排序问题总是要求每个工件必须被加工,然而在实际中由于某些特殊原因,决策者会选择拒绝加工某些工件.把允许工件被拒绝的这类问题称为工件可拒绝排序问题,有的文献称之为外包的排序问题.这些问题不仅具有很强的应用价值,在理论上也有重要的意义.近年来该领域受到越来越广泛的关注,新的研究成果不断涌现.现就离线、在线情况下的可拒绝排序问题的进展情况作了全面介绍,展示了已有的研究成果和新的问题,给出了此方面的比较重要的参考文献,旨在帮助感兴趣的读者迅速了解问题研究的进展并由此进入此研究领域的前沿.     

带有交易费用和持有成本的局内采购管理模型竞争分析

采购管理是企业经营活动的一个重要组成部分,更加有效的采购管理策略可以大大减少采购费用,对于企业的经营业绩非常重要。在现实的经济活动中交易费用和持有成本在企业管理费用中占很大一部分比率,而采购过程影响着交易费用和持有成本。所以在前人研究的基础上,将交易费用和持有成本引入到局内采购管理模型中,使得运用该策略无论以后采购价格如何变化,局内人的采购成本总是对应局外问题最优采购成本的一定比例c之内,并得到c与原模型相同。但是引入交易费用和持有成本后每天的采购量将发生变化,原模型是在不考虑交易费用和持有成本的前提下得得到的每天采购量和最优竞争比,如果考虑到现实经济活动中不可忽略的交易费用和持有成本,仍然按照原模型来确定每天的采购量来采购就不能得到最优竞争比c。所以本文考虑到了交易费用和持有成本,并得到和原模型不同的每天采购量,并求出最优竞争比c。