کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
434746 | 689790 | 2012 | 7 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: A best possible online algorithm for scheduling equal-length jobs on two machines with chain precedence constraints A best possible online algorithm for scheduling equal-length jobs on two machines with chain precedence constraints](/preview/png/434746.png)
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 13−12.
► We study online scheduling on two identical machines with chain precedence constraints.
► Jobs arrive over time and have identical processing times.
► Huo and Leung [Y. Huo and J.Y.-T. Leung, Online scheduling of precedence constrained tasks, SIAM Journal on Computing, 34 (2005), 743–762] considered this problem of minimizing makespan.
► They 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 1.3028.
Journal: Theoretical Computer Science - Volume 457, 26 October 2012, Pages 174–180