Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Thuật toán tối ưu cho các vấn đề lập lịch trước bán trực tuyến trên hai máy đồng nhất
Tóm tắt
Bài báo này nghiên cứu hai vấn đề lập lịch bán trực tuyến có thể tạm dừng nhằm tối thiểu hóa thời gian hoàn thành trên hai máy đồng nhất. Trong vấn đề bán trực tuyến đầu tiên, chúng ta biết trước rằng tất cả các công việc đều có thời gian xử lý nằm giữa $p$ và $rp$ $(p > 0, r \geq 1)$. Trong vấn đề bán trực tuyến thứ hai, chúng ta biết kích thước của công việc lớn nhất trước. Chúng tôi thiết kế một thuật toán bán trực tuyến tối ưu mà là tối ưu cho mọi tổ hợp của tỷ lệ tốc độ máy $s \geq 1$ và tỷ lệ thời gian xử lý công việc $r \geq 1$ cho vấn đề đầu tiên, và một thuật toán bán trực tuyến tối ưu cho mọi tỷ lệ tốc độ máy $s \geq 1$ cho vấn đề thứ hai.
Từ khóa
#lập lịch bán trực tuyến #máy đồng nhất #thuật toán tối ưu #thời gian hoàn thành #tốc độ máyTài liệu tham khảo
Chen B, van Vliet A, Woeginger G (1995) An optimal algorithm for preemptive on-line scheduling.Operations Research Letters 18: 127-131
Epstein L (2001) Optimal preemptive on-line scheduling on uniform processors with non-decreasing speed ratios. Operations Research Letters 29: 93-98
Epstein L (2003) Bin stretching revisited. Acta Informatica 39: 97-117
Epstein L, Favrholdt L (2002) Optimal preemptive semi-online scheduling to minimize makespan on two related machines. Operations Research Letters 30: 269-275
Epstein L, Noga J, Seiden S, Sgall J, Woeginger G (2001) Randomized on-line scheduling on two uniform machines. Journal of Scheduling 4: 71-92
Epstein L, Sgall J (2000) A lower bound for on-line scheduling on uniformly related machines. Operations Research Letters 26: 17-22
Graham RL (1969) Bounds on multiprocessing finishing anomalies. SIAM Journal on Applied Mathematics 17: 416-429
Gonzalez T, Sahni S (1978) Preemptive scheduling of uniform processor systems. J. Assoc. Comput. Mach. 25: 92-101
He Y, Jiang YW (to appear) Optimal preemptive algorithm for semi-online scheduling with tightly-grouped processing times. Journal of Computer Science and Technology
He Y, Zhang GC (1999) Semi on-line scheduling on two identical machines. Computing 62, 179-187
Kellerer H, Kotov V, Speranza MG, Tuza Z (1997) Semi on-line algorithms for the partition problem. Operations Research Letters 21: 235-242
Sgall J (1997) A lower bound for randomized on-line multiprocessor scheduling. Information Processing Letters 63: 51-55
Seiden S, Sgall J, Woeginger G (2000) Semi-online scheduling with decreasing job sizes. Operations Research Letters 27: 215-221
Vestjens APA (1998) Scheduling uniform machines on-line requires nondecreasing speed ratios. Mathematical Programming 82: 225-234
Wen J, Du D (1998) Preemptive on-line scheduling for two uniform processors. Operations Research Letters 23: 113-116