单台和多台机器可解的误工排序问题

本文讨论带有子集约束的单台和多台机器使误工工件个数为最少的排序问题，提出两个多项式算法求其最优解。     

考虑学习效应的最小化延误总时间的单机批次排序问题

一些生产场景中,工件以批次作业的形式被安排生产,工件批量大、加工工序基本相同,所以标准工时相同,而且实际加工时间会受到学习效应的影响.为此,讨论学习效应的最小化延误总时间的单机批次排序问题,对该问题建立数学模型.该问题属于NP-hard问题,采用动态规划算法(DP)和模拟退火算法(SA)求解该问题,通过实验分析不同规模时DP的执行时间与SA的执行时间和求解误差的变化趋势,比较SA与其他实践中常用的经典规则的求解效果.最后得出DP适合批次数小于13的小规模问题,可以得到精确解;与经典规则相比,SA至少可以使目标函数降低20%,表明SA算法具有有效性.SA解决大规模问题时效果较优,并得出SA的执行时间和误差随着控制参数改变的变化趋势.     

灰色随机多准则决策的优劣势排序法

针对准则值具有灰色性和随机性两种信息不确定的多准则决策问题,提出一种灰色随机多准则决策方法.通过对灰数与白数比较的定义,将随机支配规则推广到对灰色随机变量型准则值的处理中,得出方案之间的随机支配关系;利用一般性准则对该随机支配关系进行转换,构建出优势矩阵和劣势矩阵,得出每一方案的优势流和劣势流,进而确定出方案的排序.最后通过算例说明了所提出方法的可行性和有效性.     

Lp范数下2台机器并行工件在线排序问题研究

本文研究一类并行工件平行机在线排序问题。给定2台平行机和一组按列表到达的并行工件,对每一到达的工件进行机器指派和确定开工时间,使得机器完工时间的lp范数最小。本文首先分析了LS算法的竞争比,其值为2;其次证明了任何在线算法的竞争比不小于4/3。     

一个期望时间为O（N）的递归分组排序

1982年,Akl等人提出桶排序算法；若排序文件中的数据服从概率分布,其密度函数有界,则桶排序的平均工作量为O(N),特殊的,若排序文件中的数据服从均匀分布,则桶排序的平均工作量也为O(N)。但当数据服从正态分布时,由于数据范围无界,桶排序的平均工作量大于O(N)。     

基于随机森林和自适应随机排序的昂贵多目标进化算法

针对昂贵约束多目标离散优化问题,提出一种基于随机森林和自适应随机排序的昂贵多目标进化算法(a random forest and adaptive stochastic ranking based multi-objective evolutionary algorithm,RFASRMOEA).为了提高代理模型对离散问题的近似精度,RFASRMOEA采用随机森林作为代理模型辅助进化算法进行搜索.同时,为提升综合性能,提出一种基于平衡适应度评估策略和自适应概率操作的自适应随机排序机制.具体地,平衡适应度评估策略利用种群迭代信息结合所设计的基于目标转移的多样性评估和基于余弦的收敛性评估,充分发掘种群个体潜力.而自适应概率操作通过动态调整随机排序机制的关注点,使得算法在前期探索更多可行域而后期迅速收敛于可行域,进而平衡约束条件的满足与目标函数优化之间的冲突.在测试问题上的实验结果表明,所提出算法在处理昂贵约束多目标离散优化问题时具有较高的竞争力.     

单选题随机排序算法及PHP&MySQL程序实现

论述了网络考试系统中单选题的随机排序和4个选项的随机排列。阐述了算法的基本思想,较详细介绍了用PHP&MySQL编程语言的程序实现。     

过饱和状态下的单交叉口最小延误信号周期模型

由于现有单交叉口信号配时方法主要适用于低饱和交通状态,本文以过饱和交通状态作为研究对象,利用定数理论分析了信号交叉口进口道的车辆到达与驶离规律,建立了信号周期与延误时间之间的数学模型,推导了单交叉口最小延误的信号周期计算公式.以某个四相位交叉口为例,针对3组不同流量比的过饱和交通状态,分别获取了延误时间与信号周期之间的变化曲线,计算了最小延误所对应的最佳信号周期,并利用VISSIM微观交通仿真软件,仿真得到了3组不同流量比情况下的延误时间.仿真结果表明:在各组流量比设置下,延误时间的理论计算值与仿真实验值相一致,有效验证了该模型的准确合理性,为解决过饱和状态下的交叉口信号配时优化问题提供了理论指导依据.     

基于学习排序的多分类标签排序方法研究

学习排序是利用机器学习技术来对搜索结果进行排序的技术。它在包括信息检索与数据挖掘等技术在内的众多应用领域中具有重大作用,因此近年来备受关注。学习排序通常假设每个培训实例都与一个可靠的标签相关联产生列表,但并不假定此列表是完整的或一致的。通过结合广义线性模型和Plackett-Luce(P-L)模型,提出一种基于实例的解决多分类标签的排序方法。目标是训练学习一种排序功能,排序功能通过训练提出一种最大似然估计方法。该方法估计标签排序,并迭代地训练排序功能,该功能可以在整套标签上产生全部排序。先利用广义线性模型对标签进行分类,再用P-L模型对各类别的标签进行排序,最后利用最大似然估计的方法对框架模型进行优化处理。该方法在不完整的训练数据的情况下,较其他模型方法在准确性上提升5%。     

基于团簇随机连接的CliqueNet航班延误预测模型

针对目前民航运输业延误率较高,而传统算法难以解决高精度延误预测的问题,提出一种基于随机连接团簇网络（CliqueNet）航班延误预测模型。该模型首先对航班数据和相关气象数据进行融合;然后,充分利用改进后的网络模型对融合后的数据集进行特征提取;最后,使用Softmax分类器进行航班离港延误各等级的高精度预测。模型的主要特点是：在团簇特征层的随机连接,以及在转换层引入通道和空间注意力残差（CSAR）模块。前者以更为有效的连接方式传递特征信息;后者则对特征信息进行通道和空间维度的双重标定,以提高准确率。实验结果表明,对融合数据进行预测,引入随机连接和CSAR模块后,新模型的准确率分别提高了0.5%、1.3%,最终准确率能达到93.40%。     

到达时间依赖于资源分配的单机排序问题*

研究了具有线性退化及学习效应作用下的单机排序问题,对于工件的到达时间是其资源消耗量的正的严格单调递减函数时,考虑了总资源消耗量限定情形下最大完工时间极小化问题,给出了相应的最优算法;也考虑了满足工件最大完工时间限制的条件下极小化资源消耗的总量问题,提出最优资源分配方案。     

基于一类特殊问题的排序算法

本文提出了一类特殊问题的拓序算法，其特点是在内排序中关键字与数组下标作映射或链接处理，不实施反复比较与交换关键字的操作，时间复杂性达到O（N）；在外排序中，文件输入／输出次数减少，提高了效率 。这类算法适宜今后在相关大规模信息处理中广泛应用。     

一种新的随机游走的异构网络节点排序算法研究

异构网络中往往包含多种不同类型的节点。为了满足用户对不同类型节点的检索需求,需要对不同类型的节点进行排序。同时鉴于用户对不同类型节点的检索需求不同, 提出了一种基于随机游走的异构网络节点排序算法,以提高检索结果的性能。首先,对包含用户、图片和文本内容的异构网络进行了形式化描述。其次,对异构网络中节点之间的相似性进行了定义,并提出了一种包含不同类型邻居节点的相似性计算方法。接下来,基于随机游走思想提出了节点重要性的计算算法,并分析了随机游走模型中偏好向量的选取方法。最后采用大量真实数据进行了实验验证,结果证明了提出的方法在处理信息检索请求时的有效性。     

基于关键飞行资源的航班延误波及DAG模型的研究

由于一架飞机和一个机组在一天中通常要执行多个前后衔接的航班,因此一个航班延误可能会导致下游多个航班发生延误.本文重点研究飞机、驾驶员机组和乘务员机组等关键飞行资源对航班延误波及的影响.首先根据航班计划和机组计划构建以一个初始延误航班为根顶点的全体下游航班DAG,然后给出算法以求解各顶点属性值,通过对初始DAG的顶点进行"染色"构造出航班延误波及DAG,得到完整的下游航班波及延误情况,结合提供的延误航班指数、延误时间指数等综合指标,为航班延误问题提供了有效的定量分析手段.最后,通过仿真计算和分析,提出预防和处理航班延误的建议.     

单机随机调度中机器的失效分析

随机调度问题已越来越受到人们的重视,单机随机调度的研究已经取得了不少结果,而当机器失效时会出现什么现象呢?这是实际生产中更关心的问题.本文考虑了机器允许失效时的单机随机调度问题,在部件的加工时间,机器的寿命和修复时间都服从指数分布的情况下,得到并证明了使目标函数∑ωjCj,∑ωjUj,∑ωjTj最小的最优调度策略与机器是否失效无关这一更具一般性的结论.     

图最小线性排序问题的Memetic爬山算法

针对图最小线性排序问题优化目标的特性及其可行域总是连通的特点,提出了一个新型的Memetic爬山算法。在Memetic算法框架及其主要算子内部流程中同时结合爬山法,并在主要算子内部采用迂回爬山策略。设计可变型顶点-边-邻接交叉算子,改进使用基于贪心随机自适应搜索过程的初始解生成算法,采用动态更新等保持种群多样性策略。公认测试集的实验结果表明,与最近的两阶段模拟退火算法(two-stage simulated annealing,TSSA)和分散搜索与路径重链接算法(scatter search and path relinking,SSPR)相比,该算法具有更好的整体性能。在相近平均运行时间内,该算法近优解质量分别平均提高1.6%和2.01%,21个测试例子中13个获得当时最好的近优解,比TSSA算法多出4个,比SSPR算法多出2个。     

基于可变优先级的航班时隙排序

空中交通拥塞日益严重．这不仅带来大量的经济损失．同时给飞行安全带来隐患。地面等待策略作为短期措施中缓解交通拥塞的有效方法．其核心是如何解决时隙分配问题。传统的时隙分配算法（RBS和Compression算法）采用的是“先排班先服务”的原则,且没有考虑到航空公司的公平性。针对RBS和Compression算法的局限性．采用一种新的优先级设定方法,在同时考虑航空公司公平性、不同类型航班延误损失的不同、同类型航班载客量不同以及同一航班等待时间不同的基础上对航班进行优先级设定。采用分支定界法求解最优解。使用该算法对北京首都机场某个时间段内航班进行仿真排序结果显示：该改进算法在一定程度上提高时隙分配的合理性。减少航空公司的总延误损失．同时尽可能公平的保证航空公司所服务对象的利益。     

快速排序的改进算法

排序是计算机科学中一个非常重要的研究问题。2000年,排序曾被列为20世纪对科学和工程计算的研究与实践影响最大的十大问题之一。本文在分析通常的快速排序算法的平均时间复杂度的基础上,提出了一种新的改进算法,提高了快速排序算法的性能。     

基因组Translocation排序问题的改进多项式算法

该文给出基因组Transhocation排序问题的一个改进多项式算法,原算法所有存储空间O（n),时间复杂度为O(n^3),文中改进算法仍采用O(n)存储空间,时间复杂度为O(n^2logn),具体地,将计算Translocation距离的时间复杂度由O(n^3)改进为O(n^2),将计算Translocation序列的时间复杂度由O(n^3)改进为O(n^2logn).