本文研究两台单位流水作业上,具有前瞻区间的两个不相容工件族无界批处理的在线排序问题。单位流水车间问题是指任何工件在每台机器上的加工长度均为1,工件按时到达,目标是最小化最大完工时间。具有前瞻区间是指在时刻t,在线算法能预见(t,t+β]区间内到达工件的信息。不可相容工件族是指属于不同工件族的工件不能安排在同一批加工。本文提供了一个竞争比为1+α的在线算法A_1(β),其中■是方程3α~2+(β+2)α+β-2=0的一个正根,这里0≤β<1。
科研之友
微信
新浪微博
Facebook
分享链接
