Minimizing the Total Stretch when Scheduling Flows of Divisible Requests without Interruption

Suk-Hun Yoon

Abstract


Many servers, such as web and database servers, receive a continual stream of requests. The servers should schedule these requests to provide the best services to users. In this paper, a hybrid genetic algorithm is proposed for scheduling divisible requests without interruption in which the objective is to minimize the total stretch. The stretch of a request is the ratio of the amount of time the request spent in the system to its response time. The hybrid genetic algorithm adopts the idea of seed selection and development in order to improve the exploitation and exploration power of genetic algorithms. Extensive computational experiments have been conducted to compare the performance of the hybrid genetic algorithm with that of genetic algorithms.


Full Text:

PDF

References


Bender, M. A., Muthukrishnan, S., and Rajaraman, R., “Approximation algorithms for average stretch scheduling,” Journal of Scheduling, Vol. 7, pp. 195-222, 2004.

Bhattacharyya, S., “Direct marketing performance modeling using genetic algorithms,” INFORMS Journal on Computing, Vol. 11, pp. 248-257, 1999.

Chan, W.-T., Lan, T.-W., Liu, K.-S., and Wong, P. W. H., “New resource augmentation analysis of the total stretch of SRPT and SJF in multiprocessor scheduling,” Theoretical Computer Science, Vol. 359, pp. 430-439, 2006.

Chang, J. H. and Chiu, H. N., “A comprehensive review of lot streaming,” International Journal of Production Research, Vol. 43, No. 8, pp. 1515-1536, 2005.

Cheng, M., Mukherjee, H. J., and Sarin, S. C., “A review of lot streaming,” International Journal of Production Research, Vol. 51, No. 23-24, pp. 7023-7046, 2013.

Chiu, H.-N., Chang, J.-H., and Lee, C.-H., “Lot streaming models with a limited number of capacitated transporters in multistage batch production system,” Computers and Operations Research, Vol. 31, pp. 2003-2020, 2004.

Dreo, J., Petrowski, A., Siarry, P., and Taillard, E., Metaheuristics for Hard Optimization : Methods and Case Studies. Springer, New York, 2005.

Edis, R. S. and Ornek, M. A., “A tabu search-based heuristic for single-product lot streaming problems in flow shops,” International Journal of Advanced Manufacturing Technology, Vol. 43, pp. 1202-1213, 2009.

Feldmannn, M. and Biskup, D., “Lot streaming in a multiple product permutation flow shop with intermingling,” International Journal of Production Research, Vol. 46, No. 1, pp. 197-216, 2008.

Goldberg, D. E., Genetic algorithms in search, optimization, and machine learning, Addison-Wesley, New York, 1989.

Liepins, G. E. and Hilliard, M. R., “Genetic algorithms : Foundation and applications,” Annals of Operations Research, Vol. 21, No. 1-4, pp. 31-58, 1989.

Muthukrishnan, S., Rajaraman, R., Shaheen, A., and Gehrke, J. F., “Online scheduling to minimize average stretch,” Siam Journal on Computing, Vol. 34, No. 2, pp. 433-452, 2005.

Pan, Q.-K., Suganthan, P. N., Liang, J. J., and Tasgetiren, M. F., “A local-best harmony search algorithm with dynamic sub-harmony memories for lot-streaming lfow shop scheduling problem,” Expert Systems with Applications, Vol. 38, pp. 3252-3259, 2011.

Pinedo, M. L., Scheduling : Theory, Algorithms, and Systems(4th Ed.), Springer, New York, 2012.

Song, B. D. and Oh, Y., “A study on network redesign for supply chain expansion,” The Journal of Society for e-Business Studies, Vol. 17, No. 4, pp. 141-153, 2012.

Wong, T. C., Chan, F. T. S., and Chan, L. Y., “A resource-constrained assembly job shop scheduling problem with lot streaming technique,” Computers and Industrial Engineering, Vol. 57, 983-995, 2009.


Refbacks

  • There are currently no refbacks.