中文摘要：

本文研究了单台机器上工件具有退化效应并且需要考虑工件运输的在线排序问题.目标函数是最小化最大运输完工时间.对于这个在线排序问题,主要是设计一个有效的在线算法.首先采用对手法找到问题的下界,即设计一个坏实例,使得算法得到的目标值与离线最优目标值的比尽可能的大,之后依据下界设计给出一个在线算法.通过对手法的应用,给出问题的下界,并设计了一个竞争比为2的在线算法.

英文摘要：

In this paper, we study the online scheduling on a single machine with deteriorating jobs and deliv- ery times. The objective function is to minimize the maximum delivery completion time of these jobs. For this online scheduling problem, the objective is to design an effective online algorithm. We establish a lower bound by adversary strategy, i. e. , design a bad instance to make the ratio of the objective by online algorithm and offiine objective as big as possible, then we present an online algorithm by this lower bound. Thus we get a lower bound by adversary strategy and an online algorithm with the competitive ratio of 2.