Semi-online scheduling jobs with tightly-grouped processing times on three identical machines. (English) Zbl 1114.90035
Summary: This paper investigates the semi-online version of the scheduling problem \(P||C_{max}\) on a three-machine system. We assume that all jobs have their processing times between \(p\) and \(rp (p>0,\geqslant 1\)). We give a comprehensive competitive ratio of \(LS\) the algorithm which is a piecewise function on \(r\geqslant 1\). It shows that \(LS\) is an optimal semi-online algorithm for every \(r \in [1,1.5], [\sqrt 3,2]\) and \([6,+\infty)\). We further present an optimal algorithm for every \(r \in [2,2.5]\), and an almost optimal algorithm for every \(r \in (2.5,3]\) where the largest gap between its competitive ratio and the lower bound of the problem is at most 0.01417. We also present an improved algorithm with smaller competitive ratio than that of \(LS\) for every \(r \in (3,6)\).
References:
| [1] | Albers, S., Better bounds for on-line scheduling, SIAM J. Comput., 29, 459-473 (1999) · Zbl 0943.68183 |
| [2] | S. Albers, On randomized online scheduling, Proceedings of the 34th ACM Symposium on Theory of Computing, Montreal, 2002, pp. 134-143.; S. Albers, On randomized online scheduling, Proceedings of the 34th ACM Symposium on Theory of Computing, Montreal, 2002, pp. 134-143. · Zbl 1192.68091 |
| [3] | Azar, Y.; Epstein, L., On-line machine covering, J. Scheduling, 1, 67-77 (1998) · Zbl 0909.90169 |
| [4] | Azar, Y.; Regev, O., Online bin stretching, Theoret. Comput. Sci., 268, 17-41 (2001) · Zbl 0984.68195 |
| [5] | Bartal, Y.; Fiat, A.; Karloff, H.; Vohra, R., New algorithms for an ancient scheduling problem, J. Comput. System Sci., 51, 359-366 (1995) · Zbl 1295.90008 |
| [6] | Epstein, L., Bin stretching revisited, Acta Inform., 39, 97-117 (2003) · Zbl 1034.68039 |
| [7] | L. Epstein, L. Favrholdt, Optimal non-preemptive semi-online scheduling on two related machines, Proceedings of the 27th MFCS, 2002, pp. 245-256.; L. Epstein, L. Favrholdt, Optimal non-preemptive semi-online scheduling on two related machines, Proceedings of the 27th MFCS, 2002, pp. 245-256. · Zbl 1014.68017 |
| [8] | Faigle, U.; Kern, W.; Turán, G., On the performance of on-line algorithm for particular problems, Acta Cybernet., 9, 107-119 (1989) · Zbl 0689.68051 |
| [9] | Fleischer, R.; Wahl, M., On-line scheduling revisited, J. Scheduling, 3, 343-353 (2000) · Zbl 0966.90032 |
| [10] | Graham, R. L., Bounds for certain multiprocessing anomalies, The Bell System. Tech. J., 45, 1563-1581 (1966) · Zbl 0168.40703 |
| [11] | He, Y., The optimal on-line parallel machine scheduling, Comput. Math. Appl., 39, 117-121 (2000) · Zbl 0973.90033 |
| [12] | He, Y.; Tan, Z., Ordinal on-line scheduling for maximizing the minimum machine completion time, J. Combin. Optim., 6, 199-206 (2002) · Zbl 0991.90069 |
| [13] | He, Y.; Zhang, G., Semi on-line scheduling on two identical machines, Computing, 62, 179-187 (1999) · Zbl 0940.90032 |
| [14] | Karger, D. R.; Phillips, S. J.; Torng, E., A better algorithm for an ancient scheduling problem, J. Algorithms, 20, 400-430 (1996) · Zbl 0844.68010 |
| [15] | Kellerer, H.; Kotov, V.; Speranza, M. R.; Tuza, Z., Semi on-line algorithms for the partition problem, Oper. Res. Lett., 21, 235-242 (1997) · Zbl 0908.90165 |
| [16] | Liu, W. P.; Sidney, J. B.; van Vliet, A., Ordinal algorithms for parallel machine scheduling, Oper. Res. Lett., 18, 223-232 (1996) · Zbl 0855.90070 |
| [17] | J.F. Rudin III, Improved bounds for the online scheduling problem, Ph.D. Thesis, The University of Texas at Dallas, May 2001.; J.F. Rudin III, Improved bounds for the online scheduling problem, Ph.D. Thesis, The University of Texas at Dallas, May 2001. |
| [18] | Seiden, S.; Sgall, J.; Woeginger, G., Semi-online scheduling with decreasing job sizes, Oper. Res. Lett., 27, 215-221 (2000) · Zbl 1024.90044 |
| [19] | J. Sgall, On-line scheduling, On-line Algorithms: The State of Art, Lecture Notes in Computer Sciences 1442, Springer, Berlin, 1998, pp. 196-231.; J. Sgall, On-line scheduling, On-line Algorithms: The State of Art, Lecture Notes in Computer Sciences 1442, Springer, Berlin, 1998, pp. 196-231. · Zbl 1177.68009 |
| [20] | Tan, Z.; He, Y., Semi-on-line scheduling with ordinal data on two uniform machines, Oper. Res. Lett., 28, 221-231 (2001) · Zbl 0992.90031 |
| [21] | Tan, Z.; He, Y., Semi-on-line problems on two identical machines with combined partial information, Oper. Res. Lett., 30, 408-414 (2002) · Zbl 1013.90064 |
| [22] | Tan, Z.; He, Y., Ordinal algorithms for parallel machine scheduling with nonsimultaneous machine available times, Comput. Math. Appl., 43, 1521-1528 (2002) · Zbl 1002.68200 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
