文章导读
总览 评价 李文华 ， 原晋江 （ 郑州大学数学系； ） 摘要： 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 compet
李文华， 原晋江
（
郑州大学数学系； ）
摘要：
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
Li Wenhua， Yuan Jinjiang
（
Department of Mathematics, Zhengzhou University； ）
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.
Tag：
点此返回栏目查看更多>>>参考论文
