本文研究NDP约束下的最小化最大运输完工时间单机在线排序问题。这里的“NDP约束”是指当有工件到达时, 则空闲机器必须立刻选择工件加工, 即工件不能被强制推迟加工。本文讨论所有工件的加工时间与运输时间均具有一致性的排序模型, 即若工件$J_{i}$和$J_{j}$的加工时间满足$p_{i}\geq p_{j}$, 则其运输时间满足$q_{i}\geq q_{j}$。我们首先给出NDP约束下该排序问题的下界为4/3, 其次设计出一个竞争比是1.382的在线算法。

This paper studies the single-machine online schedule under the NDP-constraint to minimize the maximum delivery completion time. Here "NDP-constraint" means that the idle machine must schedule the available jobs at any time, i.e., the available jobs cannot be delayed for processing. In this paper, we study the restricted version in which the jobs have agreeable processing times and delivery times (if $p_{i}\geq p_{j}$, then $p_{i}\geq p_{j}$). we first present a lower bound of 4/3 and then design an online algorithm with the competitive ratio of 1.382.