加工时间与运输时间具有一致性的单机NDP约束在线排序问题研究  

Research on the NDP-constraint online scheduling of jobs have agreeable processing times and delivery times

作　　者：李文杰[1] 杜智慧[1] 苏孟龙[1] LI Wenjie;DU Zhihui;SU Menglong(School of Mathematical Sciences,Luoyang Normal University,Luoyang 471934,Henan,China)

机构地区：[1]洛阳师范学院数学科学学院,河南洛阳471934

出　　处：《运筹学学报(中英文)》2024年第4期18-28,共11页Operations Research Transactions

基　　金：河南省自然科学基金(No.222300420503);河南省高校重点基础研究基金(No.22A110015);河南省高校青年骨干教师培养计划基金(Nos.2019GGJS202,2018XJGGJS-10)。

摘　　要：本文研究NDP约束下的最小化最大运输完工时间单机在线排序问题。这里的“NDP约束”是指当有工件到达时,则空闲机器必须立刻选择工件加工,即工件不能被强制推迟加工。本文讨论所有工件的加工时间与运输时间均具有一致性的排序模型,即若工件Ji和Jj的加工时间满足pi≥pj,则其运输时间满足qi≥qj。我们首先给出NDP约束下该排序问题的下界为4/3,其次设计出一个竞争比是1.382的在线算法。This paper studies the single-machine online schedule under the NDPconstraint 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)≥p_(j),then p_(i)≥p_(i)).we first present a lower bound of 4/3 and then design an online algorithm with the competitive ratio of 1.382.

关 键 词：在线排序 在线算法 NDP约束 一致性 运输完工时间 

分 类 号：O221.7[理学—运筹学与控制论]