具有学习效应的单机可控加工时间排序问题研究

在经典排序问题中，工件的加工时间往往是一个常数，但在现代生产过程中，工件的加工时间受许多因素的影响。因此，研究工件具有学习效应的单机可控加工时间排序问题，其中工件的加工时间是其所在位置的函数，且与加工时间的控制变量有关。目标是求出最优的加工时间控制变量和最优的排序使得目标函数最小，目标函数包括极小化时间表长与控制费用的和、极小化总完工时间与控制费用的和、极小化总完工时间偏差和与控制费用和。证明他们都能转化为指派问题，从而多项式时间可解。并给出数值例子来说明问题是如何求解的。     

加工时间依赖工件位置的单机成组排序问题

排序问题是一类重要的组合优化问题,现代排序问题突破了经典排序问题的种种假设,有着越来越广阔的应用前景。对加工时间依赖于工件位置的单机成组排序问题进行了研究,讨论了成组技术中,要求同一组内工件必须连续加工,加工时间的函数变量是工件所在的加工位置,目标函数分别为极小化最大完工时间与总完工时间。分别给出其多项式时间的最优算法。     

加工时间为随机变量的排序问题

在实际排序问题中,工件的提前完工或者拖期,都将会导致某种损失。因此,使得工件完工时间的偏差之和最小,便是这类排序问题的重要目标。本文证明了,当满足一定的假设条件,不少关于加工时间为确定位的排序问题的结果,可以推广到加工时间为随机变量的排序领域,尤其当σ_i~2=σ~2或者μ_i=μ时,这一问题的最优解是关于加工时间的二阶原点矩呈V形结构的。本文还给出了有悖于所给结果的特例,同时指出了这一领域的进一步的研究方向。     

多机场终端区进离场交通流协同排序方法

针对大都市及都市圈飞行冲突、空域拥堵和航班延误日益严峻的现状,研究了多机场终端区进离场交通流协同排序问题。综合考虑尾流间隔、跑道间隔、时间窗、进离场容量等约束限制,从时空多维角度引入航班满意度概念,建立了多机场终端区进离场交通流协同排序模型,设计了带精英策略的非支配排序多目标遗传算法(NSGA-II),寻求多机场终端区进离场排序问题的Pareto最优解。实例验证表明,所提方法可对多机场终端区进离场交通流进行优化排序,有效降低航班延误总时间,显著提高航班总满意度,并实现多机场系统对终端区空域资源的公平均衡使用。与经典的先到先服务策略相比,协同排序策略的整体优化效果较为显著,其中航班延误时间得到了一定的降低。     

多机场终端区进场航班协同排序方法

为有效缓解大都市圈机场群日益严重的空域拥堵和航班延误现状,系统研究了多机场终端区进场航班协同排序问题。通过深入剖析多机场终端区时空运行特性,综合考虑移交间隔、尾流间隔和多跑道运行间隔等约束限制,科学权衡安全、经济和公平等各方利益需求,引入多元受限时间窗的创新理念,建立了多机场终端区进场航班协同排序模型。结合多目标优化及遗传算法基本理论,设计了带精英策略的非支配排序遗传算法,寻求多机场终端区进场航班协同排序问题的Pareto最优解。仿真实验表明,模型可对多机场终端区进场航班进行优化排序,显著降低航班延误总时间,有效增强多机场空域资源使用公平性。与经典的先到先服务(FCFS)策略相比,协同排序策略优化效果较为显著,其中航班延误时间减少了31.0%,所提方法可显著缓解大都市圈机场群航班延误现状,有效提升航空运输服务品质。     

基于改进粒子群算法的离场航班排序

航班离场过程中,以时间或经济损失最小的单目标排序会导致延误时间分配不均和多目标排序在求解时存在算法收敛速度慢、易于陷入局部最优的缺陷,导致计算效率低。为解决这一问题,基于航班优先级、尾流间隔、航班延误时间、航班延误标准差构造航班离场排序模型,对粒子群算法的惯性权重和学习因子采用动态调整的改进策略。以厦门高崎机场非拥挤和拥挤场景下的共4 h离场航班进行优化排序验证,结果表明：与先到先服务(FCFS)方法、惯性权重线性递减粒子群(LDWPSO)算法相比,文中方法非拥挤场景下延误总时间减少了72%,26%,延误标准差减少了27%,28%;拥挤场景下,较FCFS延误总时间减少69%,延误标准差减少68%,与LDWPSO算法相比,优化效果上无明显差异,但在解空间的迭代收敛速度更快,达到最优罚值的迭代速度提升了55.6%。     

蚂蚁算法在订单排序中的应用

在分析印刷业工艺瓶颈工序的基础上，将印刷业订单排序问题简化为单机排序问题，并建立了该排序的数学模型。同时以最小化订单的提前／拖期为目标，将蚂蚁算法合理的应用于该模型中。该算法已经应用于实际的印刷业生产排序中，并且取得了较为良好的效果。     

基于空中交通密度的进场航班动态协同排序方法

为适应协同决策（CDM）需要，考虑空管、航空公司和机场的诉求，对进场航班动态协同排序问题进行了系统的研究。设计了一种进场航班动态排序方法，提出了一种时隙交换方法，建立了基于空中交通密度的进场航班协同排序模型，设计了精英保留的遗传算法和带精英策略的快速非支配排序遗传算法以求解所建模型，寻求进场航班动态协同排序的最优解。仿真结果表明，较基于滚动时域控制（RHC）方法，动态协同方法所得结果与排序开始时间无关，所需排序次数平均减少26.4%，且排序效率更高。较先到先服务（FCFS）方法，动态协同方法在高密度条件下各排序阶段最后一个进场航班的落地时间平均提前199.8 s；中密度条件下各排序阶段航班延误总时间平均减少29.9%，航班延误均衡性平均提高34.4%；低密度条件在航班正常率及航班延误公平性得到保证的前提下，满足时隙交换规则的排序阶段均增加了1种进场航班排序模式。所提方法可对进场航班进行优化排序，显著提高跑道容量，有效提升航班延误均衡性和航班延误公平性，契合协同决策理念，可实现三方协同排序。     

基于管制习惯的多跑道机场离场航班排序

针对我国航空迅速发展致使终端区空域拥挤以及航班延误问题,研究了繁忙多跑道机场的离场航班排序问题,以缓解终端区空域拥挤和减少航班延误及提高跑道利用率。将管制习惯因素引入到离场航班的排序中,根据飞机尾流间隔的要求,建立基于管制员管制习惯的多跑道机场离场航班排序模型。针对机场小规模的离场航班流量,采用穷举法求解,并用算例进行仿真验证。结果表明,与先到先服务排序方法相比,经算法排序后的总延误时间减少了近30％。     

基于拉格朗日松弛算法的终端区飞机排序研究

终端区飞机排序问题是减少航班延误、降低成本的关键技术.考虑机型运行成本和飞机总延误时间,建立一个0~1整数规划模型.因其是一个组合优化问题,多约束相互制约,采用拉格朗日松弛算法将复杂约束转换为线性约束进行求解.仿真结果表明,求得的进近队列延误小、延误成本低、无冲突,且拉格朗日松弛算法计算得到的结果更为可靠,符合实际运行需求,结果优于传统的启发式算法.