一类Qm|rj|Cmax on-line 问题的LS算法分析

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

一类Qm/rj/Cmax on-line问题的LS算法分析

考虑一类 Ｑｍ／ｒｊ／ Ｃｍａｘ ｏｎ＿ｌｉｎｅ 排序问题的 Ｌ Ｓ算法（ ｍ 台机器,其中一台机器的速度为ｂ（ ｂ ＞ １） ,其余机器的速度都为１） ,证明这个算法的性能指标的上界是１ ＋ ｍ － １ｂ ．     

一类Qm/rj/Cmax on-line问题的LS算法分析

考虑一类Q     

一类P／Sij／Cmax问题的LS算法分析

提出一类有准备时间的排序问题；分析了ＬＳ算法解此问题的最坏情况；个性了ＬＰＴ算法，使最差性能指标由４－２／ｍ改进到８／３－２／３ｍ。     

同类处理机排序问题Q2｜｜C_(max)的一个算法

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

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

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

一类单机排序问题的算法研究

本文讨论了加工时间依赖于开工时间的单机排序问题。在这一模型中每个工件具有一个基本加工时间。本文就目标函数为极小化最大完工时间和总完工时间的问题进行了讨论,对某些特殊情况给出了多项式算法。     

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

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

一类调整时间可分离的FlowShop排序问题F3|s|C_(max)的最优算法

讨论调整时间可分离的FlowShop排序问题F3 |s|Cmax.对其一类特殊情况给出了最优算法     

F2│r_j,t_j│C_(max)问题的多项式时间近似算法

针对具有到达时间和运输延迟的两机器流水车间排序问题F2│rj,tj│Cmax,证明了有运输时间约束的条件下,该问题最优排序是同顺序的,并给出了一种基于动态规划的多项式时间近似算法.     

工件带准备时间的平行机调度问题的一个近似算法

提出了一个启发式算法,在该算法中,工件中断的次数至多为2N次,计算的复杂度为O(Nnlogn),并以一个实例加以说明.证明了对某些特殊的实例,该算法能够得到最优调度.指出了对于一般情况该算法的最坏情况误差界为(2(n-1))/n.     

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

研究带机器准备时间的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)。     

改进遗传蜂群算法求解分布式柔性作业车间调度问题

针对分布式柔性作业车间调度问题,提出一种改进遗传蜂群算法求解方案。算法采用基于机器编码的编码方案,根据编码特点和分布式柔性作业车间的特点,设计了一种基于编码相似度的交叉操作,可以避免在交叉过程中产生非法解,提高算法的运行效率,并通过在不同的交叉操作后,以不同概率进行两种变异操作的方式改进了雇佣蜂时期的搜索操作,改善了算法的迭代速度;采用排序选择策略替代原来跟随蜂时期的选择策略;改进侦查蜂的蜜源抛弃机制,通过对比已获得的全局最优解,对达到搜索上限的蜜源进行部分抛弃,防止破坏优质解再次陷入随机搜索。最后,通过对比不同算法对实例求解,验证本文算法的有效性。     

一类Qm／pmtn／Cmax的on—line排序问题的有效算法

对一类Ｑｍ／ｐｍｔｎ／Ｃｍａｘ的ｏｎｌｉｎｅ 排序问题, 提出一种算法, 给出其性能指标是ｂ（ｍ －１＋ｂ）ｍ／（（ｍ － １＋ ｂ）ｍ －（ｍ －１）ｍ）, 其中ｍ ≥２ , 当ｍ →∞时,性能指标趋于ｂｅｂ／（ｅｂ－１）．     

多任务并行调度系统中的一种订票算法

本文提出多道相关任务系统并行调度方法,文中引入了一种描述任务资源分配的数据基ＴＣＢ（任务控制块）,并提出一个用于任务定序的“订票”算法,简称ＢＴ算法,改善了系统的处理能力。     

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

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