同类处理机排序问题Q2∥Cmax的一个算法

本文对ｎ个任务，２台同类处理机的排序问题Ｑ２∥Ｃｍａｘ进行讨论，提出一个算法，用该算法得到的排序表长的界是２ｂ＋１／２ｂＭ，算法的复杂性为Ｏ（ｎｌｏｇｎ）。     

一类Q_m|r_j|C_(max)on-line问题的LS算法分析

考虑一类Qm|rj|Cmax的on_line问题的LS算法 (m台机器 ,速度分别为s1,s2 ,… ,sm,且s1≤s2 ≤…≤sm) ,证明了这个算法性能指标上的上界是 1+ m - 1i =1si sm .     

处理机具有不同的开始加工时间的Q,ai｜pmtn｜Cmax排序问题

本文给出处理机具有不同的开始加工时间的Ｑ，ａｉ｜ｐｍｉｔｎ｜Ｃｍａｘ排序问题的一个最优算法，算法的复杂性为Ｏ（ｍ＾２ｎ＾２）。     

同类机随机在线排序模型及算法分析

考虑同类机随机在线排序问题.假设有m台同类机,工件在线到达,问题的目标是使总加权完工时间的期望值最小.考察该随机在线问题,首先利用线性规划松弛的方法,得到问题最优解的一个下界;然后给出解决该问题的一个在线算法,并分析了该算法的竞争比.     

工件可拒绝的在线同类机排序

针对带有惩罚费用的工件在同类平行机上的在线排序问题,目标函数为极小化被接收工件的最大完工时间加上被拒收工件的总拒绝费用,给出了一在线算法,证明了该算法的竞赛比不超过,有Z^on/Z^OPT≤1＋ρ。     

具有传递时间的排序问题

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

Flow Shop排序问题F3|s|C_(max)的最优算法

讨论调整时间可分离的Ｆｌｏｗ Ｓｈｏｐ 排序问题Ｆ３｜ｓ｜Ｃｍａｘ ．对其一类特殊情况给出了最优算法．     

带机器准备时间的同类机在线与半在线排序问题

研究带机器准备时间的m台同类机(uniform machines)在线和半在线排序问题，目标函数为极小化最大机器(工件)完工时间。对于在线情形，证明了LS算法的最坏情况为ρ=｛（1 √5）/2，m=2,1 √2m-2/2,m≥3，并且当m=2，LS算法是最好的近似算法；当m=2，3，…，6时界是紧的，特别地，当s1=s2=…=sm-1,sm≥l时，证明了LS算法的最坏情况界为ρ=｛（1 √5）/2，m=2,3-4/m 1,m≥3，而且界是紧的；对于已知加工时间递减的半在线排序问题，证明了LS算法的最坏情况界为2—2/(m 1)。     

关于两台平行机上在线排序问题的一个探讨

研究了两台平行机上目标为开工时间的在线排序问题,即目标函数为极小化最大工件开工时间。首先给出了问题的下界,然后证明了贪婪算法的上界等于问题的下界,从而是最优的在线算法。     

单机排序问题1|r_j|L_(max)的分枝定界算法

给出了单机排序问题 1 |rj|Lmax的分枝定界算法     

一种改进的时序安排算法

时序安排或任务调度算法广泛应用于计算机的各个领域,如Linux进程调度算法,排课表算法等。本文使用无向图模型．得到一种改进的时序安排或任务调度算法。通过对比,显示该算法在实际应用中可大大提高工作效率。     

一种面向动态异构多处理器的任务调度算法

提出了基于遗传算法的面向动态异构多处理器的调度算法(Heterogeneous Scheduling Genetic Algorithm,HSGA),该算法利用连续的多个调度时间片完成遗传算法的迭代计算,在保证计算效率的同时获得较好的调度结果,从而为每个应用选择符合其计算特性的处理器内核.仿真实验表明,本文算法在4核、8核和16核的平台上相比较于经典的匈牙利算法ED2仅分别增加了0.4%,1.1%和1.3%,新的调度算法相比于匈牙利算法和Local调度算法具有更好的调度效果及更好的动态适应性.     

并行加工设备组生产调度的一般模型及算法

给出了一个描述并行加工设备组生产调度问题的一般模型及两个启发式算法，对ＥＬＰＴ方法，另提供了一个误差分析结果，对极大消去法给出了个数值计算实例.     

具有通用机的多组工件的Q//C_(max)问题的近似算法

研究的目的在于解决实践中对多组任务的优化排序问题,即在最短的时间内完成所有给定的任务。由于这类问题往往都是NP完全问题,人们通常寻求其近似算法。提出了一种改进的LPT算法,利用"最大相对加工时间"准则和"首先空闲"准则,讨论了将n组工件安排在n台速度不同的专用机,一台速度小于专用机的通用机上的Cmax问题,得到了利用该近似算法所得的解T与最优解T*的一个估计:T/T*≤1+1/∑i∈Isi,其中I表示在最后完工的工件完工之前,在通用机上至少安排了一个工件的工件组的下标集合。由此得出采用该近似算法对工件排序,在最差情况下要比最优排序多出1/∑i∈Isi的时间。     

多处理机调度问题的一种近似算法

对多处理机调度问题Ｐ∥Ｃｍａｘ，给出一种近似算法，大量实例的计算结果表明，本文的算法是非常有效的。     

An Ant Colony Optimization Algorithm to Satellite Data Transmission Scheduling Problems

数据传输资源调度是空间资源管理的重要内容之一。为了有效求解数据传输资源调度问题,基于蚁群算法构建了一种数据传输资源调度方法。实验结果表明,蚁群算法能有效求解数据传输资源调度问题。本文方法可推广应用到其他资源调度领域。     

基于调度效益最大化的多功能组网认知雷达资源优化调度算法

在组网认知雷达中,针对多目标多任务(如搜索、跟踪与成像等)按优先级进行资源调度时易造成目标任务丢失的问题,提出基于调度效益最大化的多功能组网认知雷达资源优化调度算法。该算法将搜索与跟踪任务的时间窗考虑到目标函数中,通过目标任务的重要性(优先级)和有效性(时间窗)两个因素的加权来表示雷达对目标任务的调度效益,根据调度效益最大准则建立并利用遗传算法求解资源调度模型。对仿真结果分析表明,该方法能够提高组网认知雷达的整体效能。     

速度相同的具有m-2台通用机的两组工件的LS算法分析

对于实践中存在的具有两组任务的优化排序问题进行了讨论,在经典的LS算法的基础上提出了一种改进的LS算法,利用"首先空闲"准则选择机器,按照工件的到达顺序安排工件,讨论了将两组工件安排在两台速度相同的专用机,m-2台同速度的通用机上的Cm ax问题,其中工件具有准备或到达时间,且工件的准备或到达时间均不超过其加工时间的α倍。目标是在最短的时间内完成所有给定的任务。得到了利用该近似算法所得的解TLS与最优解T*的一个估计(1+α)(2-1/m),并且证明了对任意的α此界是紧的。