List scheduling for jobs with arbitrary release times and similar lengths
Tóm tắt
This paper considers the problem of on-line scheduling a list of independent jobs in which each job has an arbitrary release time and length in [1,r] with r≥1 on m parallel identical machines. For the list scheduling algorithm, we give an upper bound of the competitive ratio for any m≥1 and show that the upper bound is tight when m=1. When m=2, we present a tight bound for r≥4. For r<4, we give a lower bound and show that 2 provides an upper bound.
Tài liệu tham khảo
Azar, Y., & Regev, O. (2001). On-line bin stretching. Theoretical Computer Science, 268, 17–41.
Dósa, G., & He, Y. (2004). Semi-online algorithms for parallel machine scheduling problems. Computing, 72, 355–363.
Graham, R. L. (1969). Bounds on multiprocessing timing anomalies. SIAM Journal on Applied Mathematics, 17, 416–429.
He, Y., & Zhang, G. (1999). Semi on-line scheduling on two identical machines. Computing, 62, 179–187.
Kellerer, H. (1991). Bounds for non-preemptive scheduling jobs with similar processing times on multiprocessor systems using LPT-algorithm. Computing, 46, 183–191.
Kellerer, H., Kotov, V., Speranza, M. G., & Tuza, Z. (1997). Semi on-line algorithms for the partition problem. Operations Research Letters, 21, 235–242.
Li, R., & Huang, H. C. (2004). On-line scheduling for jobs with arbitrary release times. Computing, 73, 79–97.
Liu, W. P., Sidney, J. B., & Vliet, A. (1996). Ordinal algorithm for parallel machine scheduling. Operations Research Letters, 18, 223–232.
Seiden, S., Sgall, J., & Woeginger, G. J. (2000). Semi-online scheduling with decreasing job sizes. Operations Research Letters, 27, 215–227.
Tan, Z. Y., & He, Y. (2002). Semi-online problem on two identical machines with combined partial information. Operations Research Letters, 30, 408–414.