LS排序的界

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

有限次分组排序算法

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

具有传递时间的排序问题

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

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

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

各种排序算法小议

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

映射排序算法研究

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

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

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

一种改进的起泡排序算法

本文给出了一种改进的起泡排序算法．改进后的起泡排序算法与经典的起泡排序算法相比，通常可以减少排序过程中总的比较次数．用ＰＡＳＣＡＬ语言描述的与算法有关的类型定义和变量说明如下：ＴＹＰＥｎｏｄｅ＝ＲＥＣＯＲＤｋｅｙ：ｉｎｔｅｇｅｒ；ｉｎｆｏ：ｄａｔａｔ...     

基于拉格朗日下界求解的炼钢-连铸生产调度方法

为提高炼钢-连铸生产效率,以加权总完工时间、作业等待惩罚总和最小化为目标,基于时间索引建立数学规划模型。在证明原问题、松弛问题、对偶问题三者最优解关系基础上,将机器容量约束松弛到目标函数中,运用次梯度算法求原问题下界,得到各炉次的开始时间序列。为消除松弛解中的有向环,采用融入启发式规则的列表调度,按照机器可用性优先原则,将炉次均衡地指派到各个加工机器上。利用GAMS/Cplex软件对18个调度算例进行测试运算,结果表明以较少的计算代价可以得到令人满意的近优解,因此本文提出的基于拉格朗日下界求解的方法对炼钢-连铸生产调度问题是可行的和有效的。     

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

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

一种基于有向无环图的相依性网格任务调度算法

网格任务调度算法是影响网格成功与否的关键技术之一.本文首先描述了网格计算环境中的DAG任务调度模型.然后,结合网格计算环境的特点, 讨论了多个相依性任务组成的应用任务调度问题,并对GS和CIGS算法进行了全面而深入的研究,并在此基础上提出了一个CIGS算法的改进算法.     

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

分装式流水作业加工模型是从生产实践中提炼出来的一种新的加工模型,是流水作业与复合并行机加工方式的组合.在已证明该问题一般情况下是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.     

一种基于参数扫描应用容错的粗粒度网格调度算法

考虑作业处理时延以及作业传输时延对调度器性能的影响,在RR调度算法的基础上提出了一种新的基于参数扫描应用的调度算法PRR,并对该算法进行了理论分析,得出了该调度算法不需要作业以及处理器的相关信息,且具有比较好的容错性的结论.利用网格仿真软件Gridsim对PRR调度算法的理论分析结果进行了验证,并将该算法与RR调度算法的性能进行了比较.结果表明,当时延较大时,PRR调度算法性能改善比较明显.     

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

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

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

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

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.     

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

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