具有m台通用机和两台专用机的Q_(m+2)/r_j/C_(max)问题的改进LS算法

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

具有通用机的两组工件的排序问题

讨论了具有两台速度不同的专用机,m台速度相同的通用机的两组工件的Cmax问题,提出了改进的LPT算法,得到了最差情况下性能指标的界。

具有通用机的三组工件的排序问题

该文讨论了具有三台速度相同的专用机,一台同速度的通用机的三组工件的Cmax问题,提出了改进的LPT算法,得到了近似算法的一个估计.

具有通用机的n组工件的排序问题

本文讨论了具有n台速度相同的专用机,一台同速度的通用机的n组工件的Cmax问题,提出了改进的LPT算法,得到了近似算法的一个估计．

同速度的具有m台通用机的n组工件的排序问题

改进了经典的LPT(Longest Processing Time)算法,利用"首先空闲"准则安排机器,而对于工件的安排则按照"长时间任务优先"的原则,讨论了将n组工件安排在n台速度相同的专用机,m台同速度的通用机上的优化排序问题,得到了利用该近似算法所得的解T与最优解T*的一个估计:T/T*≤(2m+1)/(m+1)。

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

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

一类速度不同的具有m台通用机的n组工件的排序问题

研究的目的在于解决实践中对多组任务的优化排序问题，即在最短的时间内完成所有给定的任务，由于这类问题往往都是NP完全问题，人们通常寻求其近似算法．文中提出了一种改进的LPT算法，利用。首先空闲”准则，讨论了将n组工件安排在n台速度不同的专用机，m台速度小于专用机的通用机上的C‰。。问题，得到了利用该近似算法所得的解T与最优解T＊的—个估计：T/T＊≤2＋（n-2）/（m＋1）