Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Sử dụng phương pháp tổng hợp để xây dựng các chính sách định kỳ cho việc định tuyến công việc đến các máy chủ song song với thời gian phục vụ xác định
Tóm tắt
Vấn đề định tuyến các công việc đến theo cách xác định đến các máy chủ song song với thời gian phục vụ xác định, khi tỷ lệ đến của công việc bằng tổng công suất phục vụ, yêu cầu tìm một chính sách định kỳ. Vì chưa có phương pháp chính xác hiệu quả nào để giảm thiểu thời gian chờ trung bình lâu dài của các công việc đến, các phương pháp tiếp cận heuristics để xây dựng các chính sách định kỳ đã được đề xuất. Bài báo này trình bày một phương pháp tổng hợp kết hợp các máy chủ có tỷ lệ phục vụ giống nhau, xây dựng một chính sách cho hệ thống tổng hợp, và sau đó phân tách chính sách này thành một chính sách khả thi cho hệ thống ban đầu. Các thí nghiệm tính toán cho thấy việc sử dụng phương pháp tổng hợp không chỉ giảm thời gian chờ trung bình mà còn giảm nỗ lực tính toán.
Từ khóa
#định tuyến công việc #máy chủ song song #thời gian phục vụ xác định #chính sách định kỳ #tổng hợp hệ thốngTài liệu tham khảo
Altman, E., Gaujal, B., & Hordijk, A. (2000). Balanced sequences and optimal routing. Journal of the ACM, 47(4), 752–775.
Arian, Y., & Levy, Y. (1992). Algorithms for generalized round robin. Operations Research Letters, 12, 313–319.
Balinski, M. L., & Young, H. P. (1982). Fair representation. New Haven: Yale University Press.
Bar-Noy, A., Bhatia, R., Naor, J., & Schieber, B. (2002). Minimizing service an operation costs of periodic scheduling. Mathematics of Operations Research, 27, 518–544.
Combé, M. B., & Boxma, O. J. (1994). Optimization of static traffic allocation policies. Theoretical Computer Science, 125, 17–43.
Corominas, A., Kubiak, W., & Palli, N. M. (2007). Response time variability. Journal of Scheduling, 10, 97–110.
Hajek, B. (1985). Extremal splittings of point processes. Mathematics of Operations Research, 10, 543–556.
Herrmann, J. W. (2007). Generating cyclic fair sequences using aggregation and stride scheduling (Technical Report 2007-12). Institute for Systems Research, University of Maryland, College Park. http://hdl.handle.net/1903/7082. Accessed 1 November 2010.
Herrmann, J. W. (2008). Constructing perfect aggregations to eliminate response time variability in cyclic fair sequences (Technical Report 2008-29). Institute for Systems Research, University of Maryland, College Park. http://hdl.handle.net/1903/8643. Accessed 1 November 2010.
Herrmann, J. W. (2009a). Generating cyclic fair sequences for multiple servers. In MISTA 2009, Dublin, Ireland, August 10–12, 2009.
Herrmann, J. W. (2009b). Using aggregation to reduce response time variability in cyclic fair sequences. Journal of Scheduling. doi:10.1007/s10951-009-0127-7.
Hordijk, A., & van der Laan, D. (2005). On the average waiting time for regular routing to deterministic queues. Mathematics of Operations Research, 30(2), 521–544.
Hordijk, A., Koole, G. M., & Loeve, J. A. (1994). Analysis of a customer assignment model with no state information. Probability in the Engineering and Informational Sciences, 8, 419–429.
Kubiak, W. (2004). Fair sequences. In J. Y.-T. Leung (Ed.), Handbook of scheduling: algorithms, models and performance analysis (pp. 1–21). Boca Raton: Chapman & Hall/CRC Press.
Kubiak, W. (2009). Proportional optimization and fairness. New York: Springer.
Nowicki, E., & Smutnicki, C. (1989). Worst-case analysis of an approximation algorithm for flow shop scheduling. Operations Research Letters, 8, 171–177.
Rock, H., & Schmidt, G. (1983). Machine aggregation heuristics in shop scheduling. Methods of Operations Research, 45, 303–314.
Rogers, D. F., Plante, R. D., Wong, R. T., & Evans, J. R. (1991). Aggregation and disaggregation techniques and methodology in optimization. Operations Research, 39(4), 553–582.
Sano, S., Miyoshi, N., & Kataoka, R. (2004). m-balanced words: a generalization of balanced words. Theoretical Computer Science, 314(12), 97–120.
van der Laan, D. A. (2000). Routing jobs to servers with deterministic service times (Technical Report 2000-20). Leiden University.
van der Laan, D. A. (2003). The structure and performance of optimal routing sequences. Ph.D. thesis, Leiden University, Leiden, The Netherlands.
van der Laan, D. A. (2005). Routing jobs to servers with deterministic service times. Mathematics of Operations Research, 30(1), 195–224.
Waldspurger, C. A., & Weihl, W. E. (1995). Stride scheduling: deterministic proportional-share resource management. Technical Memorandum MIT/LCS/TM-528, MIT Laboratory for Computer Science, Cambridge, Massachusetts.
Wei, W. D., & Liu, C. L. (1983). On a periodic maintenance problem. Operations Research Letters, 2(2), 90–93.
Yum, T. P. (1981). The design and analysis of a semi-dynamic deterministic routing rule. IEEE Transactions on Communications, 29, 498–504.