可中断半在线排序问题 (2006年)

讨论两台同型机上的可中断半在线排序问题 ,目标函数为极大化最小的机器完工时间 C min .首先考虑已知所有工件的加工时间在 p和 rp( p>0 ,r≥1)之间的情形,对任意的参数 r ,设计了最优半在线算法.接着 ,对已知最大工件加工时间的情形作了研究 ,得到了一个竞争比为 54的最优半在线算法.