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

An Analysis of LS Algorithm for the Scheduling Problem on m-2 General-Purpose Machinery and Two Group Tasks with Uniform Processors

作　　者：丁伟[1] 

机构地区：[1]中山大学数学与计算科学学院,广东广州510275

出　　处：《中山大学学报（自然科学版）》2010年第6期1-5,共5页Acta Scientiarum Naturalium Universitatis Sunyatseni

基　　金：国家自然科学基金资助项目(10971234;10671213)

摘　　要：对于实践中存在的具有两组任务的优化排序问题进行了讨论,在经典的LS算法的基础上提出了一种改进的LS算法,利用"首先空闲"准则选择机器,按照工件的到达顺序安排工件,讨论了将两组工件安排在两台速度相同的专用机,m-2台同速度的通用机上的Cm ax问题,其中工件具有准备或到达时间,且工件的准备或到达时间均不超过其加工时间的α倍。目标是在最短的时间内完成所有给定的任务。得到了利用该近似算法所得的解TLS与最优解T*的一个估计(1+α)(2-1/m),并且证明了对任意的α此界是紧的。The Cmax problem on two-group jobs with m-2general-purpose machineries and two special-purpose machineries that they are the same speed,and the jobs have the setup times and it is no more α time than its processing times is studied.An improved LS algorithm and the upper tight bound performance are given.The ratio of the approximate solution T LS and the best way T＊ is（1＋α）（2-1/m）,and it is tight for all α.

关 键 词：启发式算法 性能指标 LS算法 LPT算法 通用机与专用机 

分 类 号：O223[理学—运筹学与控制论]