×

Using a hybrid evolutionary algorithm to minimize variance in response time for multimedia object requests. (English) Zbl 1087.68633

Summary: This research addresses the scheduling problem of multimedia object requests, which is an important problem in information systems, in particular, for World Wide Web applications. The performance measure considered is the variance of response time which is crucial as end users expect fair treatment to their service requests. This problem is known to be NP-hard. The literature survey indicates that two heuristics have been proposed to solve the problem. In this paper, we present a new heuristic, a hybrid evolutionary heuristic, which is shown to perform much better than the two existing ones, e.g., the overall average errors of the existing ones are \(1.012\) and \(2.042\) while the error of the proposed hybrid evolutionary heuristic is \(0.154\).

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90B35 Deterministic scheduling theory in operations research
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Al-Anzi, F. and Allahverdi, A.: The relation between three-tired client-server internet database and two-machine flowshop, Int. J. Parallel Distrib. Syst. Netw. 4 (2001), 94–101.
[2] Allahverdi, A. and Al-Anzi, F.: Using two-machine flowshop with maximum lateness objective to model multimedia data objects scheduling problem for WWW applications, Comput. Oper. Res. 29 (2002), 971–994. · Zbl 0995.90026 · doi:10.1016/S0305-0548(00)00097-6
[3] Allahverdi, A., Gupta, J. N. D. and Aldowaisan, T.: A review of scheduling research involving setup considerations, OMEGA Int. J. Manag. Sci. 27 (1999), 219–239. · doi:10.1016/S0305-0483(98)00042-5
[4] Al-Turki, U., Fedjki, C. and Andijani, A.: Tabu search for a class of single-machine scheduling problems, Comput. Oper. Res. 28 (2001), 1223–1230. · Zbl 1008.90020 · doi:10.1016/S0305-0548(00)00036-8
[5] Campbell, H. G., Dudek, R. A. and Smith, M. L.: A heuristic algorithm for the n-job, m-machine sequencing problem, Manag. Sci. 16 (1970), B630–B637. · Zbl 0194.50504 · doi:10.1287/mnsc.16.10.B630
[6] Gowrishankar, G., Rajendran, C. and Srinivasan, G.: Flowshop scheduling algorithms for minimizing the completion time variance and the sum of squares of completion time deviations from a common due date, Eur. J. Oper. Res. 132 (2001), 643–665. · Zbl 1024.90038 · doi:10.1016/S0377-2217(00)00170-3
[7] Hall, N. G. and Posner, M. E.: Generating experimental data for computational testing with machine scheduling applications, Oper. Res. 49 (2001), 854–865. · Zbl 1163.90490 · doi:10.1287/opre.49.6.854.10014
[8] Kubiak, W.: Completion time variance minimization on a single machine is difficult, Oper. Res. Lett. 14 (1993), 49–59. · Zbl 0794.90024 · doi:10.1016/0167-6377(93)90019-D
[9] Kwok, Y. K., Karlapalem, K., Ahmad, I. and Pun, N. M.: Design and Evaluation of Data Allocation Algorithms for Distributed Multimedia Database Systems, IEEE J. Sel. Areas in Commun. 14 (1996), 1332–1348. · doi:10.1109/49.536483
[10] Manna, D. K. and Prasad V. R.: Bounds for the position of the smallest job in completion time variance minimization, Eur. J. Oper. Res. 114 (1999), 411–419. · Zbl 0935.90014 · doi:10.1016/S0377-2217(98)00002-2
[11] Manna, D. K. and Prasad V. R.: Pseudopolynomial algorithms for CTV minimization in single machine scheduling, Comput. Oper. Res. 24 (1997), 1119–1128. · Zbl 0893.90092 · doi:10.1016/S0305-0548(97)00032-4
[12] Marangos, C. A., Govande, V., Sirinvasan, G. and Zimmers Jr., W.: Algorithms to minimize completion time variance in a two-machine flowshop, Comput. Ind. Eng. 35 (1998), 101–104. · doi:10.1016/S0360-8352(98)00030-8
[13] Nawaz, M., Enscore, E. and Ham, I.: A heuristic algorithm for the m-machine, n-job flowshop sequencing problem, OMEGA Int. J. Manag. Sci. 11 (1983), 91–95. · doi:10.1016/0305-0483(83)90088-9
[14] Ng, C. T., Cai, X. and Cheng, T. C. E.: A tight lower bound for the completion time variance problem, Eur. J. Oper. Res. 92 (1996), 211–213. · Zbl 0912.90179 · doi:10.1016/0377-2217(95)00165-4
[15] Ozsu, M. T. and Valduriez, P.: Principles of Distributed Database Systems, Prentice-Hall, New Jersey, 1991.
[16] Pan, C. H. and Chen, J. S.: Scheduling alternative operations in two-machine flow-shops, J. Oper. Res. Soc. 48 (1997), 533–540. · Zbl 0882.90072
[17] Pinedo, M. and Chao, X.: Operations Scheduling with Applications in Manufacturing and Services, Irwing McGraw-Hill, Boston, 1999. · Zbl 1094.90561
[18] Sundararaghavan, P. S., Kunnathur, A. S. and Viswanathan, I.: Minimizing makespan in parallel flowshops, J. Oper. Res. Soc. 48 (1997), 834–842. · Zbl 0890.90110
[19] Wang, M. Y., Sethi, S. P. and Van De Velde, S. L.: Minimizing makespan in a class of reentrant shops, Oper. Res. 45 (1997), 702–712. · Zbl 0902.90102 · doi:10.1287/opre.45.5.702
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.