本文研究NDP约束下的最小化最大运输完工时间单机在线排序问题。这里的“NDP约束”是指当有工件到达时,则空闲机器必须立刻选择工件加工,即工件不能被强制推迟加工。本文讨论所有工件的加工时间与运输时间均具有一致性的排序模型,即若工件Ji和Jj的加工时间满足pi≥pj,则其运输时间满足qi≥qj。我们首先给出NDP约束下该排序问题的下界为4/3,其次设计出一个竞争比是1.382的在线算法。
科研之友
微信
新浪微博
Facebook
分享链接
