论文部分内容阅读
研究单处理机工件按加工长度不增顺序到达的在线分批排序问题．工件按时在线到达，目标是最小化最大流程．流程时间是指工件的完工时间与到达时间的差值，它体现了工件在系统内的逗留时间．对于批容量有界的情形，给出了一个竞争比为1＋√5/2的最好可能的在线算法；对于批容量无界的情形，给出了一个竞争比为√2的最好可能的在线算法．