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

An Improved LS Algorithm for the Q_(m+2)/r_j/C_(max) Scheduling Problem on m General-Purpose Machineries and Two Special-Purpose Machineries

作　　者：丁伟[1] 

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

出　　处：《应用数学与计算数学学报》2009年第2期26-34,共9页Communication on Applied Mathematics and Computation

基　　金：国家自然科学基金(No.10971234和No.10531040)资助项目

摘　　要：对于实践中存在的机器加工速度不同的,具有两组任务的优化排序问题进行了讨论,在经典的LS算法的基础上提出了一种改进的LS算法,利用"首先空闲"准则选择机器,按照工件的到达顺序安排工件,讨论了将两组工件安排在两台速度不同的专用机,m台速度相同的通用机上的C_(max)问题,其中工件具有调整时间或安装时间,且工件的调整时间或安装时间均不超过其加工时间的α倍.目标是在最短的时间内完成所有给定的任务.得到了利用该近似算法所得的解T^(LS)与最优解T~*在不同条件下的两个估计,并且证明了这两个估计是紧的。To study the Cmax problem on two-group jobs with m general-purpose machineries and two special-purpose machineries that they are the different speed in this paper,and the jobs have the ready times and it is no moreαtime than its processing times.An improved LS algorithm and two upper tight bounds performance in different conditions are given.

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

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