论文部分内容阅读
研究半在线模型的松弛,讨论以下半在线松弛模型:已知工件最大加工时间在某一区域内(known largest job interval),分别讨论了该模型下2台同型机的极小化Cmax问题和极大化Cmin问题.对这两个问题构造pInterval算法,给出其竞争比并证明它是紧的,还分析了上述两个问题的特征和LS算法的竞争比.