Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Tổng quan về một số kết quả cho bộ đệm tái sắp xếp
Tóm tắt
Nhìn trước là một khái niệm cổ điển trong lý thuyết lập lịch trực tuyến. Một thuật toán trực tuyến không có nhìn trước phải xử lý các tác vụ ngay khi chúng đến và không có bất kỳ thông tin nào về các tác vụ trong tương lai. Với nhìn trước, giả định nghiêm ngặt này được nới lỏng. Có nhiều biến thể khác nhau về loại thông tin cụ thể được cung cấp cho thuật toán dưới dạng nhìn trước, nhưng có thể nói rằng giả định phổ biến nhất là tại mọi thời điểm, thuật toán đều có kiến thức về các thuộc tính của k tác vụ tiếp theo sẽ đến. Giả định này được xác nhận bởi thực tế là, trong thực hành, các tác vụ không phải lúc nào cũng đến một cách lần lượt và do đó, một số lượng tác vụ nhất định luôn chờ trong hàng đợi để được xử lý. Trong những năm gần đây, các bộ đệm tái sắp xếp đã được nghiên cứu như một sự tổng quát hợp lý của nhìn trước. Ý tưởng cơ bản là trong các cài đặt vấn đề mà thứ tự xử lý các tác vụ không quan trọng, chúng ta có thể cho phép một thuật toán lập lịch chọn xử lý bất kỳ tác vụ nào đang chờ trong hàng đợi. Điều này trái ngược với nhìn trước, nơi thuật toán có kiến thức về tất cả các tác vụ trong hàng đợi nhưng vẫn phải xử lý chúng theo thứ tự mà chúng đến. Chúng tôi thảo luận về một số kết quả cho các bộ đệm tái sắp xếp cho các bài toán lập lịch khác nhau.
Từ khóa
#nhìn trước #thuật toán trực tuyến #bộ đệm tái sắp xếp #lập lịch #tác vụ chờTài liệu tham khảo
Albers S (2004) New results on web caching with request reordering. In: Proceedings of the 16th ACM symposium on parallel algorithms and architectures (SPAA), pp 84–92
Alborzi H, Torng E, Uthaisombut P, Wagner S (2001) The k-client problem. J Algorithms 41(2):115–173
Asahiro Y, Kawahara K, Miyano E (2010) NP-hardness of the sorting buffer problem on the uniform metric. Unpublished manuscript
Aspnes J, Azar Y, Fiat A, Plotkin SA, Waarts O (1997) On-line routing of virtual circuits with applications to load balancing and machine scheduling. J ACM 44(3):486–504
Avigdor-Elgrabli N, Rabani Y (2010) An improved competitive algorithm for reordering buffer management. In: Proceedings of the 21st ACM-SIAM symposium on discrete algorithms (SODA), pp. 13–21
Azar Y, Gamzu I, Rabani Y (October 2008) Personal communication
Azar Y, Naor J, Rom R (1995) The competitiveness of on-line assignments. J Algorithms 18(2):221–237
Berman P, Charikar M, Karpinski M (2000) On-line load balancing for related machines. J Algorithms 35(1):108–121
Chan H-L, Megow N, van Stee R, Sitters R (2010) The sorting buffer problem is NP-hard. CoRR, arXiv:1009.4355
Chen B, van Vliet A, Woeginger GJ (1995) An optimal algorithm for preemptive on-line scheduling. Oper Res Lett 18(3):127–131
Dósa G, Epstein L (2008) Online scheduling with a buffer on related machines. Journal of Combinatorial Optimization. doi:10.1007/s10878-008-9200-y
Dósa G, Epstein L (2009) Preemptive online scheduling with reordering. In: Proceedings of the 17th European symposium on algorithms (ESA), pp 456–467
Englert M, Özmen D, Westermann M (2008) The power of reordering for online minimum makespan scheduling. In: Proceedings of the 49th IEEE symposium on foundations of computer science (FOCS), pp 603–612
Englert M, Räcke H, Westermann M (2007) Reordering buffers for general metric spaces. In: Proceedings of the 39th ACM symposium on theory of computing (STOC), pp 556–564
Englert M, Westermann M (2005) Reordering buffer management for non-uniform cost models. In: Proceedings of the 32nd international colloquium on automata, languages and programming (ICALP), pp 627–638
Epstein L, Levin A, van Stee R (2010) Max-min online allocations with a reordering buffer. In: Proceedings of the 37th international colloquium on automata, languages and programming (ICALP), pp 336–347
Fakcharoenphol J, Rao SB, Talwar K (2004) A tight bound on approximating arbitrary metrics by tree metrics. J Comput Syst Sci 69(3):485–497
Feder T, Motwani R, Panigrahy R, Seiden SS, van Stee R, Zhu A (2004) Combining request scheduling with web caching. Theor Comput Sci 324(2–3):201–218
Fleischer R, Wahl M (2000) On-line scheduling revisited. J Sched 3(6):343–353
Gamzu I, Segev D (2007) Improved online algorithms for the sorting buffer problem. In: Proceedings of the 24th symposium on theoretical aspects of computer science (STACS), pp 658–669
Kellerer H, Kotov V, Speranza MG, Tuza Z (1997) Semi on-line algorithms for the partition problem. Oper Res Lett 21(5):235–242
Khandekar R, Pandit V (2006) Online sorting buffers on line. In: Proceedings of the 23rd symposium on theoretical aspects of computer science (STACS), pp 584–595
Li S, Zhou Y, Sun G, Chen F (2007) Study on parallel machine scheduling problem with buffer. In: Proceedings of the 2nd international multi-symposiums on computer and computational sciences, pp 278–273
McNaughton R (1959) Scheduling with deadlines and loss functions. Manag Sci 6(1):1–12
Räcke H, Sohler C, Westermann M (2002) Online scheduling for sorting buffers. In: Proceedings of the 10th European symposium on algorithms (ESA), pp 820–832
Rudin JF III (2001) Improved bound for the online scheduling problem. PhD thesis, University of Texas at Dallas
Sleator D, Tarjan R (1985) Amortized efficiency of list update and paging rules. Commun ACM 28(2):202–208
Zhang G (1997) A simple semi on-line algorithm for P2//C max with a buffer. Inf Process Lett 61(3):145–148