单机上带有可变前瞻区间的分批在线排序问题
Online scheduling on single batch machine with variable lookahead interval作者机构:郑州大学数学与统计学院
出 版 物:《运筹学学报》 (Operations Research Transactions)
年 卷 期:2022年第26卷第1期
页 面:134-140页
核心收录:
学科分类:07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学]
基 金:国家自然科学基金(Nos.11971443 11771406)。
摘 要:本文研究单台无界平行批处理机上带有可变前瞻区间的在线排序问题。工件按时在线到达,目标是最小化时间表长。在时刻t,在线算法能够预见到(t,t+Δ(t)]内到达工件的信息,这里前瞻区间的长度△(t)=βp;(t)并非定长,其中p;(t)表示在t时刻及之前到达工件的最大加工时长,β∈(0,1)是常数。本文对于工件加工时长的一般情形,给出了当0 β≤1/6时最好可能的在线算法;对于工件加工时长被限制在一个区间的情形,给出了当0 β1时最好可能的在线算法。