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

• 作 者: 丁伟
• 机 构: 中山大学数学与计算科学学院
• 出 处: 数学研究
• 发表日期: 2010年2期
• 关键词: 运筹学 排序 启苎目濞法 性能指标 多组工件 通用机与专用机 operations research scheduling heuristic approa
• 基金项目: 基金项目：国家自然科学基金资助项目（10971234）.

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