A best possible online algorithm for scheduling equal-length jobs on two machines with chain precedence constraints

作者：Yuan, Junling; Li, Wenhua^*; Yuan, Jinjiang

来源：Theoretical Computer Science, 2012, 457: 174-180.

DOI：10.1016/j.tcs.2012.07.009

• Online algorithm
• Parallel-machine scheduling
• Equal-length jobs
• Chain precedence constraints
• Competitive ratio

We consider the online scheduling on two identical parallel machines with chain precedence constraints to minimize makespan, where jobs arrive over time and have identical processing times. For this online scheduling problem, Huo and Leung [Y. Huo and J.Y.-T. Leung, Online scheduling of precedence constrained tasks, SIAM Journal on Computing, 34 (2005), 743-762] proved that it is impossible to have an online algorithm of a competitive ratio 1. We provide a best possible online algorithm of competitive ratio root 13-1/2.

• 出版日期2012-10-26
• 单位北京科技大学; 郑州大学