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

• 作者: 丁伟
• 来源期刊: 中山大学学报（自然科学版）
• 学科: 数学
• 关键词: 启发式算法 性能指标 LS算法 LPT算法 通用机与专用机
• 年，卷（期）: 2010,（6）
• 页码范围: 1-5
• 分类号: O223
• 字数: 2959字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	丁伟	中山大学数学与计算科学学院	11	34	4.0	5.0