同类机半在线排序问题及其近似算法  

Semi On-Line Scheduling on Two Uniform Machines

作　　者：谈之奕[1] 何勇[1] 

机构地区：[1]浙江大学数学系,浙江杭州310027

出　　处：《系统工程理论与实践》2001年第2期53-57,共5页Systems Engineering-Theory & Practice

基　　金：国家973重点基础研究专项经费;国家自然科学基金!( 1 970 1 0 2 8)

摘　　要：研究两台同类机系统两个半在线排序问题 .第一个为总加工时间已知 ,第二个为最大工件加工时间已知 .对这两个问题 ,文章给出了各自的近似算法 ,证明了它们的最坏情况界分别为 3和3/2 .This paper investigates two semi on\|line scheduling problems on a two uniform machine system. In the first case, we assume that the total processing time is known in advance. In the second case, we assume that the largest processing time is known in advance. For each case we propose a heuristic and investigate its worst\|case ratio.

关 键 词：在线排序 近似算法 最坏情况分析 组合最优化 

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