LS排序的界

讨论任务的加工是不可中断,处理机是同速机的排序问题Ｐｍ,ａｉ∥Ｃｍａｘ,证明了用ＬＳ算法求解该问题的误差界是２－１／ｍ。     

有限次分组排序算法

本文给出一种有限次分组快速排序算法并证明该排序算法处理均匀分布数据记录,正态分布数据记录及一般概率分布数据记录的平均时间复杂性为Ｏ（Ｎ）;给出四种快速 序算法分别关于均匀分布数据记录,正态分布数据记录,均匀波浪式分布数据记录和异常分布数据记录,进行排序的实验结果,表明有限次分组排序算法具有更快的效率。     

具有传递时间的排序问题

研究具有传递时间的两类单机排序问题，运用交换方法证明最优性条件并设计了相应算法。     

一种新的排序方法——影射排序法

提出了一种新的排序方法－影射排序法,在很多问题的应用中使用此方法可提高程序的运行效率,其时间复杂度为Ｏ（Ｎ）。     

各种排序算法小议

排序算法是一种基本并且常用的算法.本文主要是按照算法的复杂度,从简单到复杂来分析算法,对算法进行分类,并介绍在不同条件下算法的使用与选择.     

关于同顺序m×n排序问题中总工时下界的一种简便算法

本文对越民义、韩继业《同顺序m×n排序问题的一个新方法》(见《科学通报》1979,18,pp.821~824)一文关于下界B(S…S″)的算法中需大量反复计算的t_m-1m(R_m.)给出了一种简便算法,同时,又对其所提出的下界B(S…S′)的算法作了改进.从而提高了B(s…s′)的估值精度.     

映射排序算法研究

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

单台机器速度可选择的排序问题

研究一类单台机器具有速度可选择约束的排序问题。引进了有关记号，给出了该问题解的概念。ｍ＝１的情形问题１｜ｓｐｅ．｜ΣＣ＿ｊ和问题１｜ｓｐｅ．｜Σｗ＿ｊＣ＿ｉ具有多项式时间算法，即为所谓的Ｐ问题，但对ｍ为一般情形其计算复杂性尚未解决。     

基于LTE网络的QoS保障调度算法

提出了一种基于LTE网络的混合模式MAC层调度算法,该算法有效地保障了不同用户、不同业务的QoS需求,同时合理的平衡了系统吞吐量和用户间公平性.当系统中已产生或者即将产生无法满足QoS需求业务时系统优先对该类业务进行调度,不同业务间基于QCI等级进行排序,优先保障高等级的业务的QoS需求;当系统中不存在濒临无法满足QoS需求的业务时则采用逐个资源块儿的调度模式,同时通过信噪比的指数配置可以平衡系统的吞吐量和用户间的公平性.系统引入的混合调度模式附加计算量低、易于实现,在满足系统需求的时候可以有效降低计算量提高系统处理能力.     

分装式流水作业加工模型的算法研究

分装式流水作业加工模型是从生产实践中提炼出来的一种新的加工模型,是流水作业与复合并行机加工方式的组合.在已证明该问题一般情况下是NP-完全问题,没有多项式算法的基础上,进一步研究了TMF排序问题在特殊情况下的多项式时间算法和一般情况下的启发式算法.     

A genetic algorithm for the flowshop scheduling problem

The flowshop scheduling problem is NP complete. To solve it by genetic algorithm, an efficient crossover operator is designed. Compared with another crossover operator, this one often finds a better solution within the same time. Supported by the National Natural Science Foundation of China and 863 High Technology Project of China Qi Yuesheng: born in 1967, Ph. D.     

求解多目标单机分批排序问题

分批排序(Batch Scheduling)是在半导体生产过程的最后阶段提炼出来的一类新型的排序问题．单机分批排序问题就是n个工件在一台机器上加工,要将工件分批,每批最多可以同时加工B个工件,每批的加工时间等于此批工件中的最大的加工时间．目前只有Cheng-shuo Wang,Reha Uzsoy运用Random Key方法编码研究了单目标函数为Lmax的分批排序问题．给出组合优化中的多目标分批排序问题的一种新编码,结合模糊数学知识,运用遗传算法研究多目标分批排序问题．研究了多目标遗传算法的机制特征,进而给出求解多目标分批排序的遗传算法．     

一种新的静态优先级在线节能调度算法

合理运用动态电压调整技术可有效降低嵌入式实时系统能耗.针对静态优先级实时调度,提出了一种能够有效分析松弛时间并尽可能平衡分配松弛时间的在线节能调度算法TPSRM.设计了一种两段式频率执行策略来改变任务执行时间的分配,能充分在线分析各种形式的松弛时间.通过尽可能合理降低高优先级任务的处理器执行频率来实现有效的在线频率调整.实验结果表明TPSRM算法可实现较好的节能效果.     

多品种装配顺序的一种改进遗传算法

多品种装配顺序的安排问题属于旅行商问题（TSP）,具有NP计算复杂性,针对该问题,以工艺辅助时间需求为优化目标,对遗传算法的边重组交叉算子（ER）作了改进．将基因的邻接关系分为左邻接关系和右邻接关系,通过抛弃基因的左邻接关系,将ER改进为右边重组算子（R—ER）,仿真表明改进后的遗传算法寻优能力更强、收敛性更佳．     

A Throughput-Driven Scheduling Algorithm of Differentiated Service for Web Cluster

Requests distribution is an key technology for Web cluster server. This paper presents a throughput-driven scheduling algorithm （TDSA）. The algorithm adopts the throughput of cluster back-ends to evaluate their load and employs the neural network model to predict the future load so that the scheduling system features a self-learning capability and good adaptability to the change of load. Moreover, it separates static requests from dynamic requests to make full use of the CPU resources and takes the locality of requests into account to improve the cache hit ratio. Experimental re suits from the testing tool of WebBench^TM show better per formance for Web cluster server with TDSA than that with traditional scheduling algorithms.     

任务长度可变的多机排序问题

把由Czumaj等人提出的用于网络信息搜索的任务长度可变的排列问题推广到任务长度可变的多机排序问题,证明该问题的判定形式是NP困难的,而且对任务最大完成数目的优化形式给出了一个近似比α小于4的近似算法．     

A hybrid differential evolution algorithm for meta-task scheduling in grids

Task scheduling is one of the core steps to effectively exploit the capabilities of heterogeneous re- sources in the grid.This paper presents a new hybrid differential evolution(HDE)algorithm for finding an optimal or near-optimal schedule within reasonable time.The encoding scheme and the adaptation of classical differential evolution algorithm for dealing with discrete variables are discussed.A simple but ef- fective local search is incorporated into differential evolution to stress exploitation.The perfo...     

TTCAN周期性任务的优化调度算法

TTCAN周期性任务调度是最优装载问题的推广,它在通信时间关键的实时分布式系统中有着很强的应用背景.本文提出了4种确定基本周期的策略,给出了首次适应和最佳适应两种不同的可以在多项式时间内构造出TTCAN周期性任务调度表的算法,最后对不同规模下的两种算法的实验结果进行了比较,指出了两种算法在不同的周期策略下的渐近性能比.