Online scheduling on unbounded parallel-batch machines to minimize maximum flow-time
首发时间:2011-01-11
Abstract:This paper considers online scheduling on m unbounded parallel-batch machines to minimize maximum flow-time of the jobs. The research shows that no online algorithm can have a competitive ratio less than, where is the positive root of, and this lower bound is still valid even when all jobs have the same processing times. An online algorithm of competitive ratio 1+1/m is presented in the paper. When the jobs have the same processing times, a best possible online algorithm of competitive ratio is established.
keywords: operations research online scheduling parallel-batch machines makespan competitive ratio
点击查看论文中文信息
无界平行分批机器上的最小化最大流程的在线排序
摘要:This paper considers online scheduling on m unbounded parallel-batch machines to minimize maximum flow-time of the jobs. The research shows that no online algorithm can have a competitive ratio less than , where is the positive root of , and this lower bound is still valid even when all jobs have the same processing times. An online algorithm of competitive ratio 1+1/m is presented in the paper. When the jobs have the same processing times, a best possible online algorithm of competitive ratio is established.
关键词: operations research; online scheduling; parallel-batch machines; makespan; competitive ratio
论文图表:
引用
No.4403852558848129****
同行评议
共计0人参与
勘误表
无界平行分批机器上的最小化最大流程的在线排序
评论
全部评论0/1000