Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Lập Lịch Nhiệm Vụ Trên Các Máy Không Liên Quan: Quy Trình Cải Tiến Khu Vực Rộng Lớn
Tóm tắt
Hai thuật toán xấp xỉ được trình bày nhằm tối thiểu hóa thời gian hoàn thành của các nhiệm vụ độc lập được phân công trên các máy không liên quan. Thuật toán đầu tiên dựa trên việc khám phá một cách bán phần và theo hướng tìm kiếm heuristics của một cây tìm kiếm, không chỉ để xây dựng một giải pháp mà còn để cải thiện nó nhờ vào quy trình tối ưu hóa sau. Thuật toán thứ hai triển khai một quy trình cải tiến khu vực rộng lớn mới cho một thuật toán đã có sẵn. Các thực nghiệm tính toán cho thấy hiệu quả của chúng tương đương với các phương pháp heuristics tìm kiếm cục bộ tốt nhất.
Từ khóa
#lập lịch #máy không liên quan #thuật toán xấp xỉ #tối ưu hóa #heuristicsTài liệu tham khảo
Davis, E. and J.M. Jaffe. (1981). “Algorithms for Scheduling Tasks on Unrelated Parallel Processors.” Journal of the Association of Computing Machinery28, 721–736.
Duin, C. and S. Voss. (1999). “The Pilot Method: A Strategy for Heuristic Repetition with Application to the Steiner Problem in Graphs.” Networks34, 181–191.
Graham, R.L., E.L. Lawler, J.K. Lenstra, and A.H.G. Rinnooy Kan. (1979). “Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey.” Annals of Discrete Mathematics5,287–326.
Harvey, W.D. and M.L. Ginsberg. (1995). “Limited Discrepancy Search.” In Proceedings of the 14th International Conference on Artificial Intelligence, Montréal, Canada, pp. 607–613.
Ibarra, O.H. and C.G. Kim. (1977). “On Heuristic Algorithms for Scheduling Independant Tasks on Nonidentical Processors.” Journal of the Association of Computing Machinery24,280–289.
Lenstra, J.K. and D.B. Schmoys. (1995). “Computing Near-Optimal Schedules.” In P. Chrétienne, E.G. Coffman Jr., J.K. Lenstra and Z. Liu, (eds.), Scheduling Theory and its Applications. Chichesters, England: John Wiley and Sons.
Lenstra, J.K., D.B. Schmoys, and E. Tardos. (1990). “Approximation Algorithms for Scheduling Unrelated Parallel Machines.” Mathematical Programming46, 259–271.
P. Meseguer. (1997). “Interleaved Depth-First Search.” In Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, Nagoya, Japan, pp. 1382–1387.
Piersma, N. and W. van Dijk. (1996). “A Local Search Heuristic for Unrelated Machine Scheduling with Efficient Neighborhood Search.” Mathematical and Computational Modelling 24, 11–19.
Potts, C.N. (1985). “Analysis of a Linear Programming Heuristic for Scheduling Unrelated Parallel Machines.” Discrete Applied Mathematics10, 155–164.
Potts, C.N., C.A. Glass, and P. Shade. (1994). “Unrelated Parallel Machine Scheduling using Local Search.” Mathematical and Computational Modelling20, 41–52.
Sourd, F. and P. Chrétienne. (1999). “Fiber-to-Object Assignment Heuristics.” European Journal of Operations Research117, 1–14.
van deVelde, S.L. (1993). “Duality-Based Algorithms for Scheduling Unrelated Parallel Machines.” ORSA Journal on Computing5, 182–205.
Walsh, T. (1997). “Depth-Bounded Discrepancy Search.” In Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, Nagoya, Japan, pp. 1382–1387.