论文部分内容阅读
研究了已知总加工时间的两台同类机半在线问题．假设工件是分别独立地到达加工机器。并俎工件的总加工时间是已知的，目标函数为极大化最小机器负载．将总加工时间标准化后，给出近似算法及其竞争比，并证明此竞争比是紧的．给出此问题竞争比的一个下界1．6180，并由此推出当两台机器的速度比为1．6180时，算法是最优的，算法的竞争比与最优算法的竞争比之差小于0．089．